Optimize the product of three binary variables: convex relaxation and integer solutionsHow to linearize a quadratic objective function with linear constraints?Binary integer variables in linear programmingConverting nonlinear constraints (product of binary and continuous variables) for linear programmingLinearize nonquadratic nonlinear constraintHow to decide whether this objective function (with integer variables) is convex or not?how to solve binary integer programming with non-convex nonlinear objective function?A nonlinear integer programming problem?How to linearize (or convexify) a function that takes the maximum of binary variables?Integer Linear Programming: Sum of Products of Binary VariablesHow to reformulate (or model differently) the sum of fractions in the objective of integer program?
Has any country ever had 2 former presidents in jail simultaneously?
What is the evidence for the "tyranny of the majority problem" in a direct democracy context?
Drawing ramified coverings with tikz
Are the IPv6 address space and IPv4 address space completely disjoint?
How do I color the graph in datavisualization?
Is the U.S. Code copyrighted by the Government?
What should you do when eye contact makes your subordinate uncomfortable?
How could a planet have erratic days?
What does "Scientists rise up against statistical significance" mean? (Comment in Nature)
copy and scale one figure (wheel)
Why Shazam when there is already Superman?
Store Credit Card Information in Password Manager?
Can Legal Documents Be Siged In Non-Standard Pen Colors?
Does an advisor owe his/her student anything? Will an advisor keep a PhD student only out of pity?
How do you respond to a colleague from another team when they're wrongly expecting that you'll help them?
What does routing an IP address mean?
Pre-mixing cryogenic fuels and using only one fuel tank
Added a new user on Ubuntu, set password not working?
Delivering sarcasm
"Spoil" vs "Ruin"
Can I sign legal documents with a smiley face?
Redundant comparison & "if" before assignment
Is this toilet slogan correct usage of the English language?
How much character growth crosses the line into breaking the character
Optimize the product of three binary variables: convex relaxation and integer solutions
How to linearize a quadratic objective function with linear constraints?Binary integer variables in linear programmingConverting nonlinear constraints (product of binary and continuous variables) for linear programmingLinearize nonquadratic nonlinear constraintHow to decide whether this objective function (with integer variables) is convex or not?how to solve binary integer programming with non-convex nonlinear objective function?A nonlinear integer programming problem?How to linearize (or convexify) a function that takes the maximum of binary variables?Integer Linear Programming: Sum of Products of Binary VariablesHow to reformulate (or model differently) the sum of fractions in the objective of integer program?
$begingroup$
I am working on a problem related to graphs and I formulated the problem as follows:
$$max_y,e sum_i=1^n (c_i^1 y_i^1 + c_i^2 y_i^2) + sum_(i,j)in E(d^1y_i^1y_j^1e_ij +d^2y_i^2y_j^2e_ij)-sum_(i,j)in Ea_ije_ij$$
s.t. $$y_i^1 + y_i^2 = 1, i=1,2,cdots,n$$
$$sum_(i,j)in E e_ij geq D$$
The variables are $(cdots, y_i^1,y_i^2,cdots)$ for $i=1,2,cdots,n$ and $e_ij$ for $(i,j)$ in an edge set $E$. All variables are binary.
$(c_i^1,c_i^2)$ are (unrestricted) constants and $d^1,d^2,a_ij,D$ are non-negative constants.
The above objective function is nonlinear and the variables are binary. So I used the standard method to linearize the objective:
Let $z_ij^1 = y_i^1y_j^1e_ij$ and $z_ij^2 = y_i^2y_j^2e_ij$ and add constraints $z_ij^1 leq y_i^1,z_ij^1 leq y_j^1,z_ij^1 leq e_ij,z_ij^1 geq y_i^1 + y_j^1 + e_ij -2$ and similarly for each $z_ij^2$.
Second, I relax the integer constraints and let every variable be within $[0,1]$.
The resulting problem is a linear program, which can be solved optimally. However, the solutions are fractional.
Below are some issues.
Is there any condition (for the form of the objective function) with which the linear program is guaranteed to produce integer solutions? I met with similar problems where the nonlinear terms in the objective only involve products of two binary variables and using the same linearization technique, the solutions are integral. Also, I removed the terms $-sum_(i,j)in E a_ije_ij$ in the original objective functions and then it seems that the solutions are all integral.
Is there any other technique to linearize the product of three binary variables? What are the standard method(s) to deal with such optimization problems?
Since the solutions are fractional, what are the standard method(s) to round the results to get integer solutions? And are there any approximation guarantees for such rounding methods? I tried a few methods, such as setting a threshold (fractional values above the threshold are set to 1) and ranking the fractional solutions (pick the top-K to be 1).
convex-optimization linear-programming integer-programming binary-programming
asked Mar 15 at 16:16
ParadoxParadox
909
$endgroup$
|
show 1 more comment
$begingroup$
I am working on a problem related to graphs and I formulated the problem as follows:
$$max_y,e sum_i=1^n (c_i^1 y_i^1 + c_i^2 y_i^2) + sum_(i,j)in E(d^1y_i^1y_j^1e_ij +d^2y_i^2y_j^2e_ij)-sum_(i,j)in Ea_ije_ij$$
s.t. $$y_i^1 + y_i^2 = 1, i=1,2,cdots,n$$
$$sum_(i,j)in E e_ij geq D$$
The variables are $(cdots, y_i^1,y_i^2,cdots)$ for $i=1,2,cdots,n$ and $e_ij$ for $(i,j)$ in an edge set $E$. All variables are binary.
$(c_i^1,c_i^2)$ are (unrestricted) constants and $d^1,d^2,a_ij,D$ are non-negative constants.
The above objective function is nonlinear and the variables are binary. So I used the standard method to linearize the objective:
Let $z_ij^1 = y_i^1y_j^1e_ij$ and $z_ij^2 = y_i^2y_j^2e_ij$ and add constraints $z_ij^1 leq y_i^1,z_ij^1 leq y_j^1,z_ij^1 leq e_ij,z_ij^1 geq y_i^1 + y_j^1 + e_ij -2$ and similarly for each $z_ij^2$.
Second, I relax the integer constraints and let every variable be within $[0,1]$.
The resulting problem is a linear program, which can be solved optimally. However, the solutions are fractional.
Below are some issues.
Is there any condition (for the form of the objective function) with which the linear program is guaranteed to produce integer solutions? I met with similar problems where the nonlinear terms in the objective only involve products of two binary variables and using the same linearization technique, the solutions are integral. Also, I removed the terms $-sum_(i,j)in E a_ije_ij$ in the original objective functions and then it seems that the solutions are all integral.
Is there any other technique to linearize the product of three binary variables? What are the standard method(s) to deal with such optimization problems?
Since the solutions are fractional, what are the standard method(s) to round the results to get integer solutions? And are there any approximation guarantees for such rounding methods? I tried a few methods, such as setting a threshold (fractional values above the threshold are set to 1) and ranking the fractional solutions (pick the top-K to be 1).
convex-optimization linear-programming integer-programming binary-programming
asked Mar 15 at 16:16
ParadoxParadox
909
$endgroup$
1
$begingroup$
Google "integrality gap" and "total unimodularity".
$endgroup$
– Rodrigo de Azevedo
Mar 16 at 7:47
$begingroup$
When you say "the solutions", what do you mean? Are you getting basic feasible solutions?
$endgroup$
– Alex Shtof
Mar 16 at 17:59
$begingroup$
@AlexShtof I mean the optimal fractional solutions to the Linear program
$endgroup$
– Paradox
Mar 16 at 19:33
$begingroup$
You are saying 'the' solution, as if it is unique. That is why I am asking if you are getting a basic feasible solution each time.
$endgroup$
– Alex Shtof
Mar 16 at 19:36
$begingroup$
@AlexShtof Sorry, I don't know. How can I check if the solution is a basic feasible solution? and what's the implication of the solution being a basic feasible solution? From the results I have now, the solutions of $e_ij$ take three values 0, 0.5, and 1.
$endgroup$
– Paradox
Mar 16 at 19:55
|
show 1 more comment
$begingroup$
I am working on a problem related to graphs and I formulated the problem as follows:
$$max_y,e sum_i=1^n (c_i^1 y_i^1 + c_i^2 y_i^2) + sum_(i,j)in E(d^1y_i^1y_j^1e_ij +d^2y_i^2y_j^2e_ij)-sum_(i,j)in Ea_ije_ij$$
s.t. $$y_i^1 + y_i^2 = 1, i=1,2,cdots,n$$
$$sum_(i,j)in E e_ij geq D$$
The variables are $(cdots, y_i^1,y_i^2,cdots)$ for $i=1,2,cdots,n$ and $e_ij$ for $(i,j)$ in an edge set $E$. All variables are binary.
$(c_i^1,c_i^2)$ are (unrestricted) constants and $d^1,d^2,a_ij,D$ are non-negative constants.
The above objective function is nonlinear and the variables are binary. So I used the standard method to linearize the objective:
Let $z_ij^1 = y_i^1y_j^1e_ij$ and $z_ij^2 = y_i^2y_j^2e_ij$ and add constraints $z_ij^1 leq y_i^1,z_ij^1 leq y_j^1,z_ij^1 leq e_ij,z_ij^1 geq y_i^1 + y_j^1 + e_ij -2$ and similarly for each $z_ij^2$.
Second, I relax the integer constraints and let every variable be within $[0,1]$.
The resulting problem is a linear program, which can be solved optimally. However, the solutions are fractional.
Below are some issues.
Is there any condition (for the form of the objective function) with which the linear program is guaranteed to produce integer solutions? I met with similar problems where the nonlinear terms in the objective only involve products of two binary variables and using the same linearization technique, the solutions are integral. Also, I removed the terms $-sum_(i,j)in E a_ije_ij$ in the original objective functions and then it seems that the solutions are all integral.
Is there any other technique to linearize the product of three binary variables? What are the standard method(s) to deal with such optimization problems?
Since the solutions are fractional, what are the standard method(s) to round the results to get integer solutions? And are there any approximation guarantees for such rounding methods? I tried a few methods, such as setting a threshold (fractional values above the threshold are set to 1) and ranking the fractional solutions (pick the top-K to be 1).
convex-optimization linear-programming integer-programming binary-programming
asked Mar 15 at 16:16
ParadoxParadox
909
$endgroup$
I am working on a problem related to graphs and I formulated the problem as follows:
$$max_y,e sum_i=1^n (c_i^1 y_i^1 + c_i^2 y_i^2) + sum_(i,j)in E(d^1y_i^1y_j^1e_ij +d^2y_i^2y_j^2e_ij)-sum_(i,j)in Ea_ije_ij$$
s.t. $$y_i^1 + y_i^2 = 1, i=1,2,cdots,n$$
$$sum_(i,j)in E e_ij geq D$$
The variables are $(cdots, y_i^1,y_i^2,cdots)$ for $i=1,2,cdots,n$ and $e_ij$ for $(i,j)$ in an edge set $E$. All variables are binary.
$(c_i^1,c_i^2)$ are (unrestricted) constants and $d^1,d^2,a_ij,D$ are non-negative constants.
The above objective function is nonlinear and the variables are binary. So I used the standard method to linearize the objective:
Let $z_ij^1 = y_i^1y_j^1e_ij$ and $z_ij^2 = y_i^2y_j^2e_ij$ and add constraints $z_ij^1 leq y_i^1,z_ij^1 leq y_j^1,z_ij^1 leq e_ij,z_ij^1 geq y_i^1 + y_j^1 + e_ij -2$ and similarly for each $z_ij^2$.
Second, I relax the integer constraints and let every variable be within $[0,1]$.
The resulting problem is a linear program, which can be solved optimally. However, the solutions are fractional.
Below are some issues.
Is there any condition (for the form of the objective function) with which the linear program is guaranteed to produce integer solutions? I met with similar problems where the nonlinear terms in the objective only involve products of two binary variables and using the same linearization technique, the solutions are integral. Also, I removed the terms $-sum_(i,j)in E a_ije_ij$ in the original objective functions and then it seems that the solutions are all integral.
Is there any other technique to linearize the product of three binary variables? What are the standard method(s) to deal with such optimization problems?
Since the solutions are fractional, what are the standard method(s) to round the results to get integer solutions? And are there any approximation guarantees for such rounding methods? I tried a few methods, such as setting a threshold (fractional values above the threshold are set to 1) and ranking the fractional solutions (pick the top-K to be 1).
convex-optimization linear-programming integer-programming binary-programming
convex-optimization linear-programming integer-programming binary-programming
asked Mar 15 at 16:16
ParadoxParadox
909
asked Mar 15 at 16:16
ParadoxParadox
909
asked Mar 15 at 16:16
ParadoxParadox
909
asked Mar 15 at 16:16
ParadoxParadox
909
asked Mar 15 at 16:16
ParadoxParadox
909
909
1
$begingroup$
Google "integrality gap" and "total unimodularity".
$endgroup$
– Rodrigo de Azevedo
Mar 16 at 7:47
$begingroup$
When you say "the solutions", what do you mean? Are you getting basic feasible solutions?
$endgroup$
– Alex Shtof
Mar 16 at 17:59
$begingroup$
@AlexShtof I mean the optimal fractional solutions to the Linear program
$endgroup$
– Paradox
Mar 16 at 19:33
$begingroup$
You are saying 'the' solution, as if it is unique. That is why I am asking if you are getting a basic feasible solution each time.
$endgroup$
– Alex Shtof
Mar 16 at 19:36
$begingroup$
@AlexShtof Sorry, I don't know. How can I check if the solution is a basic feasible solution? and what's the implication of the solution being a basic feasible solution? From the results I have now, the solutions of $e_ij$ take three values 0, 0.5, and 1.
$endgroup$
– Paradox
Mar 16 at 19:55
|
show 1 more comment
1
$begingroup$
Google "integrality gap" and "total unimodularity".
$endgroup$
– Rodrigo de Azevedo
Mar 16 at 7:47
$begingroup$
When you say "the solutions", what do you mean? Are you getting basic feasible solutions?
$endgroup$
– Alex Shtof
Mar 16 at 17:59
$begingroup$
@AlexShtof I mean the optimal fractional solutions to the Linear program
$endgroup$
– Paradox
Mar 16 at 19:33
$begingroup$
You are saying 'the' solution, as if it is unique. That is why I am asking if you are getting a basic feasible solution each time.
$endgroup$
– Alex Shtof
Mar 16 at 19:36
$begingroup$
@AlexShtof Sorry, I don't know. How can I check if the solution is a basic feasible solution? and what's the implication of the solution being a basic feasible solution? From the results I have now, the solutions of $e_ij$ take three values 0, 0.5, and 1.
$endgroup$
– Paradox
Mar 16 at 19:55
1
1
$begingroup$
Google "integrality gap" and "total unimodularity".
$endgroup$
– Rodrigo de Azevedo
Mar 16 at 7:47
$begingroup$
Google "integrality gap" and "total unimodularity".
$endgroup$
– Rodrigo de Azevedo
Mar 16 at 7:47
$begingroup$
When you say "the solutions", what do you mean? Are you getting basic feasible solutions?
$endgroup$
– Alex Shtof
Mar 16 at 17:59
$begingroup$
When you say "the solutions", what do you mean? Are you getting basic feasible solutions?
$endgroup$
– Alex Shtof
Mar 16 at 17:59
$begingroup$
@AlexShtof I mean the optimal fractional solutions to the Linear program
$endgroup$
– Paradox
Mar 16 at 19:33
$begingroup$
@AlexShtof I mean the optimal fractional solutions to the Linear program
$endgroup$
– Paradox
Mar 16 at 19:33
$begingroup$
You are saying 'the' solution, as if it is unique. That is why I am asking if you are getting a basic feasible solution each time.
$endgroup$
– Alex Shtof
Mar 16 at 19:36
$begingroup$
You are saying 'the' solution, as if it is unique. That is why I am asking if you are getting a basic feasible solution each time.
$endgroup$
– Alex Shtof
Mar 16 at 19:36
$begingroup$
@AlexShtof Sorry, I don't know. How can I check if the solution is a basic feasible solution? and what's the implication of the solution being a basic feasible solution? From the results I have now, the solutions of $e_ij$ take three values 0, 0.5, and 1.
$endgroup$
– Paradox
Mar 16 at 19:55
$begingroup$
@AlexShtof Sorry, I don't know. How can I check if the solution is a basic feasible solution? and what's the implication of the solution being a basic feasible solution? From the results I have now, the solutions of $e_ij$ take three values 0, 0.5, and 1.
$endgroup$
– Paradox
Mar 16 at 19:55
|
show 1 more comment
0
active
oldest
votes
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
);
);
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3149486%2foptimize-the-product-of-three-binary-variables-convex-relaxation-and-integer-so%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3149486%2foptimize-the-product-of-three-binary-variables-convex-relaxation-and-integer-so%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
Google "integrality gap" and "total unimodularity".
$endgroup$
– Rodrigo de Azevedo
Mar 16 at 7:47
$begingroup$
When you say "the solutions", what do you mean? Are you getting basic feasible solutions?
$endgroup$
– Alex Shtof
Mar 16 at 17:59
$begingroup$
@AlexShtof I mean the optimal fractional solutions to the Linear program
$endgroup$
– Paradox
Mar 16 at 19:33
$begingroup$
You are saying 'the' solution, as if it is unique. That is why I am asking if you are getting a basic feasible solution each time.
$endgroup$
– Alex Shtof
Mar 16 at 19:36
$begingroup$
@AlexShtof Sorry, I don't know. How can I check if the solution is a basic feasible solution? and what's the implication of the solution being a basic feasible solution? From the results I have now, the solutions of $e_ij$ take three values 0, 0.5, and 1.
$endgroup$
– Paradox
Mar 16 at 19:55