Tuesday, January 27, 2009

Adding redundant constraint to MIP

Whenever a MIP model is very slow I try to invent "redundant" constraints that can be added to the model. Here is an example with Cplex. We report number of nodes needed to prove optimality on some small examples of a (proprietary) scheduling model:
casewithwithout
8-3-22334
8-6-207290
9-3-3081
9-4-30180
9-5-37487738
As can be seen the version with the redundant equation added has much better performance. Furthermore it is noted that the duality gap was much smaller.

5 comments:

  1. This is amazing, could you please give us more information on that please!!!

    Thanks

    ReplyDelete
  2. Sorry, it is difficult to explain without divulging more than I am comfortable with (this is a model I developed for a commercial client).

    ReplyDelete
  3. Erwin, how do you define "redundant"? Is is something like a+b= c and 2a+2b=2c or redundant like x+y<10 and x+y<5?

    ReplyDelete
  4. Let me try: A redundant constraint would not significantly change the nature of the problem. They are also sometimes called user-cuts. A good example is symmetry-breaking cuts, here is an example: http://yetanothermathprogrammingconsultant.blogspot.com/2009/03/msf-csp-tiling-squares-2.html

    ReplyDelete
  5. The symmetry breaking techniques are very powerful to cut equivalent solutions while it is very problem dependent.Usually fixing some 0-1 variables or adding some explicit constraints may work.

    Erwin, could you please highlight any other similiar situations about the redundent constraints /

    Thanks a lot.

    ReplyDelete