How to add a constraint only to a single step of a hierarchical optimization?

Answered

Vincent

• April 09, 2020 20:40

I have a model with three objectives and defined three environments (env1, env2, and env3) for each pass. I am solving this multiobjective problem with a hierarchical approach and wondering if there is a way to add a constraint only to the third step (env3) when Gurobi wants to optimize the 3rd objective.

 

Thanks!

0

• 

  Eli Towle

  Gurobi Staff

  • April 09, 2020 23:28

  Hi,

  This doesn't fit well into Gurobi's multiobjective optimization framework, because the third solve considers a (potentially) different feasible region. In this case, it might be better to implement the hierarchical optimization on your own:

  1. Solve the model with respect to the first objective
  2. Add a constraint so the first objective does not degrade (at least, not much) in subsequent solves
  3. Solve the model with respect to the second objective
  4. Add another constraint to disallow degradation of the second objective
  5. Add the special constraint for the third solve
  6. Solve the model with respect to the third objective

  Could you try this out? Note that depending on the constraint you want to add, the third model might be infeasible. Thanks!

  Eli

  0
• 

  Vincent

  • April 09, 2020 23:53

  

  

  

  Thanks, Eli Towle! I've already tried that but, other than the degrade in the first and second objectives, there is another downside. When I add a constraint to the second or third objective to disallow degradation of previous objectives, Gurobi spends a long time finding the first feasible solution for the new (third) problem, and it makes the solution time much longer. But that doesn't happen when I use Gurobi's multiobjective framework.
  
  To further illustrate my situation, I only have a symmetry breaking constraint that extremely helps the third objective to be solved faster, but it hurts the first two problems in terms of solution time. There is this tradeoff that adding this symmetry constraint makes the third step faster, whereas removing it makes the first two steps faster. That's why I want to apply it only on the third pass. Is there any other way to deal with this tradeoff?

  0
• 

  Eli Towle

  Gurobi Staff

  • April 10, 2020 01:32

  Hi Vincent,

  If you add a constraint to prevent degradation of the previous objectives, the solution from the previous model should remain feasible. In this case, Gurobi should warm-start the subsequent MIP solve using that solution. Are you sure you aren't cutting off the previous solution with your objective constraints, even by a very small amount? Consider adding a small \( \epsilon > 0 \) to the constraint to account for this. E.g., instead of adding the constraint \( c^\top x \leq z^* \) to the next model, add the constraint \( c^\top x \leq z^* + \epsilon \) (perhaps \( \epsilon = 10^{-6} \) ).

  Also, is it possible that you are cutting off the solution from the second solve with your symmetry-breaking constraint? I would make an effort to make sure that the symmetry-breaking constraint does not cut off the feasible solution from the second solve. Symmetry-breaking constraints can often be rewritten to break the same symmetry, while changing which solutions remain feasible.

  Lastly, are you sure the symmetry-breaking constraint is helpful for the third solve? Perhaps it works well on the base model, but this may not be the case after additional objective constraints and a warm start are added to the problem.

  Thanks,

  Eli

   

  1

Please sign in to leave a comment.