Upgrade 17 decision models to optimization versions

[isPANN]

Summary

17 models in the codebase have optimization-sounding names but are implemented as decision problems (Value = Or with a bound threshold field). They should be upgraded to true optimization problems (Value = Max/Min), removing the threshold parameter and letting the solver find the optimal value directly.

Motivation: Decision versions are less useful for problem-solving — knowing "yes, there exists a solution ≤ k" is less valuable than knowing the actual optimum. Optimization versions also enable value-preserving reductions (Category A/B↑ rules) instead of threshold-only mappings.

Group A — Direct upgrade (12 models)

These have a single bound field that is a pure objective threshold. Upgrade: delete bound, change Value from Or to Max/Min.

Model	Threshold field	Target Value	Existing → ILP rule?
LongestCommonSubsequence	bound: usize	Max	Yes — rewrite
LongestCircuit	bound: W::Sum	Max	No
ShortestCommonSupersequence	bound: usize	Min	No
OptimalLinearArrangement	bound: usize	Min	No
RuralPostman	bound: W::Sum	Min	No
StackerCrane	bound: i32	Min	No
MixedChinesePostman	bound: W::Sum	Min	No
MultipleCopyFileAllocation	bound: i64	Min	Yes — rewrite
ExpectedRetrievalCost	bound: f64	Min	Yes — rewrite
SumOfSquaresPartition	bound: i64	Min	Yes — rewrite
MinimumCardinalityKey	bound: i64	Min	No
SequencingToMinimizeMaximumCumulativeCost	bound: i64	Min	No

Group B — Constrained optimization redesign (5 models)

These have multiple bound/constraint parameters. One parameter is a problem constraint, the other is the optimization target. Upgrade: keep the constraint parameter, remove the threshold, optimize the objective.

Model	Constraint (keep)	Threshold (remove)	Target Value	Existing → ILP rule?
MinMaxMulticenter	k: usize (num centers)	bound: W::Sum	Min	Yes — rewrite
LengthBoundedDisjointPaths	max_length: usize	num_paths_required: usize	Max	No
MinimumCutIntoBoundedSets	size_bound: usize	cut_bound: W::Sum	Min	No
ShortestWeightConstrainedPath	weight_bound: N::Sum	length_bound: N::Sum	Min (path length)	Yes — rewrite
CapacityAssignment	delay_budget: u64	cost_budget: u64	Min (cost)	Yes — rewrite

Upgrade checklist per model

• Remove threshold field from struct
• Change type Value from Or to Max<T> or Min<T>
• Update evaluate() to return the objective value instead of threshold comparison
• Update dims() if the bound was encoded in the config space
• Update declare_variants! registration
• Update or rewrite → ILP reduction if one exists (add objective function)
• Update unit tests
• Update paper entry in docs/paper/reductions.typ if applicable
• Update canonical example in src/example_db/model_builders.rs if applicable

Notes

• No model appears as a target in any existing reduction rule, so there are no downstream dependency concerns.
• 6 models have existing → ILP reductions that need rewriting (feasibility ILP → optimization ILP with objective function).
• Group B bicriteria decisions (ShortestWeightConstrainedPath, CapacityAssignment) follow the convention: minimize cost subject to the more natural constraint.
• This upgrade unblocks ~12 Category B↑ reduction rules where the source is already optimization (MinVC, MinDomSet, etc.) and the target can now support value-preserving reductions.

[zazabap]

Correction to my previous comment

My earlier comment flagging LongestCommonSubsequence, ShortestCommonSupersequence, and LengthBoundedDisjointPaths as needing "config space redesign" was wrong — the checklist in this issue already covers that case ("Update dims() if the bound was encoded in the config space"). All 17 models are correctly identified. Apologies for the noise.

Additional models to consider (5)

After auditing all 80 Or models, these 5 have bounds only in evaluate() (not in dims()) and have clear optimization formulations:

Model	Bound field	dims()	Target Value
StrongConnectivityAugmentation	bound: W::Sum	vec![2; num_candidate_arcs]	Min<W::Sum>
RectilinearPictureCompression	bound: i64	vec![2; num_maximal_rects]	Min<i64>
FlowShopScheduling	deadline: u64	Lehmer code (permutation)	Min<u64> (makespan)
MultiprocessorScheduling	deadline: u64	vec![num_processors; num_tasks]	Min<u64> (makespan)
MultipleChoiceBranching	threshold: W::Sum	vec![2; num_arcs]	Max<W::Sum>

All other Or models are either genuinely decision (no bound, or bound defines dims(), or bound is a structural parameter like k in KClique).