Skip to main content

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

Ongoing

Comments

2 comments

  • Simon Bowly
    Gurobi Staff Gurobi Staff

    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
    Gurobi-versary
    First Comment
    First Question

    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

Please sign in to leave a comment.