CPLEX Return Local Optimal


Hello everyone,

CPLEX returns optimal solution for small instances of a MIP model. But when try to solve a larger instance, CPLEX return a local optimum (solution checked by a heuristic). The model is MIP with a number of Big-M formulations that are replaced by Indicator Constraints. For one of the large instances: 

# of constraints: 2086337

#of variables: 1122331 (66225 int) 

#of none zero: 7223176

It takes 53557 seconds for CPLEX to close the optimality Gap.

Any idea? please share your thought.


10 replies

Userlevel 3

What exactly is your question? If CPLEX closes the optimality gap then it should (normally) return an optimal solution. Did you observe that CPLEX returned a sub-optimal solution for your MIP model (for a larger instance)?

If your question is about improving the performance then you should first print (and share) the CPLEX status file which can be printed by setting the following options:

  • Solvers General option 'Solver listing messages' to 'All'
  • CPLEX option 'MIP display' to 'Nth node + info on node cuts'

The CPLEX status file will be printed in the log folder.

Thanks for your reply.

“Did you observe that CPLEX returned a sub-optimal solution for your MIP model (for a larger instance)?”

This is exactly what I meant. I checked the solution given by CPLEX and compared it with what the solution obtained (for the same large problem instance) by a heuristic. The value of the obj function (returned) by CPLEX is larger than that from the heuristic!.

Userlevel 3

How did you check that the heuristic solution is a feasible solution for the MIP?

If the solution of the heuristic is feasible then I would have to investigate the project to help you further. Would it be possible to add your project here, preferably after adding it to a zip file, or send it to our support by email if your project contains sensitive information?

I can check a solution feasibility by turning the solution into a graphical representation.

I emailed the project to support. Thanks again for your help.

Further information…

I examined the solution returned by the CPLEX for a larger instance.
The model I am trying to solve, among many other decision variables, has a binary variable, let say Xr where sum Xr=1 for r=1,2,3,4.
In the CPLEX final solution (supposedly optimal solution), X3=1. However if X4=1 then a less expensive solution is obtained. Don’t understand why CPLEX is unable to find and use X4=1.
Other factors may also contribute to this problem I am sharing with you here.
 

Userlevel 3

Which case did you use for the larger instance for which you obtained a sub-optimal solution?

Do you have the heuristic solution available in the AIMMS model? Is it saved in one of the cases? Otherwise, how can I verify this heuristic solution or compare it to the solution found by AIMMS?

Hi Marcel,

The solution provided by the heuristic need to be transformed into a solution similar to that generate by AIMMS I guess. So I manually calculated the values of the key decision variables (the binary ones) and emailed it to support.

Hope this would be enough to build the “heuristic solution”.

Many thanks.

Hi Marcel,

I is possible that the discrepancy between the results obtained from CPLEX and my heuristic for the problem that I am investigating be related to my formulation. Here is my reason:

As mentioned above after examining the CPLEX solution (for a larger instance) I realise that for a binary variable AIMMS is not picking up the right value that result in lower objective function value. I reformulate that part of the model. The new formulation become harder to solve even for small instances. For larger instance (I tested earlier), solver terminated after 44948 seconds and reported the best LP (1623792848) and best solution (2789389756). The CPLEX best solution cost is reasonable now and it is in line with and close to what heuristic has found (2779810667). The optimality Gap is quite large (41%) and I need to get the optimal solution for this problem instance and compare it to heuristic result to confirm correctness of the formulation .

Question (1): Is there any way performance of the CPLEX can be improved in this case i.e., reducing the CPLEX computational time and closing the gap?

Questions (2): If CPLEX performance can not be improved in this case then is there any way I can prevent the solver being terminated and run the CPLEX for a couple days hoping it will close the gap at the end? 

Below is a summary of the information printed on AIMMS progress report for the larger instance:

#Constraints: 2090837

#Variables: 1127631 (68955  INT)

#nonzeros: 6723616

Iterations: 936708

Best LP: 1623792848

Best solution: 2789389756

Warning: After 936708 iterations CPLEX 12.9 found an integer solution to LeastCostHS. The minimum found for TCost is 2789389755.56.

I have also attached CPLEX file.

Regards,

Userlevel 3

The model seems to have numerical issues, caused by large matrix coefficients. This can result in an sub-optimal solution or a solution that is not (completely) feasible. Improving the numerical stability of the model can be done by scaling the model. One way to do so it using the new Scaling Tool that was introduced in AIMMS 4.74; see the AIMMS Help (under Diagnostic Tools - Math Program Inspector) for more information. I used the Scaling Tool for a smaller instance and noticed that CPLEX found a slightly better solution after the model was scaled, unfortunately at the cost of an increased solving time.

The CPLEX 12.9 log that you attached shows that CPLEX terminated after encountering a singular basis. This is another symptom of numerical issues.

I would strongly recommend to improved the scaling of your model. It might also be useful to enable the CPLEX modeling assistance by setting the CPLEX option 'Data Check and Modeling Assistance’ to 'Assist’.

To improve the performance by CPLEX you could try the Tuning Tool, preferably for a small instance because it can take a large amount of time as the model will be solved multiple times by the Tuning Tool. However, I think that the best way to improve the performance is to look at the model formulation.

 

 

@Marcel Hunting

Dear Marcel; many thanks for your time and your advise. I will follow your advice step-by-step and will use the Tuning tool. I have used “Piecewise linear approximation” within an MIP. When I remove this part the model perform much better and the larger instance is solved to optimality (exactly same solution obtained by heuristic). Anyhow thanks again for your support and helps on this issue.

Regards,

Jean

Reply


Didn't find what you were looking for? Try searching on our documentation pages:

AIMMS Developer & PRO | AIMMS How-To | AIMMS SC Navigator