# QP to MIP Formulation

 0 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 29 Oct '14, 11:18 zBirdy 171●2●12 accept rate: 20%

 4 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 29 Oct '14, 15:50 Paul Rubin ♦♦ 14.6k●4●13 accept rate: 19%
 1 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 30 Oct '14, 01:58 Erling_MOSEK 616●1●4 accept rate: 3%
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: