What is the difference between minrelax = False and minrelax = True in feasRelax?

進行中

Keyur Shah

2022年04月13日 02:50

• 
• 
• 

I read the documentation for minrelax parameter in model.feasRelax

The minrelax argument is a boolean that controls the type of feasibility relaxation that is created. If minrelax=False, optimizing the returned model gives a solution that minimizes the cost of the violation. If minrelax=True, optimizing the returned model finds a solution that minimizes the original objective, but only from among those solutions that minimize the cost of the violation. Note that feasRelax must solve an optimization problem to find the minimum possible relaxation when minrelax=True, which can be quite expensive.

How are the two options different from each other? I understand that if minrelax = False, then the objective function being optimized is represents the cost of violation and if minrelax = True, then the objective function being optimized is the original one (only from amongst those solutions that minimize the cost of violation)

However, what I don't understand in the case of minrelax = False is how Gurobi solves for the original decision variables if they are not even in the objective function?

Also, let's say that my objective function is respresented by a linear expression 'obj'. Would the following two scenarios bellow yield the exact same optimal objective function value:

# Scenario 1: minrelax = False
obj.getValue()

# Scenario 2: minrelax = True
model.getObjective().getValue() 

1

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2025年11月16日 23:39

  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.
• 

  Simon Bowly

  • Gurobi Staff

  2022年04月13日 06:28

  Hi Keyur,

  In the first case (minrelax=False), Gurobi modifies the model so that it aims to minimize violations of the constraints while entirely ignoring your original objective. So, if you do the following:

   

  obj = model.getObjective()  # store the original objective
  model.feasRelax(...)        # with minrelax=False
  model.optimize()

  
  then Gurobi will terminate with either:
   

  • A solution with objective value zero (for the new objective). In this case, the solution arrived at is feasible to the original model (no violations). If you then run obj.getValue(), you will get a computation of the original objective for the current solution. This value is likely to be quite poor, since while Gurobi has found a solution that is feasible to the constraints in the original model, the objective has been ignored, hence there is no emphasis on solution quality.
  • A solution with an objective value greater than zero (for the new objective). In this case, the solution found is infeasible to the original model. So, computing obj.getValue() may actually give an objective value that is better than the optimal solution value of the original model, since the solution violates some of the original model constraints.

   
  In the case of minrelax=True, the model is solved in two stages: (1) minimise violations, then (2) optimize your original objective without incurring further violations.
   

  obj = model.getObjective()  # store the original objective
  model.feasRelax(...)        # with minrelax=False
                              # In this case, the solver is immediately started to find a
                              # solution which minimises constraint violations.
  ...
  model.optimize()            # The model now has the original objective restored.

   
  So the result in the two scenarios you've described is actually very different. Scenario 1 never considers your original objective (the solver is concerned only with finding a feasible solution) so the value of your original objective is likely to be much worse in that case.

  0
• 

  Keyur Shah

  2022年04月13日 15:32

  • 
  • 
  • 

  Hi Simon,

  Thank you for the quick answer. I had a follow-up question:
  
  

  • A solution with an objective value greater than zero (for the new objective). In this case, the solution found is infeasible to the original model. So, computing obj.getValue() may actually give an objective value that is better than the optimal solution value of the original model, since the solution violates some of the original model constraints.

  Question 1 - If the solution of the new objective is greater than zero, then can I safely to assume that had I run the optimizer on the original objective (without feasRelax), it would have yielded infeasibility?

  Question 2 - After running feasRelax with minrelax = False, if I run obj.getValue(), the objective value may be better than the optimal solution of the original objective but it may still not be optimal given the constraint violations, right? (since you mentioned that with minrelax = False, there is no emphasis on solution quality)

  In the case of minrelax=True, the model is solved in two stages: (1) minimise violations, then (2) optimize your original objective without incurring further violations.

  Question 3 - I am using multiple objective functions in my model which does not allow me to run feasRelax with minrelax = True. However, if I want to achieve the same two stages above with minrelax = False, what should I do?

  0

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