Originally posted by: maiklb2005

Hello, everybody!

To see what LP problem CPLEX solves at the root node (including cuts added by CPLEX), I use the following input MIP problem (stored in .lp file) for the admipex1.c :

 

 

I know the LP problem formulation looks self-explanatory, there are still certain points that I would like to clarify.

Even though, the optimal value to the original problem found by CPLEX is 149 (please see the screenshot attached), by inspection, the optimal value of the LP problem is 79+61 = 140 (since x1 = x3 = 1). How can it be?

The lower bound value that is shown in the screenshot - 178.1343 corresponds to the LP problem subject to c1 only.  The value that satisfies c1, c2, v0 and i1 is 162, but it is not shown (why?), and it is different from 149. It appears that these cuts are not facet-defining, and yet, the lower bound is zero. Was the lower bound obtained by branching?

The LP model does not contain the original constraint. Was the constraint c1 of the original formulation deleted because it was replaced by a stronger inequality? 

The LP contains a new decision variable x5, how was that variable introduced and why?

Is there a way to tell the cut type (Gomory, cover, etc) based on the output?

Thank you very much.

#DecisionOptimization
#OPLusingCPLEXOptimizer

Even though, the optimal value to the original problem found by CPLEX is 149 (please see the screenshot attached), by inspection, the optimal value of the LP problem is 79+61 = 140 (since x1 = x3 = 1). How can it be?

That is the exact desired effect of cuts: Adding new cuts will tighten the LP formulation and will thus improve the dual bound. In your case cuts and additional presolve reductions allow CPLEX to prove that things can not get better than 149. The nodelp you printed has objective 140, which is worse than the current best primal bound 149, so CPLEX can stop.

The lower bound value that is shown in the screenshot - 178.1343 corresponds to the LP problem subject to c1 only.  The value that satisfies c1, c2, v0 and i1 is 162, but it is not shown (why?), and it is different from 149. It appears that these cuts are not facet-defining, and yet, the lower bound is zero. Was the lower bound obtained by branching?

I guess you mean "upper bound" since this is a maximization problem. As you can see in your log output, no branching is going on for your model. So the lower bound was obtained exclusively by cuts and presolve reductions.

The LP model does not contain the original constraint. Was the constraint c1 of the original formulation deleted because it was replaced by a stronger inequality? 

The LP contains a new decision variable x5, how was that variable introduced and why?

Presolve modified your problem. When I solve your model then I can clearly see information about this modification in the log:

MIP Presolve added 1 rows and 1 columns.
MIP Presolve modified 2 coefficients.

You may want to disable presolve if you want the nodelp to look more like the original problem.

Is there a way to tell the cut type (Gomory, cover, etc) based on the output?

The first character of the cut name is different for each cut type. This way you can distinguish the different types of cuts.

#DecisionOptimization
#OPLusingCPLEXOptimizer

Originally posted by: maiklb2005

Daniel, thank you for the explanations. Still, I have a few follow up questions.

It has been my understanding that the algorithm should stop after 0% duality gap has been reached.  This can happen when a feasible solution (primal) is the same as the LP solution (dual).  In order to ensure that the LP solution is integral, in particular, facet-defining cuts are needed.  Since the problem is small, I expected that the cuts obtained by CPLEX will define facets of the convex hull. However, the solution to the problem

Maximize

 obj: 79 x1 + 70 x2 + 61 x3 + 52 x4

Subject To

 c1: 35 x1 + 51 x2 + 67 x3 + 83 x4 <= 118

 c2: 3 x2 + 4 x4 - x5  = 0

 v0: x2 + x3 <= 1

 i1: x3 + 0.25 x5 <= 1

is (1, 1, 0, 0.25, 4), which tells us that a fractional solution x4 = 0.25 has not been cut off, and, therefore, more cuts are needed. If an additional presolve was used instead, how exactly did it eliminate the fractional point?

In contrast, the solution x1 = x3 = 1 is not optimal to the problem above, and it is not clear how it was obtained. Moreover, the solution x1 = x3 = 1 would not be an optimal solution to the dual problem even if facet-defining cuts were obtained. Since the dual solution cannot be lower than the best primal solution, I can conclude that 140 is not the dual value, and x1 = x3 = 1 is not the LP (dual) solution. Again, if the solution x1 = x3 = 1 is purely a product of the additional presolve, how was it obtained? Why wouldn't the algorithm stop after obtaining the LP solution x1 = x2 = 1?

Thank you.

#DecisionOptimization
#OPLusingCPLEXOptimizer

First of all, for your model one does not need to achieve a relative gap of 0% to be able to stop. Since the objective function is integer for any integer-feasible solution, optimality is proved as soon as the absolute gap drops below 1.

I cannot speak about details of CPLEX presolve here. Variable fixings as in your case may for example be obtained by reduced cost fixing or probing. Also note that once a feasible solution of value 149 was obtained, presolve may use arguments like "for a solution to have an objective better than 149, the variable xN must be at least l" (where 'xN' is some variable and 'l' is some value). This way you may end up with a nodelp that has a value worse than 149, proving that one cannot improve on 149.

#DecisionOptimization
#OPLusingCPLEXOptimizer

Originally posted by: maiklb2005

Dear Daniel, thank you for the reply.

Wouldn't it be risky to use arguments what some variables should take certain values while the upper bound is still 162 (which is still far from 149) as in the example above? On the other hand, if the upper bound is exactly 149 (or the absolute gap is less than 1), then there would be no need to prove that better solutions cannot be obtained.

To illustrate the idea, I disabled presolve by setting CPX_PARAM_BNDSTRENIND andCPX_PARAM_PREIND to 0.  As a result, I obtained the following LP problem with the cuts.

Maximize

 obj: 79 x1 + 70 x2 + 61 x3 + 52 x4

Subject To

 c1: 35 x1 + 51 x2 + 67 x3 + 100 x4 <= 150

 v0: x1 + x2 + x3 <= 2

 i1: 0.35 x1 + 0.51 x2 + 0.03 x3 + x4 <= 0.86

Bounds

 0 <= x1 <= 1

 0 <= x2 <= 1

 0 <= x3 <= 1

      x4 = 0

End

Both the upper bound and the feasible cost are equal to 149.  This is what I expected to obtain in the first place.

Presumably, CPLEX was able to prove that a cost better than 149 cannot be obtained without obtaining a solution that leads to a cost worse than 149.

Thank you.

#DecisionOptimization
#OPLusingCPLEXOptimizer

CPLEX does not take "risky" decisions. It only performs reductions that are mathematically correct (within the specified tolerances). So if CPLEX performs a reduction, then there is a proof that this reduction is correct. It may sometimes be hard to follow this logic by only looking at the LP files, since the logic may be involved.

As you already noticed, disabling presolve makes it easier to follow the things that happen internally :-)

#DecisionOptimization
#OPLusingCPLEXOptimizer