Decision Optimization

Decision Optimization

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


#Analytics
#DecisionOptimization
#DecisionOptimization
 View Only

  • 1.  Performance decreases when using indicator constraints

    Posted 09/20/17 05:46 AM

    Originally posted by: BenjaminKlotz


    Hi,

    I am trying to speed up the solving of a MIP.

    The MIP contains a lot of "conditional constraints" that should only be enforced if a certain set of binary variables are all true.

    Formerly, I created these conditional constraints using the big-M method. The coefficients for the big-M notation have been chosen optimally.

    I now tried to replace the big-M method by using indicator constraints. For each conditional constraint I added a binary indicator variable x. I then added linear constraints to force the binary variable x to true, when the all the binary variables that influence the activation of the conditional constraint are true.

    Unfortunately, changing to the indicator constraints decreased increased the runtime significantly on a large set of instances (factor 2 to 10).   
    Even using both the indicator constraints and the big-M method simultaneously decreased increased the runtime  similarly.

    Can anybody give any pointers as to why the indicator constraints, which are supposed to help CPLEX, slow it down so much?

     

    CPLEX outputs:

    big-M 
     (D) CPLEX:  CPXPARAM_Simplex_Tolerances_Optimality           1.0000000000000001e-09
 (D) CPLEX:  CPXPARAM_Simplex_Tolerances_Feasibility          1.0000000000000001e-09
 (D) CPLEX:  CPXPARAM_TimeLimit                               590
 (D) CPLEX:  CPXPARAM_Threads                                 1
 (D) CPLEX:  CPXPARAM_Parallel                                1
 (D) CPLEX:  CPXPARAM_MIP_Tolerances_MIPGap                   0.02
 (D) CPLEX:  CPXPARAM_MIP_Limits_TreeMemory                   15360
 (D) CPLEX:  1 of 1 MIP starts provided solutions.
 (D) CPLEX:  MIP start 'm1' defined initial solution with objective 23370.0000.
 (D) CPLEX:  Probing fixed 1399 vars, tightened 33 bounds.
 (D) CPLEX:  Probing changed sense of 120 constraints.
 (D) CPLEX:  Probing time = 1.37 sec. (706.50 ticks)
 (D) CPLEX:  Cover probing fixed 0 vars, tightened 13 bounds.
 (D) CPLEX:  Clique table members: 36033.
 (D) CPLEX:  Tightened 4 constraints.
 (D) CPLEX:  MIP emphasis: balance optimality and feasibility.
 (D) CPLEX:  MIP search method: dynamic search.
 (D) CPLEX:  Parallel mode: none, using 1 thread.
 (D) CPLEX:  Root relaxation solution time = 0.44 sec. (238.29 ticks)
 (D) CPLEX:  
 (D) CPLEX:          Nodes                                         Cuts/
 (D) CPLEX:     Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap
 (D) CPLEX:  
 (D) CPLEX:  *     0+    0                        23370.0000     9700.0000            58.49%
 (D) CPLEX:        0     0    23056.0000   190    23370.0000    23056.0000     2660    1.34%
 (D) CPLEX:  
 (D) CPLEX:  Root node processing (before b&c):
 (D) CPLEX:    Real time             =    1.99 sec. (1053.15 ticks)
 (D) CPLEX:  Sequential b&c:
 (D) CPLEX:    Real time             =    0.00 sec. (0.00 ticks)
 (D) CPLEX:                            ------------
 (D) CPLEX:  Total (root+branch&cut) =    1.99 sec. (1053.15 ticks)

     

     

    indicator constraints 
     (D) CPLEX:  CPXPARAM_Simplex_Tolerances_Optimality           1.0000000000000001e-09
 (D) CPLEX:  CPXPARAM_Simplex_Tolerances_Feasibility          1.0000000000000001e-09
 (D) CPLEX:  CPXPARAM_TimeLimit                               574
 (D) CPLEX:  CPXPARAM_Threads                                 1
 (D) CPLEX:  CPXPARAM_Parallel                                1
 (D) CPLEX:  CPXPARAM_MIP_Tolerances_MIPGap                   0.02
 (D) CPLEX:  CPXPARAM_MIP_Limits_TreeMemory                   15360
 (D) CPLEX:  Reduced MIP has 241398 rows, 116399 columns, and 637704 nonzeros.
 (D) CPLEX:  Reduced MIP has 83459 binaries, 770 generals, 0 SOSs, and 34141 indicators.
 (D) CPLEX:  Presolve time = 1.10 sec. (3128.09 ticks)
 (D) CPLEX:  1 of 1 MIP starts provided solutions.
 (D) CPLEX:  MIP start 'm1' defined initial solution with objective 23370.0000.
 (D) CPLEX:  Probing fixed 1944 vars, tightened 215 bounds.
 (D) CPLEX:  Probing changed sense of 313 constraints.
 (D) CPLEX:  Probing time = 2.31 sec. (834.77 ticks)
 (D) CPLEX:  Cover probing fixed 0 vars, tightened 32 bounds.
 (D) CPLEX:  Clique table members: 41959.
 (D) CPLEX:  MIP emphasis: balance optimality and feasibility.
 (D) CPLEX:  MIP search method: dynamic search.
 (D) CPLEX:  Parallel mode: none, using 1 thread.
 (D) CPLEX:  Root relaxation solution time = 0.45 sec. (222.43 ticks)
 (D) CPLEX:  
 (D) CPLEX:          Nodes                                         Cuts/
 (D) CPLEX:     Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap
 (D) CPLEX:  
 (D) CPLEX:  *     0+    0                        23370.0000     8356.0000            64.24%
 (D) CPLEX:        0     0    22226.0000   510    23370.0000    22226.0000     3368    4.90%
 (D) CPLEX:        0     0    23029.4667   696    23370.0000     Cuts: 143     4330    1.46%
 (D) CPLEX:  
 (D) CPLEX:  Clique cuts applied:  3
 (D) CPLEX:  Implied bound cuts applied:  45
 (D) CPLEX:  Zero-half cuts applied:  6
 (D) CPLEX:  Gomory fractional cuts applied:  1
 (D) CPLEX:  
 (D) CPLEX:  Root node processing (before b&c):
 (D) CPLEX:    Real time             =    5.26 sec. (4887.76 ticks)
 (D) CPLEX:  Sequential b&c:
 (D) CPLEX:    Real time             =    0.00 sec. (0.00 ticks)
 (D) CPLEX:                            ------------
 (D) CPLEX:  Total (root+branch&cut) =    5.26 sec. (4887.76 ticks)

     

     

     


    #CPLEXOptimizers
    #DecisionOptimization


  • 2.  Re: Performance decreases when using indicator constraints

    Posted 09/22/17 05:06 PM

    I assume when you "decreased" run time you actually mean increased? The key is probably this statement: "The coefficients for the big-M notation have been chosen optimally." A general rule of thumb (I think -- at least this was said to be true in earlier versions of CPLEX) is that indicators are better than big M with inflated values of M but not as good as big M with tight, problem-specific values of M. As to why the combination of the big M and indicator constraints is slower than just big M, it's probably that the indicator constraints do not help and perhaps add to the size of the model or the work CPLEX does per iteration.

    If you have tight values of M (as you seem to) and are unhappy with the performance of the big M model, you could consider combinatorial Benders decomposition (Codato and Fischetti, "Combinatorial Benders' Cuts for Mixed-Integer Linear Programming", Operations Research 54, 2006). I've had good luck with that in a few cases, but there is no guarantee of improvement, as Benders decomposition adds additional work and takes an "outer approximation" approach to solving the original problem (progressively tightened relaxations).

     


    #CPLEXOptimizers
    #DecisionOptimization


Related Content