Originally posted by: LucasOliveira

Hi! I'm programming a MIP model using CPLEX Callable Library, and for my surprise I'm facing a problem that I can understand what is happening.

My model has an exponential formulation, so I have a routine to generate cuts and a routine to test integer solution factibility.
The model corresponds to a minimization problem and the cuts are global (valid for all nodes).
I have an instance that I know the optimal solution.
When I run the code for this instance, the integer solution found by CPLEX has an objective value greater than the optimal solution.

And the right optimal solution satisfies all cuts generated, why CPLEX don't found it ?

The stat code returned is MIP_OPTIMAL (101), so the solver don't stop before due tolerance cutoff.

Any ideia that what can be the problem ?
Or some test that I can do to understand what is happening ?

Thanks!!!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

This could be a numerical issue.

If you dump the model including all the generated cuts into an lp file, is the CPLEX interactive version also not able to find the optimal solution for the lp file?

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: LucasOliveira

Yes, I try this, and the solution value found by interactive optimizer is less than the optimal solution value.
But in my code the solution value found is always greater than the optimal solution value.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

If numerical stability is in question, a SAV file might be better than an LP file.

/Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: LucasOliveira

Paul, I checked the model using SAV file and I got the same effect of LP file, the right optimal solution is feasible for this model, but CPLEX find a solution with greater value.

Do you know more tests that I can do ???

Thanks
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

To assess the numerics in a model, you could do the following in the interactive CPLEX:

1. "disp prob stat" gives some basic problem statistics, in particular the min and max absolute values of the matrix, rhs, and obj coefficients. If the range of coefficients is very large (like from 1e-3 to 1e+8), then numerical problems are likely to occur. But even if the range is small (like for all 1's matrices), the linear algebra can still be numerically sensitive.

2. As a second step, use the "MIP kappa" feature of CPLEX 12.2. Enter "set mip str kappa 2" and then optimize your problem. If it takes too long and CPLEX has processed a reasonable number of nodes, you can just interrupt with Ctrl-C. Finally enter "disp sol qual" to get solution quality information. This includes a text histogram of condition numbers of matrices encountered during the MIP solve. If you get lots of unstable or ill-conditioned matrices, you know that you are in trouble.

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: LucasOliveira

Tobias, I do the first test and the result is shown below. The range of coefficients is 0 to 1.

===========================================================================
Variables : 307 Binary: 307
Objective nonzeros : 194
Linear constraints : 19265 Less: 19253, Greater: 11, Equal: 1
Nonzeros : 385445
RHS nonzeros : 12

Variables : Min LB: 0.000000 Max UB: 1.000000
Objective nonzeros : Min : 1.000000 Max : 1000000.
Linear constraints :
Nonzeros : Min : 1.000000 Max : 1.000000
RHS nonzeros : Min : 1.000000 Max : 1.000000
===========================================================================

The second test I cannot perform because my CPLEX version is 12.1.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> LucasOliveira wrote:

> The second test I cannot perform because my CPLEX version is 12.1.

Try solving the LP relaxation. CPLEX 12.1 should be able to give you the basis condition number. It's not as informative as the kappa stats in the newer version, but it may tell you something.

/Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Look at your objective function coefficients: they are in the range of 1 and 1 million. This range is not terribly large but still at the border where it may cause numerical issues.

Regarding condition number, I have basically the same answer as Paul: change the problem type to LP and solve it to get the condition number of the LP relaxation. Or better, upgrade to CPLEX 12.2 or CPLEX 12.2.0.2 (which has just been released).

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: LucasOliveira

First, sorry Tobias! I posted the wrong test results.
In my model I have some penalization coefficients but I removed them!
So the right results are:

=====================================================================================
Variables : 307 Fix: 2, Box: 305
Objective nonzeros : 192
Linear constraints : 1644 Less: 1632, Greater: 11, Equal: 1
Nonzeros : 29144
RHS nonzeros : 12

Variables : Min LB: 0.000000 Max UB: 1.000000
Objective nonzeros : Min : 1.000000 Max : 33.00000
Linear constraints :
Nonzeros : Min : 1.000000 Max : 1.000000
RHS nonzeros : Min : 1.000000 Max : 1.000000
=====================================================================================

Following the suggestion of Paul, I investigate the LP of nodes and I detected what can be the problem, but I still don't know why this is happening.

In my code, after the root LP is solved, the variable x215 is selected to branch.
With x215 fixed to 1 (node 2) the model has a feasible solution.
With x215 fixed to 0 (node 1) the model model should be feasible too, but CPLEX outputs that node is infeasible and prune it.

Here is the output snippet:

=====================================================================================
0 0 50.8333 107 191.0000 User: 1 67936 73.39%
0 2 50.8333 107 191.0000 50.8446 67936 73.38%
1 1 infeasible 191.0000 51.8758 67952 72.84%
2 2 77.5000 95 191.0000 77.5003 75676 59.42%
=====================================================================================

I saved the root node model and checked that no cuts was added at node 1. (The model is attached in this message.)
When I fix x215 to 0 and try to solve this model using Interactive Optimizer it found a feasible solution!
Why in my code this model is infeasible ?

Another question!
In the above ouput the fist line is the output when the cutting plane don't found more cuts for the root node!
But after this, in the next line the lower bound is improved again! How this improvement is done ?

Thansk for all suggestions until now! It's helping a lot!!!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I think that we can rule out numerics as the problematic issue. I took your nodelp model and manually declared all variables to be binary. Then, I solved the IP problem using the "MIP kappa" feature of CPLEX 12.2. The result is as follows:

MILP objective                                 9.7000000000e+01
MILP solution norm |x| (Total, Max)            4.80000e+01  1.00000e+00
MILP solution error (Ax=b) (Total, Max)        0.00000e+00  0.00000e+00
MILP x bound error (Total, Max)                0.00000e+00  0.00000e+00
MILP x integrality error (Total, Max)          0.00000e+00  0.00000e+00
MILP slack bound error (Total, Max)            0.00000e+00  0.00000e+00
 
Branch-and-cut subproblem optimization:
Max condition number:             3.4615e+05
Percentage of stable bases:       100.0%
Percentage of suspicious bases:   0.0%
Percentage of unstable bases:     0.0%
Percentage of ill-posed bases:    0.0%

As you can see, there are absolutely no numerical difficulties. I checked the optimal solution, and indeed we have indeed x215 = 0.

So, the issue must be either a bug in CPLEX or there is something strange in your callbacks. Does the same issue arise if you change your callbacks to do nothing if you are no longer in the root node?

Regarding your second question, it could be that the global dual bound is improved by strong branching. Namely, if a variable with fractional LP value is inspected by strong branching (which means to tentatively solve the two subproblems associated with the branch), and there is progress in the objective function in both subproblems, then you have found a better global dual bound, namely the smaller of the two subproblem objective values. This is a valid bound even if you decide to branch on a different variable.

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: LucasOliveira

Hi Tobias, sorry I take too long time to respond.
I'm trying to get the CPLEX 12.2 to test and making other things for my dissertation!

Well, I get the CPLEX 12.2 but the result still is the same! But more strange now!

Now there is no node exploration!
The CPLEX is able to apply a cutoff at root node!
And find another wrong solution!

So, I check for memory errors with valgrind and nothing! I don't understand what is happening! Can I send my C++ code to you check for CPLEX bug ?

Thanks for attention!!!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Yes, please send me your code, but there are some restrictions to make my life easier:

• You must be legally entitled to send me your code and the data. If you need to send anything that comes from a third party, you need to ask them for permission first.
• Your code should compile and run under Linux. I don't use Windows, so having to deal with stuff like a Visual Studio project file exceeds my bandwidth. If this is the case, I need to ask some colleagues whether they are willing to help.
• Please send me a single zip or tgz file that contains everything (excepts the CPLEX library and include files and system stuff):

- your source code
- the data I need
- a Makefile or instructions how to build the code

• Include instructions how to reproduce the behavior and specification of your hardware and software (number of CPU cores in your machine, compiler version) in your email.
• In any case, I cannot promise to find anything useful in reasonable time. But I will try!

My email address is achterberg at de dot ibm dot com.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> LucasOliveira wrote:

>
> Do you know more tests that I can do ???
>

Yes, but it may be a bit painful. Since you know the true optimal value, I assume you know an optimal solution. (If not, you can get one from the interactive optimizer.) In your code, set the MIP log display interval to 1 (so that every node is printed) and print out the MIP log. Now trace through the log, from the root, following the branches that should lead you to the known optimal solution. At some point, you should find a pruned node on that path. Now you need to figure out why it was pruned. (You might want to print out exactly what cuts are added at each node, along with the node id.)

Also, when you followed Tobias's suggestion, did you remember to add your cuts to the model before saving it? I assume from what you wrote earlier that you are using callbacks to add the cuts (?). Cuts added in a callback are not part of the model, so to save them you need to record them somewhere and add them to the model after the solution process ends (and before saving the model).

/Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization