Decision Optimization

Decision Optimization

Delivers prescriptive analytics capabilities and decision intelligence to improve decision-making.

 View Only

  • 1.  C callable library: MIP performance seems highly dependent on how the problem has been instantiated

    Posted Sun July 18, 2021 08:04 AM
    Edited by System Admin Fri January 20, 2023 04:27 PM
    Hello,

    I have a binary integer program

    Max  cx
s.t. Ax = b
     x in {0,1}

    that can get instantiated in two ways:

    (Way 1)

    Create the LP relaxation

    Max  cx
s.t. Ax = b
     0 <= x <= 1


    That is, there is a call to CPXnewcols(env, lp, Ncol, obj, lb, ub, vartype, varname);

    where vartype entries are all 'C' denoting continuous variables.

    Solve this using call to CPXprimopt()

    Then, call

    CPXchgctype(env, lp, number_changed, indices, ctype);//here ctype is a char* of all entries 'B' denoting binary variables
    CPXchgprobtype(env, lp, CPXPROB_MILP);

    After this, call to CPXmipopt(env, lp) gives a log that looks thus:

    Version identifier: 12.10.0.0 | 2019-11-26 | 843d4de2ae
CPXPARAM_TimeLimit                               7200
Probing fixed 686 vars, tightened 296 bounds.
Probing time = 0.03 sec. (12.91 ticks)
Cover probing fixed 1 vars, tightened 354 bounds.
Clique table members: 7599.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 8 threads.
Root relaxation solution time = 0.05 sec. (17.51 ticks)

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

*     0+    0                            0.0000                           0.00%
      0     0    27600.3333   139        0.0000    27600.3333      474     ---
*     0+    0                          941.0000    27600.3333              ---
*     0+    0                         1033.0000    27600.3333              ---
      0     0    14396.2409   139     1033.0000     Cuts: 913      725     ---
      0     0     3173.5983   139     1033.0000     Cuts: 863      979  207.22%
      0     0     2654.4265   139     1033.0000     Cuts: 706     1179  156.96%
      0     0     1199.2878   139     1033.0000     Cuts: 454     1284   16.10%
      0     0     1192.9676   139     1033.0000     Cuts: 521     1355   15.49%
      0     0     1189.2662   139     1033.0000     Cuts: 151     1393   15.13%
      0     0     1185.0240   139     1033.0000      Cuts: 91     1428   14.72%
      0     0     1183.5318   139     1033.0000      Cuts: 50     1453   14.57%
      0     0     1183.5318   139     1033.0000      Cuts: 57     1479   14.57%
      0     0     1183.5276   139     1033.0000      Cuts: 30     1494   14.57%
      0     0     1183.5276   139     1033.0000     Cuts: 245     1539   14.57%
*     0+    0                         1042.0000     1183.5276            13.58%
Detecting symmetries...
      0     2     1183.5276    86     1042.0000     1173.1277     1539   12.58%
Elapsed time = 0.88 sec. (542.46 ticks, tree = 0.02 MB, solutions = 4)
*    24+    2                         1044.0000     1157.4561            10.87%
    293   187     1054.5067    51     1044.0000     1134.1228     2606    8.63%
   1073   688     1066.6562    60     1044.0000     1094.7462     7619    4.86%
   1999  1300     1057.9912    58     1044.0000     1083.8762    18334    3.82%
   2967  1854     1044.5000    44     1044.0000     1078.3558    26361    3.29%
   4168  2403     1046.7143    38     1044.0000     1076.3747    34221    3.10%
   5363  2945     1071.3246    49     1044.0000     1072.7077    45632    2.75%
   6765  3544     1044.9365    45     1044.0000     1070.1413    57361    2.50%
   7909  4055     1055.0520    70     1044.0000     1067.1077    67591    2.21%
   9249  4548     1054.8801    49     1044.0000     1065.7896    78924    2.09%
  14690  6779     1050.5365    51     1044.0000     1060.4964   117756    1.58%
Elapsed time = 5.95 sec. (3643.50 ticks, tree = 7.46 MB, solutions = 5)
  20724  8609     1049.2143    44     1044.0000     1056.1878   155672    1.17%
  26725 10006     1047.2019    52     1044.0000     1053.7070   190282    0.93%
  33252 10815     1050.8780    52     1044.0000     1051.8889   217586    0.76%
  39021 10649     1046.5000    45     1044.0000     1050.8790   244866    0.66%
  44758  9767     1044.2500    47     1044.0000     1049.1667   266144    0.49%
  50591  8413     1047.0000    37     1044.0000     1047.4889   296666    0.33%
  56392  7662     1044.8889    56     1044.0000     1046.8878   320280    0.28%​
...
    As can be observed, it takes quite a bit of nodes to reduce the gap.

    (Way 2)

    In this way, I directly create the binary integer program thus:

    Max  cx
s.t. Ax = b
     x in {0,1}​

    and solve it directly by a call to CPXmipopt(env, lp)

    That is, there is a call to CPXnewcols(env, lp, Ncol, obj, lb, ub, vartype, varname);
    where the values of vartype are 'B' indicating binary variables being added to the problem.

    This solve the problem much quicker. See log:

    Version identifier: 12.10.0.0 | 2019-11-26 | 843d4de2ae
CPXPARAM_TimeLimit                               7200
Tried aggregator 3 times.
MIP Presolve eliminated 2596 rows and 791 columns.
MIP Presolve modified 8805 coefficients.
Aggregator did 51 substitutions.
Reduced MIP has 989 rows, 642 columns, and 3278 nonzeros.
Reduced MIP has 447 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.03 sec. (14.56 ticks)
Probing fixed 50 vars, tightened 27 bounds.
Probing time = 0.02 sec. (5.42 ticks)
Cover probing fixed 0 vars, tightened 53 bounds.
Tried aggregator 2 times.
MIP Presolve eliminated 116 rows and 64 columns.
MIP Presolve modified 379 coefficients.
Aggregator did 1 substitutions.
Reduced MIP has 872 rows, 577 columns, and 2861 nonzeros.
Reduced MIP has 390 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.03 sec. (2.02 ticks)
Probing time = 0.02 sec. (2.55 ticks)
Cover probing fixed 0 vars, tightened 26 bounds.
Tried aggregator 1 time.
Detecting symmetries...
MIP Presolve eliminated 1 rows and 0 columns.
MIP Presolve modified 355 coefficients.
Reduced MIP has 871 rows, 577 columns, and 2858 nonzeros.
Reduced MIP has 390 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.02 sec. (1.73 ticks)
Probing fixed 2 vars, tightened 6 bounds.
Probing time = 0.02 sec. (3.46 ticks)
Cover probing fixed 0 vars, tightened 7 bounds.
Clique table members: 2129.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 8 threads.
Root relaxation solution time = 0.00 sec. (2.67 ticks)

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

      0     0     1133.9133   123                   1133.9133      185
      0     0     1081.3978   123                   Cuts: 317      316
*     0+    0                         1029.0000     1081.3978             5.09%
      0     0     1059.3933   123     1029.0000     Cuts: 317      450    2.95%
      0     0     1057.2601   123     1029.0000     Cuts: 285      551    2.75%
*     0+    0                         1042.0000     1057.2601             1.46%
      0     0     1055.8400   123     1042.0000     Cuts: 255      645    1.33%
      0     0     1053.8510   123     1042.0000     Cuts: 211      727    1.14%
Detecting symmetries...
      0     0     1052.9856   123     1042.0000     Cuts: 200      812    1.05%
      0     0     1052.8992   123     1042.0000     Cuts: 160      870    1.05%
      0     0     1052.8992   123     1042.0000      Cuts: 84      902    1.05%
      0     0     1052.8992   123     1042.0000      Cuts: 11      917    1.05%
      0     0     1052.8992   123     1042.0000      Cuts: 42      943    1.05%
Detecting symmetries...
      0     2     1052.8992    35     1042.0000     1052.8992      943    1.05%
Elapsed time = 0.45 sec. (161.64 ticks, tree = 0.02 MB, solutions = 2)
*   252    66      integral     0     1044.0000     1045.7143     1907    0.16%

Clique cuts applied:  11
Cover cuts applied:  2
Implied bound cuts applied:  122
Flow cuts applied:  8
Mixed integer rounding cuts applied:  77
Zero-half cuts applied:  1
Lift and project cuts applied:  2
Gomory fractional cuts applied:  11

Root node processing (before b&c):
  Real time             =    0.45 sec. (161.26 ticks)
Parallel b&c, 8 threads:
  Real time             =    0.06 sec. (28.45 ticks)
  Sync time (average)   =    0.02 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =    0.52 sec. (189.71 ticks)​


    Looking at the two logs, it appears that the preprocessing path taken by the two ways differ significantly. In (Way 2), the aggregator is called amongst others, for instance. Then, the path taken within the branch and bound tree also differs significantly.

    Is there a way to figure out why this is happening and how this can be avoided?

    In each instance, I call CPLEX using default parameters except for the time limit of 7200 seconds in both cases.

    Thanks.

    ------------------------------
    CPLEX User
    ------------------------------
    #DecisionOptimization


  • 2.  RE: C callable library: MIP performance seems highly dependent on how the problem has been instantiated

    Posted Sun July 18, 2021 08:10 AM
    Attached is the binary mixed integer program as a .lp file.

    ------------------------------
    CPLEX User
    ------------------------------

    Original Message


  • 3.  RE: C callable library: MIP performance seems highly dependent on how the problem has been instantiated

    Posted Sun July 18, 2021 02:25 PM
    Presolving a MIP lets the presolver make certain reductions based on the fact the specific variables are integer/binary. Those same reductions cannot be made when presolving the LP relaxation. So the only way I can think of to improve the first approach is to play around with some of the presolve settings before solving the MIP. Perhaps turning on repeat presolve might help?

    It's unclear to me what you are trying to achieve by solving the LP relaxation first. You are not seeding the MIP with a feasible solution (the MIP node log in the first approach starts with an incumbent value of 0) and, as noted above, the presolve step is weaker. What is the motivation for the first approach?

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

    Original Message


  • 4.  RE: C callable library: MIP performance seems highly dependent on how the problem has been instantiated

    Posted Sun July 18, 2021 03:05 PM
    Edited by System Admin Fri January 20, 2023 04:48 PM
    Paul,

    There could be a variety of reasons for this workflow. One could be adding user generated cuts in an attempt to improve the bound before converting the variables from continuous to binary / integer and submitting to cplex MIP solver. One may want to store the root node bound via this workflow instead of preferring to write a callback function to extract that information after submitting the problem to CPXmipopt.

    Regardless of the reasons, on writing out the .lp file before the call to CPXmipopt, in both the approaches the exact same .lp file gets generated. Hence, regardless of the history, the user can justifiably feel aggrieved that one approach performs significantly worse off than the other. After all, the same problem instance is being presented to the MIP Solver in both cases. Also, both cases run with the same default CPLEX settings (excepting for the time limit of 7200 seconds that is anyway common in both cases, as can be seen from the log.)

    So, it seems to me Way 1 of my OP seems to mess up some MIP settings behind the scenes: calls to CPXprimopt, CPXchgctype,CPXchgprobtype and then finally, the call to CPXmipopt  seem to affect what should otherwise be the straightforward default performance on directly calling CPXmipopt without the former three calls. It would help if CPLEX developers confirm what could be happening under the hood in these two differing workflows.

    ------------------------------
    CPLEX User
    ------------------------------

    Original Message


  • 5.  RE: C callable library: MIP performance seems highly dependent on how the problem has been instantiated
    Best Answer

    Posted Sun July 18, 2021 04:30 PM
    Just to be clear, the .lp file is the problem as submitted by the user. It does not include any presolve reductions, so it is not surprising (nor probitive) that the .lp file is the same in both cases.

    Have you tried setting the advanced start switch (CPXPARAM_Advance in the C API) to 0 before trying to solve the MIP in the first approach? I'm not sure it would resolve the problem, but it is easy to test (along with maybe trying the repeat presolve parameter).

    Regarding a hypothetical user's reaction to the difference, it is known (if not entirely appreciated) that things as subtle as the order that constraints are entered into a model can affect how (and how quickly) CPLEX, or any solver of which I am aware, solves a MIP model. So the user is free to feel aggrieved that this difference occurs, but the not-entirely-benevolent gods of discrete optimization are unlikely to take note.

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

    Original Message


  • 6.  RE: C callable library: MIP performance seems highly dependent on how the problem has been instantiated

    Posted Sun July 18, 2021 11:54 PM
    Edited by System Admin Fri January 20, 2023 04:48 PM
    Paul:

    Setting CPXPARAM_Advance to 0 did indeed do the trick in Way 1. 

    Just so I understand, the reason why this works is that in solving the LP before converting the problem to MIP, a primal optimal basis has to get generated. Then, after conversion to MIP, this basis is used as an advanced basis for the root node LP relaxation of the MIP. That seems to prevent opportunities for the MIP to do presolvings and other stuff that it could have done otherwise. These "presolvings and other stuff" are precisely what Way 2 accomplishes. There is no starting LP basis available for the MIP in Way 2. So, by setting CPXPARAM_Advance to 0 we are trying to mimic Way 2 as much as we can in Way 1.

    Is this a reasonable understanding of what could be going on?

    Thanks for your inputs. I certainly learn something new each day with CPLEX!

    ------------------------------
    CPLEX User
    ------------------------------

    Original Message


  • 7.  RE: C callable library: MIP performance seems highly dependent on how the problem has been instantiated

    Posted Mon July 19, 2021 12:03 PM
    First off, you are quite welcome. I'm still learning new things about CPLEX myself ... and then having to unlearn some of them, if they turn out to be wrong, or have changed in the latest version, or no longer work due to misalignment of the planets. :-)

    As to your understanding, you are correct (to the best of my knowledge). Solving the LP will definitely generate a basis (presumably for an optimal solution to the relaxation, unless the model turns out to be infeasible or too chewy to solve). With the default (on) setting for the advanced start switch, I think CPLEX will use (or at least try to use) the advanced basis to start solving the root node LP of the MIP. I say "try" in part because I think there is some amount of presolving of the MIP going on even with the first approach, and so the LP basis might be for a somewhat different model than the original LP relaxation. I'm not sure in that case whether CPLEX tries to "repair" the basis and use it, but I suspect it does. I might be wrong about whether CPLEX does any presolving at all in this case, but I would assume that it would, particularly since integrality restrictions add information that can be used to shrink the problem in many cases.

    This is all a bit speculative on my part. There's a lot of stuff going on under the hood that we mere mortals are not entirely privy to, either because it's a trade secret or because too many details would cause our heads to explode (a possible legal liability for IBM).

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

    Original Message