Decision Optimization

 View Only
Expand all | Collapse all

Cplex not reaching optimal solution

  • 1.  Cplex not reaching optimal solution

    Posted Wed January 04, 2023 07:40 AM
    Edited by System Fri January 20, 2023 04:15 PM
    Hi All,

    I am experiencing an issue with my cplex solution (MIP). The log reads as below;

    Tried aggregator 2 times.
    MIP Presolve eliminated 2193 rows and 11266 columns.
    MIP Presolve modified 4839 coefficients.Aggregator did 2 substitutions.

    Reduced MIP has 3282 rows, 34713 columns, and 505657 nonzeros.
    Presolve time = 1.06 sec.
    Clique table members: 2161.
    MIP emphasis: balance optimality and feasibility.
    MIP search method: dynamic search.
    Parallel mode: deterministic, using up to 2 threads.
    Root relaxation solution time = 0.04 sec.

     Nodes Cuts/
    Node Left Objective     IInf     Best    Integer    Best    Node   ItCnt  Gap

    0        0     infeasible                                                                   0


    Root node processing (before b&c):
    Real time = 0.16
    Parallel b&c, 2 threads Real time = 0.00
    Sync time (average) = 0.00
    Wait time (average) = 0.00
    -------
    Total (root+branch&cut) = 0.16 sec.
    Solution status = Optimal
    Solution value = 1.1383008422684283E22


    Although solution status says optimal. I see that its no where near optimum. Could you please share your views?



    Thanks,
    Shahul

    ------------------------------
    Shah
    ------------------------------
    #DecisionOptimization


  • 2.  RE: Cplex not reaching optimal solution

    IBM Champion
    Posted Wed January 04, 2023 11:53 AM
    When you say "nowhere near optimum", do you mean that you know a feasible solution with a better objective value?

    ------------------------------
    Paul Rubin
    Professor Emeritus
    Michigan State University
    ------------------------------



  • 3.  RE: Cplex not reaching optimal solution

    Posted Wed January 04, 2023 12:11 PM
    Edited by System Fri January 20, 2023 04:19 PM

    Hi Professor,

    The allocations are very poor. It's a leave allocation optimization of staffs of different groups. When ran individual groups, it gives desirable outcome but with all the groups we are getting minimal assignments which is weird. 

    I see 'infeasible' in the node log file (I showed above) under the objective column and it's exiting in 0.16 seconds. Can we conclude something from this?

    the log definitely seems some issues..?


    for a well run scenario earlier (for a group seperately), the log looks like below;

    MIP Presolve eliminated 387 rows and 1675 columns.
    MIP Presolve modified 869 coefficients.
    Reduced MIP has 580 rows, 2344 columns, and 33186 nonzeros.
    Presolve time = 0.07 sec.
    Clique table members: 146.
    MIP emphasis: balance optimality and feasibility.
    MIP search method: dynamic search.
    Parallel mode: deterministic, using up to 2 threads.
    Root relaxation solution time = 0.02 sec.

    Nodes Cuts/
    Node  Left  Objective     IInf  Best Integer  Best Node            ItCnt     Gap

    * 0+   0                                  3.08034e+13       3.39977e+23   626        ---
    * 0+   0                                  3.22124e+23       3.39977e+23   626     5.54%
    * 0+   0                                  3.32806e+23       3.39977e+23   626     2.15%
      0     0      3.32881e+23 22  3.32806e+23         Cuts: 26         757     0.02%

    Zero-half cuts applied: 1
    Gomory fractional cuts applied: 2

    Root node processing (before b&c):
    Real time = 0.13
    Parallel b&c, 2 threads:
    Real time = 0.00
    Sync time (average) = 0.00
    Wait time (average) = 0.00
    -------
    Total (root+branch&cut) = 0.13 sec.

    Solver Version = 11.0.0
    Cplex status = OptimalTol
    NumericalEmphasis = false
    Solution status = Optimal
    Solution value = 3.328061358153315E23


    Thanks
    ------------------------------
    Shah
    ------------------------------



  • 4.  RE: Cplex not reaching optimal solution

    IBM Champion
    Posted Wed January 04, 2023 02:53 PM

    Is this a maximization or minimization problem?

    The first node log does seem to indicate that the full model is infeasible. Were the "solution status" and "solution value" lines written by your code and, if so, how did you get the values ("Optimal" and "1.1383008422684283E22")? Were you able to recover the alleged solution (get the values of the decision variables)?



    ------------------------------
    Paul Rubin
    Professor Emeritus
    Michigan State University
    ------------------------------



  • 5.  RE: Cplex not reaching optimal solution

    Posted Wed January 04, 2023 04:19 PM
    Thanks Professor.

    this is a maximization problem.

    solution status and solution value is printed after calling the solve method.

    yes it makes hard to understand the behavior as it says solution is optimal with objective value.

    also I'm able to get the values of variables and majority of them is 0's wherein we would expect it to be 1's at optimality.

    what could be done potentially to resolve this?


    thanks

    ------------------------------
    Shah
    ------------------------------



  • 6.  RE: Cplex not reaching optimal solution

    Posted Wed January 04, 2023 04:30 PM
    If you approve , I can send the log/lp files for reference….



    thanks

    ------------------------------
    Shah
    ------------------------------



  • 7.  RE: Cplex not reaching optimal solution

    IBM Champion
    Posted Wed January 04, 2023 06:00 PM
    I'm not sure what the log files would contain beyond what you have already shown. If you want to post the .lp file for the original problems (all groups in a single model), I can try to run it and see if the log results are the same.

    Am I correct to assume that when you solve all groups at once, there are constraints that span multiple groups? If so, it would not be surprising that solving one group at a time would produce better results than solving all groups at once. As a simple example, suppose I have two jobs to do, an employee who can do one job at cost $1K, and a consultant who can do one job at cost $5M. If I find the optimal allocation of just the first job, it goes to the employee at cost $1K. The same is true if I just solve for the second job. When I solve for both jobs, the cost is $5,001,000, not $2K. So I have to ask how you can be sure that the all-groups solution is suboptimal?

    ------------------------------
    Paul Rubin
    Professor Emeritus
    Michigan State University
    ------------------------------



  • 8.  RE: Cplex not reaching optimal solution

    Posted Thu January 05, 2023 01:36 AM
    Thanks Professor,

    thats because each groups have their own seperate limits. for eg: staff in cat A can have 10 people go on leave and cat B can have its 15 people can go on leave and so on. That means this limits are not overlapping. Just that we solve it at once.

    ------------------------------
    Shah
    ------------------------------



  • 9.  RE: Cplex not reaching optimal solution

    IBM Champion
    Posted Thu January 05, 2023 02:18 PM
    Okay, then there is a simple way to diagnose this. Solve each group's individual model and record the solutions. In the combined model, fix each variable to its value in the single-group solution by setting lower bound = upper bound = optimal value. Now solve the modified combined model. Either it will tell you the composite solution is infeasible or it will declare it optimal and give you an objective value. If the solution is infeasible, use the conflict refiner to find an irreducible conflict. One or more of the constraints involved in the conflict are likely to be incorrectly formulated. If the solution is optimal but the objective value is below the actual optimum (sum of the individual objective values), check the formulation of the objective function.

    ------------------------------
    Paul Rubin
    Professor Emeritus
    Michigan State University
    ------------------------------



  • 10.  RE: Cplex not reaching optimal solution

    Posted Fri January 06, 2023 12:57 AM
    Edited by System Fri January 20, 2023 04:40 PM
    Thanks again.

    Also can I ask you if there can be any relation to the cplex version 11.0.0 which is being used in our server, which is very old?

    I'm here trying to debug a solution developed a decade ago.





    ------------------------------
    Shah
    ------------------------------



  • 11.  RE: Cplex not reaching optimal solution

    IBM Champion
    Posted Fri January 06, 2023 02:01 PM
    Well, I would definitely recommend updating to the current version (particularly since I'm not the one who would have to pay for the upgrade). ;-) That said, I would be surprised if the problem was your use of version 11.

    ------------------------------
    Paul Rubin
    Professor Emeritus
    Michigan State University
    ------------------------------