Wednesday, October 21, 2009

MIQP

I am following your blog with great interest and I would be very happy to have your insight on an optimisation problem I am currently struggling with.
I am wondering if there is an easy way to solve a model with linear constraints on a vector of both continuous and binary variables and a quadratic objective function depending only on the subset of continous variables (e.g. least squares distance to an objective vector) without having to resort to a non-linear solver.
I reckon this is some kind of 'MIP + Constrained' Linear Least Squares. I would be disappointed if there was no better way to solve this than treating it as 'any' non-linear problem, but as I found nothing relevant at the moment, I'd be glad to hear what you think about it.

Some solvers (such as Cplex) offer a MIQP (Mixed Integer Quadratic Programming) functionality. That may be something to try out. Otherwise, if the objective tries to penalize some large deviations, it may be possible to achieve a similar result by minimizing the maximum deviation. This can be formulated in a linear fashion.

Yet another linear approximation can be formed by minimizing the sum of absolute deviations. For an example see http://yetanothermathprogrammingconsultant.blogspot.com/2009/07/ms-solver-foundation-excel-interface_07.html. These linear formulations essentially choose a different norm ||x||.