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.

- Serverfault Help
- Superuser Help
- Ubuntu Help
- Webapps Help
- Webmasters Help
- Programmers Help
- Dba Help
- Drupal Help
- Wordpress Help
- Magento Help
- Joomla Help
- Android Help
- Apple Help
- Game Help
- Gaming Help
- Blender Help
- Ux Help
- Cooking Help
- Photo Help
- Stats Help
- Math Help
- Diy Help
- Gis Help
- Tex Help
- Meta Help
- Electronics Help
- Stackoverflow Help
- Bitcoin Help
- Ethereum Help