= Solution
The constraints give the valid <upper bound>
$$
x_1+x_2+x_3+x_4=(x_1+x_2+x_4)+x_3\leq5+x_3\leq8-x_1\leq8.
$$
For example $(x_1,x_2,x_3,x_4)=(0,1,3,4)$ satisfies every constraint: the first left side is four, the next three are three, five and two, and $x_4\geq1$. Its objective is eight. Hence the <upper bound> is attained by an <integer> point, proving
$$
\boxed{z_{IP}=8.}
$$
All optimal solutions can also be identified. Equality forces $x_1=0$, $x_3=3$ and $x_2+x_4=5$. The remaining constraints reduce to $x_2\geq1$ and $x_4\geq1$. Thus exactly four <integer> optima occur:
$$
\boxed{(x_1,x_2,x_3,x_4)=(0,k,3,5-k),\qquad k=1,2,3,4.}
$$
This is an optimality certificate by a valid relaxation bound and a feasible <integer> solution; no assumption of total unimodularity is needed. The source's $\mathbb Z_+$ denotes nonnegative integers, as is also necessary for its assignment equations in the next question.
Back to article page
