Lagrangian Relaxation

Answered

Asefeh Hassani Goodarzi

• May 11, 2022 22:27

Hello,

I am doing Lagrangian Relaxation with Gurobi for a minimization problem. The relaxed constraint has two integer variables in both right-hand side and left-hand 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 above-mentioned 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

0

• 

  Jaromił Najman

  Gurobi Staff

  • May 12, 2022 09:36

  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
• 

  Asefeh Hassani Goodarzi

  • May 12, 2022 13:17

  

  

  

  Hi Joramil,

  Thanks for replying to my question. The term ∑k Xk−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
• 

  Jaromił Najman

  Gurobi Staff

  • May 12, 2022 14:32

  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
• 

  Asefeh Hassani Goodarzi

  • May 12, 2022 15:20

  

  

  

  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.