Benchmarking & Parameter Tuning
Algorithm Engineering — T05
Dr. Dominik Krupke
Benchmarking & Parameter Tuning
You changed the model and it got faster on your three test instances. Did it actually get better?
What this tutorial is about
Starting CP-SAT solver v9.15.6755
Setting number of workers to 24
Initial optimization model 'multiple_knapsack':
#Variables: 560 (#bools: 560)
#kLinearN: 144 (#terms: 1'120)
Starting presolve at 0.00s
[Symmetry] #generators: 7, average support size: 8
presolved: 560 vars, 144 constraints
Starting search at 0.01s with 24 workers
#1 0.01s best:1891 next:[1892,3797] no_lp
#5 0.01s best:1939 next:[1940,2271] core
#10 0.01s best:2226 next:[2227,2271] default_lp
#13 0.02s best:2266 next:[2267,2271] reduced_costs
#Bound 0.05s best:2267 next:[2268,2270] probing_max_lp
#15 0.08s best:2269 next:[2270,2270] default_lp
#16 0.18s best:2270 next:[] graph_var_lns
Solutions (7) Num Rank
'no_lp': 3 [1,7]
'quick_restart': 1 [3,3]
'quick_restart_no_lp': 3 [2,5]
CpSolverResponse summary:
status: OPTIMAL
objective: 2270
best_bound: 2270
gap_integral: 0.44563
Benchmarking
Reading the log
Parameter tuning
- Is a “win” real, or three lucky instances?
- Which metric and plot fit the goal?
- Timeouts, variance, and the right instance set.
- What did the solver actually do?
- Which strategies moved the bounds?
- Where is the easy tuning win?
- Tuning as a search problem.
- Grid, random, then model-based.
- A hands-on recipe to run it.
Benchmarking is Hard
How we wish things looked
- Runtime grows smoothly with instance size.
- One algorithm dominates everywhere.
- Pick the lowest curve and you are done.
What is more likely
- The curves cross: A wins small, B medium, C large.
- “Best” needs a fixed instance-size range.
No-free-lunch (Wolpert & Macready, 1997): over all instances, no algorithm beats another; a gain on one class costs you on another.
And we don’t even have clear curves
- We never see the curve, only one run per instance.
- NP-hard runtimes vary by orders of magnitude.
- A trend is there, but no single instance settles who wins.
Too few instances, unevenly spread
- Instances cluster and leave gaps.
- Tight confidence band where dense, wide where sparse.
- A trend line across a gap is wishful interpolation.
Sometimes, we may even have unknowns
No timelimit? Run forever.
Remove timeouts? Drop the hard instances.
Substitute timeouts? We don’t know if they are 1s from done or stuck forever. We either over or underestimate the mean.
Be very careful with the impact of how you handle such unknowns.
Sometimes, we don’t have an n (x-axis)
A SAT formula’s hardness is not captured by one clean size: variable and clause counts say surprisingly little. Dozens of features are used instead. No simple scalability plot.
Problem size
- variables, clauses, ratio
- reciprocals, powers of the ratio
Balance
- pos/neg literals per clause
- unary / binary / ternary fractions
Graph structure
- variable-clause graph degrees
- variable graph degrees
- clause graph degrees
- clause graph clustering coefficient
Horn proximity
- fraction of Horn clauses
- Horn occurrences per variable
LP relaxation
- LP objective value
- integer slack of variables
Probing (run briefly, measure)
- DPLL unit-propagation counts
- search-space size estimate
- local search (SAPS / GSAT) trajectory
- clause-learning length
- survey-propagation bias
Feature families from SATzilla (Xu, Hutter, Hoos, Leyton-Brown). The point is the count, not the contents: no single axis captures hardness.
And often, we don’t even have a clear target! (y-axis)
Benchmarking optimization algorithms is inherently multi-objective over time and quality.
And don’t get us started on multi-objective optimization problems…
What to measure, and when it lies
| KPI | Needs | Good when | Misleads when |
|---|---|---|---|
| Raw runtime | everything solved | pure speed, no timeouts | one timeout breaks the mean |
| Runtime / fastest | everything solved | mixed instance difficulty | still dies under censoring |
| PAR2 / PAR10 | a time limit | timeouts are the norm | penalty factor is arbitrary |
| Objective / best-known solution | always available | no optimum in reach | “best known” shifts over time |
| Objective / best-known bound | a dual bound | want a true gap ceiling | loose bound inflates the gap |
| Objective / optimum | oracle knowledge | small or pre-solved set | almost never available |
| Bound / best-known solution | a dual bound | judging proof progress | weak bound says little |
| Proven optimality gap | bound + incumbent | solver nearly closes it | meaningless while bound is weak |
Tame outliers at the source: hand every algorithm a naive fallback (a quick greedy) so a run that finds nothing, or returns something absurd, reports the fallback instead of a value that skews the aggregate.
One number for the whole trajectory: integral metrics
A milestone metric captures one instant. An integral scores the entire anytime curve: reward a solver for closing the gap early and keeping it closed.
- Primal integral: area under the primal gap (incumbent vs. best known). Small means good solutions early.
- Dual integral: area under the dual gap (bound vs. best known). Small means proof progress early.
- Primal-dual integral: the shaded band between bound and incumbent; it shrinks only as the true gap closes.
CP-SAT reports a gap integral: the integral of \(\log(1 + \text{gap})\) over time (primal-dual gap). Smaller is better.
Which config performed better?
Both prove the optimum at 24 s — time-to-optimality is a tie.
The primal integral (area under the gap curve) breaks the tie: A converged faster.
Summarizing a set: which “average”?
- Arithmetic mean: a few hard instances pull it into the tail; a timeout leaves no finite value to average.
- Median + IQR: the typical instance and its spread; unaffected by outliers and censored runs, but silent on the tail.
- Geometric mean: the mean of the logs; stays meaningful for ratios and speedups (needs all values > 0).
- Quantiles (p90, p95): describe the tail the median hides.
- Confidence interval: how far the summary could move on another instance sample; wide means too few instances.
Don’t just simply use “the average”.
One run gives one number per instance; a benchmark gives a whole distribution. The summary you report has to match its shape: runtimes are right-skewed and often censored.
Ratios must be averaged geometrically
A is 2× faster on one instance and 2× slower on the other: the two solvers are equal.
\[\text{arith. mean} = \frac{1}{n}\sum_i x_i \qquad \text{geom. mean} = \Big(\prod_i x_i\Big)^{1/n} = \exp\!\Big(\tfrac{1}{n}\sum_i \ln x_i\Big)\]
| A/B | B/A | |
|---|---|---|
| inst 1 | 0.5 | 2.0 |
| inst 2 | 2.0 | 0.5 |
| arithmetic mean | 1.25 | 1.25 |
| geometric mean | 1.0 | 1.0 |
Relative or absolute? Both can mislead
| Inst. | A | B | A/B | abs (s) |
|---|---|---|---|---|
| I1 ⚠ | 0.02 | 0.20 | 0.1× | 0.18 |
| I2 ⚠ | 0.05 | 0.30 | 0.2× | 0.25 |
| I3 ⚠ | 0.04 | 0.01 | 4× | 0.03 |
| I4 | 2.0 | 2.2 | 0.9× | 0.2 |
| I5 | 60 | 45 | 1.3× | 15 |
| I6 | 120 | 90 | 1.3× | 30 |
Be wary of small values in relative aggregations. A tiny absolute value, from timer or numeric noise and from tolerances, can blow up the values.
The Plot Portfolio
Bar plot: aggregate comparison across a few categories
- One bar per category: a median (or mean) read at a glance.
- Best when every run finishes; group by instance class or by solver.
- Add IQR whiskers; a bar still hides the distribution, so pair it with a scatter or cactus.
Scatter + performance zones: prototype vs. baseline
- One point per instance: baseline on x, your model on y.
- Diagonal = parity; shaded zones = “meaningfully better/worse”.
- Instantly exposes outliers and the no-free-lunch trade.
Cactus plot: runtime and success rate in one view
- x = # instances solved, y = solve time, sorted ascending per config.
- Combines runtime and success rate in one view; further right / lower is better.
- Timeouts just stop a curve, so it also stays honest under censoring.
Performance plot: solution quality under a time budget
How to read: each curve is one config/algorithm. A point \((x, y)\) means “on a fraction \(y\) of instances, this config/algorithm was within factor \(x\) of the best result.” Higher and further left is better; the curve that reaches 1.0 first dominates.
Split plot: how far does a single model scale?
- Solved instances: plot runtime (lower region).
- Unsolved instances: plot optimality gap (upper region).
- One figure for “solves to here, degrades like this beyond”.
The table is the artifact of record
- Plots show trends; the table lets a reader verify them and inspect single instances.
- Include at least one table of raw results for the key instances. Many strong papers rely on tables alone.
- Be selective: not every instance, not every column. Link the full dataset externally.
Example table from a real publication (SampLNS).
Linear or log? Same scatter, two stories
Designing the Study
A benchmark is only as good as the instances it runs on.
Exploratory vs. workhorse studies
Exploratory — fast, cheap, throwaway.
- few instances, short limits.
- Build intuition, kill bad ideas early.
- Conclusions are hypotheses, not results.
Workhorse — large, rigorous, reproducible.
- Curated instance set, fixed seeds, pinned environment.
- The numbers you put in a paper or a deploy decision.
The classic failure: Not clearly distinguishing the two. Don’t just “iterate” an exploratory study until it feels like a workhorse study.
Selecting the instance set, and managing the runs
- Instance set: representative of production, spanning sizes; include hard cases, not just the solvable ones. Beware homogeneous generators that hide the no-free-lunch effect.
- Reproducibility: allow others to rerun your study.
- Log everything: there will be outliers and Heisenbugs; you can only debug on the data you saved.
- Folder discipline:
evaluations/<problem>/<date_tag>/withPRIVATE_DATA+PUBLIC_DATA, aREADME, numbered scripts (00_generate,01_run, …). - Make runs observable, interruptible & resumable — the longer the runs, the higher the risk of system failures.
Reading the Solver Log
Solvers are actually grey boxes. The logs can tell us quite a bit.
The log has five acts
- Initialization — parameters in effect (worker count, seed, limits).
- Initial model — variable and constraint counts by type.
- Presolve — how much the model shrank before search.
- Search phase — the event stream: every improved incumbent and bound, tagged with the subsolver that found it.
- Summary — final status, objective, bound, gap integral.
It is event-driven: lines appear when something happens, so the timeline is uneven. Skim structure first, then zoom into the act you care about.
Universal acts: one model, three solvers
Model it once in MathOpt; swap the solver and read each log.
from ortools.math_opt.python import mathopt
# multiple knapsack: place items into bins to maximize value
model = mathopt.Model(name="multiple_knapsack")
x = {(i, j): model.add_binary_variable() for i in bins for j in items}
for j in items: # each item in at most one knapsack
model.add_linear_constraint(sum(x[i, j] for i in bins) <= 1)
for i in bins: # each knapsack within capacity
model.add_linear_constraint(sum(w[j] * x[i, j] for j in items) <= cap[i])
model.maximize(sum(v[j] * x[i, j] for i in bins for j in items))
# the whole point: write the model once, swap the backend
ST = mathopt.SolverType
for solver in [ST.CP_SAT, ST.HIGHS, ST.GSCIP]: # GSCIP = SCIP
result = mathopt.solve(model, solver, params=mathopt.SolveParameters(enable_output=True))| Solver | Status | Objective | Wall | Log lines |
|---|---|---|---|---|
| CP-SAT | OPTIMAL | 2270 | 0.2 s | 433 |
| HiGHS | OPTIMAL | 2270 | 3.1 s | 73 |
| SCIP | OPTIMAL | 2270 | 3.4 s | 81 |
Same model, same optimum. Three very different logs — but the same four acts in each: initial model, presolve, primal/dual convergence, final status.
140 items, 4 knapsacks.
HiGHS: the four acts in one B&B table
MIP multiple_knapsack has 144 rows; 560 cols; 1120 nonzeros; 560 integer variables (560 binary)
Coefficient ranges:
Matrix [1e+00, 4e+01]
Cost [5e+00, 5e+01]
Bound [1e+00, 1e+00]
RHS [1e+00, 5e+02]
Presolving model
144 rows, 560 cols, 1120 nonzeros 0s
144 rows, 560 cols, 1120 nonzeros 0s
Presolve reductions: rows 144(-0); columns 560(-0); nonzeros 1120(-0) - Not reduced
Objective function is integral with scale 1
Solving MIP model with:
144 rows
560 cols (560 binary, 0 integer, 0 implied int., 0 continuous, 0 domain fixed)
1120 nonzeros
Src: B => Branching; C => Central rounding; F => Feasibility pump; H => Heuristic;
I => Shifting; J => Feasibility jump; L => Sub-MIP; P => Empty MIP; R => Randomized rounding;
S => Solve LP; T => Evaluate node; U => Unbounded; X => User solution; Y => HiGHS solution;
Z => ZI Round; l => Trivial lower; p => Trivial point; u => Trivial upper; z => Trivial zero
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
z 0 0 0 0.00% inf -0 Large 0 0 0 0 0.0s
J 0 0 0 0.00% inf 47 Large 0 0 0 0 0.0s
S 0 0 0 0.00% 3797 2185 73.78% 0 0 0 0 0.0s
0 0 0 0.00% 2271.538462 2185 3.96% 0 0 0 128 0.0s
S 0 0 0 0.00% 2271.538462 2192 3.63% 13 1 0 128 0.0s
L 0 0 0 0.00% 2271.538462 2247 1.09% 366 46 1 343 0.1s
L 0 0 0 0.00% 2271.538462 2265 0.29% 366 46 1 742 0.2s
22.1% inactive integer columns, restarting
Model after restart has 113 rows, 436 cols (436 bin., 0 int., 0 impl., 0 cont., 0 dom.fix.), and 872 nonzeros
0 0 0 0.00% 2271.538462 2265 0.29% 9 0 0 1160 0.2s
0 0 0 0.00% 2271.538462 2265 0.29% 9 1 1 1164 0.2s
L 0 0 0 0.00% 2271.538462 2269 0.11% 204 38 1 1376 0.3s
23.9% inactive integer columns, restarting
Model after restart has 87 rows, 332 cols (332 bin., 0 int., 0 impl., 0 cont., 0 dom.fix.), and 664 nonzeros
0 0 0 0.00% 2271.538462 2269 0.11% 19 0 0 2692 0.4s
0 0 0 0.00% 2271.538462 2269 0.11% 19 3 1 2704 0.4s
Symmetry detection completed in 0.0s
Found 4 full orbitope(s) acting on 32 columns
L 806 93 211 3.14% 2271.388889 2270 0.06% 783 17 1684 15235 1.7s
6144 0 2519 100.00% 2270 2270 0.00% 2214 19 3083 56025 3.2s
Solving report
Model multiple_knapsack
Status Optimal
Primal bound 2270
Dual bound 2270
Gap 0% (tolerance: 0.01%)
P-D integral 0.100224577118
Solution status feasible
2270 (objective)
0 (bound viol.)
9.99200722163e-16 (int. viol.)
0 (row viol.)
Timing 3.15
Max sub-MIP depth 5
Nodes 6144
Repair LPs 4 (0 feasible; 0 iterations)
LP iterations 56025
3666 (strong br.)
3290 (separation)
7531 (heuristics)
WARNING: Method setLogCallback is deprecated: alternative method is setCallbackSCIP: the same arc, a denser table
feasible solution found by trivial heuristic after 0.0 seconds, objective value 0.000000e+00
presolving:
(round 1, exhaustive) 0 del vars, 0 del conss, 0 add conss, 0 chg bounds, 0 chg sides, 0 chg coeffs, 144 upgd conss, 0 impls, 140 clqs, 0 implints
(0.0s) probing: 51/560 (9.1%) - 0 fixings, 0 aggregations, 0 implications, 0 bound changes
(0.0s) probing aborted: 50/50 successive totally useless probings
Deactivated symmetry handling methods, since SCIP was built without symmetry detector (SYM=none).
Deactivated symmetry handling methods, since SCIP was built without symmetry detector (SYM=none).
presolving (2 rounds: 2 fast, 2 medium, 2 exhaustive):
0 deleted vars, 0 deleted constraints, 0 added constraints, 0 tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients
0 implications, 140 cliques, 0 implied integral variables (0 bin, 0 int, 0 cont)
presolved problem has 560 variables (560 bin, 0 int, 0 cont) and 144 constraints
4 constraints of type <knapsack>
140 constraints of type <setppc>
transformed objective value is always integral (scale: 1)
Presolving Time: 0.00
transformed 1/1 original solutions to the transformed problem space
time | node | left |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr| dualbound | primalbound | gap | compl.
p 0.0s| 1 | 0 | 0 | - | clique| 0 | 560 | 144 | 144 | 0 | 0 | 0 | 0 | 1.518800e+04 | 1.856000e+03 | 718.32%| unknown
0.0s| 1 | 0 | 134 | - | 5214k | 0 | 560 | 144 | 144 | 0 | 0 | 0 | 0 | 2.271538e+03 | 1.856000e+03 | 22.39%| unknown
r 0.0s| 1 | 0 | 134 | - |simplero| 0 | 560 | 144 | 144 | 0 | 0 | 0 | 0 | 2.271538e+03 | 2.131000e+03 | 6.59%| unknown
r 0.0s| 1 | 0 | 134 | - |randroun| 0 | 560 | 144 | 144 | 0 | 0 | 0 | 0 | 2.271538e+03 | 2.177000e+03 | 4.34%| unknown
r 0.0s| 1 | 0 | 134 | - |shifting| 0 | 560 | 144 | 144 | 0 | 0 | 0 | 0 | 2.271538e+03 | 2.209000e+03 | 2.83%| unknown
i 0.0s| 1 | 0 | 134 | - | oneopt| 0 | 560 | 144 | 144 | 0 | 0 | 0 | 0 | 2.271538e+03 | 2.252000e+03 | 0.87%| unknown
0.0s| 1 | 0 | 144 | - | 5955k | 0 | 560 | 144 | 148 | 4 | 1 | 0 | 0 | 2.271538e+03 | 2.252000e+03 | 0.87%| unknown
0.0s| 1 | 0 | 152 | - | 6835k | 0 | 560 | 144 | 152 | 8 | 2 | 0 | 0 | 2.271538e+03 | 2.252000e+03 | 0.87%| unknown
0.0s| 1 | 0 | 163 | - | 7697k | 0 | 560 | 144 | 155 | 11 | 3 | 0 | 0 | 2.271488e+03 | 2.252000e+03 | 0.87%| unknown
0.0s| 1 | 0 | 173 | - | 10M | 0 | 560 | 144 | 157 | 13 | 4 | 0 | 0 | 2.271488e+03 | 2.252000e+03 | 0.87%| unknown
0.0s| 1 | 0 | 183 | - | 11M | 0 | 560 | 144 | 158 | 14 | 5 | 0 | 0 | 2.271000e+03 | 2.252000e+03 | 0.84%| unknown
0.0s| 1 | 0 | 186 | - | 14M | 0 | 560 | 144 | 162 | 18 | 6 | 0 | 0 | 2.271000e+03 | 2.252000e+03 | 0.84%| unknown
0.0s| 1 | 0 | 196 | - | 16M | 0 | 560 | 144 | 164 | 20 | 7 | 0 | 0 | 2.271000e+03 | 2.252000e+03 | 0.84%| unknown
0.0s| 1 | 0 | 204 | - | 19M | 0 | 560 | 144 | 166 | 22 | 8 | 0 | 0 | 2.271000e+03 | 2.252000e+03 | 0.84%| unknown
0.1s| 1 | 0 | 210 | - | 23M | 0 | 560 | 144 | 170 | 26 | 9 | 0 | 0 | 2.271000e+03 | 2.252000e+03 | 0.84%| unknown
time | node | left |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr| dualbound | primalbound | gap | compl.
0.1s| 1 | 0 | 228 | - | 25M | 0 | 560 | 144 | 173 | 29 | 10 | 0 | 0 | 2.271000e+03 | 2.252000e+03 | 0.84%| unknown
0.1s| 1 | 0 | 257 | - | 25M | 0 | 560 | 144 | 175 | 32 | 11 | 0 | 0 | 2.271000e+03 | 2.252000e+03 | 0.84%| unknown
0.1s| 1 | 0 | 270 | - | 25M | 0 | 560 | 144 | 178 | 35 | 12 | 0 | 0 | 2.271000e+03 | 2.252000e+03 | 0.84%| unknown
0.1s| 1 | 0 | 275 | - | 26M | 0 | 560 | 144 | 181 | 38 | 13 | 0 | 0 | 2.271000e+03 | 2.252000e+03 | 0.84%| unknown
0.1s| 1 | 0 | 290 | - | 26M | 0 | 560 | 144 | 183 | 40 | 14 | 0 | 0 | 2.271000e+03 | 2.252000e+03 | 0.84%| unknown
0.1s| 1 | 0 | 301 | - | 26M | 0 | 560 | 144 | 185 | 42 | 15 | 0 | 0 | 2.271000e+03 | 2.252000e+03 | 0.84%| unknown
d 0.1s| 1 | 0 | 515 | - |farkasdi| 0 | 560 | 144 | 185 | 0 | 15 | 0 | 0 | 2.271000e+03 | 2.253000e+03 | 0.80%| unknown
L 0.1s| 1 | 0 | 546 | - | rens| 0 | 560 | 144 | 185 | 42 | 15 | 0 | 0 | 2.271000e+03 | 2.254000e+03 | 0.75%| unknown
0.1s| 1 | 0 | 546 | - | 26M | 0 | 560 | 144 | 185 | 42 | 15 | 0 | 0 | 2.271000e+03 | 2.254000e+03 | 0.75%| unknown
0.1s| 1 | 0 | 562 | - | 26M | 0 | 560 | 144 | 180 | 46 | 16 | 0 | 0 | 2.271000e+03 | 2.254000e+03 | 0.75%| unknown
0.1s| 1 | 0 | 573 | - | 26M | 0 | 560 | 144 | 184 | 50 | 17 | 0 | 0 | 2.271000e+03 | 2.254000e+03 | 0.75%| unknown
0.1s| 1 | 2 | 574 | - | 26M | 0 | 560 | 144 | 184 | 50 | 17 | 0 | 21 | 2.271000e+03 | 2.254000e+03 | 0.75%| unknown
d 0.3s| 34 | 35 | 954 | 19.0 |adaptive| 21 | 560 | 144 | 162 | 0 | 1 | 0 | 61 | 2.271000e+03 | 2.259000e+03 | 0.53%| unknown
d 0.3s| 46 | 47 | 1175 | 18.8 |fracdivi| 21 | 560 | 144 | 163 | 0 | 1 | 0 | 61 | 2.271000e+03 | 2.260000e+03 | 0.49%| unknown
0.4s| 100 | 101 | 1862 | 15.5 | 60M | 21 | 560 | 159 | 167 | 119 | 2 | 18 | 81 | 2.271000e+03 | 2.260000e+03 | 0.49%| unknown
time | node | left |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr| dualbound | primalbound | gap | compl.
0.6s| 200 | 201 | 4909 | 23.0 | 70M | 33 | 560 | 171 | 162 | 161 | 1 | 30 | 241 | 2.271000e+03 | 2.260000e+03 | 0.49%| unknown
L 0.8s| 246 | 247 | 5335 | 20.4 |crossove| 33 | 560 | 171 | 166 | 198 | 1 | 30 | 316 | 2.271000e+03 | 2.268000e+03 | 0.13%| unknown
0.9s| 300 | 301 | 6880 | 21.9 | 82M | 33 | 560 | 178 | 161 | 233 | 1 | 37 | 325 | 2.271000e+03 | 2.268000e+03 | 0.13%| unknown
1.2s| 400 | 401 | 11218 | 27.3 | 84M | 33 | 560 | 352 | 161 | 284 | 1 | 211 | 325 | 2.271000e+03 | 2.268000e+03 | 0.13%| unknown
1.4s| 500 | 501 | 14843 | 29.1 | 91M | 33 | 560 | 402 | 163 | 328 | 1 | 261 | 325 | 2.271000e+03 | 2.268000e+03 | 0.13%| unknown
1.6s| 600 | 601 | 17895 | 29.3 | 91M | 33 | 560 | 522 | 163 | 373 | 1 | 382 | 349 | 2.271000e+03 | 2.268000e+03 | 0.13%| unknown
1.8s| 700 | 701 | 20467 | 28.8 | 95M | 33 | 560 | 577 | 163 | 437 | 1 | 437 | 354 | 2.271000e+03 | 2.268000e+03 | 0.13%| unknown
2.0s| 800 | 797 | 23218 | 28.6 | 96M | 33 | 560 | 620 | 165 | 491 | 2 | 480 | 370 | 2.271000e+03 | 2.268000e+03 | 0.13%| unknown
2.2s| 900 | 895 | 25359 | 27.8 | 96M | 33 | 560 | 652 | 166 | 551 | 0 | 513 | 378 | 2.271000e+03 | 2.268000e+03 | 0.13%| unknown
2.4s| 1000 | 995 | 26660 | 26.4 | 96M | 33 | 560 | 688 | 165 | 627 | 1 | 549 | 381 | 2.271000e+03 | 2.268000e+03 | 0.13%| unknown
2.6s| 1100 | 1093 | 28027 | 25.2 | 96M | 33 | 560 | 707 | 159 | 674 | 1 | 568 | 387 | 2.271000e+03 | 2.268000e+03 | 0.13%| unknown
2.7s| 1200 | 1193 | 28731 | 23.7 | 96M | 33 | 560 | 711 | 165 | 727 | 1 | 573 | 401 | 2.271000e+03 | 2.268000e+03 | 0.13%| unknown
2.8s| 1300 | 1293 | 29881 | 22.8 | 96M | 33 | 560 | 712 | 172 | 784 | 3 | 576 | 404 | 2.271000e+03 | 2.268000e+03 | 0.13%| unknown
2.9s| 1400 | 1393 | 30630 | 21.7 | 96M | 33 | 560 | 720 | 168 | 818 | 1 | 591 | 409 | 2.270901e+03 | 2.268000e+03 | 0.13%| unknown
3.0s| 1500 | 1491 | 31166 | 20.6 | 96M | 33 | 560 | 723 | 167 | 839 | 1 | 596 | 409 | 2.270806e+03 | 2.268000e+03 | 0.12%| unknown
time | node | left |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr| dualbound | primalbound | gap | compl.
3.0s| 1600 | 1591 | 31978 | 19.8 | 97M | 33 | 560 | 738 | 163 | 867 | 1 | 617 | 423 | 2.270800e+03 | 2.268000e+03 | 0.12%| unknown
3.1s| 1700 | 1691 | 32990 | 19.2 | 97M | 33 | 560 | 737 | 168 | 916 | 1 | 621 | 433 | 2.270800e+03 | 2.268000e+03 | 0.12%| unknown
3.1s| 1800 | 1791 | 33590 | 18.5 | 97M | 33 | 560 | 733 | 167 | 952 | 1 | 623 | 438 | 2.270778e+03 | 2.268000e+03 | 0.12%| unknown
3.2s| 1900 | 1891 | 34419 | 18.0 | 97M | 33 | 560 | 720 | 165 | 989 | 1 | 625 | 452 | 2.270778e+03 | 2.268000e+03 | 0.12%| unknown
3.2s| 2000 | 1987 | 35181 | 17.4 | 97M | 33 | 560 | 704 | 171 |1030 | 1 | 630 | 465 | 2.270778e+03 | 2.268000e+03 | 0.12%| unknown
3.3s| 2100 | 2085 | 36170 | 17.1 | 98M | 33 | 560 | 703 | 162 |1067 | 1 | 655 | 478 | 2.270778e+03 | 2.268000e+03 | 0.12%| unknown
3.3s| 2200 | 2185 | 36870 | 16.6 | 98M | 33 | 560 | 691 | 170 |1109 | 2 | 655 | 489 | 2.270778e+03 | 2.268000e+03 | 0.12%| unknown
d 3.4s| 2285 | 0 | 37490 | 16.3 |farkasdi| 38 | 560 | 681 | 168 | 0 | 1 | 655 | 502 | 2.270000e+03 | 2.270000e+03 | 0.00%| 100.00%
SCIP Status : problem is solved [optimal solution found]
Solving Time (sec) : 3.36
Solving Nodes : 2285
Primal Bound : +2.27000000000000e+03 (466 solutions)
Dual Bound : +2.27000000000000e+03
Gap : 0.00 %Different column names — dualbound/primalbound instead of BestBound/BestSol — but the identical primal-up, dual-down, gap-to-zero arc.
When a solver struggles, the log says why
Same model, identical-capacity bins. CP-SAT 0.3 s ✓, SCIP 2 s ✓, HiGHS → time limit. The full log:
MIP multiple_knapsack has 75 rows; 350 cols; 700 nonzeros; 350 integer variables (350 binary)
Coefficient ranges:
Matrix [1e+00, 4e+01]
Cost [3e+00, 5e+01]
Bound [1e+00, 1e+00]
RHS [1e+00, 1e+02]
Presolving model
75 rows, 350 cols, 700 nonzeros 0s
75 rows, 350 cols, 700 nonzeros 0s
Presolve reductions: rows 75(-0); columns 350(-0); nonzeros 700(-0) - Not reduced
Objective function is integral with scale 1
Solving MIP model with:
75 rows
350 cols (350 binary, 0 integer, 0 implied int., 0 continuous, 0 domain fixed)
700 nonzeros
Src: B => Branching; C => Central rounding; F => Feasibility pump; H => Heuristic;
I => Shifting; J => Feasibility jump; L => Sub-MIP; P => Empty MIP; R => Randomized rounding;
S => Solve LP; T => Evaluate node; U => Unbounded; X => User solution; Y => HiGHS solution;
Z => ZI Round; l => Trivial lower; p => Trivial point; u => Trivial upper; z => Trivial zero
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
z 0 0 0 0.00% inf -0 Large 0 0 0 0 0.0s
J 0 0 0 0.00% inf 50 Large 0 0 0 0 0.0s
S 0 0 0 0.00% 1899 751 152.86% 0 0 0 0 0.0s
0 0 0 0.00% 908.826087 751 21.02% 0 0 0 58 0.0s
L 0 0 0 0.00% 908.6470588 890 2.10% 1752 66 4 1193 0.2s
L 0 0 0 0.00% 908.6470588 896 1.41% 1752 66 4 1667 0.3s
2.9% inactive integer columns, restarting
Model after restart has 73 rows, 340 cols (340 bin., 0 int., 0 impl., 0 cont., 0 dom.fix.), and 680 nonzeros
0 0 0 0.00% 908.6470588 896 1.41% 27 0 0 2288 0.3s
0 0 0 0.00% 908.6470588 896 1.41% 27 1 2 2289 0.3s
L 0 0 0 0.00% 908.6470588 903 0.63% 1563 87 2 3157 0.5s
27.9% inactive integer columns, restarting
Model after restart has 54 rows, 245 cols (245 bin., 0 int., 0 impl., 0 cont., 0 dom.fix.), and 490 nonzeros
0 0 0 0.00% 908.6470588 903 0.63% 22 0 0 4873 0.7s
0 0 0 0.00% 908.6470588 903 0.63% 22 5 1 4887 0.7s
Symmetry detection completed in 0.0s
Found 8 generator(s)
L 0 0 0 0.00% 908.6470588 905 0.40% 836 25 1 7071 1.0s
T 577 81 221 0.02% 908.6470588 906 0.29% 1558 23 3000 16553 1.4s
Restarting search from the root node
Model after restart has 38 rows, 178 cols (178 bin., 0 int., 0 impl., 0 cont., 0 dom.fix.), and 361 nonzeros
1209 0 0 0.00% 908.6470588 906 0.29% 27 0 0 20968 1.6s
1209 0 0 0.00% 908.6470588 906 0.29% 27 1 2 21008 1.6s
Symmetry detection completed in 0.0s
Found 3 generator(s)
Restarting search from the root node
Model after restart has 38 rows, 177 cols (177 bin., 0 int., 0 impl., 0 cont., 0 dom.fix.), and 359 nonzeros
2856 0 0 0.00% 908.6470588 906 0.29% 13 0 0 41778 2.8s
2856 0 0 0.00% 908.6470588 906 0.29% 13 0 1 41778 2.8s
Symmetry detection completed in 0.0s
Found 2 generator(s)
Restarting search from the root node
Model after restart has 38 rows, 177 cols (177 bin., 0 int., 0 impl., 0 cont., 0 dom.fix.), and 359 nonzeros
5485 0 0 0.00% 908.6470588 906 0.29% 43 0 0 66552 4.3s
5485 0 0 0.00% 908.6470588 906 0.29% 43 0 1 66552 4.3s
Symmetry detection completed in 0.0s
Found 2 generator(s)
T 7459 147 876 0.01% 908.6470588 907 0.18% 1628 29 7328 79723 4.9s
Restarting search from the root node
Model after restart has 37 rows, 157 cols (157 bin., 0 int., 0 impl., 0 cont., 0 dom.fix.), and 314 nonzeros
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
10926 0 0 0.00% 908.6470588 907 0.18% 19 0 0 126981 7.7s
10926 0 0 0.00% 908.6470588 907 0.18% 19 1 2 126983 7.7s
Symmetry detection completed in 0.0s
Found 2 generator(s)
Restarting search from the root node
Model after restart has 37 rows, 156 cols (156 bin., 0 int., 0 impl., 0 cont., 0 dom.fix.), and 312 nonzeros
17748 0 0 0.00% 908.6470588 907 0.18% 39 0 0 171302 9.5s
17748 0 0 0.00% 908.6470588 907 0.18% 39 0 1 171302 9.5s
Symmetry detection completed in 0.0s
Found 1 full orbitope(s) acting on 10 columns
38906 1604 9347 13.98% 908.6470588 907 0.18% 1395 44 9830 300398 14.5s
41985 1874 10726 14.00% 908.6470588 907 0.18% 1365 12 9932 315337 15.0s
Solving report
Model multiple_knapsack
Status Time limit reached
Primal bound 907
Dual bound 908
Gap 0.11% (tolerance: 0.01%)
P-D integral 0.10104171198
Solution status feasible
907 (objective)
0 (bound viol.)
2.26485497024e-14 (int. viol.)
0 (row viol.)
Timing 15.00
Max sub-MIP depth 4
Nodes 41985
Repair LPs 9 (0 feasible; 0 iterations)
LP iterations 315337
7047 (strong br.)
17497 (separation)
94399 (heuristics)
WARNING: Method setLogCallback is deprecated: alternative method is setCallbackThe diagnosis: it was symmetry
- Symptom: primal optimal in 0.3 s, but the dual bound is frozen and the gap will not close — nodes explode, time runs out.
- Cause (named in the log): “Found … orbitope(s)”, “Restarting search from the root”, over and over. Identical knapsacks ⇒ every solution has \(5! = 120\) equivalent relabelings.
- Fix: break the symmetry. The easy scenario was the same model with distinct capacities — it proved optimal in 3 s. Or add ordering constraints; or use a solver that exploits symmetry (CP-SAT detected the orbitopes and closed it in 0.3 s).
A stalled gap with a moving node count is the classic “my MIP won’t close” signature. Before you reach for more time or more cores, read the log: the bottleneck (symmetry, a weak relaxation, no incumbent) is usually named.
CP-SAT: the same acts, plus who did it
Running basic LP presolve, initial problem dimensions: 144 rows, 560 columns, 1120 entries with magnitude in [1.000000e+00, 3.900000e+01]
glop::FixedVariablePreprocessor 144 rows, 560 columns, 1120 entries with magnitude in [1.000000e+00, 3.900000e+01]
glop::SingletonPreprocessor 144 rows, 560 columns, 1120 entries with magnitude in [1.000000e+00, 3.900000e+01]
glop::ForcingAndImpliedFreeConstraintPreprocessor 144 rows, 560 columns, 1120 entries with magnitude in [1.000000e+00, 3.900000e+01]
glop::FreeConstraintPreprocessor 144 rows, 560 columns, 1120 entries with magnitude in [1.000000e+00, 3.900000e+01]
glop::UnconstrainedVariablePreprocessor 144 rows, 560 columns, 1120 entries with magnitude in [1.000000e+00, 3.900000e+01]
IntegerBoundsPreprocessor 144 rows, 560 columns, 1120 entries with magnitude in [1.000000e+00, 3.900000e+01]
BoundPropagationPreprocessor 144 rows, 560 columns, 1120 entries with magnitude in [1.000000e+00, 3.900000e+01]
ImpliedIntegerPreprocessor 144 rows, 560 columns, 1120 entries with magnitude in [1.000000e+00, 3.900000e+01]
IntegerBoundsPreprocessor 144 rows, 560 columns, 1120 entries with magnitude in [1.000000e+00, 3.900000e+01]
ReduceCostOverExclusiveOrConstraintPreprocessor 144 rows, 560 columns, 1120 entries with magnitude in [1.000000e+00, 3.900000e+01]
Scaling to pure integer problem.
Num integers: 560/560 (implied: 0 in_inequalities: 0 max_scaling: 0) [IP]
Maximum constraint coefficient relative error: 0
Maximum constraint worst-case activity error: 0
Constraint scaling factor range: [1, 1]
Starting CP-SAT solver v9.15.6755
Parameters: max_time_in_seconds: 15 log_search_progress: true catch_sigint_signal: false log_to_stdout: false
Setting number of workers to 24
Initial optimization model 'multiple_knapsack': (model_fingerprint: 0x96dbe1b2ccc50c0e)
#Variables: 560 (#bools: 560 in floating point objective) (560 primary variables)
- 560 Booleans in [0,1]
#kLinearN: 144 (#terms: 1'120)
Starting presolve at 0.00s
[Scaling] Floating point objective has 560 terms with magnitude in [5, 47] average = 27.1214
[Scaling] Objective coefficient relative error: 0
[Scaling] Objective worst-case absolute error: 0
[Scaling] Objective scaling factor: 1
2.41e-04s 0.00e+00d [DetectDominanceRelations]
6.29e-04s 0.00e+00d [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1
6.39e-06s 0.00e+00d [ExtractEncodingFromLinear] #potential_supersets=140
2.17e-05s 0.00e+00d [DetectDuplicateColumns]
7.96e-05s 0.00e+00d [DetectDuplicateConstraints]
[Symmetry] Graph for symmetry has 1'264 nodes and 1'680 arcs.
[Symmetry] Symmetry computation done. time: 0.000119985 dtime: 0.00025118
[Symmetry] #generators: 7, average support size: 8
[Symmetry] 28 orbits on 56 variables with sizes: 2,2,2,2,2,2,2,2,2,2,...
[Symmetry] Found orbitope of size 4 x 2
8.21e-05s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements]
7.99e-04s 2.74e-04d [Probe] #probed=1'120
6.13e-05s 2.48e-05d [MaxClique]
1.94e-04s 0.00e+00d [DetectDominanceRelations]
4.05e-04s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
6.28e-05s 0.00e+00d [ProcessAtMostOneAndLinear]
6.99e-05s 0.00e+00d [DetectDuplicateConstraints]
5.90e-05s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements]
8.22e-06s 1.68e-06d [DetectDominatedLinearConstraints] #relevant_constraints=4
2.08e-06s 0.00e+00d [DetectDifferentVariables]
2.87e-05s 3.50e-06d [ProcessSetPPC] #relevant_constraints=144
3.42e-05s 0.00e+00d [TransformClausesToExactlyOne] #num_amos=140
9.02e-07s 0.00e+00d [DetectEncodedComplexDomains]
1.30e-06s 0.00e+00d [FindAlmostIdenticalLinearConstraints]
1.74e-04s 8.57e-04d [FindBigAtMostOneAndLinearOverlap]
2.25e-05s 4.00e-04d [FindBigVerticalLinearOverlap]
4.27e-06s 1.12e-05d [FindBigHorizontalLinearOverlap] #linears=4
1.75e-06s 0.00e+00d [MergeClauses]
1.84e-04s 0.00e+00d [DetectDominanceRelations]
3.62e-04s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
1.91e-04s 0.00e+00d [DetectDominanceRelations]
3.56e-04s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
1.64e-05s 0.00e+00d [DetectDuplicateColumns]
6.21e-05s 0.00e+00d [DetectDuplicateConstraints]
[Symmetry] Graph for symmetry has 1'264 nodes and 1'680 arcs.
[Symmetry] Symmetry computation done. time: 8.9749e-05 dtime: 0.00025114
[Symmetry] #generators: 7, average support size: 8
[Symmetry] 28 orbits on 56 variables with sizes: 2,2,2,2,2,2,2,2,2,2,...
[Symmetry] Found orbitope of size 4 x 2
6.65e-05s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements]
7.02e-04s 2.74e-04d [Probe] #probed=1'120
5.46e-05s 2.48e-05d [MaxClique]
1.90e-04s 0.00e+00d [DetectDominanceRelations]
3.75e-04s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
5.75e-05s 0.00e+00d [ProcessAtMostOneAndLinear]
6.21e-05s 0.00e+00d [DetectDuplicateConstraints]
5.60e-05s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements]
6.03e-06s 1.68e-06d [DetectDominatedLinearConstraints] #relevant_constraints=4
1.42e-06s 0.00e+00d [DetectDifferentVariables]
2.62e-05s 3.50e-06d [ProcessSetPPC] #relevant_constraints=144
3.25e-05s 0.00e+00d [TransformClausesToExactlyOne] #num_amos=140
7.71e-07s 0.00e+00d [DetectEncodedComplexDomains]
9.11e-07s 0.00e+00d [FindAlmostIdenticalLinearConstraints]
1.72e-04s 8.57e-04d [FindBigAtMostOneAndLinearOverlap]
2.22e-05s 4.00e-04d [FindBigVerticalLinearOverlap]
3.34e-06s 1.12e-05d [FindBigHorizontalLinearOverlap] #linears=4
1.19e-06s 0.00e+00d [MergeClauses]
1.80e-04s 0.00e+00d [DetectDominanceRelations]
3.44e-04s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
7.82e-07s 0.00e+00d [MergeNoOverlap]
6.71e-07s 0.00e+00d [MergeNoOverlap2D]
5.51e-05s 0.00e+00d [ExpandObjective]
Presolve summary:
- 0 affine relations were detected.
- rule 'TODO dual: only one unspecified blocking constraint?' was applied 3'360 times.
- rule 'linear: positive at most one' was applied 140 times.
- rule 'presolve: 0 unused variables removed.' was applied 1 time.
- rule 'presolve: iteration' was applied 2 times.
Presolved optimization model 'multiple_knapsack': (model_fingerprint: 0x634bbab90ac02824)
#Variables: 560 (#bools: 560 in objective) (560 primary variables)
- 560 Booleans in [0,1]
#kAtMostOne: 140 (#literals: 560)
#kLinearN: 4 (#terms: 560)
[Symmetry] Graph for symmetry has 1'264 nodes and 1'680 arcs.
[Symmetry] Symmetry computation done. time: 8.8666e-05 dtime: 0.00025114
[Symmetry] #generators: 7, average support size: 8
[Symmetry] 28 orbits on 56 variables with sizes: 2,2,2,2,2,2,2,2,2,2,...
[Symmetry] Found orbitope of size 4 x 2
Preloading model.
#Bound 0.01s best:-inf next:[-0,15188] initial_domain
#Model 0.01s var:560/560 constraints:144/144
Starting search at 0.01s with 24 workers.
15 full problem subsolvers: [core, default_lp, lb_tree_search, max_lp_sym, no_lp, objective_lb_search, objective_shaving_max_lp, objective_shaving_no_lp, probing, probing_max_lp, probing_no_lp, pseudo_costs, quick_restart, quick_restart_no_lp, reduced_costs]
9 first solution subsolvers: [fj(3), fj_lin, fs_random, fs_random_no_lp(2), fs_random_quick_restart, fs_random_quick_restart_no_lp]
13 interleaved subsolvers: [feasibility_pump, graph_arc_lns, graph_cst_lns, graph_dec_lns, graph_var_lns, lb_relax_lns, ls(2), ls_lin, rins/rens, rnd_cst_lns, rnd_var_lns, variables_shaving]
3 helper subsolvers: [neighborhood_helper, synchronization_agent, update_gap_integral]
#Bound 0.01s best:-inf next:[-0,3797] am1_presolve (num_literals=560 num_am1=140 increase=11391 work_done=4480)
#1 0.01s best:1891 next:[1892,3797] no_lp
#2 0.01s best:1892 next:[1893,3797] no_lp
#3 0.01s best:1911 next:[1912,3797] no_lp
#Bound 0.01s best:1911 next:[1912,2271] default_lp
#4 0.01s best:1914 next:[1915,2271] no_lp
#5 0.01s best:1939 next:[1940,2271] core
#6 0.01s best:1947 next:[1948,2271] core
#7 0.01s best:1961 next:[1962,2271] ls_restart_decay(batch:1 lin{mvs:3 evals:516} #w_updates:7 #perturb:0)
#8 0.01s best:1963 next:[1964,2271] ls_restart_perturb(batch:1 lin{mvs:8 evals:560} #w_updates:13 #perturb:0)
#9 0.01s best:1982 next:[1983,2271] ls_lin_restart_decay_compound_perturb(batch:1 lin{mvs:0 evals:498} gen{mvs:3 evals:0} comp{mvs:3 btracks:0} #w_updates:0 #perturb:0)
#10 0.01s best:2226 next:[2227,2271] default_lp
#11 0.02s best:2237 next:[2238,2271] ls_restart_compound(batch:1 lin{mvs:0 evals:2'645} gen{mvs:31 evals:0} comp{mvs:3 btracks:14} #w_updates:0 #perturb:0)
#12 0.02s best:2253 next:[2254,2271] reduced_costs
#13 0.02s best:2266 next:[2267,2271] reduced_costs
#Model 0.03s var:408/560 constraints:106/144
#14 0.04s best:2267 next:[2268,2271] quick_restart_no_lp
#Bound 0.05s best:2267 next:[2268,2270] probing_max_lp
#15 0.08s best:2269 next:[2270,2270] default_lp
#Model 0.08s var:372/560 constraints:97/144
#Model 0.14s var:320/560 constraints:84/144
#16 0.18s best:2270 next:[] graph_var_lns (d=2.93e-01 s=44 t=0.10 p=0.00 stall=0 h=base) [hint]
#Done 0.18s probing_no_lp
Task timing n [ min, max] avg dev time n [ min, max] avg dev dtime
'core': 1 [172.38ms, 172.38ms] 172.38ms 0.00ns 172.38ms 2 [291.21us, 272.17ms] 136.23ms 135.94ms 272.46ms
'default_lp': 1 [172.40ms, 172.40ms] 172.40ms 0.00ns 172.40ms 2 [ 3.28ms, 186.83ms] 95.06ms 91.78ms 190.11ms
'feasibility_pump': 3 [984.29us, 1.71ms] 1.33ms 299.55us 3.98ms 2 [333.42us, 541.75us] 437.58us 104.16us 875.16us
'fj': 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns
'fj': 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns
'fj': 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns
'fj_lin': 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns
'fs_random': 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns
'fs_random_no_lp': 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns
'fs_random_no_lp': 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns
'fs_random_quick_restart': 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns
'fs_random_quick_restart_no_lp': 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns
'graph_arc_lns': 1 [168.05ms, 168.05ms] 168.05ms 0.00ns 168.05ms 1 [ 43.77ms, 43.77ms] 43.77ms 0.00ns 43.77ms
'graph_cst_lns': 1 [167.31ms, 167.31ms] 167.31ms 0.00ns 167.31ms 1 [ 79.00ms, 79.00ms] 79.00ms 0.00ns 79.00ms
'graph_dec_lns': 1 [167.29ms, 167.29ms] 167.29ms 0.00ns 167.29ms 1 [ 56.65ms, 56.65ms] 56.65ms 0.00ns 56.65ms
'graph_var_lns': 2 [906.36us, 166.09ms] 83.50ms 82.59ms 167.00ms 2 [ 10.00ns, 100.00ms] 50.00ms 50.00ms 100.00ms
'lb_relax_lns': 1 [167.29ms, 167.29ms] 167.29ms 0.00ns 167.29ms 1 [ 44.66ms, 44.66ms] 44.66ms 0.00ns 44.66ms
'lb_tree_search': 1 [168.81ms, 168.81ms] 168.81ms 0.00ns 168.81ms 2 [ 3.35ms, 100.30ms] 51.83ms 48.47ms 103.65ms
'ls': 3 [362.20us, 101.90ms] 56.11ms 42.05ms 168.34ms 3 [232.96us, 100.01ms] 66.75ms 47.04ms 200.25ms
'ls': 3 [429.53us, 111.86ms] 37.66ms 52.47ms 112.98ms 3 [131.83us, 100.01ms] 33.64ms 46.93ms 100.91ms
'ls_lin': 3 [241.95us, 102.68ms] 35.79ms 47.34ms 107.36ms 3 [ 92.86us, 100.01ms] 35.50ms 45.69ms 106.49ms
'max_lp_sym': 1 [172.37ms, 172.37ms] 172.37ms 0.00ns 172.37ms 2 [ 3.12ms, 82.18ms] 42.65ms 39.53ms 85.29ms
'no_lp': 1 [172.32ms, 172.32ms] 172.32ms 0.00ns 172.32ms 2 [291.88us, 48.40ms] 24.35ms 24.05ms 48.69ms
'objective_lb_search': 1 [168.67ms, 168.67ms] 168.67ms 0.00ns 168.67ms 2 [ 3.02ms, 97.34ms] 50.18ms 47.16ms 100.36ms
'objective_shaving_max_lp': 3 [643.80us, 10.92ms] 4.44ms 4.61ms 13.31ms 1 [ 18.20ms, 18.20ms] 18.20ms 0.00ns 18.20ms
'objective_shaving_no_lp': 3 [664.13us, 8.68ms] 6.00ms 3.77ms 18.00ms 2 [ 17.27ms, 17.27ms] 17.27ms 0.00ns 34.54ms
'probing': 1 [168.82ms, 168.82ms] 168.82ms 0.00ns 168.82ms 2 [ 3.05ms, 212.23ms] 107.64ms 104.59ms 215.28ms
'probing_max_lp': 1 [168.46ms, 168.46ms] 168.46ms 0.00ns 168.46ms 2 [ 3.27ms, 174.16ms] 88.72ms 85.44ms 177.43ms
'probing_no_lp': 1 [168.38ms, 168.38ms] 168.38ms 0.00ns 168.38ms 2 [291.88us, 72.10ms] 36.19ms 35.90ms 72.39ms
'pseudo_costs': 1 [168.93ms, 168.93ms] 168.93ms 0.00ns 168.93ms 2 [ 3.02ms, 106.27ms] 54.65ms 51.62ms 109.29ms
'quick_restart': 1 [169.23ms, 169.23ms] 169.23ms 0.00ns 169.23ms 2 [ 3.24ms, 127.51ms] 65.37ms 62.14ms 130.74ms
'quick_restart_no_lp': 1 [168.93ms, 168.93ms] 168.93ms 0.00ns 168.93ms 2 [291.88us, 86.92ms] 43.61ms 43.31ms 87.21ms
'reduced_costs': 1 [169.03ms, 169.03ms] 169.03ms 0.00ns 169.03ms 2 [ 3.10ms, 119.26ms] 61.18ms 58.08ms 122.35ms
'rins/rens': 2 [ 44.18ms, 166.15ms] 105.17ms 60.99ms 210.34ms 2 [ 16.82ms, 51.65ms] 34.23ms 17.42ms 68.46ms
'rnd_cst_lns': 1 [167.53ms, 167.53ms] 167.53ms 0.00ns 167.53ms 1 [ 84.52ms, 84.52ms] 84.52ms 0.00ns 84.52ms
'rnd_var_lns': 2 [ 36.41ms, 167.67ms] 102.04ms 65.63ms 204.08ms 2 [ 17.35ms, 61.07ms] 39.21ms 21.86ms 78.42ms
'variables_shaving': 3 [965.09us, 1.24ms] 1.10ms 113.76us 3.29ms 3 [ 10.00ns, 10.00ns] 10.00ns 0.00ns 30.00ns
Search stats Bools Conflicts Branches Restarts BacktrackToRoot Backtrack BoolPropag IntegerPropag
'core': 700 13'063 50'975 64 17'222 30'375 944'844 129'075
'default_lp': 560 326 8'993 1 6'360 6'707 11'788 38'973
'fs_random': 0 0 0 0 0 0 0 0
'fs_random_no_lp': 0 0 0 0 0 0 0 0
'fs_random_no_lp': 0 0 0 0 0 0 0 0
'fs_random_quick_restart': 0 0 0 0 0 0 0 0
'fs_random_quick_restart_no_lp': 0 0 0 0 0 0 0 0
'lb_tree_search': 560 465 8'125 0 4'420 5'088 20'235 52'835
'max_lp_sym': 560 716 9'564 2 6'856 7'600 16'349 69'684
'no_lp': 560 2'653 7'683 5 4'151 6'822 70'596 142'556
'objective_lb_search': 563 777 6'081 2 4'103 4'912 12'588 43'832
'probing': 560 1 1'401 0 1'401 1'401 2'427 4'589
'probing_max_lp': 560 0 1'322 0 1'322 1'322 2'249 4'074
'probing_no_lp': 560 1'142 125'033 4 51'340 52'490 139'463 345'822
'pseudo_costs': 560 687 8'186 3 5'220 5'940 13'775 46'481
'quick_restart': 560 98 13'057 9 10'521 10'717 18'817 59'756
'quick_restart_no_lp': 560 1'466 28'364 132 4'615 6'099 47'957 171'223
'reduced_costs': 560 481 7'609 2 5'886 6'381 14'037 46'204
SAT formula Fixed Equiv Total VarLeft BinaryClauses PermanentClauses TemporaryClauses
'core': 300 0 700 400 50 80 4'509
'default_lp': 228 0 560 332 0 0 256
'fs_random': 0 0 0 0 0 0 0
'fs_random_no_lp': 0 0 0 0 0 0 0
'fs_random_no_lp': 0 0 0 0 0 0 0
'fs_random_quick_restart': 0 0 0 0 0 0 0
'fs_random_quick_restart_no_lp': 0 0 0 0 0 0 0
'lb_tree_search': 240 0 560 320 0 0 382
'max_lp_sym': 230 0 560 330 18 0 553
'no_lp': 240 0 560 320 16 0 1'036
'objective_lb_search': 243 0 563 320 48 0 604
'probing': 234 0 560 326 102 0 0
'probing_max_lp': 240 0 560 320 38 0 0
'probing_no_lp': 240 0 560 320 48 0 1'112
'pseudo_costs': 240 0 560 320 48 0 593
'quick_restart': 240 0 560 320 48 0 68
'quick_restart_no_lp': 240 0 560 320 48 0 766
'reduced_costs': 240 0 560 320 0 0 387
SAT stats ClassicMinim LitRemoved LitRemovedBinary LitLearned LitForgotten Subsumed
'core': 2'567 16'483 1'563 611'331 84'265 123
'default_lp': 215 2'567 1'256 29'718 0 57
'fs_random': 0 0 0 0 0 0
'fs_random_no_lp': 0 0 0 0 0 0
'fs_random_no_lp': 0 0 0 0 0 0
'fs_random_quick_restart': 0 0 0 0 0 0
'fs_random_quick_restart_no_lp': 0 0 0 0 0 0
'lb_tree_search': 210 10'833 1'403 48'748 0 82
'max_lp_sym': 695 19'551 73'505 97'270 0 158
'no_lp': 2'472 47'447 131'301 842'347 0 40
'objective_lb_search': 740 24'461 27'822 127'199 0 168
'probing': 0 0 0 1 0 0
'probing_max_lp': 0 0 0 0 0 0
'probing_no_lp': 958 3'314 68'341 225'833 0 29
'pseudo_costs': 304 1'577 14'900 127'466 0 88
'quick_restart': 51 1'080 1'939 8'794 0 20
'quick_restart_no_lp': 1'070 8'301 67'541 355'977 0 425
'reduced_costs': 329 5'534 26'449 68'538 0 82
Vivification Clauses Decisions LitTrue Subsumed LitRemoved DecisionReused Conflicts
'core': 2'728 10'912 0 0 0 0 0
'default_lp': 0 0 0 0 0 0 0
'fs_random': 0 0 0 0 0 0 0
'fs_random_no_lp': 0 0 0 0 0 0 0
'fs_random_no_lp': 0 0 0 0 0 0 0
'fs_random_quick_restart': 0 0 0 0 0 0 0
'fs_random_quick_restart_no_lp': 0 0 0 0 0 0 0
'lb_tree_search': 0 0 0 0 0 0 0
'max_lp_sym': 0 0 0 0 0 0 0
'no_lp': 0 0 0 0 0 0 0
'objective_lb_search': 0 0 0 0 0 0 0
'probing': 0 0 0 0 0 0 0
'probing_max_lp': 0 0 0 0 0 0 0
'probing_no_lp': 0 0 0 0 0 0 0
'pseudo_costs': 0 0 0 0 0 0 0
'quick_restart': 0 0 0 0 0 0 0
'quick_restart_no_lp': 0 0 0 0 0 0 0
'reduced_costs': 0 0 0 0 0 0 0
Clause deletion at_true l_and_not(l) to_binary sub_conflict sub_extra sub_decisions sub_eager sub_vivify sub_probing sub_inpro blocked eliminated forgotten promoted conflicts
'core': 6'893 8 1 113 19 0 10 0 0 86 0 0 1'483 26'603 13'063
'default_lp': 9 1 0 54 3 0 3 0 0 0 0 0 0 757 326
'fs_random': 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
'fs_random_no_lp': 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
'fs_random_no_lp': 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
'fs_random_quick_restart': 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
'fs_random_quick_restart_no_lp': 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
'lb_tree_search': 1 0 0 79 0 0 3 0 0 0 0 0 0 1'011 465
'max_lp_sym': 4 0 0 149 1 0 9 0 0 0 0 0 0 1'733 716
'no_lp': 1'128 449 0 38 0 0 2 0 0 0 0 0 0 5'260 2'653
'objective_lb_search': 0 2 0 167 3 0 1 0 0 0 0 0 0 1'936 777
'probing': 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
'probing_max_lp': 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
'probing_no_lp': 0 0 0 29 1 0 0 0 0 0 0 0 0 2'236 1'142
'pseudo_costs': 6 0 0 86 0 0 2 0 0 0 0 0 0 2'330 687
'quick_restart': 8 2 0 20 0 0 0 0 0 0 0 0 0 165 98
'quick_restart_no_lp': 132 136 0 392 7 0 33 0 0 0 0 0 0 2'708 1'466
'reduced_costs': 4 0 0 78 8 0 4 0 0 0 0 0 0 1'078 481
Lp stats Component Iterations AddedCuts OPTIMAL DUAL_F. DUAL_U.
'default_lp': 1 8'541 104 794 0 0
'lb_tree_search': 1 5'104 115 1'809 27 0
'max_lp_sym': 1 3'466 88 981 11 0
'objective_lb_search': 1 4'691 65 1'212 1 0
'probing': 1 2'660 553 247 0 0
'probing_max_lp': 1 2'467 518 176 17 0
'pseudo_costs': 1 4'351 100 1'337 31 0
'quick_restart': 1 4'392 220 871 0 0
'reduced_costs': 1 5'363 149 890 89 0
Lp dimension Final dimension of first component
'default_lp': 76 rows, 560 columns, 2389 entries
'lb_tree_search': 62 rows, 560 columns, 552 entries
'max_lp_sym': 30 rows, 532 columns, 270 entries
'objective_lb_search': 90 rows, 560 columns, 3296 entries
'probing': 361 rows, 560 columns, 32181 entries
'probing_max_lp': 313 rows, 560 columns, 21486 entries
'pseudo_costs': 97 rows, 560 columns, 4212 entries
'quick_restart': 111 rows, 560 columns, 6025 entries
'reduced_costs': 44 rows, 560 columns, 2648 entries
Lp debug CutPropag CutEqPropag Adjust Overflow Bad BadScaling
'default_lp': 0 0 529 0 38 0
'lb_tree_search': 0 0 1'711 0 70 0
'max_lp_sym': 0 0 887 0 91 0
'objective_lb_search': 0 0 988 0 18 0
'probing': 0 0 142 0 466 0
'probing_max_lp': 0 0 119 0 494 0
'pseudo_costs': 0 0 1'255 0 20 0
'quick_restart': 0 0 781 0 112 0
'reduced_costs': 0 0 624 0 60 0
Lp pool Constraints Updates Simplif Merged Shortened Split Strengthened Cuts/Call
'default_lp': 248 0 426 0 260 0 0 104/144
'lb_tree_search': 259 0 428 0 284 0 0 115/158
'max_lp_sym': 225 0 580 0 373 0 0 88/133
'objective_lb_search': 209 0 373 0 202 0 0 65/86
'probing': 697 0 1'430 0 1'231 0 0 553/710
'probing_max_lp': 662 0 449 0 449 0 0 518/649
'pseudo_costs': 244 0 376 0 252 0 0 100/140
'quick_restart': 364 0 820 0 436 0 0 220/301
'reduced_costs': 293 0 626 0 387 0 0 149/228
Lp Cut default_lp max_lp_sym quick_restart reduced_costs pseudo_costs lb_tree_search probing objective_lb_search probing_max_lp
CG_FF: 11 6 12 10 13 4 48 5 31
CG_K: - 4 10 8 4 2 24 2 34
CG_KL: 1 - 8 8 4 2 22 1 24
CG_R: 34 17 68 50 22 19 162 10 139
MIR_1_FF: 17 24 40 22 17 24 91 15 89
MIR_1_K: 7 6 15 10 8 9 27 8 37
MIR_1_KL: 11 7 24 16 13 21 51 9 63
MIR_1_R: 17 22 40 25 16 25 116 15 97
ZERO_HALF_FF: 3 1 1 - 1 3 4 - 1
ZERO_HALF_K: - - - - - 1 - - 1
ZERO_HALF_KL: - - - - 1 1 3 - 1
ZERO_HALF_R: 3 1 2 - 1 4 5 - 1
LNS stats Improv/Calls Closed Difficulty TimeLimit
'graph_arc_lns': 1/1 0% 2.93e-01 0.10
'graph_cst_lns': 1/1 0% 2.93e-01 0.10
'graph_dec_lns': 1/1 0% 2.93e-01 0.10
'graph_var_lns': 2/2 50% 4.62e-01 0.10
'lb_relax_lns': 1/1 0% 2.93e-01 0.50
'rins/rens': 1/2 0% 1.86e-01 0.10
'rnd_cst_lns': 1/1 0% 2.93e-01 0.10
'rnd_var_lns': 1/2 0% 1.86e-01 0.10
LS stats Batches Restarts/Perturbs LinMoves GenMoves CompoundMoves Bactracks WeightUpdates ScoreComputed
'ls_lin_restart_decay_compound': 1 1 0 0 0 0 17'617 13'480
'ls_lin_restart_decay_compound_perturb': 2 2 0 276 36 120 3 19'811
'ls_restart_compound': 1 1 0 31 3 14 0 2'788
'ls_restart_compound_perturb': 1 1 0 0 0 0 17'789 300
'ls_restart_decay': 1 1 3 0 0 0 7 516
'ls_restart_decay_compound': 1 1 0 0 0 0 17'617 13'480
'ls_restart_perturb': 2 2 5'721 0 0 0 6'005 1'120
Solutions (16) Num Rank
'core': 4 [4,6]
'default_lp': 4 [9,15]
'graph_var_lns': 2 [15,16]
'ls_lin_restart_decay_compound_perturb': 2 [8,9]
'ls_restart_compound': 2 [10,11]
'ls_restart_decay': 2 [6,7]
'ls_restart_perturb': 2 [7,8]
'no_lp': 8 [0,4]
'quick_restart_no_lp': 2 [13,14]
'reduced_costs': 4 [11,13]
Objective bounds Num
'am1_presolve': 1
'default_lp': 1
'initial_domain': 1
'probing_max_lp': 1
Solution repositories Added Queried Synchro
'alternative_path': 1 0 1
'best_solutions': 41 25 26
'fj solution hints': 0 0 0
'lp solutions': 68 2 14
'pump': 10 0
Improving bounds shared Num Sym
'default_lp': 3 0
'probing': 1 1
'probing_max_lp': 7 0
'quick_restart': 69 0
'reduced_costs': 144 0
Clauses shared #Exported #Imported #BinaryRead #BinaryTotal
'core': 0 0 70 70
'default_lp': 0 0 4 70
'lb_tree_search': 0 0 33 70
'max_lp_sym': 7 0 7 70
'no_lp': 0 0 50 70
'objective_lb_search': 0 0 70 70
'probing': 47 0 4 70
'probing_max_lp': 16 0 7 70
'probing_no_lp': 0 0 70 70
'pseudo_costs': 0 0 70 70
'quick_restart': 0 0 70 70
'quick_restart_no_lp': 0 0 70 70
'reduced_costs': 0 0 33 70
LRAT_status: NA
CpSolverResponse summary:
status: OPTIMAL
objective: 2270
best_bound: 2270
integers: 0
booleans: 0
conflicts: 0
branches: 0
propagations: 0
integer_propagations: 0
restarts: 0
lp_iterations: 0
walltime: 0.18537
usertime: 0.185371
deterministic_time: 2.73518
gap_integral: 0.44563
solution_fingerprint: 0x7157bac31786971fThe search phase: who is moving the bounds?
#2 0.07s best:1050 next:[1051,7125] fj_long_default(...)
#3 0.08s best:1051 next:[1052,7125] quick_restart_no_lp (fixed_bools=0/884)
#15 0.13s best:1064 next:[1065,1579] quick_restart_no_lp (fixed_bools=28/924)
#Bound 8.73s best:1449 next:[1450,1528] lb_tree_search (nodes=13/18 ...)
#Bound 29.35s best:1450 next:[1451,1515] objective_lb_search#Nlines = new incumbent (better solution);#Boundlines = better lower bound.- The trailing tag is the subsolver responsible.
best:/next:= current objective and the remaining bound gap.
The payoff: which strategies actually contributed
CP-SAT tabulates it for you near the end of the log:
A handful of subsolvers found every solution and every bound. The rest of the portfolio contributed nothing on this instance.
One trap in the summary block
These counters are not a portfolio-wide sum. They belong to the single subsolver that held the final solution. For per-strategy effort, read the per-worker Search stats and the Task timing block — not the summary.
Insight → action: prune the portfolio
If the same few subsolvers do all the work on your instance class, stop paying for the rest.
Validate on the whole benchmark set, not one log. One instance’s contributors are a hypothesis — confirm it before pruning, or you re-create the overfitting trap from the first half.
The risk: tuning away the safety net
The defaults you start from were tuned over a wide, diverse range of benchmarks. Narrow them to your instances and you narrow what the solver can still handle.
- Tune to your instance set and you optimize for it. Instances it does not represent will most likely get slower.
- Even a representative set under-samples the rare, truly hard instance. That is the case the portfolio and the symmetry handling were there to crack.
- The trap: a better median runtime, but more unsolved instances in production.
A faster median is not a safer solver. Before you prune a strategy or ship a tuned parameter, check the tail on hard instances, not just the average on easy ones.
From Guessing to Searching
Tuning is a search problem. Treat it like one.
Two different questions
Algorithm selection
Which solver / strategy for this instance?
Pick from a discrete set: CP-SAT vs. Gurobi; no_lp vs. max_lp. The no-free-lunch theorem is exactly why this matters.
Algorithm configuration
Given the algorithm, what parameter values?
Tune a (large, mixed) parameter vector: worker count, linearization level, LNS settings, presolve toggles.
This section is about configuration. The log-driven subsolver pruning from the last section was a hand-rolled instance of it.
Tuning is black-box optimization
You optimize a function you can only sample, never inspect, and every sample is expensive — so the budget is small, and the search strategy decides how well it is spent.
Three search strategies over the parameter space
Same surface, same 36-evaluation budget; only the sampler changes (grid / random / TPE). Top strips: how each budget sampled the important parameter.
Model-based search: learn where to look next
- Surrogate (blue): posterior mean + uncertainty band over a few expensive runs.
- Acquisition (orange): low predicted objective and high uncertainty; its peak is the next run.
- Each sample shrinks the band where we looked, so the search self-concentrates near the optimum.
TPE (Tree-structured Parzen Estimator) models good vs. bad configs and samples toward the good; Gaussian-process BO (SMAC) is the other classic.
What to actually tune in CP-SAT
| Knob | Why it can matter |
|---|---|
num_workers |
fewer workers → higher clock, more bandwidth; sometimes faster |
subsolvers / ignore_subsolvers |
drop strategies the log showed contribute nothing |
linearization_level |
wrong if the LP relaxation is weak (drop max_lp) |
| LNS / presolve toggles | large effect on hard instances |
| decision strategy | exploit known problem structure |
Each evaluation is a full solve over many instances — the budget is small and expensive. This is exactly the regime where model-based search pays off over grid.
Commercial solvers (Gurobi, FICO Xpress) ship dedicated tuning tools that automate this search for their own parameters.
A Short Optuna Tutorial
One framework, any algorithm: define the space, pick a sampler, read what mattered.
The three moving parts
- Objective function takes a
trial, picks parameter values, runs the work, and returns one number to minimize or maximize. - Study drives the search with a sampler (TPE by default) and remembers every trial it has seen.
- Suggest API (
trial.suggest_int / suggest_float / suggest_categorical) defines the search space inline, as the objective runs.
The search space is define-by-run: there is no separate config file. The space is ordinary Python, so loops, computed bounds, and conditional parameters all just work.
The suggest API: build the space as the objective runs
# define-by-run: the space is built WHILE the objective executes,
# so it is plain Python -- loops, computed bounds, conditionals.
trial.suggest_int("num_workers", 1, 16) # integer range
trial.suggest_int("linearization_level", 0, 2) # small ordinal knob
trial.suggest_categorical("use_phase_saving", [False, True]) # unordered choice
trial.suggest_float("penalty_weight", 1e-3, 1e3, log=True) # continuous, log-scaled
if trial.suggest_categorical("use_lns", [True, False]): # conditional parameter
trial.suggest_int("lns_workers", 1, 8) # sampled only when use_lns is onCP-SAT’s knobs are mostly small integers and enums, so suggest_int and suggest_categorical do most of the work. suggest_float(..., log=True) is the tool for the continuous penalties and rates of other algorithms.
The objective: wire Optuna to your solver
import optuna
from ortools.sat.python import cp_model
from my_benchmark import INSTANCES, build_model, par2 # your set + metric from part one
def objective(trial: optuna.Trial) -> float:
p = {"num_workers": trial.suggest_int("num_workers", 1, 16),
"linearization_level": trial.suggest_int("linearization_level", 0, 2),
"cp_model_probing_level": trial.suggest_int("cp_model_probing_level", 0, 2)}
total = 0.0
for inst in INSTANCES: # average over the WHOLE set
solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 30
for name, value in p.items():
setattr(solver.parameters, name, value)
total += par2(solver, solver.solve(build_model(inst)), limit=30)
return total / len(INSTANCES) # one scalar back to OptunaThe objective is your benchmark from the first half, wrapped in a loop. Anything you can measure into a single number (PAR2, gap integral, mean runtime) you can hand to Optuna and tune.
Samplers: swap the search strategy in one line
| Sampler | Strategy | Reach for it when |
|---|---|---|
TPESampler (default) |
model-based (Tree-structured Parzen) | the workhorse: many trials, mixed parameter types |
RandomSampler |
uniform random | the honest baseline; cheap and embarrassingly parallel |
GridSampler |
exhaustive grid | only for a genuinely tiny space |
CmaEsSampler |
evolution strategy (CMA-ES) | mostly-continuous, higher-dimensional spaces |
QMCSampler |
quasi-random (Sobol) | better-spread coverage than plain random |
Swapping TPESampler for RandomSampler is a one-line change on the same objective. That is how you prove model-based search earned its keep over the random baseline from the first half.
Spend the budget well: seed the default, prune the hopeless
study = optuna.create_study(direction="minimize",
pruner=optuna.pruners.MedianPruner()) # cap hopeless trials
study.enqueue_trial({"num_workers": 8, "linearization_level": 1,
"cp_model_probing_level": 1}) # evaluate the solver's DEFAULT, first
study.enqueue_trial({"num_workers": 16}) # ... and an expert guess
# inside the objective, report progress so the pruner can act:
for i, inst in enumerate(INSTANCES):
... # solve inst, update running_par2
trial.report(running_par2, step=i)
if trial.should_prune(): # already worse than the median run?
raise optuna.TrialPruned()Seed the default with enqueue_trial so a “win” is always measured against out-of-the-box, and you never ship something worse. Pruning then spends the saved budget on promising configs instead of finishing doomed ones.
Persist and distribute: tuning a solver is expensive
A local file is enough to survive crashes and resume. It does not hold up for many nodes: SQLite locking over a shared/network filesystem is unreliable.
# Point every worker at one real database server
study = optuna.create_study(
storage="postgresql://user:pw@db-host:5432/optuna",
study_name="cpsat-tuning",
direction="minimize",
load_if_exists=True, # workers attach to the SAME study
)
study.optimize(objective, n_trials=200) # run this SAME script on every nodeRun the script on many cluster nodes at once; the SQL server serializes trial hand-out and result writes, so Optuna coordinates them safely.
A local SQLite file gives you persistence and resume. For real distribution across a cluster, back the study with a proper SQL server (PostgreSQL/MySQL) — one database, many workers, one shared study.
Inspect what mattered
optuna.importance.get_param_importances(study)
# -> {'num_workers': 0.41, 'linearization_level': 0.28, ...}
optuna.visualization.plot_optimization_history(study) # are we still improving?
optuna.visualization.plot_param_importances(study) # which knob carried the gains?
optuna.visualization.plot_slice(study, params=["num_workers"]) # how does it respond?
optuna.visualization.plot_contour(study) # interactions between knobsParameter importance is the tuning analogue of the log’s Solutions and Objective bounds blocks: it names the knobs that did the work, so the next study fixes the rest and searches a smaller space.
The catch with exhaustive search: seed variance and overfitting
Tune the seed and report the lucky 0.13 s run: a flawless “speedup” built on pure noise. It is overfitting at its most extreme, and it evaporates on the next instance. So average several samples per trial, re-verify a new best with more samples, and validate on the full set.
Wrap-up
That’s all folks!
What this tutorial covered
Starting CP-SAT solver v9.15.6755
Setting number of workers to 24
Initial optimization model 'multiple_knapsack':
#Variables: 560 (#bools: 560)
#kLinearN: 144 (#terms: 1'120)
Starting presolve at 0.00s
[Symmetry] #generators: 7, average support size: 8
presolved: 560 vars, 144 constraints
Starting search at 0.01s with 24 workers
#1 0.01s best:1891 next:[1892,3797] no_lp
#5 0.01s best:1939 next:[1940,2271] core
#10 0.01s best:2226 next:[2227,2271] default_lp
#13 0.02s best:2266 next:[2267,2271] reduced_costs
#Bound 0.05s best:2267 next:[2268,2270] probing_max_lp
#15 0.08s best:2269 next:[2270,2270] default_lp
#16 0.18s best:2270 next:[] graph_var_lns
Solutions (7) Num Rank
'no_lp': 3 [1,7]
'quick_restart': 1 [3,3]
'quick_restart_no_lp': 3 [2,5]
CpSolverResponse summary:
status: OPTIMAL
objective: 2270
best_bound: 2270
gap_integral: 0.44563
Benchmarking
Reading the log
Parameter tuning
- A win needs the full instance set, not three.
- Median + IQR; cactus / performance / split under timeouts.
- Match the metric and plot to the goal.
- The Solutions and bounds blocks show the real work.
- Strategy ranks point at what to tune.
- A tuning hypothesis, for free.
- Random search is the baseline.
- Model-based search (TPE) spends budget where it pays.
- Prune relentlessly; run it in Optuna.
References
Algorithm Engineering SS 2026 — T05 Benchmarking & Parameter Tuning