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

zBirdy
171211
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.

link

answered 29 Oct '14, 15:50

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
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
link

answered 30 Oct '14, 01:58

Erling_MOSEK's gravatar image

Erling_MOSEK
61614
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

By RSS:

Answers

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

Tags:

×231
×127
×65

Asked: 29 Oct '14, 11:18

Seen: 1,060 times

Last updated: 30 Oct '14, 01:58

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