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's gravatar image

accept rate: 20%

edited 29 Oct '14, 14:03

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%20Rubin's gravatar image

Paul Rubin ♦♦
accept rate: 19%

edited 29 Oct '14, 15:50

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's gravatar image

accept rate: 3%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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



Asked: 29 Oct '14, 11:18

Seen: 1,228 times

Last updated: 30 Oct '14, 01:58

OR-Exchange! Your site for questions, answers, and announcements about operations research.