Representing an indicator function: binary variables and “indicator constraints”When to use indicator constraints versus big-M approaches in solving (mixed-)integer programsDoes dispersion really matter?How to formulate this scheduling problem efficiently?How to reformulate (linearize/convexify) a budgeted assignment problem?Soft constraints and hard constraintsDifference between Chance constraints and logical constraintsThe rationale to improve MTZ?Static stochastic knapsack problem: unbounded versionFormulating a MINLP for CPLEX in PYOMOIs there a way to proportionalize fixed costs in a MILP?
What if a restaurant suddenly cannot accept credit cards, and the customer has no cash?
Why don't modern jet engines use forced exhaust mixing?
Can anybody tell me who this Pokemon is?
Have there ever been other TV shows or Films that told a similiar story to the new 90210 show?
Why do so many people play out of turn on the last lead?
If it isn't [someone's name]!
Why is su world executable?
Why does this image of cyclocarbon look like a nonagon?
How to train a replacement without them knowing?
Quick destruction of a helium filled airship?
Icon is not displayed in lwc
Eric Andre had a dream
Which manga depicts Doraemon and Nobita on Easter Island?
Why are certain quantities so fundamental to physics
Is it alright to say good afternoon Sirs and Madams in a panel interview?
Do I need to start off my book by describing the character's "normal world"?
Reducing contention in thread-safe LruCache
Build a mob of suspiciously happy lenny faces ( ͡° ͜ʖ ͡°)
A+ rating still unsecure by Google Chrome's opinion
When and which board game was the first to be ever invented?
What allows us to use imaginary numbers?
What should I do with the stock I own if I anticipate there will be a recession?
Vegetarian dishes on Russian trains (European part)
Designing a prison for a telekinetic race
Representing an indicator function: binary variables and “indicator constraints”
When to use indicator constraints versus big-M approaches in solving (mixed-)integer programsDoes dispersion really matter?How to formulate this scheduling problem efficiently?How to reformulate (linearize/convexify) a budgeted assignment problem?Soft constraints and hard constraintsDifference between Chance constraints and logical constraintsThe rationale to improve MTZ?Static stochastic knapsack problem: unbounded versionFormulating a MINLP for CPLEX in PYOMOIs there a way to proportionalize fixed costs in a MILP?
$begingroup$
I want to represent the indicator function:
$$ mathbb1_(y=j)$$
where $y$ is a non negative, integer variable.
My attempt is as follows: define a binary variable:
$$ z_j =begincases
1 qquadtextif $y=j$ \
0 qquadtextotherwise
endcases $$
the model of the indicator function would be:
$$
sum_j=0^n z_j = 1
$$
$$
sum_j=0^n j cdot z_j = y
$$
where $n$ is an upper bound for $y$.
Actually, this can be conveniently modeled in OPL Cplex (for example) using indicator constraints such as follows:
forall(j in 0..n)
(y == j) == (z[j] == 1);
QUESTIONS:
- is my binary-variables-based formulation attempt correct? Do you know better (performance wise) formulations?
- in a hypothetical academic journal paper, is the second formulation (based on indicator constraints) acceptable? If yes, how would you formally express it in the paper in a way that is implementation-independent (that is, in a way that does not depend upon how a specific solver models such a constraint)? Or it is better to provide the more general, binary-variables-based formulation?
Thanks a lot.
modeling cplex academic binary-variable indicator-constraints
asked 9 hours ago
LibraLibra
3061 silver badge8 bronze badges
$endgroup$
add a comment |
$begingroup$
I want to represent the indicator function:
$$ mathbb1_(y=j)$$
where $y$ is a non negative, integer variable.
My attempt is as follows: define a binary variable:
$$ z_j =begincases
1 qquadtextif $y=j$ \
0 qquadtextotherwise
endcases $$
the model of the indicator function would be:
$$
sum_j=0^n z_j = 1
$$
$$
sum_j=0^n j cdot z_j = y
$$
where $n$ is an upper bound for $y$.
Actually, this can be conveniently modeled in OPL Cplex (for example) using indicator constraints such as follows:
forall(j in 0..n)
(y == j) == (z[j] == 1);
QUESTIONS:
- is my binary-variables-based formulation attempt correct? Do you know better (performance wise) formulations?
- in a hypothetical academic journal paper, is the second formulation (based on indicator constraints) acceptable? If yes, how would you formally express it in the paper in a way that is implementation-independent (that is, in a way that does not depend upon how a specific solver models such a constraint)? Or it is better to provide the more general, binary-variables-based formulation?
Thanks a lot.
modeling cplex academic binary-variable indicator-constraints
asked 9 hours ago
LibraLibra
3061 silver badge8 bronze badges
$endgroup$
$begingroup$
This is correct, assuming $y in 0,dots,n$. More generally, if $y$ takes (not necessarily integer) values in a finite set $V$, impose $sum_j in V z_j=1$ and $sum_j in V j z_j=y$.
$endgroup$
– Rob Pratt
8 hours ago
1
$begingroup$
Something else to consider is to do a binary expansion of $y$, i.e., add the constraint $sum_j=0^m 2^j z_j=y$, where $2^m$ is an upper bound on $y$. Depending on the application you have in mind you might not be able to use this representation, but if you can I would imagine it's more efficient.
$endgroup$
– Ryan Cory-Wright
7 hours ago
$begingroup$
Note that you will need to linearize a product of binary variables to recover the indicator function for a fixed $j$. This can be achieved via $y <= z_i, forall i, y>=sum_i z_i - (n-1)$.
$endgroup$
– Ryan Cory-Wright
7 hours ago
add a comment |
$begingroup$
I want to represent the indicator function:
$$ mathbb1_(y=j)$$
where $y$ is a non negative, integer variable.
My attempt is as follows: define a binary variable:
$$ z_j =begincases
1 qquadtextif $y=j$ \
0 qquadtextotherwise
endcases $$
the model of the indicator function would be:
$$
sum_j=0^n z_j = 1
$$
$$
sum_j=0^n j cdot z_j = y
$$
where $n$ is an upper bound for $y$.
Actually, this can be conveniently modeled in OPL Cplex (for example) using indicator constraints such as follows:
forall(j in 0..n)
(y == j) == (z[j] == 1);
QUESTIONS:
- is my binary-variables-based formulation attempt correct? Do you know better (performance wise) formulations?
- in a hypothetical academic journal paper, is the second formulation (based on indicator constraints) acceptable? If yes, how would you formally express it in the paper in a way that is implementation-independent (that is, in a way that does not depend upon how a specific solver models such a constraint)? Or it is better to provide the more general, binary-variables-based formulation?
Thanks a lot.
modeling cplex academic binary-variable indicator-constraints
asked 9 hours ago
LibraLibra
3061 silver badge8 bronze badges
$endgroup$
I want to represent the indicator function:
$$ mathbb1_(y=j)$$
where $y$ is a non negative, integer variable.
My attempt is as follows: define a binary variable:
$$ z_j =begincases
1 qquadtextif $y=j$ \
0 qquadtextotherwise
endcases $$
the model of the indicator function would be:
$$
sum_j=0^n z_j = 1
$$
$$
sum_j=0^n j cdot z_j = y
$$
where $n$ is an upper bound for $y$.
Actually, this can be conveniently modeled in OPL Cplex (for example) using indicator constraints such as follows:
forall(j in 0..n)
(y == j) == (z[j] == 1);
QUESTIONS:
- is my binary-variables-based formulation attempt correct? Do you know better (performance wise) formulations?
- in a hypothetical academic journal paper, is the second formulation (based on indicator constraints) acceptable? If yes, how would you formally express it in the paper in a way that is implementation-independent (that is, in a way that does not depend upon how a specific solver models such a constraint)? Or it is better to provide the more general, binary-variables-based formulation?
Thanks a lot.
modeling cplex academic binary-variable indicator-constraints
modeling cplex academic binary-variable indicator-constraints
asked 9 hours ago
LibraLibra
3061 silver badge8 bronze badges
asked 9 hours ago
LibraLibra
3061 silver badge8 bronze badges
asked 9 hours ago
LibraLibra
3061 silver badge8 bronze badges
asked 9 hours ago
LibraLibra
3061 silver badge8 bronze badges
asked 9 hours ago
LibraLibra
3061 silver badge8 bronze badges
3061 silver badge8 bronze badges
$begingroup$
This is correct, assuming $y in 0,dots,n$. More generally, if $y$ takes (not necessarily integer) values in a finite set $V$, impose $sum_j in V z_j=1$ and $sum_j in V j z_j=y$.
$endgroup$
– Rob Pratt
8 hours ago
1
$begingroup$
Something else to consider is to do a binary expansion of $y$, i.e., add the constraint $sum_j=0^m 2^j z_j=y$, where $2^m$ is an upper bound on $y$. Depending on the application you have in mind you might not be able to use this representation, but if you can I would imagine it's more efficient.
$endgroup$
– Ryan Cory-Wright
7 hours ago
$begingroup$
Note that you will need to linearize a product of binary variables to recover the indicator function for a fixed $j$. This can be achieved via $y <= z_i, forall i, y>=sum_i z_i - (n-1)$.
$endgroup$
– Ryan Cory-Wright
7 hours ago
add a comment |
$begingroup$
This is correct, assuming $y in 0,dots,n$. More generally, if $y$ takes (not necessarily integer) values in a finite set $V$, impose $sum_j in V z_j=1$ and $sum_j in V j z_j=y$.
$endgroup$
– Rob Pratt
8 hours ago
1
$begingroup$
Something else to consider is to do a binary expansion of $y$, i.e., add the constraint $sum_j=0^m 2^j z_j=y$, where $2^m$ is an upper bound on $y$. Depending on the application you have in mind you might not be able to use this representation, but if you can I would imagine it's more efficient.
$endgroup$
– Ryan Cory-Wright
7 hours ago
$begingroup$
Note that you will need to linearize a product of binary variables to recover the indicator function for a fixed $j$. This can be achieved via $y <= z_i, forall i, y>=sum_i z_i - (n-1)$.
$endgroup$
– Ryan Cory-Wright
7 hours ago
$begingroup$
This is correct, assuming $y in 0,dots,n$. More generally, if $y$ takes (not necessarily integer) values in a finite set $V$, impose $sum_j in V z_j=1$ and $sum_j in V j z_j=y$.
$endgroup$
– Rob Pratt
8 hours ago
$begingroup$
This is correct, assuming $y in 0,dots,n$. More generally, if $y$ takes (not necessarily integer) values in a finite set $V$, impose $sum_j in V z_j=1$ and $sum_j in V j z_j=y$.
$endgroup$
– Rob Pratt
8 hours ago
1
1
$begingroup$
Something else to consider is to do a binary expansion of $y$, i.e., add the constraint $sum_j=0^m 2^j z_j=y$, where $2^m$ is an upper bound on $y$. Depending on the application you have in mind you might not be able to use this representation, but if you can I would imagine it's more efficient.
$endgroup$
– Ryan Cory-Wright
7 hours ago
$begingroup$
Something else to consider is to do a binary expansion of $y$, i.e., add the constraint $sum_j=0^m 2^j z_j=y$, where $2^m$ is an upper bound on $y$. Depending on the application you have in mind you might not be able to use this representation, but if you can I would imagine it's more efficient.
$endgroup$
– Ryan Cory-Wright
7 hours ago
$begingroup$
Note that you will need to linearize a product of binary variables to recover the indicator function for a fixed $j$. This can be achieved via $y <= z_i, forall i, y>=sum_i z_i - (n-1)$.
$endgroup$
– Ryan Cory-Wright
7 hours ago
$begingroup$
Note that you will need to linearize a product of binary variables to recover the indicator function for a fixed $j$. This can be achieved via $y <= z_i, forall i, y>=sum_i z_i - (n-1)$.
$endgroup$
– Ryan Cory-Wright
7 hours ago
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
First question: Yes, your algebraic formulation is correct.
Second question: I would lean toward using the algebraic formulation, for two reasons. First, it is not solver-specific. Second, a reader not familiar with indicator constraints will find interpreting the algebraic formulation a bit easier, while a reader familiar with indicators is not likely to find the algebraic formulation much harder. That said, it would not hurt to mention in the paper that the constraint can be implemented by indicators in a solver that supports them (or, if your computational results were produced using CPLEX and you used indicators, just say that in the section describing the experiments).
answered 8 hours ago
prubinprubin
3,2615 silver badges24 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
);
);
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%2f1316%2frepresenting-an-indicator-function-binary-variables-and-indicator-constraints%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
First question: Yes, your algebraic formulation is correct.
Second question: I would lean toward using the algebraic formulation, for two reasons. First, it is not solver-specific. Second, a reader not familiar with indicator constraints will find interpreting the algebraic formulation a bit easier, while a reader familiar with indicators is not likely to find the algebraic formulation much harder. That said, it would not hurt to mention in the paper that the constraint can be implemented by indicators in a solver that supports them (or, if your computational results were produced using CPLEX and you used indicators, just say that in the section describing the experiments).
answered 8 hours ago
prubinprubin
3,2615 silver badges24 bronze badges
$endgroup$
add a comment |
$begingroup$
First question: Yes, your algebraic formulation is correct.
Second question: I would lean toward using the algebraic formulation, for two reasons. First, it is not solver-specific. Second, a reader not familiar with indicator constraints will find interpreting the algebraic formulation a bit easier, while a reader familiar with indicators is not likely to find the algebraic formulation much harder. That said, it would not hurt to mention in the paper that the constraint can be implemented by indicators in a solver that supports them (or, if your computational results were produced using CPLEX and you used indicators, just say that in the section describing the experiments).
answered 8 hours ago
prubinprubin
3,2615 silver badges24 bronze badges
$endgroup$
add a comment |
$begingroup$
First question: Yes, your algebraic formulation is correct.
Second question: I would lean toward using the algebraic formulation, for two reasons. First, it is not solver-specific. Second, a reader not familiar with indicator constraints will find interpreting the algebraic formulation a bit easier, while a reader familiar with indicators is not likely to find the algebraic formulation much harder. That said, it would not hurt to mention in the paper that the constraint can be implemented by indicators in a solver that supports them (or, if your computational results were produced using CPLEX and you used indicators, just say that in the section describing the experiments).
answered 8 hours ago
prubinprubin
3,2615 silver badges24 bronze badges
$endgroup$
First question: Yes, your algebraic formulation is correct.
Second question: I would lean toward using the algebraic formulation, for two reasons. First, it is not solver-specific. Second, a reader not familiar with indicator constraints will find interpreting the algebraic formulation a bit easier, while a reader familiar with indicators is not likely to find the algebraic formulation much harder. That said, it would not hurt to mention in the paper that the constraint can be implemented by indicators in a solver that supports them (or, if your computational results were produced using CPLEX and you used indicators, just say that in the section describing the experiments).
answered 8 hours ago
prubinprubin
3,2615 silver badges24 bronze badges
answered 8 hours ago
prubinprubin
3,2615 silver badges24 bronze badges
answered 8 hours ago
prubinprubin
3,2615 silver badges24 bronze badges
answered 8 hours ago
prubinprubin
3,2615 silver badges24 bronze badges
3,2615 silver badges24 bronze badges
add a comment |
add a comment |
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%2f1316%2frepresenting-an-indicator-function-binary-variables-and-indicator-constraints%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
$begingroup$
This is correct, assuming $y in 0,dots,n$. More generally, if $y$ takes (not necessarily integer) values in a finite set $V$, impose $sum_j in V z_j=1$ and $sum_j in V j z_j=y$.
$endgroup$
– Rob Pratt
8 hours ago
1
$begingroup$
Something else to consider is to do a binary expansion of $y$, i.e., add the constraint $sum_j=0^m 2^j z_j=y$, where $2^m$ is an upper bound on $y$. Depending on the application you have in mind you might not be able to use this representation, but if you can I would imagine it's more efficient.
$endgroup$
– Ryan Cory-Wright
7 hours ago
$begingroup$
Note that you will need to linearize a product of binary variables to recover the indicator function for a fixed $j$. This can be achieved via $y <= z_i, forall i, y>=sum_i z_i - (n-1)$.
$endgroup$
– Ryan Cory-Wright
7 hours ago