Lagrangian Relaxation
AnsweredHello,
I am doing Lagrangian Relaxation with Gurobi for a minimization problem. The relaxed constraint has two integer variables in both righthand side and lefthand side, meaning that both Xijskm and Y'ijsm are integer variables and Vm is a parameter to the model. This constraint explains the capacity limitation of different vehicles.
When I add the relaxed constraint as a penalty to the objective function, it gives a very huge value to the variable Y'ijsm, which has a Lagrangian multiplier with negative sign in the objective function, so the model is unbounded in iteration 2.
In order to better explain, this term is added to the objective function due to relaxing the abovementioned constraint:
When I ran the model, the process of running the algorithm is stopped at the second iteration with this error “The model is unbounded or infeasible”. I checked it by adding a couple of lines of commands to the code. It is unbounded, not infeasible.
It seems that because of negative sign of this term in the objective function, it assigns a very huge value to Y'ijsm, so the objective function will be a big negative value.
Is there a way to handle this issue? I do appreciate you.
Asefeh

Hi Asefeh,
I will omit some indices to simplicity. Due to the constraint
\[\sum_k X^k \leq Y\]
the term \(\sum_k X^k  Y\) is always nonpositive \(\leq 0\). To my understanding the penalty term should read
\[\sum \lambda \left ( Y  \sum_k X^k \right) \]
Best regards,
Jaromił0 
Hi Joramil,
Thanks for replying to my question. The term
Y is nonpositive ≤0, but just in feasible solutions. Since I relaxed this Constraint, the infeasible solution also could be generated, in which ∑k Xk−Y is positive ≥0. This violation should be added to the objective function as a penalty. I hope I was clear.Thanks again,
Asefeh
0 
Hi Asefeh,
Thank you for clarifying. The Lagrangian relaxation does not work if you allow for negative terms in the term you want to penalize. This is because the solver will always exploit this fact making the model unbounded.
For your particular relaxed constraint, you have to bound your variables such that only the infeasible ones are allowed, i.e., only variables for which \(\sum X  Y \geq 0\).
Best regards,
Jaromił0 
Hi Jaromił,
I will try it. Thanks again for your recommendation and solution to this issue.
Regards,
Asefeh
0
Please sign in to leave a comment.
Comments
4 comments