Originally posted by: EdKlotz
>
> I just tripped over something very strange in CPLEX 12.5.
The CPLEX version doesn't matter; you can reproduce this with earlier recent versions
as well. I stopped checking after moving back to 12.2.
>Suppose that we want to minimize x + 10y subject to x <= My, where y is a binary
> variable and x is a real variable with lower bound 1. Consider the following simple > CPLEX model (which I constructed in a Java program, although I doubt the provenance > matters), with M = 1e9:
>
> IloModel
{ > IloMinimize Obj : (1.0*x + 10.0*y) > IloRange C1 : -infinity <= (1.0*x - 1.0E9*y) <= 0.0 > >
} > Tried aggregator 1 time. > MIP Presolve eliminated 1 rows and 2 columns. > MIP Presolve modified 1 coefficients. > All rows and columns eliminated. > Presolve time = 0.00 sec. (0.00 ticks) > x = 1.0, y = 1.0, obj = 11.0 >
>
> Presolve correctly computes the optimal solution. Now change M from 1e9 to 1e10 and see what happens:
>
>
> IloModel
{ > IloMinimize Obj : (1.0*x + 10.0*y) > IloRange C1 : -infinity <= (1.0*x - 1.0E10*y) <= 0.0 > >
} > Infeasibility row
'C1': 0 = -1. > Presolve time = 0.00 sec. (0.00 ticks) > CPLEX status = Infeasible >
>
> I modified the model to include a real variable z and the constraint z = 1e7*y (as a workaround to the problem that the interactive optimizer does not display enough digits to distinguish y = 0 from y = 1e-10), and dumped the model to a SAV file (attached). Playing with the SAV file in the interactive optimizer, I discovered the following:
>
> 1) if I load the file and try to solve the MIP, CPLEX reports the MIP is infeasible (as with the Java code);
>
> 2) if I relax the problem to an LP and solve it, CPLEX reports an optimal solution with x = 1 and y = 1/M (correct);
>
> 3) if I then revert the problem to a MILP and solve it, CPLEX reports an "optimal" solution.
>
> I put optimal in quotes because
>
> 3a) if the advanced start indicator is on when I do step 3, the MIP solution has x = 1, y = 0, z = 0.001 (indicating that y had a value of 1e-10 and was rounded to zero), whereas
>
> 3b) if the advanced start indicator is off before step 3, the MIP solution has z = 1, y = 0 and z = 0.
>
> With advanced starts off, I would expect CPLEX to again claim that the MIP is infeasible. Both 3a and 3b occur even with the integrality tolerance set to 1e-12, which I would think would prevent CPLEX from claiming that y = 1e-10 was "close enough" to y = 0.
>
> The big mystery to me, though, is why the MIP presolver thinks the original model is infeasible.
>
We have:
CPLEX> d pr all
Minimize
obj: x + 10 y
Subject To
Con1: x - 10000000000 y <= 0
c2: - 10000000 y + z = 0
Bounds
x >= 1
0 <= y <= 1
All other variables are >= 0.
Binaries
y
Now, if you restrict presolve reductions to primal only (i.e. 'set pre reduce 1'),
the unexpected infeasibility goes away. As we shall see, dual presolve reductions
matter here. So, how would presolve handle this? For starters, it can aggregate
out c2 since it's just an accounting constraint that sets the column singleton z.
Now, because dual presolve reductions are enabled and x is a column singleton, we can
fix x at its lower bound of 1 given the positive objective coefficient and minimization.
So, removing that, so have
Con1: - 10000000000 y <= -1
or equivalently
Con1: 10000000000 y >= 1
Now, dual presolve reductions strike again. y is a column singleton with positive objective,
so we can push it downwards and change the constraint to
Con1: 10000000000 y = 1
Now, this gives us an upper bound on y of 1e-10. The integrality of y then changes that upper bound to 0. Now we are indeed infeasible.
Regarding why this doesn't occur with a coefficient of 1e+9 or other values < 1e+10,
with a value of 1e+10, CPLEX normalizes Con1 to
y >= 1e-10
The 1e-10 value is small enough so that it views this as within tolerance of an all
integer constraint, which then allows it, due to the positive objective coefficient on y, to change this from a >= constraint to a = constraint. That is not the case
with coefficients < 1e+10; CPLEX no longer views this as a constraint with all integer
coefficients, so it must leave this constraint as a >= constraint.
While we could say this is just one of the many hazards of using large big M values,
I have examined the issue and think CPLEX can handle this better. So, the odds are
good that a future version of CPLEX will handle this large big M value more effectively. However, keep in mind that even so, such large big M values could
lead to solutions that are within CPLEX's default integrality tolerance of 1e-5, and hence treated as integral. Yet, the violate the intent of the model. For example,
in this case, y = 1e-10, x = 1 is feasible within any integrality tolerance <= 1e-10,
resulting an objective value of 1 + 1e-9, which essentially avoids the intended
fixed cost on y. So, using large big M values in general can lead to unexpected
results. And, more specifically, because of CPLEX tolerances on machine with standard 64 bit representation of doubles, choosing values of 1e+10 or greater for
big M is more likely to cause trouble than smaller values.
For more information on big M values and their impacts on models, take a look at the technotes at
http://www-01.ibm.com/support/docview.wss?uid=swg21399984 and
http://www-01.ibm.com/support/docview.wss?uid=swg21400084#CPLEXOptimizers#DecisionOptimization