Originally posted by: Olivia.w

Hi.

I am trying to solve an integer programming model by CPLEX.

At first, it works well on my MacBook. I coded in C++ in Xcode and got the following solution, whose status is optimal.

 

MIP search method: dynamic search.

Parallel mode: deterministic, using up to 4 threads.

Root relaxation solution time = 0.00 sec. (1.00 ticks)

        Nodes                                         Cuts/

   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

 

*     0+    0                            0.0000      920.0000              --- 

      0     0      248.1007    23        0.0000      248.1007       51     --- 

      0     0      246.3133    31        0.0000      Cuts: 11       73     --- 

      0     0      244.9282     5        0.0000      Cuts: 15      137     --- 

*     0+    0                          244.9282      244.9282            -0.00%

      0     0        cutoff            244.9282      244.9282      137   -0.00%

Elapsed time = 0.09 sec. (20.28 ticks, tree = 0.01 MB, solutions = 2)

Cover cuts applied:  1

Flow cuts applied:  1

Zero-half cuts applied:  5

Lift and project cuts applied:  1

Gomory fractional cuts applied:  5

 

Root node processing (before b&c):

  Real time             =    0.09 sec. (20.31 ticks)

Parallel b&c, 4 threads:

  Real time             =    0.00 sec. (0.00 ticks)

  Sync time (average)   =    0.00 sec.

  Wait time (average)   =    0.00 sec.

                          ------------

Total (root+branch&cut) =    0.09 sec. (20.31 ticks)

solution:

Solution status: Optimal

Objective=244.928

 

But after I move the same program and test instance to a linux system and compiled with g++, Cplex outputs a solution as follows.

The objective value is better but It actually seems to be infeasible since I printed out the model and solution in detail.

 

MIP search method: dynamic search.

Parallel mode: deterministic, using up to 8 threads.

Root relaxation solution time = 0.00 sec. (1.00 ticks)

        Nodes                                         Cuts/

   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

 

*     0+    0                            0.0000      920.0000              --- 

      0     0      248.1007    23        0.0000      248.1007       51     --- 

      0     0      246.3133    31        0.0000      Cuts: 11       73     --- 

      0     0      244.9282     5        0.0000      Cuts: 15      137     --- 

*     0+    0                          244.9282      244.9282            -0.00%

*     0     0      integral     0      245.1313                    137     --- 

Elapsed time = 0.08 sec. (20.64 ticks, tree = 0.01 MB, solutions = 2)

Cover cuts applied:  1

Flow cuts applied:  1

Zero-half cuts applied:  5

Lift and project cuts applied:  1

Gomory fractional cuts applied:  5

Root node processing (before b&c):

  Real time             =    0.08 sec. (20.66 ticks)

Parallel b&c, 8 threads:

  Real time             =    0.00 sec. (0.00 ticks)

  Sync time (average)   =    0.00 sec.

  Wait time (average)   =    0.00 sec.

                          ------------

Total (root+branch&cut) =    0.08 sec. (20.66 ticks)

solution:

Solution status: Optimal

Objective=245.131

 

All I use are the default settings of CPLEX. Does anyone know what may cause this integral solution shown on linux which seems to be infeasible?

Thanks a lot.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EXCT_RALF_GOLLMER

Hi Olivia,

seems weird that you get these different optimal values.

One possible cause: the problem is ill-conditioned.

How do you conclude that the second one is infeasible? Did both programs really build the same model?

 

I propose you include

public IloNum getQuality(IloCplex::Quality q, IloInt soln, IloConstraint * rng, IloNumVar * var=0) const

public IloNum getQuality(IloCplex::Quality q, IloNumVar * var=0, IloConstraint * rng=0) const

into your program to access CPLEX's information about the information about solution quality, i.e. unscaled violation of bounds and constraints.

Another way to get that information: let the program write out a p.sav file of the model and p.mst file with the solution info to be used as a MIP start - and analyze is in the interactive CPLEX.

There you enter the commands

set mip str kappa 2

r p.sav

r p.mst

m

d sol qual

This loads the solution produced by your program as a MIP start and solved the problem, 'd sol qual' displays the maximal condition numbers of bases, the percentage of ill-conditioned ones, and the violations of bounds/constraints.

Afterwards you could query e.g.  the slacks of constraints you think are violated.

If you change the default options before entering  m (=mipopt) you could check the consequences.

Possible candidates are tighter tolerances

set sim tol feas 1e-8

set sim tol opt 1e-8

set mip tol int 1e-16

set mip tol abs 0.

set mip tol mip 1e-8

and - if the problem is ill-conditioned:

set emp num y

Best regards

Ralf

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Olivia.w

Hi. Ralf,

 

Thank you so much for your reply.

 

First I am sure I use the same program since I just copy my .h and .cpp files to the linux system. Both program run with CPLEX 128.

Actually I run many test instances on linux, but this is the first one I got this kind of solution.

Maybe you are right the problem is ill-conditioned in some special cases. I have to check my IP formulation.

 

I named each variable in the program and print out the model of this instance build by cplex in detail. So I think yes the two models built for this instance on the two systems are the same.

I also printed out each of the variable values in the optimal solutions.

I think the second solution is infeasible. Because I have a constraint in the model, for example, x1 + x2 - q1 + q2 + 100000*y <= 100000.

In the printed solution I have x1=1, x2=0, q1=0, q2=0, y=1.

One thing I am not sure whether it is relevant or not. I define the variables as IloIntVarArray. But I use .add(IloConversion(env,vars[x],ILOBOOL)) for the variables x1, x2 and y.

 

I will try the options as you suggested. Please let me know if you have other ideas. Thanks again.

 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EXCT_RALF_GOLLMER

O.k., if that are the solution values and the constraint, that one would obviously be violated.

If you include the line

cplex.exportModel ("p.lp.gz");

in your program just before cplex.solve() you could verify in the file that the program really built the constraint you intended.

After the solve set

IloCplex::Param::Output::WriteLevel = 1

for all variable values to be written to the mst file and call 

cplex.writeMIPStarts("p.mst",0,1);

This should write out the values of the last (optimal) incumbent to p.mst.

If the problem is huge, you could append a .gz to both file names to have CPLEX write gzip-compressed files.

The first check for me would be: is the constraint really there in the problem as intended (or was somenthing mixed up by a bug in the program - which could easily happen)?

It helps if all constraints were given sensible names in the program to easily find the one you look for.

 

This seems to be a Big-M formulation with M = 10000. This seems not te be extremely big - but it still it produces a range of matrix coefficients from 1 to 10^5.

Looks familiar if you are using alternative inequalities.

What are the ranges for the variables x1, x2, q1 and q2 and thus what is the possible range of the expression x1 + x2 - q1 + q2?

Big-M has to be chosen at least the absolute value of that possible range, but by taking a much bigger value the numerical stability may be degraded.

If the constraint is there in the model you could look in the interactive cplex what slack is given for the constraint with that name.

CPLEX is not completely bug-free either, so if you found a proof for a bug, you might well ask again in the forum.

But a violation of that amount seems not so likely - if not the rest of the constraints makes the problem very ill-conditioned.

In the interactive cplex you could query the ranges of matrix and rhs coefficients by 'dis prob stat'

 

I'm just a user, not a CPLEX developer, so I am just guessing what could be the problem here. But if you encountered a bug in CPLEX (which prevails in the interactive solver) you should upload the probem (if you would not like or cabot share your problem it may be in an anonymized form with dvariable/constraint names v1...vn, c1...cm, which could be produced by the write command in the interactive solver). Otherwise the developers would have to guess, too.

Best regards

Ralf

 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Olivia.w

Hi Ralf.

 

I change the mip int tolerance to 1e-9, and the problem seems to be solved so far. 

It is a big-M formulation, and I think the value of M is sufficient. But maybe it cannot be too large as well.

There are too many things I have to learn on careful formulation and coding...

Thank you very much for your kind help.

 

Best regards,

Olivia

#CPLEXOptimizers
#DecisionOptimization

As Ralf said, this could be a numerical issue related to your choice of "big M" (100000, or 1e+5). CPLEX has a default integrality tolerance of 1e-5 (meaning that any variable value within 1e-5 of the nearest integer counts as an integer) and a feasibility tolerance of 1e-6 (meaning any constraint whose value comes out within that much of being on the correct side of the right-hand side value counts as satisfied). The latter may or may not be relevant here. Here, if CPLEX got x1 = 1 and y = 1 - 1e-5 = 0.99999, the left side would evaluate to 1e+5 (so feasible) and y would still be considered 1 in the solution. Similarly, if y came out 1 - epsilon where 1e-5 > epsilon > 1e-5 - 1e-11, then y would be even closer to 1 (so within integrality tolerance) and 1 + 0 - 0 + 1e+5*y = 1 + 1e+5(1-epsilon) = 1e+5 + (1 - 1e+5 epsilon) < 1e+5 + (1 - 1 + 1e-6), within feasibility tolerance of meeting the constraint.

You could try cranking the integrality tolerance and feasibility tolerance parameters a bit lower and see if the second machine still gives you the erroneous answer. Alternatively, you could turn on the numerical emphasis parameter, which will cause CPLEX to try to be a bit more accurate with arithmetic (at a speed cost). Perhaps the best option, if feasible, is to reduce the value of tht 1e5 coefficient.

As to why it happens on one machine but not another, that could be due to differences in the floating point libraries used to compile the CPLEX binaries on each, or possibly (but less likely) something to do with thread sequencing (you have twice as many threads on the Linux box), or just planetary alignments.

Paul

 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Olivia.w

Hi, Paul.

 

Thank you so much for your kind reply. The detailed explanations help a lot.

 

I set IloCplex::EpInt to 1e-9 in Linux, and get the same optimal solution as on my MacBook.

I notice that this is indeed the first instance I have only one x to be equal to 1 in the left of the constraint.

So maybe y is 1-epsilon where epsilon is so small that, along with q1, the error ends up within the tolerance.

That is my best guess and solve this instance so far. I will try to validate my formulation and other settings.

 

Thanks a lot again.

Best regards.

 

Olivia

 

#CPLEXOptimizers
#DecisionOptimization