Mixing
how to express big-M formulation as an indicator constraint
$begingroup$
I want to solve the following LP using CPLEX. In the CPLEX documentation it is suggested to use indicator constraint instead of big-M formulation. I searched on google the term "indicator constraints" but except some research papers I could not find much information on this type of constraints.
I would appreciate it if someone could guide me on how to convert the big-M equation into an indicator constraint.
Problem Formulation
$$ min sum_{(i,j) in E} sum_{f in F} c_{ij}^fx^f_{ij}$$
$$ sum_{j in V}x^f_{ij} - sum_{j in V}x_{ji}^f = begin{cases}
d_f &, & i = s_f \
-d_f&, & i = t_f\
0 &,& text{otherwise}
end{cases} $$
$$ sum_{i,j in E} x_{ij}^f le u_{ij}$$
$$ sum_{i,j in E} w_{i,j}y_{ij}^f le W^f$$
$$0 le x^f_{i,j} le My^f_{i,j}, ,, y^f_{i,j} in {0, 1} quad forall (i,j) in E, f in F$$
This is a modified multicommodity flow problem that for a flow $f$ the sum of all the weights $w_{ij}$ of the edges for which $x^f_{i,j} gt 0$ should be less than $W^f$.
Solution 1
$$ min sum_{(i,j) in E} sum_{f in F} c_{ij}^fx^f_{ij}$$
$$ sum_{j in V}x^f_{ij} - sum_{j in V}x_{ji}^f = begin{cases}
d_f &, & i = s_f \
-d_f&, & i = t_f\
0 &,& text{otherwise}
end{cases} $$
$$ sum_{i,j in E} x_{ij}^f le u_{ij}$$
$$ sum_{i,j in E} w_{i,j}y_{ij}^f le W^f$$
$$ y_{i,j}^f = 0 Rightarrow x_{i,j}^f = 0 quad forall (i,j) in E, f in F$$
$$ x^f_{i,j} ge 0, ,, y^f_{i,j} in {0, 1} quad forall (i,j) in E, f in F$$
linear-programming
asked Jan 21 at 10:42
CoreyCorey
103
$endgroup$
add a comment |
$begingroup$
I want to solve the following LP using CPLEX. In the CPLEX documentation it is suggested to use indicator constraint instead of big-M formulation. I searched on google the term "indicator constraints" but except some research papers I could not find much information on this type of constraints.
I would appreciate it if someone could guide me on how to convert the big-M equation into an indicator constraint.
Problem Formulation
$$ min sum_{(i,j) in E} sum_{f in F} c_{ij}^fx^f_{ij}$$
$$ sum_{j in V}x^f_{ij} - sum_{j in V}x_{ji}^f = begin{cases}
d_f &, & i = s_f \
-d_f&, & i = t_f\
0 &,& text{otherwise}
end{cases} $$
$$ sum_{i,j in E} x_{ij}^f le u_{ij}$$
$$ sum_{i,j in E} w_{i,j}y_{ij}^f le W^f$$
$$0 le x^f_{i,j} le My^f_{i,j}, ,, y^f_{i,j} in {0, 1} quad forall (i,j) in E, f in F$$
This is a modified multicommodity flow problem that for a flow $f$ the sum of all the weights $w_{ij}$ of the edges for which $x^f_{i,j} gt 0$ should be less than $W^f$.
Solution 1
$$ min sum_{(i,j) in E} sum_{f in F} c_{ij}^fx^f_{ij}$$
$$ sum_{j in V}x^f_{ij} - sum_{j in V}x_{ji}^f = begin{cases}
d_f &, & i = s_f \
-d_f&, & i = t_f\
0 &,& text{otherwise}
end{cases} $$
$$ sum_{i,j in E} x_{ij}^f le u_{ij}$$
$$ sum_{i,j in E} w_{i,j}y_{ij}^f le W^f$$
$$ y_{i,j}^f = 0 Rightarrow x_{i,j}^f = 0 quad forall (i,j) in E, f in F$$
$$ x^f_{i,j} ge 0, ,, y^f_{i,j} in {0, 1} quad forall (i,j) in E, f in F$$
linear-programming
asked Jan 21 at 10:42
CoreyCorey
103
$endgroup$
add a comment |
$begingroup$
I want to solve the following LP using CPLEX. In the CPLEX documentation it is suggested to use indicator constraint instead of big-M formulation. I searched on google the term "indicator constraints" but except some research papers I could not find much information on this type of constraints.
I would appreciate it if someone could guide me on how to convert the big-M equation into an indicator constraint.
Problem Formulation
$$ min sum_{(i,j) in E} sum_{f in F} c_{ij}^fx^f_{ij}$$
$$ sum_{j in V}x^f_{ij} - sum_{j in V}x_{ji}^f = begin{cases}
d_f &, & i = s_f \
-d_f&, & i = t_f\
0 &,& text{otherwise}
end{cases} $$
$$ sum_{i,j in E} x_{ij}^f le u_{ij}$$
$$ sum_{i,j in E} w_{i,j}y_{ij}^f le W^f$$
$$0 le x^f_{i,j} le My^f_{i,j}, ,, y^f_{i,j} in {0, 1} quad forall (i,j) in E, f in F$$
This is a modified multicommodity flow problem that for a flow $f$ the sum of all the weights $w_{ij}$ of the edges for which $x^f_{i,j} gt 0$ should be less than $W^f$.
Solution 1
$$ min sum_{(i,j) in E} sum_{f in F} c_{ij}^fx^f_{ij}$$
$$ sum_{j in V}x^f_{ij} - sum_{j in V}x_{ji}^f = begin{cases}
d_f &, & i = s_f \
-d_f&, & i = t_f\
0 &,& text{otherwise}
end{cases} $$
$$ sum_{i,j in E} x_{ij}^f le u_{ij}$$
$$ sum_{i,j in E} w_{i,j}y_{ij}^f le W^f$$
$$ y_{i,j}^f = 0 Rightarrow x_{i,j}^f = 0 quad forall (i,j) in E, f in F$$
$$ x^f_{i,j} ge 0, ,, y^f_{i,j} in {0, 1} quad forall (i,j) in E, f in F$$
linear-programming
asked Jan 21 at 10:42
CoreyCorey
103
$endgroup$
I want to solve the following LP using CPLEX. In the CPLEX documentation it is suggested to use indicator constraint instead of big-M formulation. I searched on google the term "indicator constraints" but except some research papers I could not find much information on this type of constraints.
I would appreciate it if someone could guide me on how to convert the big-M equation into an indicator constraint.
Problem Formulation
$$ min sum_{(i,j) in E} sum_{f in F} c_{ij}^fx^f_{ij}$$
$$ sum_{j in V}x^f_{ij} - sum_{j in V}x_{ji}^f = begin{cases}
d_f &, & i = s_f \
-d_f&, & i = t_f\
0 &,& text{otherwise}
end{cases} $$
$$ sum_{i,j in E} x_{ij}^f le u_{ij}$$
$$ sum_{i,j in E} w_{i,j}y_{ij}^f le W^f$$
$$0 le x^f_{i,j} le My^f_{i,j}, ,, y^f_{i,j} in {0, 1} quad forall (i,j) in E, f in F$$
This is a modified multicommodity flow problem that for a flow $f$ the sum of all the weights $w_{ij}$ of the edges for which $x^f_{i,j} gt 0$ should be less than $W^f$.
Solution 1
$$ min sum_{(i,j) in E} sum_{f in F} c_{ij}^fx^f_{ij}$$
$$ sum_{j in V}x^f_{ij} - sum_{j in V}x_{ji}^f = begin{cases}
d_f &, & i = s_f \
-d_f&, & i = t_f\
0 &,& text{otherwise}
end{cases} $$
$$ sum_{i,j in E} x_{ij}^f le u_{ij}$$
$$ sum_{i,j in E} w_{i,j}y_{ij}^f le W^f$$
$$ y_{i,j}^f = 0 Rightarrow x_{i,j}^f = 0 quad forall (i,j) in E, f in F$$
$$ x^f_{i,j} ge 0, ,, y^f_{i,j} in {0, 1} quad forall (i,j) in E, f in F$$
linear-programming
linear-programming
asked Jan 21 at 10:42
CoreyCorey
103
asked Jan 21 at 10:42
CoreyCorey
103
edited Jan 22 at 18:42
Corey
asked Jan 21 at 10:42
CoreyCorey
103
asked Jan 21 at 10:42
CoreyCorey
103
asked Jan 21 at 10:42
CoreyCorey
103
103
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The indicator constraint is
$$y_{i,j}^f = 0 Rightarrow x_{i,j}^f = 0 quad forall (i,j) in E, f in F$$
answered Jan 21 at 22:46
LinAlgLinAlg
10k1521
$endgroup$
$begingroup$
Thank you LinAlg. Would you please guide me on how to add this indicator constraint into my formulation. I have modified my formulation in my question, is this correct?
$endgroup$
– Corey
Jan 22 at 5:34
$begingroup$
@Corey yes, but you should write either $Rightarrow$ or "if .. then". Use text in latex for text.
$endgroup$
– LinAlg
Jan 22 at 12:53
$begingroup$
I removed the "if". LinAlg would you please explain this indicator constraint for me. Since we are saying that if $y^f_{ij}$ is zero then $x^f_{ij}$ should also be zero. I have a bit of doubt on how the solvers know that whether $y^f_{ij}$ is zero or one; as no where in the formulation we are changing the value of $y$
$endgroup$
– Corey
Jan 22 at 18:54
$begingroup$
The solver will optimize $y$ just as in your original formulation. The formulations are equivalent.
$endgroup$
– LinAlg
Jan 22 at 19:04
$begingroup$
Just one more question, there is no need to add $y$ to the objective function?
$endgroup$
– Corey
Jan 22 at 19:10
|
show 1 more 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
});
}
});
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%2f3081727%2fhow-to-express-big-m-formulation-as-an-indicator-constraint%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$
The indicator constraint is
$$y_{i,j}^f = 0 Rightarrow x_{i,j}^f = 0 quad forall (i,j) in E, f in F$$
answered Jan 21 at 22:46
LinAlgLinAlg
10k1521
$endgroup$
$begingroup$
Thank you LinAlg. Would you please guide me on how to add this indicator constraint into my formulation. I have modified my formulation in my question, is this correct?
$endgroup$
– Corey
Jan 22 at 5:34
$begingroup$
@Corey yes, but you should write either $Rightarrow$ or "if .. then". Use text in latex for text.
$endgroup$
– LinAlg
Jan 22 at 12:53
$begingroup$
I removed the "if". LinAlg would you please explain this indicator constraint for me. Since we are saying that if $y^f_{ij}$ is zero then $x^f_{ij}$ should also be zero. I have a bit of doubt on how the solvers know that whether $y^f_{ij}$ is zero or one; as no where in the formulation we are changing the value of $y$
$endgroup$
– Corey
Jan 22 at 18:54
$begingroup$
The solver will optimize $y$ just as in your original formulation. The formulations are equivalent.
$endgroup$
– LinAlg
Jan 22 at 19:04
$begingroup$
Just one more question, there is no need to add $y$ to the objective function?
$endgroup$
– Corey
Jan 22 at 19:10
|
show 1 more comment
$begingroup$
The indicator constraint is
$$y_{i,j}^f = 0 Rightarrow x_{i,j}^f = 0 quad forall (i,j) in E, f in F$$
answered Jan 21 at 22:46
LinAlgLinAlg
10k1521
$endgroup$
$begingroup$
Thank you LinAlg. Would you please guide me on how to add this indicator constraint into my formulation. I have modified my formulation in my question, is this correct?
$endgroup$
– Corey
Jan 22 at 5:34
$begingroup$
@Corey yes, but you should write either $Rightarrow$ or "if .. then". Use text in latex for text.
$endgroup$
– LinAlg
Jan 22 at 12:53
$begingroup$
I removed the "if". LinAlg would you please explain this indicator constraint for me. Since we are saying that if $y^f_{ij}$ is zero then $x^f_{ij}$ should also be zero. I have a bit of doubt on how the solvers know that whether $y^f_{ij}$ is zero or one; as no where in the formulation we are changing the value of $y$
$endgroup$
– Corey
Jan 22 at 18:54
$begingroup$
The solver will optimize $y$ just as in your original formulation. The formulations are equivalent.
$endgroup$
– LinAlg
Jan 22 at 19:04
$begingroup$
Just one more question, there is no need to add $y$ to the objective function?
$endgroup$
– Corey
Jan 22 at 19:10
|
show 1 more comment
$begingroup$
The indicator constraint is
$$y_{i,j}^f = 0 Rightarrow x_{i,j}^f = 0 quad forall (i,j) in E, f in F$$
answered Jan 21 at 22:46
LinAlgLinAlg
10k1521
$endgroup$
The indicator constraint is
$$y_{i,j}^f = 0 Rightarrow x_{i,j}^f = 0 quad forall (i,j) in E, f in F$$
answered Jan 21 at 22:46
LinAlgLinAlg
10k1521
answered Jan 21 at 22:46
LinAlgLinAlg
10k1521
answered Jan 21 at 22:46
LinAlgLinAlg
10k1521
answered Jan 21 at 22:46
LinAlgLinAlg
10k1521
10k1521
$begingroup$
Thank you LinAlg. Would you please guide me on how to add this indicator constraint into my formulation. I have modified my formulation in my question, is this correct?
$endgroup$
– Corey
Jan 22 at 5:34
$begingroup$
@Corey yes, but you should write either $Rightarrow$ or "if .. then". Use text in latex for text.
$endgroup$
– LinAlg
Jan 22 at 12:53
$begingroup$
I removed the "if". LinAlg would you please explain this indicator constraint for me. Since we are saying that if $y^f_{ij}$ is zero then $x^f_{ij}$ should also be zero. I have a bit of doubt on how the solvers know that whether $y^f_{ij}$ is zero or one; as no where in the formulation we are changing the value of $y$
$endgroup$
– Corey
Jan 22 at 18:54
$begingroup$
The solver will optimize $y$ just as in your original formulation. The formulations are equivalent.
$endgroup$
– LinAlg
Jan 22 at 19:04
$begingroup$
Just one more question, there is no need to add $y$ to the objective function?
$endgroup$
– Corey
Jan 22 at 19:10
|
show 1 more comment
$begingroup$
Thank you LinAlg. Would you please guide me on how to add this indicator constraint into my formulation. I have modified my formulation in my question, is this correct?
$endgroup$
– Corey
Jan 22 at 5:34
$begingroup$
@Corey yes, but you should write either $Rightarrow$ or "if .. then". Use text in latex for text.
$endgroup$
– LinAlg
Jan 22 at 12:53
$begingroup$
I removed the "if". LinAlg would you please explain this indicator constraint for me. Since we are saying that if $y^f_{ij}$ is zero then $x^f_{ij}$ should also be zero. I have a bit of doubt on how the solvers know that whether $y^f_{ij}$ is zero or one; as no where in the formulation we are changing the value of $y$
$endgroup$
– Corey
Jan 22 at 18:54
$begingroup$
The solver will optimize $y$ just as in your original formulation. The formulations are equivalent.
$endgroup$
– LinAlg
Jan 22 at 19:04
$begingroup$
Just one more question, there is no need to add $y$ to the objective function?
$endgroup$
– Corey
Jan 22 at 19:10
$begingroup$
Thank you LinAlg. Would you please guide me on how to add this indicator constraint into my formulation. I have modified my formulation in my question, is this correct?
$endgroup$
– Corey
Jan 22 at 5:34
$begingroup$
Thank you LinAlg. Would you please guide me on how to add this indicator constraint into my formulation. I have modified my formulation in my question, is this correct?
$endgroup$
– Corey
Jan 22 at 5:34
$begingroup$
@Corey yes, but you should write either $Rightarrow$ or "if .. then". Use text in latex for text.
$endgroup$
– LinAlg
Jan 22 at 12:53
$begingroup$
@Corey yes, but you should write either $Rightarrow$ or "if .. then". Use text in latex for text.
$endgroup$
– LinAlg
Jan 22 at 12:53
$begingroup$
I removed the "if". LinAlg would you please explain this indicator constraint for me. Since we are saying that if $y^f_{ij}$ is zero then $x^f_{ij}$ should also be zero. I have a bit of doubt on how the solvers know that whether $y^f_{ij}$ is zero or one; as no where in the formulation we are changing the value of $y$
$endgroup$
– Corey
Jan 22 at 18:54
$begingroup$
I removed the "if". LinAlg would you please explain this indicator constraint for me. Since we are saying that if $y^f_{ij}$ is zero then $x^f_{ij}$ should also be zero. I have a bit of doubt on how the solvers know that whether $y^f_{ij}$ is zero or one; as no where in the formulation we are changing the value of $y$
$endgroup$
– Corey
Jan 22 at 18:54
$begingroup$
The solver will optimize $y$ just as in your original formulation. The formulations are equivalent.
$endgroup$
– LinAlg
Jan 22 at 19:04
$begingroup$
The solver will optimize $y$ just as in your original formulation. The formulations are equivalent.
$endgroup$
– LinAlg
Jan 22 at 19:04
$begingroup$
Just one more question, there is no need to add $y$ to the objective function?
$endgroup$
– Corey
Jan 22 at 19:10
$begingroup$
Just one more question, there is no need to add $y$ to the objective function?
$endgroup$
– Corey
Jan 22 at 19:10
|
show 1 more comment
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%2f3081727%2fhow-to-express-big-m-formulation-as-an-indicator-constraint%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
