| case | with | without |
|---|---|---|
| 8-3-2 | 23 | 34 |
| 8-6-2 | 0 | 7290 |
| 9-3-3 | 0 | 81 |
| 9-4-3 | 0 | 180 |
| 9-5-3 | 74 | 87738 |
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:
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.
Subscribe to:
Post Comments (Atom)
This is amazing, could you please give us more information on that please!!!
ReplyDeleteThanks
Sorry, it is difficult to explain without divulging more than I am comfortable with (this is a model I developed for a commercial client).
ReplyDeleteErwin, 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?
ReplyDeleteLet 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
ReplyDeleteThe 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.
ReplyDeleteErwin, could you please highlight any other similiar situations about the redundent constraints /
Thanks a lot.