# Prove the optimal value of this minimum is not smaller than the optimal value of this maximum

by user558377   Last Updated November 09, 2018 01:20 AM - source

$$min \langle c, x \rangle$$ s.t. $$Ax \geq b, x \geq 0$$, where $$x$$ is an integer and $$A$$ has integer entries. Show the optimal value of this is no less than the optimal value of this maximum: $$max \langle b^* , \lambda \rangle$$ s.t. $$A^T\lambda \leq c, \lambda \geq 0$$, where $$b^*$$ denotes the roundup of vector $$b$$: the smallest integer vector greater than or equal to $$b$$.

I tried doing this using the dual problem, i.e $$L = \langle c, x \rangle + \langle b-Ax, \lambda \rangle = \langle c -A^T\lambda, x \rangle + \langle b , \lambda \rangle$$ so the minimum of this w.r.t $$x$$ is $$-\infty$$ if $$c > A^T\lambda$$ and $$\langle b , \lambda \rangle$$ if $$c \leq A^T\lambda$$. So the new problem because to maximize w.r.t $$\lambda$$ so its $$max \langle b , \lambda \rangle$$ s.t. $$c \leq A^T\lambda, \lambda \geq 0$$, which is obviously less equal the max we were looking to show greater or equal to.

What am I doing wrong? I tried using the dual problem to solve the original max, but also got nowhere.

Tags :