comments on solving MIPs

Well, you know MIP solve times can be unpredictable, and sometimes it comes down to luck. Formulating good MIPs is something of a black art; and sometimes stupid things like the ordering of constraints can affect solve times. That said, there are a few tips that may help: 1) Introduce as many cuts and lazy constraints as you can, based on your knowledge of the problem. 2) When formulating MIP constraints, try to use formulations that give tight relaxations. For instance, avoid Big-M formulations when possible. If you have to use Big-M formulations, try to get tight value for the M. If you have no clue how to get a good value of M, formulate it as an indicator constraint, and CPLEX will try to find a good Big-M for you. 3) In some cases, you can formulate your problem as a Linear Generalized Disjunctive Program (LGDPs). LGDPs have a convex hull formulation, which are theoretically gives the tightest relaxations possible. The relaxations are usually either as good as, or better than those obtained from Big-M formulations. http://egon.cheme.cmu.edu/Papers/SawayaGrossmann.pdf The downside is that convex hull formulations require far more constraints than Big-M formulations, and sometimes this can make the problem more complex. The paper linked describes ways of introducing cutting planes to help speed up the convex hull formulations. Also, in some cases you can further tighten the problem by performing what is known as a "basic step". http://egon.cheme.cmu.edu/Papers/IMAGrossmannRuiz.pdf 4) There are other specific formulation tricks such as aggregation for problems with degenerate solutions, aggregation to break symmetry and so forth. All these require specific knowledge of the model. Right off the bat, you can usually get a small to significant speed-up if you use CPLEX >= 11's tuning feature, which can be invoked as follows. CPLEX will probe your problem and spit out some suggested cplex_options in the cplex.tune file. option cplex_options 'tunefile=cplex.tune tunedisplay=2 tunetime=1500'; This is also a good read: http://www-01.ibm.com/support/docview.wss?uid=swg21400023