Lagrangian Relaxation

回答済み

Asefeh Hassani Goodarzi

2022年05月11日 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

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2025年11月16日 23:37

  This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.
• 

  Jaromił Najman

  • Gurobi Staff

  2022年05月12日 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

  2022年05月12日 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

  2022年05月12日 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

  2022年05月12日 15:20

  • 
  • 
  • 

  Hi Jaromił,

  I will try it. Thanks again for your recommendation and solution to this issue. 

  Regards,

  Asefeh

  0

投稿コメントは受け付けていません。