Past exam of the integer programming course of the University of Oxford / 2010 / 2 / b

The constraints give the valid upper boundFor 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\ge 1$. Its objective is eight. Hence the upper bound is attained by an integer point, provingAll 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\ge 1$ and $x_4\ge 1$. Thus exactly four integer optima occur: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.