Convert fractional to quadratic integer programming

Clash Royale CLAN TAG#URR8PPP

up vote
0
down vote

favorite

Maximize $fracsum_isum_ja_ijx_iy_j(sum_ix_i)(sum_jy_j)+ fracsum_isum_jb_ijx_iz_j(sum_ix_i)(sum_jz_j)$, subject to $Ax+By+Cz leq d, quad x,y,zin 0,1$.

Can we convert the above problem to a quadratic integer programming? I tried but I could find noway. Does anyone have any idea?

optimization linear-programming integer-programming mixed-integer-programming

share|cite|improve this question

asked Jul 24 at 21:33

Thomas Edison

239313

add a comment | 

up vote
0
down vote

favorite

Maximize $fracsum_isum_ja_ijx_iy_j(sum_ix_i)(sum_jy_j)+ fracsum_isum_jb_ijx_iz_j(sum_ix_i)(sum_jz_j)$, subject to $Ax+By+Cz leq d, quad x,y,zin 0,1$.

Can we convert the above problem to a quadratic integer programming? I tried but I could find noway. Does anyone have any idea?

optimization linear-programming integer-programming mixed-integer-programming

share|cite|improve this question

asked Jul 24 at 21:33

Thomas Edison

239313

add a comment | 

up vote
0
down vote

favorite

up vote
0
down vote

favorite

Maximize $fracsum_isum_ja_ijx_iy_j(sum_ix_i)(sum_jy_j)+ fracsum_isum_jb_ijx_iz_j(sum_ix_i)(sum_jz_j)$, subject to $Ax+By+Cz leq d, quad x,y,zin 0,1$.

Can we convert the above problem to a quadratic integer programming? I tried but I could find noway. Does anyone have any idea?

optimization linear-programming integer-programming mixed-integer-programming

share|cite|improve this question

asked Jul 24 at 21:33

Thomas Edison

239313

Maximize $fracsum_isum_ja_ijx_iy_j(sum_ix_i)(sum_jy_j)+ fracsum_isum_jb_ijx_iz_j(sum_ix_i)(sum_jz_j)$, subject to $Ax+By+Cz leq d, quad x,y,zin 0,1$.

Can we convert the above problem to a quadratic integer programming? I tried but I could find noway. Does anyone have any idea?

optimization linear-programming integer-programming mixed-integer-programming

share|cite|improve this question

asked Jul 24 at 21:33

Thomas Edison

239313

share|cite|improve this question

share|cite|improve this question

asked Jul 24 at 21:33

Thomas Edison

239313

asked Jul 24 at 21:33

Thomas Edison

239313

asked Jul 24 at 21:33

Thomas Edison

239313

239313

add a comment | 

add a comment | 

1 Answer
1

active

oldest

votes

up vote
5
down vote



accepted

Yes, one way is to introduce two new variables $t_1$and $t_2$ and maximize $t_1+t_2$with the constraints $f_1(x,y) geq t_1$ and $f_2(x,z) geq t_2$. Now multiply with denominators and you will have polynomials of $x,y$ and $t$ in your constraints.

These nonlinear constraints can all be linearized using standard strategies. For instance, $ab$ where $a$ and $b$ are binary can be written as $w$ where the new variable $w$ satisfies $w leq a$, $w leq b$ and $w geq a +b -1$. A product between binary $a$ and continuous variable $b$ is modelled using a big-M reformulation where the product is replaced with $w$ where $-Ma leq w leq Ma$ and $-M(1-a) leq w-b leq M(1-a)$

Of course, the special case here with with a cubic $abc$ involving two binaries $a$ and $b$ and a continuous variable $c$, can be done in one step as $-Ma leq w leq Ma$, $-Mb leq w leq Mb$ and $-M(2-a-b) leq w-c leq M(2-a-b)$

At this point, you have a mixed-integer linear program.

share|cite|improve this answer

edited Jul 25 at 12:25

answered Jul 25 at 7:36

Johan Löfberg

4,6921811

• 
  
  
  

  
  

  
  
  
  
  
  

  
  It might be necessary to constraint $sum_i x_i$, $sum_i y_i$ and $sum_i z_i$ to each be $ge 1$. Otherwise, I think the revised objective can be made unbounded by zeroing out all components of one of $x$, $y$ or $z$, quite possible while satisfying the linear constraint.
  – prubin
  Jul 27 at 21:21
  

  
  
  
  

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',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
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

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2861783%2fconvert-fractional-to-quadratic-integer-programming%23new-answer', 'question_page');

);

Post as a guest

Name Email

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
5
down vote



accepted

Yes, one way is to introduce two new variables $t_1$and $t_2$ and maximize $t_1+t_2$with the constraints $f_1(x,y) geq t_1$ and $f_2(x,z) geq t_2$. Now multiply with denominators and you will have polynomials of $x,y$ and $t$ in your constraints.

These nonlinear constraints can all be linearized using standard strategies. For instance, $ab$ where $a$ and $b$ are binary can be written as $w$ where the new variable $w$ satisfies $w leq a$, $w leq b$ and $w geq a +b -1$. A product between binary $a$ and continuous variable $b$ is modelled using a big-M reformulation where the product is replaced with $w$ where $-Ma leq w leq Ma$ and $-M(1-a) leq w-b leq M(1-a)$

Of course, the special case here with with a cubic $abc$ involving two binaries $a$ and $b$ and a continuous variable $c$, can be done in one step as $-Ma leq w leq Ma$, $-Mb leq w leq Mb$ and $-M(2-a-b) leq w-c leq M(2-a-b)$

At this point, you have a mixed-integer linear program.

share|cite|improve this answer

edited Jul 25 at 12:25

answered Jul 25 at 7:36

Johan Löfberg

4,6921811

• 
  
  
  

  
  

  
  
  
  
  
  

  
  It might be necessary to constraint $sum_i x_i$, $sum_i y_i$ and $sum_i z_i$ to each be $ge 1$. Otherwise, I think the revised objective can be made unbounded by zeroing out all components of one of $x$, $y$ or $z$, quite possible while satisfying the linear constraint.
  – prubin
  Jul 27 at 21:21
  

  
  
  
  

add a comment | 

up vote
5
down vote



accepted

Yes, one way is to introduce two new variables $t_1$and $t_2$ and maximize $t_1+t_2$with the constraints $f_1(x,y) geq t_1$ and $f_2(x,z) geq t_2$. Now multiply with denominators and you will have polynomials of $x,y$ and $t$ in your constraints.

These nonlinear constraints can all be linearized using standard strategies. For instance, $ab$ where $a$ and $b$ are binary can be written as $w$ where the new variable $w$ satisfies $w leq a$, $w leq b$ and $w geq a +b -1$. A product between binary $a$ and continuous variable $b$ is modelled using a big-M reformulation where the product is replaced with $w$ where $-Ma leq w leq Ma$ and $-M(1-a) leq w-b leq M(1-a)$

Of course, the special case here with with a cubic $abc$ involving two binaries $a$ and $b$ and a continuous variable $c$, can be done in one step as $-Ma leq w leq Ma$, $-Mb leq w leq Mb$ and $-M(2-a-b) leq w-c leq M(2-a-b)$

At this point, you have a mixed-integer linear program.

share|cite|improve this answer

edited Jul 25 at 12:25

answered Jul 25 at 7:36

Johan Löfberg

4,6921811

• 
  
  
  

  
  

  
  
  
  
  
  

  
  It might be necessary to constraint $sum_i x_i$, $sum_i y_i$ and $sum_i z_i$ to each be $ge 1$. Otherwise, I think the revised objective can be made unbounded by zeroing out all components of one of $x$, $y$ or $z$, quite possible while satisfying the linear constraint.
  – prubin
  Jul 27 at 21:21
  

  
  
  
  

add a comment | 

up vote
5
down vote



accepted

up vote
5
down vote



accepted

Yes, one way is to introduce two new variables $t_1$and $t_2$ and maximize $t_1+t_2$with the constraints $f_1(x,y) geq t_1$ and $f_2(x,z) geq t_2$. Now multiply with denominators and you will have polynomials of $x,y$ and $t$ in your constraints.

These nonlinear constraints can all be linearized using standard strategies. For instance, $ab$ where $a$ and $b$ are binary can be written as $w$ where the new variable $w$ satisfies $w leq a$, $w leq b$ and $w geq a +b -1$. A product between binary $a$ and continuous variable $b$ is modelled using a big-M reformulation where the product is replaced with $w$ where $-Ma leq w leq Ma$ and $-M(1-a) leq w-b leq M(1-a)$

Of course, the special case here with with a cubic $abc$ involving two binaries $a$ and $b$ and a continuous variable $c$, can be done in one step as $-Ma leq w leq Ma$, $-Mb leq w leq Mb$ and $-M(2-a-b) leq w-c leq M(2-a-b)$

At this point, you have a mixed-integer linear program.

share|cite|improve this answer

edited Jul 25 at 12:25

answered Jul 25 at 7:36

Johan Löfberg

4,6921811

Yes, one way is to introduce two new variables $t_1$and $t_2$ and maximize $t_1+t_2$with the constraints $f_1(x,y) geq t_1$ and $f_2(x,z) geq t_2$. Now multiply with denominators and you will have polynomials of $x,y$ and $t$ in your constraints.

These nonlinear constraints can all be linearized using standard strategies. For instance, $ab$ where $a$ and $b$ are binary can be written as $w$ where the new variable $w$ satisfies $w leq a$, $w leq b$ and $w geq a +b -1$. A product between binary $a$ and continuous variable $b$ is modelled using a big-M reformulation where the product is replaced with $w$ where $-Ma leq w leq Ma$ and $-M(1-a) leq w-b leq M(1-a)$

Of course, the special case here with with a cubic $abc$ involving two binaries $a$ and $b$ and a continuous variable $c$, can be done in one step as $-Ma leq w leq Ma$, $-Mb leq w leq Mb$ and $-M(2-a-b) leq w-c leq M(2-a-b)$

At this point, you have a mixed-integer linear program.

share|cite|improve this answer

edited Jul 25 at 12:25

answered Jul 25 at 7:36

Johan Löfberg

4,6921811

share|cite|improve this answer

share|cite|improve this answer

edited Jul 25 at 12:25

edited Jul 25 at 12:25

edited Jul 25 at 12:25

answered Jul 25 at 7:36

Johan Löfberg

4,6921811

answered Jul 25 at 7:36

Johan Löfberg

4,6921811

answered Jul 25 at 7:36

Johan Löfberg

4,6921811

4,6921811

• 
  
  
  

  
  

  
  
  
  
  
  

  
  It might be necessary to constraint $sum_i x_i$, $sum_i y_i$ and $sum_i z_i$ to each be $ge 1$. Otherwise, I think the revised objective can be made unbounded by zeroing out all components of one of $x$, $y$ or $z$, quite possible while satisfying the linear constraint.
  – prubin
  Jul 27 at 21:21
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  It might be necessary to constraint $sum_i x_i$, $sum_i y_i$ and $sum_i z_i$ to each be $ge 1$. Otherwise, I think the revised objective can be made unbounded by zeroing out all components of one of $x$, $y$ or $z$, quite possible while satisfying the linear constraint.
  – prubin
  Jul 27 at 21:21
  

  
  
  
  

It might be necessary to constraint $sum_i x_i$, $sum_i y_i$ and $sum_i z_i$ to each be $ge 1$. Otherwise, I think the revised objective can be made unbounded by zeroing out all components of one of $x$, $y$ or $z$, quite possible while satisfying the linear constraint.
– prubin
Jul 27 at 21:21

It might be necessary to constraint $sum_i x_i$, $sum_i y_i$ and $sum_i z_i$ to each be $ge 1$. Otherwise, I think the revised objective can be made unbounded by zeroing out all components of one of $x$, $y$ or $z$, quite possible while satisfying the linear constraint.
– prubin
Jul 27 at 21:21

add a comment | 

 

draft saved

draft discarded

 

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

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2861783%2fconvert-fractional-to-quadratic-integer-programming%23new-answer', 'question_page');

);

Post as a guest

Name Email

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

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

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

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email