Skip to content

Gurobi 12.0.1 different (and much slower) than 12.0.0 #267

Open

Description

@4er4er4er

The attached Gurobi_netflowcompl.zip appears to generate a quite different problem for Gurobi 12.0.0 (20241119) than for 12.0.1 (20250429) -- with considerable advantage to 12.0.0. Here's the relevant problem information from the logs:

*** 12.0.0
Optimize a model with 247 rows, 4236 columns and 2762 nonzeros

Model has 2760 simple general constraints
  184 AND, 368 OR, 2208 INDICATOR
Model has 1 general nonlinear constraint (0 nonlinear terms)
Variable types: 1658 continuous, 2578 integer (0 binary)

Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [8e-01, 1e+00]
  Bounds range     [1e+00, 4e+04]
  RHS range        [1e+02, 1e+03]
  GenCon rhs range [1e-04, 6e+02]
  GenCon coe range [1e+00, 1e+00]

Presolve added 1655 rows and 0 columns
Presolve removed 0 rows and 2396 columns
Presolved: 1902 rows, 1840 columns, 7360 nonzeros
Variable types: 1472 continuous, 368 integer (368 binary)

*** 12.0.1
Optimize a model with 247 rows, 4236 columns and 2762 nonzeros

Model has 2576 simple general constraints
  184 AND, 368 OR, 2024 INDICATOR
Model has 1 general nonlinear constraint (0 nonlinear terms)
Variable types: 1843 continuous, 2393 integer (0 binary)

Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [8e-01, 1e+00]
  Bounds range     [1e+00, 4e+04]
  RHS range        [1e+02, 1e+03]
  GenCon rhs range [3e+02, 6e+02]
  GenCon coe range [1e+00, 1e+00]

Presolve added 2023 rows and 0 columns
Presolve removed 0 rows and 2212 columns
Presolved: 2270 rows, 2024 columns, 7912 nonzeros
Variable types: 1472 continuous, 552 integer (552 binary)

AMPL's show_stats listing is the same for both,

1288 variables, all nonlinear
245 algebraic constraints, all linear; 2576 nonzeros
	245 inequality constraints
185 logical constraints
1 nonlinear objective; 1288 nonzeros.

and they get the same optimal values:

Gurobi 12.0.0: optimal solution; objective 54284.70288
806901 simplex iterations
22627 branching nodes

Gurobi 12.0.1: optimal solution; objective 54284.70288
1.52992e+07 simplex iterations
209168 branching nodes
absmipgap=4.64617, relmipgap=8.5589e-05

The complete logs Gurobi12.0.0.txt and Gurobi12.0.1.txt are also attached.

This is an artificial example for a talk, but I am reporting it in case it might be evidence for some more serious problem.

Activity

  1. glebbelov commented on Jun 17, 2025

    @glebbelov
    Contributor

    This is due to a change on Feb 21 that introduced exact context propagation for count. While previously,

    subject to Limit_Used:
      atmost max_arcs {(i,j) in ARCS}
        (sum {p in PRODUCTS} Flow[p,i,j] > 0);

    was linearized as

    var {(i,j) in ARCS} b_aux binary;
    subject to Limit_Used__LIN__OLD:
      sum {(i,j) in ARCS} b_aux[i, j] <= max_arcs
      && forall {(i,j) in ARCS}
        (b_aux[i, j] <==> sum {p in PRODUCTS} Flow[p,i,j] > 0);

    where each equivalence resulted in 2 indicator constraints.

    After the Feb 21 change, the equivalence was simplified to a single indicator

        b_aux[i, j]==0 ==> sum {p in PRODUCTS} Flow[p,i,j] <= 0

    I believe this was motivated by an example from Filipe.

    Restoring the old behavior, with 2x as many indicators from the atmost, returns the fast solving. However, generalizing this to all conditional inequalities proved bad on the above example. Thus, added the following options, defaulting to the 20241119 behavior:

    cvt:pre:ctx2count (ctx2count)
          Propagate exact context into atleast/atmost/exactly, count and numberof
          expressions, vs mixed. Bitwise OR of the following values:
    
          1 - atleast/atmost/exactly, count
          2 - numberof with constant total
          4 - numberof with variable total.
    
          Default 0, see #267.
    
    cvt:pre:ctx2ineq (ctx2ineq)
          0/1*: Propagate exact context into conditional inequalities, vs mixed.
          See #267.
    

    But more research is needed. Probably the best solution would be to deduce the exact domain for each expression sum {p in PRODUCTS} Flow[p,i,j], in this model it is semi-continuous. This is #268.

  2. glebbelov commented on Jun 19, 2025

    @glebbelov
    Contributor

    This is released in 20250617.

    An intuitive explanation is that while the reduced reformulation is correct, it increases the solution space (some b_aux can be 1 but their sum is till 0). However it's unclear why the same intuition does not hold for cvt:pre:ctx2ineq.

    Running with cvt:eps=250 (corresponding to min_ship) slightly reduces solving time.

  3. glebbelov commented on Sep 12, 2025

    @glebbelov
    Contributor

    Almost halved the time by these modifications:

    minimize TotalCost:
       sum {p in PRODUCTS, (i,j) in ARCS} var_cost[p,i,j] * Flow[p,i,j] +
       sum {(i,j) in ARCS}
          if sum {p in PRODUCTS} Flow[p,i,j] != 0 then fix_cost[i,j];
    
    subject to Conservation {p in PRODUCTS, j in NODES}:
       sum {(i,j) in ARCS} Flow[p,i,j] + supply[p,j] >= 
       sum {(j,i) in ARCS} Flow[p,j,i] + demand[p,j];
    
    subject to Shipment_Limits {(i,j) in ARCS}:
      sum {p in PRODUCTS} Flow[p,i,j] = 0 or
      min_ship <= sum {p in PRODUCTS} Flow[p,i,j] <= capacity[i,j];
    
    subject to Limit_Used:
      atmost max_arcs {(i,j) in ARCS}
        (sum {p in PRODUCTS} Flow[p,i,j] != 0);

    2 parts here:

    1. Replacing exists by sum reduces the number of indicators. This alone reduces solving time from 35s to 30s (Mac M1 Pro, Gurobi 12.0.3).
    2. Replacing > 0 by != 0 further reduces time to 20s. I thought this should have produced equivalent reformulations in this case (Flow's are nonnegative), need to look (and add tests).

    In all 3 models, about 30k nodes are processed, so time must improve due to smaller/different LPs.

  4. added a commit that references this issue on Sep 15, 2025
  5. glebbelov commented on Sep 15, 2025

    @glebbelov
    Contributor

    Added option

    cvt:pre:ineq2bndeq
          0/1*: Preprocess reified inequality expr <= c, where c <
          lb(expr)+cvt:mip:eps, into ==, which works better on some
          benchmarks/solvers.
    

    which automatically achieves the best known Gurobi behaviour on the model

    var Flow {p in PRODUCTS, (i,j) in ARCS} >= 0, <= capacity[i,j];
    
    minimize TotalCost:
       sum {p in PRODUCTS, (i,j) in ARCS} var_cost[p,i,j] * Flow[p,i,j] +
       sum {(i,j) in ARCS}
          if sum {p in PRODUCTS} Flow[p,i,j] > 0 then fix_cost[i,j];
    
    subject to Conservation {p in PRODUCTS, j in NODES}:
       sum {(i,j) in ARCS} Flow[p,i,j] + supply[p,j] >= 
       sum {(j,i) in ARCS} Flow[p,j,i] + demand[p,j];
    
    subject to Shipment_Limits {(i,j) in ARCS}:
      sum {p in PRODUCTS} Flow[p,i,j] = 0 or
      min_ship <= sum {p in PRODUCTS} Flow[p,i,j] <= capacity[i,j];
    
    subject to Limit_Used:
      atmost max_arcs {(i,j) in ARCS}
        (sum {p in PRODUCTS} Flow[p,i,j] > 0);

    Note that CPLEX runs under 2s in this and some other configurations, however ctx2count=1 (the original issue here) increases solve time from 1.78s to 2.78s.

  6. glebbelov commented on Oct 2, 2025

    @glebbelov
    Contributor

    While complete reformulation seems better for inequality arguments, it is different for (dis)equalities where one context may be much harder. Adding the following:

    subject to Used_500:
      atleast 10 {(i,j) in ARCS}
        (sum {p in PRODUCTS} Flow[p,i,j] == 500);

    results in ctx2count=0 (default) about 20-30% slower than ctx2count=1, both for CPLEX and Gurobi. A solution might be to only propagate full context into argument inequalities.

  7. glebbelov commented on Oct 8, 2025

    @glebbelov
    Contributor

    Status update.

    1. The major change discussed here, ctx2count=0 for the original example, reverses its effect when declaring var Flow's integer with Gurobi, although keeps the effect with CPLEX. Thus, changing to ctx2count=7 default (which concerns also numberof).

    2. To emulate previous reformulations, use ctx2count=0, or more specifically, the new option ctx2bndeq=0 to pass mixed context into bound comparisons (only those seem to improve Gurobi's and CPLEX' behavior when reformulated in mixed context). However, this option is too general, it would also concern such comparisons not used from count (not relevant in the above example, but this deteriorates performance in other examples). To track only such comparisons used from count, some more technical work is needed.

    3. Some work done on this issue, such as option cvt:pre:ineq2bndeq, has improved performance, and ctx2count=7 does not waste much (25s vs 17s on M1 Pro; vice versa, 21s vs 25s with integer Flow's).

    4. As noticed by Pierre Bonami, the opposite-sense inequality sum {...} Flow[i,j] > 0.0001 is in general not redundant (although it is in this example, due to the Shipment_Limits). Still, it probably leads the solver to better cuts etc.

    5. The latter point also reminds us of cmp:mip:eps. Pierre confirmed that being 10x the feastol is the least reasonable value, which is true for most solvers, except cuOpt. We might think about making it dependant on feastol, or printing a warning whenever it's used and small compared to feastol.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

No labels
No labels

Type

No type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions