Setup

An integer linear$-$programming problem is a linear$-$programming problem with the additional constraint that the variables x

must take on integer values. Turns out there is no known polynomial$-$time algorithm for this problem.

Part A

Show that weak duality $($Lemma $29\mathrm{.}1$ from the reading$)$ holds for an integer linear program.

Part B

Show that duality $($Theorem $29\mathrm{.}4$ from the reading$)$ does not always hold for an integer linear program.

Part C

Given a primal linear program in standard form, let P

be the optimal objective value for the primal linear program, D

be the optimal objective value for its dual, IP

be the optimal objective value for the integer version of the primal $($that is$,$ the primal with the added constraint that the variables take on integer values$),$ and ID

be the optimal objective value for the integer version of the dual. Assuming that both the primal integer program and the dual integer program are feasible and bounded, show that IP$<=$P$=$D$<=$ID

$.$