Finding binding constraints of a mixed-integer-program

Question

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?

TimChippingtonDerrick · Accepted Answer · 2019-01-01 18:40:50Z

1

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, 2019 at 18:40

TimChippingtonDerrick

2,0921 gold badge12 silver badges13 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Gunner Over a year ago

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.

TimChippingtonDerrick Over a year ago

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.

Gunner · Accepted Answer · 2019-01-02 22:56:19Z

0

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.

edited Jan 2, 2019 at 22:56

answered Jan 1, 2019 at 1:42

Gunner

113 bronze badges

Collectives™ on Stack Overflow

Finding binding constraints of a mixed-integer-program

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related