On my experience many MIQP models can and should be reformulated into straight linear MIP models. The reason is threefold: MIQP solvers are not as reliable as MIP solvers (they can experience numerical difficulties much more often), they can not solve many QPs that are not convex and the performance of a corresponding MIP model can be much better.
An example of this was discussed in https://groups.google.com/forum/#!topic/gurobi/t-N23d24uuw.
With some larger data sets (randomly generated), I saw the following:
Scip (MIQP formulation) was stopped when exceeding 1000 seconds.
This is a non-trivial reformulation, so the presolvers are not (yet) able to replicate this.
PS. In general I don’t think it is a good idea to skimp on variables and equations as is suggested in the discussion. Often we see poorly formulated models as a result of trying to save on variables and constraints, resulting in models that are much denser and actually more difficult to solve. From the above numbers we can see my liberal use of variables and equations in the MIP formulation does not really harm and actually this formulation is light years ahead in terms of performance and reliability compared to the original MIQP formulation.
No comments:
Post a Comment