Expressing a chain of boolean ORs using ILPHow to determine if a given problem seems to be a good fit to be solved using combinatorial Benders decompositionHow to reduce recursion when using Gomory cutting planes to solve an integer program?Difference between lazy callbacks and using lazy constraints directlyTightness of an LP relaxation without using objective functionHow to linearize a constraint with a maximum of binary variables times some coefficient in the right-hand-sideBin Packing with Relational PenalizationHow to formulate this scheduling problem efficiently?How to reformulate (linearize/convexify) a budgeted assignment problem?Static stochastic knapsack problem: unbounded version
What are the advantages of this gold finger shape?
What is the purpose/function of this power inductor in parallel?
Setting up a Mathematical Institute of Refereeing?
Is Fourier series a sampled version of Fourier transform?
Why does "auf der Strecke bleiben" mean "to fall by the wayside"?
Physical Interpretation of an Overdamped Pendulum
If a person claims to know anything could it be disproven by saying 'prove that we are not in a simulation'?
What allows us to use imaginary numbers?
What is the question mark?
Has the speed of light ever been measured in vacuum?
What should I do if actually I found a serious flaw in someone's PhD thesis and an article derived from that PhD thesis?
What is the opposite of "hunger level"?
Attacking the Hydra
What is the hottest thing in the universe?
Why do so many people play out of turn on the last lead?
When does The Truman Show take place?
100 Years of GCHQ - A quick afternoon puzzle!
Are there liquid fueled rocket boosters having coaxial fuel/oxidizer tanks?
What should I do with the stock I own if I anticipate there will be a recession?
What does 〇〇〇〇 mean when combined with おじさん？
Set theory with antielements?
How does the Moon's gravity affect Earth's oceans despite Earth's stronger gravitational pull?
Scam? Phone call from "Department of Social Security" asking me to call back
How do I answer an interview question about how to handle a hard deadline I won't be able to meet?
Expressing a chain of boolean ORs using ILP
How to determine if a given problem seems to be a good fit to be solved using combinatorial Benders decompositionHow to reduce recursion when using Gomory cutting planes to solve an integer program?Difference between lazy callbacks and using lazy constraints directlyTightness of an LP relaxation without using objective functionHow to linearize a constraint with a maximum of binary variables times some coefficient in the right-hand-sideBin Packing with Relational PenalizationHow to formulate this scheduling problem efficiently?How to reformulate (linearize/convexify) a budgeted assignment problem?Static stochastic knapsack problem: unbounded version
$begingroup$
How to express a chain of OR operations in an ILP in which each expression is a less than or equal constraint and the left hand side variable in all inequalities is always the same? All the variables are binary.
For example, I would like to express $x_1 leq x_3$ OR $x_1 leq x_4$ OR $x_1 leq x_6$. Notice the first variable in all the inequality constraints is $x_1$.
optimization modeling integer-programming
edited 7 hours ago
Oguz Toragay
2,2472 silver badges26 bronze badges
asked 8 hours ago
ephemeralephemeral
462 bronze badges
New contributor
ephemeral is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
How to express a chain of OR operations in an ILP in which each expression is a less than or equal constraint and the left hand side variable in all inequalities is always the same? All the variables are binary.
For example, I would like to express $x_1 leq x_3$ OR $x_1 leq x_4$ OR $x_1 leq x_6$. Notice the first variable in all the inequality constraints is $x_1$.
optimization modeling integer-programming
edited 7 hours ago
Oguz Toragay
2,2472 silver badges26 bronze badges
asked 8 hours ago
ephemeralephemeral
462 bronze badges
New contributor
ephemeral is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
How to express a chain of OR operations in an ILP in which each expression is a less than or equal constraint and the left hand side variable in all inequalities is always the same? All the variables are binary.
For example, I would like to express $x_1 leq x_3$ OR $x_1 leq x_4$ OR $x_1 leq x_6$. Notice the first variable in all the inequality constraints is $x_1$.
optimization modeling integer-programming
edited 7 hours ago
Oguz Toragay
2,2472 silver badges26 bronze badges
asked 8 hours ago
ephemeralephemeral
462 bronze badges
New contributor
ephemeral is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
How to express a chain of OR operations in an ILP in which each expression is a less than or equal constraint and the left hand side variable in all inequalities is always the same? All the variables are binary.
For example, I would like to express $x_1 leq x_3$ OR $x_1 leq x_4$ OR $x_1 leq x_6$. Notice the first variable in all the inequality constraints is $x_1$.
optimization modeling integer-programming
optimization modeling integer-programming
edited 7 hours ago
Oguz Toragay
2,2472 silver badges26 bronze badges
asked 8 hours ago
ephemeralephemeral
462 bronze badges
New contributor
ephemeral is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 7 hours ago
Oguz Toragay
2,2472 silver badges26 bronze badges
asked 8 hours ago
ephemeralephemeral
462 bronze badges
New contributor
ephemeral is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 7 hours ago
Oguz Toragay
2,2472 silver badges26 bronze badges
edited 7 hours ago
Oguz Toragay
2,2472 silver badges26 bronze badges
edited 7 hours ago
Oguz Toragay
2,2472 silver badges26 bronze badges
2,2472 silver badges26 bronze badges
asked 8 hours ago
ephemeralephemeral
462 bronze badges
New contributor
ephemeral is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 8 hours ago
ephemeralephemeral
462 bronze badges
asked 8 hours ago
ephemeralephemeral
462 bronze badges
462 bronze badges
New contributor
ephemeral is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
ephemeral is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Your example constraint is equivalent to $x_1 le textmax(x_3,x_4,x_6)$, which I will generalize to $x_1 le max(x_2,ldots,x_n)$.
This max can be handled using section 2.6 "Logical OR" of FICO MIP formulations and linearizations: Quick reference.
Specifically, introduce a binary variable, $d$, to be constrained as follows so that it will be equal to $textmax(x_2,ldots,x_n)$
beginalignd &ge x_i, quad i=2,ldots, n\d &le sumlimits_i=2^n x_iendalign
Now add the constraint: $x_1 le d$.
edited 5 hours ago
Kevin Dalmeijer
1,8945 silver badges24 bronze badges
answered 7 hours ago
Mark L. StoneMark L. Stone
3,3077 silver badges27 bronze badges
$endgroup$
1
$begingroup$
@TheSimpliFire Re: your edit. Centering constraints is o.k., but I prefer my dots at "ground level" rather than in the middle of the air. I think my way is far more common.
$endgroup$
– Mark L. Stone
7 hours ago
1
$begingroup$
Right, changed fromcdotstoldots, rather than...
$endgroup$
– TheSimpliFire♦
7 hours ago
2
$begingroup$
Note that if you are not interested in the variable $d$ itself, you can eliminate the variable to obtain $x_1 le sum_i=2^n x_i$ as in Rob Pratt's answer.
$endgroup$
– Kevin Dalmeijer
5 hours ago
$begingroup$
@Kevin Dalmeijer Yes indeedy.
$endgroup$
– Mark L. Stone
5 hours ago
add a comment |
$begingroup$
Derivation via conjunctive normal form:
beginequation
x_1 implies underseti=2overset nlor x_i \
neg x_1 bigvee underseti=2overset nlor x_i \
1 - x_1 + sum_i=2^n x_i ge 1 \
x_1 le sum_i=2^n x_i
endequation
edited 3 hours ago
TheSimpliFire♦
1,9826 silver badges38 bronze badges
answered 6 hours ago
Rob PrattRob Pratt
9321 silver badge9 bronze badges
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "700"
;
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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
);
);
ephemeral is a new contributor. Be nice, and check out our Code of Conduct.
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%2for.stackexchange.com%2fquestions%2f1300%2fexpressing-a-chain-of-boolean-ors-using-ilp%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Your example constraint is equivalent to $x_1 le textmax(x_3,x_4,x_6)$, which I will generalize to $x_1 le max(x_2,ldots,x_n)$.
This max can be handled using section 2.6 "Logical OR" of FICO MIP formulations and linearizations: Quick reference.
Specifically, introduce a binary variable, $d$, to be constrained as follows so that it will be equal to $textmax(x_2,ldots,x_n)$
beginalignd &ge x_i, quad i=2,ldots, n\d &le sumlimits_i=2^n x_iendalign
Now add the constraint: $x_1 le d$.
edited 5 hours ago
Kevin Dalmeijer
1,8945 silver badges24 bronze badges
answered 7 hours ago
Mark L. StoneMark L. Stone
3,3077 silver badges27 bronze badges
$endgroup$
1
$begingroup$
@TheSimpliFire Re: your edit. Centering constraints is o.k., but I prefer my dots at "ground level" rather than in the middle of the air. I think my way is far more common.
$endgroup$
– Mark L. Stone
7 hours ago
1
$begingroup$
Right, changed fromcdotstoldots, rather than...
$endgroup$
– TheSimpliFire♦
7 hours ago
2
$begingroup$
Note that if you are not interested in the variable $d$ itself, you can eliminate the variable to obtain $x_1 le sum_i=2^n x_i$ as in Rob Pratt's answer.
$endgroup$
– Kevin Dalmeijer
5 hours ago
$begingroup$
@Kevin Dalmeijer Yes indeedy.
$endgroup$
– Mark L. Stone
5 hours ago
add a comment |
$begingroup$
Your example constraint is equivalent to $x_1 le textmax(x_3,x_4,x_6)$, which I will generalize to $x_1 le max(x_2,ldots,x_n)$.
This max can be handled using section 2.6 "Logical OR" of FICO MIP formulations and linearizations: Quick reference.
Specifically, introduce a binary variable, $d$, to be constrained as follows so that it will be equal to $textmax(x_2,ldots,x_n)$
beginalignd &ge x_i, quad i=2,ldots, n\d &le sumlimits_i=2^n x_iendalign
Now add the constraint: $x_1 le d$.
edited 5 hours ago
Kevin Dalmeijer
1,8945 silver badges24 bronze badges
answered 7 hours ago
Mark L. StoneMark L. Stone
3,3077 silver badges27 bronze badges
$endgroup$
1
$begingroup$
@TheSimpliFire Re: your edit. Centering constraints is o.k., but I prefer my dots at "ground level" rather than in the middle of the air. I think my way is far more common.
$endgroup$
– Mark L. Stone
7 hours ago
1
$begingroup$
Right, changed fromcdotstoldots, rather than...
$endgroup$
– TheSimpliFire♦
7 hours ago
2
$begingroup$
Note that if you are not interested in the variable $d$ itself, you can eliminate the variable to obtain $x_1 le sum_i=2^n x_i$ as in Rob Pratt's answer.
$endgroup$
– Kevin Dalmeijer
5 hours ago
$begingroup$
@Kevin Dalmeijer Yes indeedy.
$endgroup$
– Mark L. Stone
5 hours ago
add a comment |
$begingroup$
Your example constraint is equivalent to $x_1 le textmax(x_3,x_4,x_6)$, which I will generalize to $x_1 le max(x_2,ldots,x_n)$.
This max can be handled using section 2.6 "Logical OR" of FICO MIP formulations and linearizations: Quick reference.
Specifically, introduce a binary variable, $d$, to be constrained as follows so that it will be equal to $textmax(x_2,ldots,x_n)$
beginalignd &ge x_i, quad i=2,ldots, n\d &le sumlimits_i=2^n x_iendalign
Now add the constraint: $x_1 le d$.
edited 5 hours ago
Kevin Dalmeijer
1,8945 silver badges24 bronze badges
answered 7 hours ago
Mark L. StoneMark L. Stone
3,3077 silver badges27 bronze badges
$endgroup$
Your example constraint is equivalent to $x_1 le textmax(x_3,x_4,x_6)$, which I will generalize to $x_1 le max(x_2,ldots,x_n)$.
This max can be handled using section 2.6 "Logical OR" of FICO MIP formulations and linearizations: Quick reference.
Specifically, introduce a binary variable, $d$, to be constrained as follows so that it will be equal to $textmax(x_2,ldots,x_n)$
beginalignd &ge x_i, quad i=2,ldots, n\d &le sumlimits_i=2^n x_iendalign
Now add the constraint: $x_1 le d$.
edited 5 hours ago
Kevin Dalmeijer
1,8945 silver badges24 bronze badges
answered 7 hours ago
Mark L. StoneMark L. Stone
3,3077 silver badges27 bronze badges
edited 5 hours ago
Kevin Dalmeijer
1,8945 silver badges24 bronze badges
edited 5 hours ago
Kevin Dalmeijer
1,8945 silver badges24 bronze badges
edited 5 hours ago
Kevin Dalmeijer
1,8945 silver badges24 bronze badges
1,8945 silver badges24 bronze badges
answered 7 hours ago
Mark L. StoneMark L. Stone
3,3077 silver badges27 bronze badges
answered 7 hours ago
Mark L. StoneMark L. Stone
3,3077 silver badges27 bronze badges
answered 7 hours ago
Mark L. StoneMark L. Stone
3,3077 silver badges27 bronze badges
3,3077 silver badges27 bronze badges
1
$begingroup$
@TheSimpliFire Re: your edit. Centering constraints is o.k., but I prefer my dots at "ground level" rather than in the middle of the air. I think my way is far more common.
$endgroup$
– Mark L. Stone
7 hours ago
1
$begingroup$
Right, changed fromcdotstoldots, rather than...
$endgroup$
– TheSimpliFire♦
7 hours ago
2
$begingroup$
Note that if you are not interested in the variable $d$ itself, you can eliminate the variable to obtain $x_1 le sum_i=2^n x_i$ as in Rob Pratt's answer.
$endgroup$
– Kevin Dalmeijer
5 hours ago
$begingroup$
@Kevin Dalmeijer Yes indeedy.
$endgroup$
– Mark L. Stone
5 hours ago
add a comment |
1
$begingroup$
@TheSimpliFire Re: your edit. Centering constraints is o.k., but I prefer my dots at "ground level" rather than in the middle of the air. I think my way is far more common.
$endgroup$
– Mark L. Stone
7 hours ago
1
$begingroup$
Right, changed fromcdotstoldots, rather than...
$endgroup$
– TheSimpliFire♦
7 hours ago
2
$begingroup$
Note that if you are not interested in the variable $d$ itself, you can eliminate the variable to obtain $x_1 le sum_i=2^n x_i$ as in Rob Pratt's answer.
$endgroup$
– Kevin Dalmeijer
5 hours ago
$begingroup$
@Kevin Dalmeijer Yes indeedy.
$endgroup$
– Mark L. Stone
5 hours ago
1
1
$begingroup$
@TheSimpliFire Re: your edit. Centering constraints is o.k., but I prefer my dots at "ground level" rather than in the middle of the air. I think my way is far more common.
$endgroup$
– Mark L. Stone
7 hours ago
$begingroup$
@TheSimpliFire Re: your edit. Centering constraints is o.k., but I prefer my dots at "ground level" rather than in the middle of the air. I think my way is far more common.
$endgroup$
– Mark L. Stone
7 hours ago
1
1
$begingroup$
Right, changed from
cdots to ldots, rather than ...$endgroup$
– TheSimpliFire♦
7 hours ago
$begingroup$
Right, changed from
cdots to ldots, rather than ...$endgroup$
– TheSimpliFire♦
7 hours ago
2
2
$begingroup$
Note that if you are not interested in the variable $d$ itself, you can eliminate the variable to obtain $x_1 le sum_i=2^n x_i$ as in Rob Pratt's answer.
$endgroup$
– Kevin Dalmeijer
5 hours ago
$begingroup$
Note that if you are not interested in the variable $d$ itself, you can eliminate the variable to obtain $x_1 le sum_i=2^n x_i$ as in Rob Pratt's answer.
$endgroup$
– Kevin Dalmeijer
5 hours ago
$begingroup$
@Kevin Dalmeijer Yes indeedy.
$endgroup$
– Mark L. Stone
5 hours ago
$begingroup$
@Kevin Dalmeijer Yes indeedy.
$endgroup$
– Mark L. Stone
5 hours ago
add a comment |
$begingroup$
Derivation via conjunctive normal form:
beginequation
x_1 implies underseti=2overset nlor x_i \
neg x_1 bigvee underseti=2overset nlor x_i \
1 - x_1 + sum_i=2^n x_i ge 1 \
x_1 le sum_i=2^n x_i
endequation
edited 3 hours ago
TheSimpliFire♦
1,9826 silver badges38 bronze badges
answered 6 hours ago
Rob PrattRob Pratt
9321 silver badge9 bronze badges
$endgroup$
add a comment |
$begingroup$
Derivation via conjunctive normal form:
beginequation
x_1 implies underseti=2overset nlor x_i \
neg x_1 bigvee underseti=2overset nlor x_i \
1 - x_1 + sum_i=2^n x_i ge 1 \
x_1 le sum_i=2^n x_i
endequation
edited 3 hours ago
TheSimpliFire♦
1,9826 silver badges38 bronze badges
answered 6 hours ago
Rob PrattRob Pratt
9321 silver badge9 bronze badges
$endgroup$
add a comment |
$begingroup$
Derivation via conjunctive normal form:
beginequation
x_1 implies underseti=2overset nlor x_i \
neg x_1 bigvee underseti=2overset nlor x_i \
1 - x_1 + sum_i=2^n x_i ge 1 \
x_1 le sum_i=2^n x_i
endequation
edited 3 hours ago
TheSimpliFire♦
1,9826 silver badges38 bronze badges
answered 6 hours ago
Rob PrattRob Pratt
9321 silver badge9 bronze badges
$endgroup$
Derivation via conjunctive normal form:
beginequation
x_1 implies underseti=2overset nlor x_i \
neg x_1 bigvee underseti=2overset nlor x_i \
1 - x_1 + sum_i=2^n x_i ge 1 \
x_1 le sum_i=2^n x_i
endequation
edited 3 hours ago
TheSimpliFire♦
1,9826 silver badges38 bronze badges
answered 6 hours ago
Rob PrattRob Pratt
9321 silver badge9 bronze badges
edited 3 hours ago
TheSimpliFire♦
1,9826 silver badges38 bronze badges
edited 3 hours ago
TheSimpliFire♦
1,9826 silver badges38 bronze badges
edited 3 hours ago
TheSimpliFire♦
1,9826 silver badges38 bronze badges
1,9826 silver badges38 bronze badges
answered 6 hours ago
Rob PrattRob Pratt
9321 silver badge9 bronze badges
answered 6 hours ago
Rob PrattRob Pratt
9321 silver badge9 bronze badges
answered 6 hours ago
Rob PrattRob Pratt
9321 silver badge9 bronze badges
9321 silver badge9 bronze badges
add a comment |
add a comment |
ephemeral is a new contributor. Be nice, and check out our Code of Conduct.
ephemeral is a new contributor. Be nice, and check out our Code of Conduct.
ephemeral is a new contributor. Be nice, and check out our Code of Conduct.
ephemeral is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Operations Research 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%2for.stackexchange.com%2fquestions%2f1300%2fexpressing-a-chain-of-boolean-ors-using-ilp%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
