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.