Gurobi 12.0.1 different (and much slower) than 12.0.0

[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.

[glebbelov]

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.

[glebbelov]

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.

[glebbelov]

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.

[glebbelov]

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.

[glebbelov]

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.