Originally posted by: UserCplex

I have an MIP that gets solved in multiple stages.

 

Stage 1: Create LP [This is attached as file ProblemLP.txt (lp format) ]

 

Stage 2: Convert LP to MIP by changing some variables to integer [This is attached as ProblemIP.txt (lp format) ]

 

Stage 3: Submit MIP of Stage 2 to cplex (Version 12.7.1) to solve with default parameters.

 

Now, as Stage 3 progresses CPLEX adds its own cuts to this problem and gets an integer feasible (and hence optimal) solution at the root node itself.

 

The final root node LP after CPLEX has added cuts to it is attached as nodelp18_0.lp file. I have extracted this lp file using the callback procedure provided in http://www-01.ibm.com/support/docview.wss?uid=swg21400065

 

One of the cuts that CPLEX seems to have imposed in nodelp18_0 is _e1#1 = 0

This cut is cutting off a valid feasible solution that can be obtained by setting _e1#1 = 1. I know that setting _e1#1 = 1 results in a feasible solution because when I impose this constraint in ProblemIP.txt file (this changed problem is provided as ProblemIP_changed.txt (lp format) file), CPLEX solves this modified problem and gives me a feasible solution.

 

Can it be clarified why this cut was added? I was under the impression that cuts added at the root node of a Branch and Bound tree do not cut off feasible integer solutions.

Thanks for your time.

 

ETA: I looked at this thread on a similar topic:

 

https://www.ibm.com/developerworks/community/forums/html/topic?id=3cb830c4-fe71-4a4d-ab2d-c7e630bcc5a1&ps=25

 

The same problem of the cuts cutting of integer feasible solutions occur even after setting CPX_PARAM_REDUCE to 0 as suggested there.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

CPLEX can perform dual based and symmetry based reductions that do cut off integer feasible solutions.   This is OK provided that they do not cut off all optimal solutions.   After all, CPLEX's branch and cut algorithm is designed (by default; we won't go into the solution pool here) to find a single optimal solution.    So preprocessing that eliminates feasible solutions is acceptable as long as it is done in a way that ensures that at least one optimal solution remains.    While the symmetry breaking constraints themselves cannot be as simple as fixing a single variable to 0, the symmetry breaking constraints can then generate cuts that are simple bound constraints, as mentioned in the technote that you reference above.

 

So as long as you don't have some indication that all optimal solutions are being cut off, all is well here.

 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: UserCplex

Ed,

 

Thanks for the response.

A few more follow up questions.

 

(1)Are there cplex settings that ensure that only those cuts that do not cut off any integer feasible point are added ?

(2)Also, whenever cplex generates cuts, and we use the program I linked to in my OP, it seems to provide some mnemonic that follows some logic -- e.g., m stands for mixed integer rounding cuts, f for flow cuts, F for multicommodity flow cuts and r for gomory fractional cuts. Are all these cuts added explicitly as inequalities (as opposed to cuts that translate to variable fixings to either 0 or 1 for binary variables) guaranteed to not cut off feasible integer points? 

I guess my question is, is there a way by looking at the final LP file produced by the program above to know which cuts do not cut off any integer feasible points and which cuts do indeed cut off integer feasible points?

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

1)  CPLEX has no documented single parameter to ensure that no integer feasible point is removed.   Note that if you are trying to do something involving enumerating all integer feasible solutions (or all integer feasible solutions within a percentage of optimality), CPLEX has a solution pool feature that does enable you to accomplish this.  Now, two documented parameters that will reduce, but not eliminate, cutting off integer feasible points, are disabling symmetry detection (i.e. 'set presolve symm 0' in interactive CPLEX, and disabling dual presolve reductions ('set pre reduce 1').   But this doesn't cover everything.   There is an undocumented parameter to do this.   You can e-mail me at klotz at us dot ibm dot com if the documented settings I mentioned above aren't enough for you and you think you have a need for this that cannot be accomplished using the solution pool feature.

 

2)  The individual cuts that CPLEX currently generates all create globally valid cuts   So, in that sense, they are guaranteed, whether they turn out to be inequalities or simple bound constraints or equalities, not to remove any integer feasible solutions.    But, as I mentioned earlier, they can combine with symmetry breaking constraints or other dual based tightenings of the model to cut off integer feasible solutions that might otherwise have remained had you disabled the cut(s) in question.  But yes, if you disable all features that use the objective to tighten the formulation, then you can be confident that, as of CPLEX 12.7.1, all cuts are currently valid.   But keep in mind this is not a documented feature; it is possible that a future version might introduce a new cut that uses the objective function and can remove some integer feasible solutions.

#CPLEXOptimizers
#DecisionOptimization