Answers to: QP to MIP Formulationhttp://www.or-exchange.com/questions/10579/qp-to-mip-formulation<p>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</p>
<p>min sum (y_i)^2</p>
<p>s.t. A*x <= y</p>
<p>x_1 + x_2 = 1</p>
<p>x_2 + x_3 = 1</p>
<p>....</p>
<p>y >= 0</p>
<p>x binary variables
y continous variables </p>
<p>A can contain negative entries</p>
<p>It is an assignment problem.
A*x is a vector which displays the energy consumption for different timepoints.</p>
<p>[Each entry in the vector is the energy consumption for each timepoint]</p>
<p>The aim is to space the energy consumption equaly as possible over all timepoints.</p>enThu, 30 Oct 2014 01:58:20 -0400Answer by Erling_MOSEKhttp://www.or-exchange.com/questions/10579/qp-to-mip-formulation/10583<p>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 </p>
<ul>
<li>On Polyhedral Approximations of the Second-Order Cone</li>
<li>Mathematics of Operations Research archive</li>
<li>Volume 26 Issue 2, May 2001 </li>
<li>Pages 193-205 </li>
</ul>Erling_MOSEKThu, 30 Oct 2014 01:58:20 -0400http://www.or-exchange.com/questions/10579/qp-to-mip-formulation/10583Answer by Paul Rubinhttp://www.or-exchange.com/questions/10579/qp-to-mip-formulation/10582<p>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.</p>
<p>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.</p>Paul RubinWed, 29 Oct 2014 15:50:13 -0400http://www.or-exchange.com/questions/10579/qp-to-mip-formulation/10582