Originally posted by: SystemAdmin

I found a problem when I was running some MIP instances using cplex. When I used the default root algorithm, the cplex said there was no feasible solution for the instance. But when I used primal root algorithm and disabled the presolve, cplex can solve the instance with an optimal solution. I wonder why this happend. Thank you very much.

The first run did not include the following codes, cplex said no feasible solutions. But the second run included the following codes, cplex found the optimal solution. The only difference between the two runs is the follow codes.

cplex.setParam(IloCplex::PreInd, false); //disable the presolve 
        cplex.setParam(IloCplex::IntParam::RootAlg, IloCplex::Algorithm::Primal); //set root algo. to primal

Also, foe both runs, I let cplex run sequentially in deterministic mode in a single thread.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I would suggest you try to use cplex.getStatus() to query the status of solutions, see what it gets back to you.

Furthermore, would you please post the output of CPLEX, that might help others to know more about your situation.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Yes, using getStatus() is a good idea. Maybe the status is not infeasible but "infeasible or unbounded". This can happen if presolve crushes the problem to nothing. The exact status will probably tell what is going on.
What happens if you only disable presolve and do not change the algorithm? Does this also give a feasible solution?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

When I disabled presolve, and used default root algo., the cplex.getStatus() shows that "infeasible".

my code is:

cplex.solve();
 
        cout<<"The SP_CM status is: "<<cplex.getStatus()<<endl;
        if(cplex.getCplexStatus() == CPX_STAT_UNBOUNDED)
                cout<<"The SP_CM is Unbounded"<<endl;
        else;
 
        if(cplex.getCplexStatus() == CPX_STAT_INFEASIBLE)
                cout<<"No Solution Exists for SP_CM."<<endl;
        else;

output is:

The Original Relative MIP Gap Tolerance is: 0.0001
The Updated Relative MIP Gap Tolerance is: 0.02
Tried aggregator 2 times.
MIP Presolve eliminated 19793 rows and 2036 columns.
MIP Presolve modified 7803 coefficients.
Aggregator did 180 substitutions.
Reduced MIP has 38581 rows, 19850 columns, and 124361 nonzeros.
Reduced MIP has 10085 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time =    0.45 sec.
Clique table members: 16182.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: none, using 1 thread.
Root relaxation solution time =    3.99 sec.
 
        Nodes                                         Cuts/ 
   Node  Left     Objective  IInf  Best Integer     Best Node    ItCnt     Gap
 
      0     0  2665911.1800   365                2665911.1800     5048
      0     0  2691790.5917   455                   Cuts: 101     6951
      0     0  2693739.6712   564                    Cuts: 50     7697
      0     0  2694551.3058   567                Flowcuts: 15    11090
      0     0  2694747.3644   546                    Cuts: 12    11347
      0     0  2694783.8408   542                     Cuts: 3    11377
      0     0  2696194.7395   451                 Flowcuts: 2    11709
      0     0  2697267.1378   483                    Cuts: 10    12127
      0     0  2697316.5520   493                 Flowcuts: 6    12553
      0     2  2697316.5520   493                2697335.6029    12553
Elapsed time =  26.64 sec. (tree size =  0.00 MB, solutions = 0)
 
Flow cuts applied:  97
Flow path cuts applied:  3
Zero-half cuts applied:  2
Gomory fractional cuts applied:  5
The SP_CM status is: Infeasible
No Solution Exists for SP_CM.
 ERROR: CPLEX Error  1217: No solution exists.
 
Press any key to continue . . .

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Sorry, there is a typo in my last posted message. I USED presolve, but not disabled presolve. I used default root algo.

Does someone know how to edit the posted message?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

When I disabled presolve, and used default algo., cplex can find feasible solution.

My code:

cplex.setParam(IloCplex::PreInd, false); //disable the presolve 
       
       cplex.solve();
 
        cout<<"The SP_CM status is: "<<cplex.getStatus()<<endl;
        if(cplex.getCplexStatus() == CPX_STAT_UNBOUNDED)
                cout<<"The SP_CM is Unbounded"<<endl;
        else;
 
        if(cplex.getCplexStatus() == CPX_STAT_INFEASIBLE)
                cout<<"No Solution Exists for SP_CM."<<endl;
        else;

My output:

The Original Relative MIP Gap Tolerance is: 0.0001
The Updated Relative MIP Gap Tolerance is: 0.02
Clique table members: 35325.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: none, using 1 thread.
Root relaxation solution time =   13.15 sec.
 
        Nodes                                         Cuts/ 
   Node  Left     Objective  IInf  Best Integer     Best Node    ItCnt     Gap
 
      0     0  2633497.7498   382                2633497.7498     8717
      0     0  2687889.3880   537                   Cuts: 172    11747
      0     0  2690181.1238   579                   Cuts: 128    12616
      0     0  2690617.3525   561                    Cuts: 38    12969
      0     0  2691668.3884   573                    Cuts: 13    13393
      0     0  2692206.1703   564                    Cuts: 34    13582
      0     0  2692210.4009   568                    Cuts: 15    13616
      0     0  2692210.4009   568                     Cuts: 5    13618
Heuristic still looking.
Heuristic still looking.
Heuristic still looking.
      0     2  2692210.4009   568                2692230.6805    13618
Elapsed time =  97.92 sec. (tree size =  0.00 MB, solutions = 0)
    100    91  2865230.7002   141                2695147.1749    49642
*   193   166      integral     0  2942774.2639  2695147.1749    80577    8.41%
    200   173  2802886.9439   467  2942774.2639  2695333.7495    87103    8.41%
    300   254  2900566.1240   162  2942774.2639  2699105.2974   110717    8.28%

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Thus, the difference is about disable the presolve or not. When I disabled presolve, cplex can find feasible solution. But when I used presolve, cplex thought the problem is infeasible. Can someone tell me why this happened? Thanks.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

My first guess is that your model has numerical issues. To assess this, I suggest to dump your model as *.sav file to disk. Then, use the interactive CPLEX solver version 12.2 or larger and do:

read model.sav
disp prob stat
set pre pre n
set mip str start 1
set mip str kappa 2
opt
disp sol qual

The first command reads in your model. The second one shows a summary about your model, in particular about the minimum and maximum values of your matrix, objective, and right hand side coefficients. The next two lines switch to your special settings (no presolve, primal simplex as starting algorithm), and the last "set" command enables "MIP kappa" tracking (a new feature of CPLEX 12.2). Then you solve the model with "opt" and display the solution quality, which will give you an idea about numerical problems encountered during the solving process. Finally, post the whole log output of this session into the forum, using a "code" block (like I did above) such that we can read everything. Then, I can tell you probably a bit more if numerics play a role in your model.

In the case that numerics are fine in your model, then you may have encountered a bug (potentially in CPLEX presolve), and we would be very interested in getting your model to fix this bug.
Thanks,

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

What if you relax the inequality tolerance by cplex.setParam, like cplex.setParam(cplex.EpRHS, 1e-004)?

See if it will give you a feasible solution even you invoke the presolve?

My guess is that there is probably some numerical issue, noting your obj is about 3e07. If your coefficient scale varies over a wide range, numerical issue will likely rise up.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I tried relax the EpRSH to 1e-4, then cplex can get the feasible solution.

the output is:

The Original Relative MIP Gap Tolerance is: 0.0001
The Updated Relative MIP Gap Tolerance is: 0.02
Tried aggregator 2 times.
MIP Presolve eliminated 19793 rows and 2036 columns.
MIP Presolve modified 7803 coefficients.
Aggregator did 180 substitutions.
Reduced MIP has 38581 rows, 19850 columns, and 124361 nonzeros.
Reduced MIP has 10085 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time =    0.47 sec.
Clique table members: 16182.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: none, using 1 thread.
Root relaxation solution time =    4.29 sec.
 
        Nodes                                         Cuts/ 
   Node  Left     Objective  IInf  Best Integer     Best Node    ItCnt     Gap
 
      0     0  2665911.1798   365                2665911.1798     5047
      0     0  2688076.0447   423                   Cuts: 102     6479
      0     0  2689936.7359   434                    Cuts: 46     6896
      0     0  2690666.1538   436                Flowcuts: 12     7031
      0     0  2690982.0970   428                     Cuts: 9     7280
      0     0  2692486.9103   434                     Cuts: 6     7545
      0     0  2692498.5673   446                     Cuts: 9     7718
      0     0  2694345.8517   523                     Cuts: 3     8405
      0     0  2694393.9146   446                 Flowcuts: 7     8500
Heuristic still looking.
*     0+    0                      4266231.6358  2694393.9146     8500   36.84%
*     0+    0                      3659562.5708  2694393.9146     8500   26.37%
*     0+    0                      3576973.5660  2694393.9146     8500   24.67%
*     0+    0                      3548624.1701  2694393.9146     8500   24.07%
      0     2  2694393.9146   446  3548624.1701  2694394.8189     8500   24.07%
Elapsed time =  44.93 sec. (tree size =  0.00 MB, solutions = 4)

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

in my last posted message, I used presolve and relaxed EpRHS.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

But I am still not understand why this happen? Can someone explain the reseaons for me? Thank you very much.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Can someone answer my question? thank you.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Tobias suggests some diagnosis, a few replies up, that would provide the information necessary to begin taking some guesses.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Thank you, Tobias. Here is the log file.

Since the webpage kept having error when I used {code} block to post the whole log file, I had to attach the log file.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Uhh... you spent a significant amount of computing resources to generate this log (almost 2 days), but unfortunately, it seems that you forgot the most important command:

display solution quality

at the very end. This would have shown the numerical stability analysis results generated with the help of the "mip kappa" feature. Do you happen to still have this interactive session open and can provide the solution quality output?

Anyway, the problem statistics at very beginning of your log file already give evidence that your model may cause serious numerical problems in a floating point arithmetic based solver like CPLEX:

Variables            :   22066  [Nneg: 9900,  Fix: 1,  Box: 45,  Binary: 12120]
Objective nonzeros   :   12121
Linear constraints   :   58554  [Less: 55414,  Greater: 165,  Equal: 2975]
  Nonzeros           :  168724
  RHS nonzeros       :    5990
 
Variables            : Min LB: 0.0000000        Max UB: 1.000000       
Objective nonzeros   : Min   : 0.02674438       Max   : 1.000000e+007  
Linear constraints   :
  Nonzeros           : Min   : 0.2674438        Max   : 996087.0       
  RHS nonzeros       : Min   : 1.000000         Max   : 24.00000

Your objective function has values ranging from about 1e-2 to 1e+7, i.e., the range is about 9 orders of magnitude. This alone can cause strange effects, in particular for the dual simplex algorithm (which is used inside MIP) where the objective function enteres as the right hand side of equation system solves.

But since your main issue seems to be feasibility, my guess is that this is not such a big deal (but still it could be a reason for numerical instability). On the other hand, the coefficient matrix coefficients also do not look so well with their range from 1e-1 to almost 1e+6.

Note that the problem statistics cannot provide the full picture regarding numerical issues. There are models with even bigger ranges in the coefficients than yours that just solve nicely, and there are models that only have +1 and -1 coefficients which are terrible in terms of numerics. The structure of the matrix plays a very important role, and this cannot be captured by the simple problem statistics that CPLEX displays. For this you really need the "mip kappa" output that I was hoping to get.

If you want to get some meaningful output without having to wait again for 2 days, this is no problem. You don't need to solve the model to optimality. Solving a certain number of nodes will suffice to get a good impression. For example, you could just set the time limit to 3600 seconds, say, and then use the same commands again, including the "display solution quality".
Regards,

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

This is what cplex shows after I entered "display solution quality"

CPLEX> display solution quality
Incumbent solution:
MILP objective                                2.8867626176e+006
MILP solution norm |x| (Total, Max)           7.06962e+006 3.70306e+005
MILP solution error (Ax=b) (Total, Max)       3.56532e-010 5.09317e-011
MILP x bound error (Total, Max)               6.18456e-011 1.45519e-011
MILP x integrality error (Total, Max)         2.92857e-010 1.16415e-010
MILP slack bound error (Total, Max)           1.80444e-009 9.96806e-010
 
Branch-and-cut subproblem optimization:
Max condition number:             3.8350e+022
Percentage of stable bases:       0.0%
Percentage of suspicious bases:   97.1%
Percentage of unstable bases:     2.9%
Percentage of ill-posed bases:    0.0%
Attention level:                  0.018833
CPLEX encountered numerical difficulties while solving this model.
CPLEX>

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Okay. This looks pretty bad. Mostly all of your LP bases are in the "suspicous" category, and there are even some in the "unstable" class. The max condition number is 3e+22. This means that if some input of a linear system is, for example, off by 1e-16 (which is roughly the precision of double precision floating point arithmetic), then the linear system solve can result in an output that is off by 3e+6 from the true solution. So, the answer to the question of feasibility in your model can just be a random artifact of round-off errors.

Of course, the condition number is only a worst case bound for the error propagation in linear algebra. Thus, in reality it could be that even for an ill-conditioned system the solution quality is actually pretty good. But still such large condition numbers as in your case show that you cannot trust the results of the linear system solves too much.

Now, having identified the most likely source of the inconsistent results, the question is what you can do about it.

One obvious proposal is to activate the "numeical emphasis" parameter setting. But still, I think it is unlikely that this will fix the intrinsic issues in your model. It just makes sure that the numerics do not become much worse.

The best approach really is to think about your model and whether you can formulate it differently to avoid the large difference in magnitude of the constraint coefficients.
Can you use indicators instead of a big-M formulation? Can you scale the columns (like using hours instead of seconds as basis for time based variables)?
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Tobias, thank you very much. I am going to try to change my formulation, and then check the solution quality again using the method you taught me. Thanks.

Another question is, if the solution quality is not good, does it mean that the optimal solution from cplex is probabibly not a feasible solution, some constraints are not satisfied?

Since the EpGap is defined by users, I am not sure what does it mean "the solution quality is not good" ?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

In your example, the solution quality (in terms of feasibility of the incumbent solution) looks very good. All max errors are in the order of 1e-10 or even 1e-11. So, your solution is certainly feasible within the tolerances.

What looks bad are the condition number statistics. This means that numerics for the linear solves are pretty poor, and this can mean that CPLEX did some wrong decisions on its way, most notably to declare a node infeasible even though it contains a feasible solution. As a consequence, it could be that your final "optimal" solution is in fact not optimal and there exists a feasible solution of better objective value. In the extreme case (which you have experienced) it could mean that CPLEX declares the whole model to be infeasible, even though feasible solutions exist.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Tobias,

My problem is a minimization problem, so it means that there may be another feasbible solution less than the "optimal" solution, right? Since the optimal solution is the upper bound within the designated EpGap (I set it as 0.02), if the upper bound is higher, does it mean that the lower bound (the "cut" column in cplex output) is also higher than the value which it should be for the numerics difficulty? Thank you very much.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Yes. Usually, if you are minimizing and CPLEX claims to have found an optimal solution, then there is no feasible solution with smaller objective value. But if there are numerical issues with your model, than it could be that CPLEX (or any other floating point based solver) produces a wrong answer, which in your case means that there is a feasible solution of smaller objective value.

There is not much more that I can say. If numerical issues arise, then the bounds can be just wrong. Checking whether the primal bound (the upper bound for minimization) is valid is easy: just check whether the solution satisfies all constraints. This you can get with the "display solution quality" command or the appropriate API function. Checking whether the dual bound is correct is hard, because a single miscalculation in some algorithm inside CPLEX can lead to a wrong dual bound. The condition number give some indication whether one can expect numerical difficulties or not, but they do not provide a definite conclusion.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Tobias,

Thanks. A last question, we already talked about the numerical issues may affact the solution quality, does the numerical issues also affact the solution time? Does it make cplex use much longer time to solve a same formulation with a same size network problem? Thank you very much for all your help.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Changing the model will certainly affect the solution time, but whether it will get faster or slower cannot be said in advance. MIP is NP-hard, so a single decision that is different in solving the two models can have a significant (exponential) impact on the solving time.

Of course, there is some probability that a numerical troublesome model can be solved faster, because a round-off error in the calculations cut off a significant part of the solution space. But I doubt that you want to have this kind of speed-up ;)
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Tobias, thank you so much for all your answers, they are very helpful.
#CPLEXOptimizers
#DecisionOptimization