Originally posted by: opal123

Hi everyone,
I am new to CPLEX and I am solving MIP problem using CPLEX and Java. I am using the default settings for CPLEX to solve MIP with emphasis on proof to optimality (cplex.setParam(IloCplex.IntParam.MIPEmphasis, 2)). When I run the code on two different machines (different versions of CPLEX -11 and 12.1 ), I had two different solutions to the same problem formulation. The status of the solution in both cases is:
cplex.getStatus Optimal
cplex.getCplexStatus: OptimalTol

My question is - Does Cplex find a true(global) optimum solution? If the "optimum" solution produced is "local" - what settings do I need to find global (true) optimum solution to my problem. Also, why my problem formulation produces two different results depending on the version of CPLEX? Thank you for your help.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

CPLEX finds a global optimal solution, i.e., a solution vector that has an objective function value which is the minimum (or maximum) over all feasible solution vectors.

But you need to be aware of the fact that many problem instances have multiple optimal solutions. In this case, CPLEX just returns one of them, and it can very well happen that even using the same binary with the same settings on two different machines results in different solution vectors. Nevertheless, the objective function value should always be the same (if numerical issues are not involved).

If you are seeing two different optimal objective values (with a difference that is larger than the MIP gap parameter, default at 0.01%), then it is most likely that your model is numerically sensitive. For example, because you have a mix of very large and very small coefficients in your constraint matrix.

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: JaneM

I've been having a problem with a MIP for which cplex finds a solution for the first model, then when I relax some constraints, cplex finds a solution that is more expensive than the first solution.  Since the second model is a relaxation of the first model, cplex should at least find the solution for the first model when running the second model.  So it seems cplex is not find the global optimal solution. 

You suggested looking for coefficients that are very large or very small in the constraint matrix.  Do I also need to look at differences in coefficients in the objective function?  Are there are things I should be looking for to avoid this problem? 

I am working on setting up a warm start using the solution from the first model as a start for the second model.  But I don't think I should have to do something like this every time I run this model to make sure I have a global optimum.

 

#CPLEXOptimizers
#DecisionOptimization

Questions of clarification:

1. CPLEX solves the relaxed problem to (what it thinks is) proven optimality? You're not hitting a time/memory limit?
2. The objective value of the solution to the relaxed problem is worse than that of the first solution by a nontrivial amount (more than could be ascribed to rounding, and more than CPLEX's optimality tolerance)?

If the difference is nontrivial and CPLEX is asserting optimality, I would suggest looking at kappa statistics to see if you have unstable bases popping up. That would indicate numerical instability.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: JaneM

Paul, 

Thanks for the response.  It looks like it was my mistake and CPLEX was working correctly.  I had, by mistake, added one small constraint to the more relaxed problem which made the original solution impossible.  I set up a warm start for the "relaxed" problem using the original solution.  When the relaxed model would not select the original solution with the warm start, I realized I must have included something somewhere that was making it impossible to select at least the original solution.

 

With that constraint fixed, the relaxed solution is less costly than the original solution.  What a relief.  

 

I do have another problem that is a lot more complicated where it seemed that the cplex solution could be improved on.  I didn't have time to check that problem when I was using to see if I had misspecified something.  Thanks for the recommendation on kappa statistics, whatever they are.  When I get back to running this more complicated model, I will know to check here and then find out more about kappa statistics and unstable bases.  Thanks.

#CPLEXOptimizers
#DecisionOptimization

Another thing to check if you get solutions that look sub-optimal: Make sure the solution status is CPXMIP_OPTIMAL and not just CPXMIP_OPTIMAL_TOL.

You may also want to set parameters CPX_PARAM_EPAGAP and CPX_PARAM_EPGAP to 0. The default values for these parameters allow CPLEX to stop with suboptimal solutions that are proven to be very close to the optimum. Depending on your model, "very close" may not be good enough.

#CPLEXOptimizers
#DecisionOptimization