Mixing
Finding binding constraints of a mixed-integer-program
I want to find constraints which are binding at the optimal solution of an MIP problem, solved by Cplex in c++. By binding, I mean constraint where the value of the LHS is equal to the value of the RHS. For example, if the solution of a problem is:
x = 1, y = 0,
then constraint x + y <= 2 is non-binding (LHS = 1 + 0 < 2 = RHS),
but x - y <= 1 is binding (LHS = 1 - 0 = 1 = RHS).
This could be done for LPs using getSlack or getDual functions of IloRange: If the slack of a constraint is zero, or the dual value is non-zero, the constraint is binding.
I cant find any function of Cplex that gives this property or value for IloRange, IloConstraint, or similar objects, when the problem is an MIP. I would also prefer not to do this manually in c++ (extracting each variable of a constraint and summing their value per constraint). Is there any way to do this?
c++ cplex mixed-integer-programming
asked Dec 31 '18 at 17:26
GunnerGunner
63
add a comment |
I want to find constraints which are binding at the optimal solution of an MIP problem, solved by Cplex in c++. By binding, I mean constraint where the value of the LHS is equal to the value of the RHS. For example, if the solution of a problem is:
x = 1, y = 0,
then constraint x + y <= 2 is non-binding (LHS = 1 + 0 < 2 = RHS),
but x - y <= 1 is binding (LHS = 1 - 0 = 1 = RHS).
This could be done for LPs using getSlack or getDual functions of IloRange: If the slack of a constraint is zero, or the dual value is non-zero, the constraint is binding.
I cant find any function of Cplex that gives this property or value for IloRange, IloConstraint, or similar objects, when the problem is an MIP. I would also prefer not to do this manually in c++ (extracting each variable of a constraint and summing their value per constraint). Is there any way to do this?
c++ cplex mixed-integer-programming
asked Dec 31 '18 at 17:26
GunnerGunner
63
add a comment |
I want to find constraints which are binding at the optimal solution of an MIP problem, solved by Cplex in c++. By binding, I mean constraint where the value of the LHS is equal to the value of the RHS. For example, if the solution of a problem is:
x = 1, y = 0,
then constraint x + y <= 2 is non-binding (LHS = 1 + 0 < 2 = RHS),
but x - y <= 1 is binding (LHS = 1 - 0 = 1 = RHS).
This could be done for LPs using getSlack or getDual functions of IloRange: If the slack of a constraint is zero, or the dual value is non-zero, the constraint is binding.
I cant find any function of Cplex that gives this property or value for IloRange, IloConstraint, or similar objects, when the problem is an MIP. I would also prefer not to do this manually in c++ (extracting each variable of a constraint and summing their value per constraint). Is there any way to do this?
c++ cplex mixed-integer-programming
asked Dec 31 '18 at 17:26
GunnerGunner
63
I want to find constraints which are binding at the optimal solution of an MIP problem, solved by Cplex in c++. By binding, I mean constraint where the value of the LHS is equal to the value of the RHS. For example, if the solution of a problem is:
x = 1, y = 0,
then constraint x + y <= 2 is non-binding (LHS = 1 + 0 < 2 = RHS),
but x - y <= 1 is binding (LHS = 1 - 0 = 1 = RHS).
This could be done for LPs using getSlack or getDual functions of IloRange: If the slack of a constraint is zero, or the dual value is non-zero, the constraint is binding.
I cant find any function of Cplex that gives this property or value for IloRange, IloConstraint, or similar objects, when the problem is an MIP. I would also prefer not to do this manually in c++ (extracting each variable of a constraint and summing their value per constraint). Is there any way to do this?
c++ cplex mixed-integer-programming
c++ cplex mixed-integer-programming
asked Dec 31 '18 at 17:26
GunnerGunner
63
asked Dec 31 '18 at 17:26
GunnerGunner
63
asked Dec 31 '18 at 17:26
GunnerGunner
63
asked Dec 31 '18 at 17:26
GunnerGunner
63
asked Dec 31 '18 at 17:26
GunnerGunner
63
63
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
Even if you have found a way to do this as you described in your own answer, it is worth reading e.g. this page: http://www-01.ibm.com/support/docview.wss?uid=swg21399941
The idea is that you can solve your MIP problem, then change your problem type to a 'fixed' linear problem and re-solve. Since this approach fixes the current solution but solves the problem as an LP, then all the other dual values and reduced costs become available.
Hope that this helps.
answered Jan 1 at 18:40
TimChippingtonDerrickTimChippingtonDerrick
1,3441711
Thank you for the answer, I had actually considered this but wanted to avoid the computational burden of solving an LP. But I believe this is another solution.
– Gunner
Jan 2 at 22:53
I think that the LP solution time etc is negligible in most cases as this approach fixes the solution values at the start of the solution process. But your argument and approach are perfectly valid.
– TimChippingtonDerrick
Jan 3 at 23:15
add a comment |
I found the answer, IloCplex::getValue(IloNumExprArg) actually gives you the value of an expression (similarly constraint LHS) given the current solution. Comparing this value to the RHS constant determines whether or not the constraint is binding.
answered Jan 1 at 1:42
GunnerGunner
63
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
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
},
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%2fstackoverflow.com%2fquestions%2f53989931%2ffinding-binding-constraints-of-a-mixed-integer-program%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
Even if you have found a way to do this as you described in your own answer, it is worth reading e.g. this page: http://www-01.ibm.com/support/docview.wss?uid=swg21399941
The idea is that you can solve your MIP problem, then change your problem type to a 'fixed' linear problem and re-solve. Since this approach fixes the current solution but solves the problem as an LP, then all the other dual values and reduced costs become available.
Hope that this helps.
answered Jan 1 at 18:40
TimChippingtonDerrickTimChippingtonDerrick
1,3441711
Thank you for the answer, I had actually considered this but wanted to avoid the computational burden of solving an LP. But I believe this is another solution.
– Gunner
Jan 2 at 22:53
I think that the LP solution time etc is negligible in most cases as this approach fixes the solution values at the start of the solution process. But your argument and approach are perfectly valid.
– TimChippingtonDerrick
Jan 3 at 23:15
add a comment |
Even if you have found a way to do this as you described in your own answer, it is worth reading e.g. this page: http://www-01.ibm.com/support/docview.wss?uid=swg21399941
The idea is that you can solve your MIP problem, then change your problem type to a 'fixed' linear problem and re-solve. Since this approach fixes the current solution but solves the problem as an LP, then all the other dual values and reduced costs become available.
Hope that this helps.
answered Jan 1 at 18:40
TimChippingtonDerrickTimChippingtonDerrick
1,3441711
Thank you for the answer, I had actually considered this but wanted to avoid the computational burden of solving an LP. But I believe this is another solution.
– Gunner
Jan 2 at 22:53
I think that the LP solution time etc is negligible in most cases as this approach fixes the solution values at the start of the solution process. But your argument and approach are perfectly valid.
– TimChippingtonDerrick
Jan 3 at 23:15
add a comment |
Even if you have found a way to do this as you described in your own answer, it is worth reading e.g. this page: http://www-01.ibm.com/support/docview.wss?uid=swg21399941
The idea is that you can solve your MIP problem, then change your problem type to a 'fixed' linear problem and re-solve. Since this approach fixes the current solution but solves the problem as an LP, then all the other dual values and reduced costs become available.
Hope that this helps.
answered Jan 1 at 18:40
TimChippingtonDerrickTimChippingtonDerrick
1,3441711
Even if you have found a way to do this as you described in your own answer, it is worth reading e.g. this page: http://www-01.ibm.com/support/docview.wss?uid=swg21399941
The idea is that you can solve your MIP problem, then change your problem type to a 'fixed' linear problem and re-solve. Since this approach fixes the current solution but solves the problem as an LP, then all the other dual values and reduced costs become available.
Hope that this helps.
answered Jan 1 at 18:40
TimChippingtonDerrickTimChippingtonDerrick
1,3441711
answered Jan 1 at 18:40
TimChippingtonDerrickTimChippingtonDerrick
1,3441711
answered Jan 1 at 18:40
TimChippingtonDerrickTimChippingtonDerrick
1,3441711
answered Jan 1 at 18:40
TimChippingtonDerrickTimChippingtonDerrick
1,3441711
1,3441711
Thank you for the answer, I had actually considered this but wanted to avoid the computational burden of solving an LP. But I believe this is another solution.
– Gunner
Jan 2 at 22:53
I think that the LP solution time etc is negligible in most cases as this approach fixes the solution values at the start of the solution process. But your argument and approach are perfectly valid.
– TimChippingtonDerrick
Jan 3 at 23:15
add a comment |
Thank you for the answer, I had actually considered this but wanted to avoid the computational burden of solving an LP. But I believe this is another solution.
– Gunner
Jan 2 at 22:53
I think that the LP solution time etc is negligible in most cases as this approach fixes the solution values at the start of the solution process. But your argument and approach are perfectly valid.
– TimChippingtonDerrick
Jan 3 at 23:15
Thank you for the answer, I had actually considered this but wanted to avoid the computational burden of solving an LP. But I believe this is another solution.
– Gunner
Jan 2 at 22:53
Thank you for the answer, I had actually considered this but wanted to avoid the computational burden of solving an LP. But I believe this is another solution.
– Gunner
Jan 2 at 22:53
I think that the LP solution time etc is negligible in most cases as this approach fixes the solution values at the start of the solution process. But your argument and approach are perfectly valid.
– TimChippingtonDerrick
Jan 3 at 23:15
I think that the LP solution time etc is negligible in most cases as this approach fixes the solution values at the start of the solution process. But your argument and approach are perfectly valid.
– TimChippingtonDerrick
Jan 3 at 23:15
add a comment |
I found the answer, IloCplex::getValue(IloNumExprArg) actually gives you the value of an expression (similarly constraint LHS) given the current solution. Comparing this value to the RHS constant determines whether or not the constraint is binding.
answered Jan 1 at 1:42
GunnerGunner
63
add a comment |
I found the answer, IloCplex::getValue(IloNumExprArg) actually gives you the value of an expression (similarly constraint LHS) given the current solution. Comparing this value to the RHS constant determines whether or not the constraint is binding.
answered Jan 1 at 1:42
GunnerGunner
63
add a comment |
I found the answer, IloCplex::getValue(IloNumExprArg) actually gives you the value of an expression (similarly constraint LHS) given the current solution. Comparing this value to the RHS constant determines whether or not the constraint is binding.
answered Jan 1 at 1:42
GunnerGunner
63
I found the answer, IloCplex::getValue(IloNumExprArg) actually gives you the value of an expression (similarly constraint LHS) given the current solution. Comparing this value to the RHS constant determines whether or not the constraint is binding.
answered Jan 1 at 1:42
GunnerGunner
63
edited Jan 2 at 22:56
answered Jan 1 at 1:42
GunnerGunner
63
answered Jan 1 at 1:42
GunnerGunner
63
answered Jan 1 at 1:42
GunnerGunner
63
63
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- 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.
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%2fstackoverflow.com%2fquestions%2f53989931%2ffinding-binding-constraints-of-a-mixed-integer-program%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
