# Linear Programming Problem/Integer Programming Problem Bounds

Consider the Integer Programming Problem (IPP) $$\text{minimize}\, \langle c,x\rangle \\ \text{subject to}\, Ax \geq b,\\ x \geq 0, \quad x-\text{integer}$$ in which the matrix $A$ has integer entries. I need to prove that its optimal value is not smaller than the optimal value of the Linear Programming Problem (LPP) $$\text{maximize}\, \langle\lceil b \rceil , \lambda\rangle \\ \text{subject to}\, A^{T}\lambda \leq c\\ \lambda \geq 0$$ where $\lceil b \rceil$ denotes the smallest integer vector greater than or equal to $b$, and $A^T$ denotes the transpose of the matrix $A$.

In attempting to prove this myself, I have approached it from myriad ways - one of which was to find the dual of the IPP, which is the following: $$\text{maximize} \langle b, \lambda \rangle \\ \text{subject to}\,A^{T}\leq c, \\ \lambda \geq 0$$ but has only $b$ and not $\lceil b \rceil$. So clearly, I cannot say that a duality relation exists between the IPP and the LPP.

From here, I had thought of maybe trying to relax the integer condition of the IPP so that it becomes a standard LPP and then trying to find the dual, but 1) I don't know how to do that, and 2) I'm not sure what good it would do me. So, I am kind of stuck.

I also thought to myself, if I can show that the LPP here is the dual to a primal problem almost identical to the IPP given here, except with $A$ not necessarily having integral entries, and with $\lceil b \rceil$ instead of just $b$, I would by weak duality have that $d^{*} \leq p^{*}$ (where $d^{*}$ is the optimal solution to the LPP, and p^{*} is the solution to the problem whose dual it is). Then, could I somehow relate $p^{*}$ to the optimal solution of the given IPP?

You can use weak-duality, as you've done, to prove the desired result after noting that the feasible set of (IPP) remains the same when the constraint $Ax \geq b$ is replaced by $Ax \geq \lceil b \rceil$ (why?).