Dtjytyk

What is difference between behavior and behaviour

Applicability of Single Responsibility Principle

Personal Teleportation as a Weapon

Was the picture area of a CRT a parallelogram (instead of a true rectangle)?

Is exact Kanji stroke length important?

Your magic is very sketchy

Is it correct to write "is not focus on"?

Is this Spell Mimic feat balanced?

How can I get through very long and very dry, but also very useful technical documents when learning a new tool?

Greatest common substring

I'm in charge of equipment buying but no one's ever happy with what I choose. How to fix this?

Can somebody explain Brexit in a few child-proof sentences?

Is there any easy technique written in Bhagavad GITA to control lust?

Teaching indefinite integrals that require special-casing

Confused about a passage in Harry Potter y la piedra filosofal

Time travel short story where a man arrives in the late 19th century in a time machine and then sends the machine back into the past

What is the oldest known work of fiction?

Is expanding the research of a group into machine learning as a PhD student risky?

Mapping a list into a phase plot

voltage of sounds of mp3files

Can a monster with multiattack use this ability if they are missing a limb?

Should my PhD thesis be submitted under my legal name?

Will it be accepted, if there is no ''Main Character" stereotype?

Products and sum of cubes in Fibonacci

How to linearize a quadratic objective function with linear constraints?

Is there an efficient way to solve this optimization problem?Quadratic Form with $ {L}_{1} $ Regularization and Box Constraints - Coordinate Descent IterationOptimization of N variables with K linear equality constraintsLinear objective function with quadratic constraintsSolving many quadratic programs with the same objective matrixOptimisation with Equality ConstraintsHow do I formulate a sum constraint in quadratic programming?Linear program with several non-convex constraintsLinearize Equality Constraint with Max FunctionEfficient numerical optimization of an “almost separable” function

1

1

$begingroup$

I have an optimization problem that I'm working on. The objective is defined as follows:

$Maximize: c_icdot w_i cdot x_i - d_i cdot y_i cdot delta_i $

subject to some linear constraints where $c_i, w_i$ and $d_i$ are scalars and

$x_i, delta_i in {0,1}$ and $y_i in Z^+$

I wish to linearize this objective function so that I can solve it with an existing ILP solver. I found this link that suggests the following in case of a quadratic variable like $y_icdotdelta_i$ above:

Introduce a variable $z_i = y_i cdot delta_i$ w.r.t. to the following constraints:

$ Lcdotdelta_i leq z_i leq U cdot delta_i $

$ z_i leq y_i - Lcdot(1-delta_i)$

$ z_i geq y_i - U cdot (1-delta_i)$

where: $ L leq y_i leq U$ are the lower and upper bounds on the values of $y_i$

Questions:

1. Is this a common trick to linearize quadratic variables where one of them is a binary variable?


2. How to intuitively understand this transformation so as to remember why/how it works?


3. Are there other ways to achieve the same thing?

optimization linear-programming quadratic-programming constraints

share|cite|improve this question

edited Mar 15 at 8:47

Silke Horn

32

asked Aug 9 '14 at 0:42

PhDPhD

1,05451830

$endgroup$

add a comment | 

1

1

$begingroup$

I have an optimization problem that I'm working on. The objective is defined as follows:

$Maximize: c_icdot w_i cdot x_i - d_i cdot y_i cdot delta_i $

subject to some linear constraints where $c_i, w_i$ and $d_i$ are scalars and

$x_i, delta_i in {0,1}$ and $y_i in Z^+$

I wish to linearize this objective function so that I can solve it with an existing ILP solver. I found this link that suggests the following in case of a quadratic variable like $y_icdotdelta_i$ above:

Introduce a variable $z_i = y_i cdot delta_i$ w.r.t. to the following constraints:

$ Lcdotdelta_i leq z_i leq U cdot delta_i $

$ z_i leq y_i - Lcdot(1-delta_i)$

$ z_i geq y_i - U cdot (1-delta_i)$

where: $ L leq y_i leq U$ are the lower and upper bounds on the values of $y_i$

Questions:

1. Is this a common trick to linearize quadratic variables where one of them is a binary variable?


2. How to intuitively understand this transformation so as to remember why/how it works?


3. Are there other ways to achieve the same thing?

optimization linear-programming quadratic-programming constraints

share|cite|improve this question

edited Mar 15 at 8:47

Silke Horn

32

asked Aug 9 '14 at 0:42

PhDPhD

1,05451830

$endgroup$

add a comment | 

$begingroup$

I have an optimization problem that I'm working on. The objective is defined as follows:

$Maximize: c_icdot w_i cdot x_i - d_i cdot y_i cdot delta_i $

subject to some linear constraints where $c_i, w_i$ and $d_i$ are scalars and

$x_i, delta_i in {0,1}$ and $y_i in Z^+$

I wish to linearize this objective function so that I can solve it with an existing ILP solver. I found this link that suggests the following in case of a quadratic variable like $y_icdotdelta_i$ above:

Introduce a variable $z_i = y_i cdot delta_i$ w.r.t. to the following constraints:

$ Lcdotdelta_i leq z_i leq U cdot delta_i $

$ z_i leq y_i - Lcdot(1-delta_i)$

$ z_i geq y_i - U cdot (1-delta_i)$

where: $ L leq y_i leq U$ are the lower and upper bounds on the values of $y_i$

Questions:

1. Is this a common trick to linearize quadratic variables where one of them is a binary variable?


2. How to intuitively understand this transformation so as to remember why/how it works?


3. Are there other ways to achieve the same thing?

optimization linear-programming quadratic-programming constraints

share|cite|improve this question

edited Mar 15 at 8:47

Silke Horn

32

asked Aug 9 '14 at 0:42

PhDPhD

1,05451830

$endgroup$

share|cite|improve this question

edited Mar 15 at 8:47

Silke Horn

32

asked Aug 9 '14 at 0:42

PhDPhD

1,05451830

share|cite|improve this question

edited Mar 15 at 8:47

Silke Horn

32

asked Aug 9 '14 at 0:42

PhDPhD

1,05451830

edited Mar 15 at 8:47

Silke Horn

32

edited Mar 15 at 8:47

Silke Horn

32

asked Aug 9 '14 at 0:42

PhDPhD

1,05451830

asked Aug 9 '14 at 0:42

PhDPhD

1,05451830

1 Answer
1

active

oldest

votes

1

$begingroup$

Yes, this is part of a set of standard tricks that can be used to linearize polynomial terms involving integer, and especially binary variables. There are lots of such transformations, and most good integer programming (and especially mixed integer nonlinear programming) texts summarize them.

The best way to understand the transformation is to take it on a case by case basis. First consider $delta_i = 0$. The first set of inequalities guarantees in this case that $z_i = 0$ which is what we want, and all the other constraints are redundant. If $delta_i = 1$, then the first set of inequalities simply enforces the bounds since $z_i = y_i$ in this case. Moreover, $1 - delta_i = 0$ means that the last 2 constraints enforce $z_i = y_i$.

There might be other ways to transform the quadratic term. For instance you could use some Big M type models, but those are usually not desirable since they yield weak relaxations if you pick your Big M parameter wrong.

You can do away with some of the constraints if your objective function "pushes" your variables in the right direction.

share|cite|improve this answer

answered Aug 12 '14 at 15:22

wonkowonko

45527

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Any recommendations on texts? I'm also intrigued by the Big M. I "have" seen and worked with something with large "M"s and have been told that's a trick without really understanding why. Pointers would be much appreciated.
  $endgroup$
  – PhD
  Aug 12 '14 at 22:02
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f891610%2fhow-to-linearize-a-quadratic-objective-function-with-linear-constraints%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

1

$begingroup$

Yes, this is part of a set of standard tricks that can be used to linearize polynomial terms involving integer, and especially binary variables. There are lots of such transformations, and most good integer programming (and especially mixed integer nonlinear programming) texts summarize them.

The best way to understand the transformation is to take it on a case by case basis. First consider $delta_i = 0$. The first set of inequalities guarantees in this case that $z_i = 0$ which is what we want, and all the other constraints are redundant. If $delta_i = 1$, then the first set of inequalities simply enforces the bounds since $z_i = y_i$ in this case. Moreover, $1 - delta_i = 0$ means that the last 2 constraints enforce $z_i = y_i$.

There might be other ways to transform the quadratic term. For instance you could use some Big M type models, but those are usually not desirable since they yield weak relaxations if you pick your Big M parameter wrong.

You can do away with some of the constraints if your objective function "pushes" your variables in the right direction.

share|cite|improve this answer

answered Aug 12 '14 at 15:22

wonkowonko

45527

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Any recommendations on texts? I'm also intrigued by the Big M. I "have" seen and worked with something with large "M"s and have been told that's a trick without really understanding why. Pointers would be much appreciated.
  $endgroup$
  – PhD
  Aug 12 '14 at 22:02
  

  
  
  
  

add a comment | 

1

$begingroup$

Yes, this is part of a set of standard tricks that can be used to linearize polynomial terms involving integer, and especially binary variables. There are lots of such transformations, and most good integer programming (and especially mixed integer nonlinear programming) texts summarize them.

The best way to understand the transformation is to take it on a case by case basis. First consider $delta_i = 0$. The first set of inequalities guarantees in this case that $z_i = 0$ which is what we want, and all the other constraints are redundant. If $delta_i = 1$, then the first set of inequalities simply enforces the bounds since $z_i = y_i$ in this case. Moreover, $1 - delta_i = 0$ means that the last 2 constraints enforce $z_i = y_i$.

There might be other ways to transform the quadratic term. For instance you could use some Big M type models, but those are usually not desirable since they yield weak relaxations if you pick your Big M parameter wrong.

You can do away with some of the constraints if your objective function "pushes" your variables in the right direction.

share|cite|improve this answer

answered Aug 12 '14 at 15:22

wonkowonko

45527

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Any recommendations on texts? I'm also intrigued by the Big M. I "have" seen and worked with something with large "M"s and have been told that's a trick without really understanding why. Pointers would be much appreciated.
  $endgroup$
  – PhD
  Aug 12 '14 at 22:02
  

  
  
  
  

add a comment | 

$begingroup$

Yes, this is part of a set of standard tricks that can be used to linearize polynomial terms involving integer, and especially binary variables. There are lots of such transformations, and most good integer programming (and especially mixed integer nonlinear programming) texts summarize them.

The best way to understand the transformation is to take it on a case by case basis. First consider $delta_i = 0$. The first set of inequalities guarantees in this case that $z_i = 0$ which is what we want, and all the other constraints are redundant. If $delta_i = 1$, then the first set of inequalities simply enforces the bounds since $z_i = y_i$ in this case. Moreover, $1 - delta_i = 0$ means that the last 2 constraints enforce $z_i = y_i$.

There might be other ways to transform the quadratic term. For instance you could use some Big M type models, but those are usually not desirable since they yield weak relaxations if you pick your Big M parameter wrong.

You can do away with some of the constraints if your objective function "pushes" your variables in the right direction.

share|cite|improve this answer

answered Aug 12 '14 at 15:22

wonkowonko

45527

$endgroup$

share|cite|improve this answer

answered Aug 12 '14 at 15:22

wonkowonko

45527

answered Aug 12 '14 at 15:22

wonkowonko

45527

answered Aug 12 '14 at 15:22

wonkowonko

45527