0
$\begingroup$

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?

Could somebody please help me figure out how to proceed? And please be as direct and obvious as possible. I thank you ahead of time for your patience.

$\endgroup$

1 Answer 1

1
$\begingroup$

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?).

$\endgroup$
3
  • $\begingroup$ is it because the only points that are feasible are integer points anyway? $\endgroup$
    – user100463
    Commented Jan 6, 2018 at 3:23
  • $\begingroup$ Yes, and the fact that the entries of A are integer. $\endgroup$
    – ProAmateur
    Commented Jan 6, 2018 at 3:23
  • $\begingroup$ dang that is clever. $\endgroup$
    – user100463
    Commented Jan 6, 2018 at 3:24

You must log in to answer this question.