I have an assignment where I need to solve a small problem using Lagrangian relaxation. $$ \min 3x_1-x_2$$ $$x_1-x_2 \ge -1$$ $$-x_1+2x_2\le 5 $$ $$3x_1+2x_2 \ge 3$$ $$6x_1+x_2 \le 15$$ $$x_1,x_2 \ge 0$$ $$x_1,x_2 \in \mathbb{Z}$$

I have formulated the Lagrangian relaxation as: $$3x_1-x_2+v_1(-1-x_1+x_2)+v_2(5+x_1-2x_2)+v_3(3-3x_1-x_2)+v_4(15-6x_1-x_2)\\$$

Initially I have set all V to zero and want to achieve a lower bound. BUT! The problem is unbounded? An initially solution for Lower bound would be infinity for variable $x_2$ since that is the best value that minimizes the objective function if $v = 0$?

To set $x_2$ to infinity since like a bad idea and I wonder how I shall continue?



The feasible set in light blue, looks bounded!

Now in red the integer lattice, in black the minimum $3x_1-x_2$ which is equal to $1$

enter image description here

  • $\begingroup$ Hi! Thank you for your answer. I thought that the constraints no longer was valid after the relaxation have been done, but I need to check the constraints in the original problem also when solving the langrage-sub problem? $\endgroup$ – Ulrich_Peters Oct 24 '18 at 10:06
  • $\begingroup$ @Ulrich_Peters Please. See the new plot. $\endgroup$ – Cesareo Oct 24 '18 at 10:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.