Originally posted by: Eumpfenbach

I am trying to solve an MIP that has a strong affinity for implied bound cuts. Cplex reports finding 17,000 of them along with 6 cover cuts during the solution. I wanted a little more information about these cuts and couldn't find a lot on the web.

The "implied bound" comes from a variable being binary, so is cplex essentially temporarily fixing a variable to zero or one, moving the constant to the RHS, and then trying to find tighter bounds on the continuous variables? How are implied bound cuts different from presolve routines to strengthen bounds?

Any information about this cut algorithm would be appreciated. The general description in the cplex manual doesn't give enough to really know what these cuts are doing. Thanks.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Implied bound cuts are the most simple cuts of all. If you have an implication

x = 0 -> y <= b
x binary
0 <= y <= u

then a valid inequality is

y + (u-b)x <= u

which is called an "implied bound cut". Of course, similar cuts can be derived for other implications (for x=1, or for y >= b).

The only remaining question is how to identify valid implications. The most important steps to do this are direct inspection of the individual constraints of the model and probing. For example, if you have a constraint

1000x + y1 - 10y2 <= 1500
x binary
0 <= y1 <= 1500
0 <= y2 <= 10

then you can immediately derive the implication

x = 1 -> y1 <= 600

Probing means to tentatively fix a binary variable to 0 and 1 and then propagate this fixing through the constraints. If this propagation leads to a tighter bound on a non-binary variable you have found an implication.

You can find more detailed information on probing and implied bound cuts in the literature, for example in my thesis http://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/1112 Chapters 8.6 and 10.6, and the references therein.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Eumpfenbach

I am trying to find more information about where these implied bound cuts are coming from. I am trying to avoid getting the actual cuts generates unless absolutely necessary (C and C++ coding is outside of my comfort zone. I like Matlab).

My plan was to generate every implied bound cut I possibly could, even if they are redundant. Then I would solve, and look to see which ones were binding. I ran my script to add all these cuts to the model, but after doing so, it became infeasible. Clearly I am generating invalid cuts. Here is my script. Can anyone tell me where the error is?

yidx is an indicator for the binary variables. Everything else is defined in the loops from a cplex object.

yidx = [

false(18144,1);

true(24,1);

false(36882,1);

true(64,1);

false(6,1);

true(198,1)]; temp = find(yidx); 

for i=1:1:size(temp,1) i 

for j = 1:1:size(cplex.Model.A,1) 

if cplex.Model.A(j,temp(i)) ~= 0 temp_row = cplex.Model.A(j,:); temp2 = find(temp_row ~= 0); temp3 = find(temp2 == temp(i)); temp2(temp3) = []; bin_coefficient = temp_row(1,temp(i)); 

for k = 1:1:size(temp2,1) var = [j,temp2(k)]; b = cplex.Model.rhs(j,1) - bin_coefficient; u = cplex.Model.rhs(j,1); new_row = sparse(1,size(cplex.Model.A,2)); new_row(1,temp2(k)) = 1; new_row(1,temp(i)) = (u-b); cplex.Model.rhs = [cplex.Model.rhs;u]; cplex.Model.lhs = [cplex.Model.lhs;-Inf]; cplex.Model.A = [cplex.Model.A;new_row]; end end end end

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: John Cui

You can export your model to a .lp file by cplex.writeModel('debug.lp'), then take a look the .lp file.
John Cui
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Maybe it is easier to first run the conflict refiner to identify the cut(s) that render(s) the problem infeasible and then figure out why/how this cut is generated?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Eumpfenbach

Ok Ok, I'll do it the right way. I was just hopeful that someone could look at the code and spot an error given that it is only 20 lines.

Will check with conflict refiner. Thanks.
#CPLEXOptimizers
#DecisionOptimization