Symmetry breaking

Answered

Gabrijela Obradovic

July 10, 2023 11:59

• 
• 

I have a problem with implementing lexicographic symmetry elimination constraints for the job scheduling problem. Default symmetry breaking Gurobi does is orbital and does not give me indexing I need (that is, 1,2,3,4,....). That is why I defined constraints:

where I essentially specify that n can occur only after n-1 has occurred (it can happen that both occur at the same time step). The problem is, such constraints slow down my MILP significantly. If anyone has some advice, it would help!

0

• 

  David Torres Sanchez

  • Gurobi Staff

  July 14, 2023 12:01 Edited

  Hi Gabrijela,

  You can try using row generation, i.e. set LazyConstraints to 1 and add these constraints in a callback using some logic (e.g. only add a few these when a solution violates them). 
  This could take you some time to implement and may not be the best way.

  Examples:

  • callback: callback.py
  • row generation for the TSP: tsp.py (uses the model.cbLazy function to add cuts).

  Cheers, 
  David

  0

Please sign in to leave a comment.