Tuesday, February 15, 2011

MIQP/MIP

Many MIQP models can be reformulated into MIPs. In my experience that is always worthwhile to try out, as MIP solvers are often much faster than MIQP algorithms. This is the case even though the MIP formulation adds many variables and constraints. Here is an example I encountered today:

  • Original MIQP model: after 10000 seconds it still had a 1% gap
  • My reformulation as a MIP model: proven optimal after 2000 seconds.

If the MIP model is still small enough it fits in available memory, then (almost) always the MIP formulation outperforms the MIQP model.