Hello is it possible to formulate this QP as a MIP and if not what is the best way to approximate it as a MIP min sum (y_i)^2 s.t. A*x <= y x_1 + x_2 = 1 x_2 + x_3 = 1 .... y >= 0 x binary variables y continous variables A can contain negative entries It is an assignment problem. A*x is a vector which displays the energy consumption for different timepoints. [Each entry in the vector is the energy consumption for each timepoint] The aim is to space the energy consumption equaly as possible over all timepoints.
asked
zBirdy |

It already is an MIP (but not an MILP). More precisely, it's an MIQP. Many contemporary MIP solvers can handle a quadratic objective function, so long as it is convex (minimizing)/concave (maximizing), which yours is. If you absolutely must linearize, you can approximate the objective function by doing piecewise linear approximations to each of the terms. You can also get an approximate solution by swapping the \(L_1\) norm (a.k.a. "taxicab norm") or the \(L_{\infty}\) norm (a.k.a. "sup norm") for the \(L_2\) (Euclidean) norm.
answered
Paul Rubin ♦♦ |

If an linear approximation of the quadratic term is good enough, then Ben-Tal and Nemirovski has method with nice theoretical bounds on the approximation quality. See - On Polyhedral Approximations of the Second-Order Cone
- Mathematics of Operations Research archive
- Volume 26 Issue 2, May 2001
- Pages 193-205
answered
Erling_MOSEK |