DefaultSolver classification for all 115 problem types

[GiggleLiu]

Summary

Classify every problem type by its best available solving strategy, to guide the design of a DefaultSolver dispatch mechanism.

Methodology

For each of the 115 registered problem types, we classify:

1. ILP — Has an existing witness-capable reduction path to ILP (via pred path <Problem> ILP)
2. ILP (easy) — No existing path, but a standard ILP formulation exists and could be implemented in <100 lines
3. ILP (complex) — Known ILP formulation but requires >100 lines (big-M, linearization, subtour elimination, etc.)
4. Poly — Polynomial-time variant (not NP-hard); a specialized exact algorithm exists
5. Specialized — Has a known exact algorithm (DP, branch-and-bound) that dominates brute-force
6. Brute-force — Only practical solver is exhaustive enumeration
7. PSPACE+ — PSPACE-complete or harder; ILP cannot naturally express the problem

Brute-force scalability depends on configuration space size:

• Binary (vec![2; n]): 2^n configs → practical up to n ≈ 25
• k-ary (vec![k; n]): k^n configs → practical up to n ≈ 15 for k=3, n ≈ 10 for k=5
• Permutation-like (vec![n; n]): n^n configs → practical up to n ≈ 8

---

Tier 1: Has existing ILP reduction path (32 problems)

These problems already have a witness-capable reduction chain to ILP in the codebase. The DefaultSolver should dispatch to ILPSolver::solve_via_reduction().

Problem	ILP Path Hops	ILP Variant	Config Space
ILP	0	(is ILP)	varies
BinPacking	2	bool	2^num_items
CircuitSAT	2	bool	2^num_variables
ClosestVectorProblem	3	bool	2^num_basis_vectors
ConsistencyOfDatabaseFrequencyTables	2	bool	large
Factoring	3	bool	2^bits
GraphPartitioning	2	bool	2^num_vertices
HamiltonianCircuit	3	bool	n^2 binary
IntegralFlowBundles	2	i32	cap^num_arcs
KColoring (KN,K3,K4,K5)	2	bool	k^num_vertices
Knapsack	2	bool	2^num_items
KSatisfiability (KN,K3)	4	bool	2^num_variables
LongestCommonSubsequence	2	bool	alpha^bound
LongestPath	2	i32	2^num_edges
MaxCut	5	bool	2^num_vertices
MaximumClique	2	bool	2^num_vertices
MaximumIndependentSet	4	bool	2^num_vertices
MaximumMatching	2	bool	2^num_edges
MaximumSetPacking	3	bool	2^num_sets
MinimumDominatingSet	2	bool	2^num_vertices
MinimumFeedbackVertexSet	2	i32	2^num_vertices
MinimumMultiwayCut	2	bool	2^num_vertices
MinimumSetCovering	2	bool	2^num_sets
MinimumVertexCover	3	bool	2^num_vertices
Partition	3	bool	2^num_elements
QUBO	2	bool	2^num_vars
Satisfiability	3	bool	2^num_variables
SequencingToMinimizeWeightedCompletionTime	2	i32	n^n
SpinGlass	4	bool	2^num_spins
SteinerTree	2	bool	2^num_vertices
SubsetSum	4	bool	2^num_elements
TravelingSalesman	2	bool	2^num_edges

---

Tier 2: Easy ILP formulation — no existing path (<100 lines) (24 problems)

These should be prioritized for new ReduceTo<ILP> implementations. Each has a textbook ILP formulation.

Problem	ILP Sketch	Est. Lines
MinimumHittingSet	Binary x_e per element; ∀ set S: Σ x_e ≥ 1 (dual of set covering)	~60
ExactCoverBy3Sets	Binary x_j per triple; ∀ element: Σ x_j = 1	~60
NAESatisfiability	Binary x_i; ∀ clause: 1 ≤ Σ ≤ |clause|−1	~70
KClique	Binary x_v; Σ x_v = k; non-edge exclusion	~65
MinimumFeedbackArcSet	Binary y_a + MTZ ordering (adapt existing FVS→ILP)	~80
MultiprocessorScheduling	Binary x_{jm}; assignment + makespan variable	~75
PartiallyOrderedKnapsack	Standard knapsack ILP + precedence x_i ≤ x_j	~70
MaximalIS	MIS constraints + maximality: x_v + Σ_{u∈N(v)} x_u ≥ 1	~70
UndirectedTwoCommodityIntegralFlow	Integer flow per commodity; conservation + shared capacity	~80
DirectedTwoCommodityIntegralFlow	Same as above but directed graph	~80
CapacityAssignment	Binary x_{l,c}; assignment + demand satisfaction	~75
ExpectedRetrievalCost	Binary x_{r,s}; assignment + cost linearization	~75
MultipleCopyFileAllocation	Binary x_{f,n}; access cost + storage constraints	~75
MinimumSumMulticenter	Binary x_j, y_{ij}; facility location / p-median	~80
MinMaxMulticenter	p-center: binary x_j, y_{ij}; minimax with auxiliary z	~85
ShortestWeightConstrainedPath	Binary x_e; flow conservation + weight constraint	~75
PartitionIntoTriangles	Binary triangle indicators; each vertex in exactly one	~80
PartitionIntoPathsOfLength2	Binary path selection; vertex covering exactly once	~80
SumOfSquaresPartition	Binary x_{ig}; partition + equal sum-of-squares	~80
UndirectedFlowLowerBounds	Integer flow; conservation + lower/upper bounds	~70
RectilinearPictureCompression	Binary rectangle indicators; pixel coverage	~75
PrecedenceConstrainedScheduling	Binary x_{jt}; precedence + resource constraints	~85
SchedulingWithIndividualDeadlines	Binary x_{jt}; assignment + deadline constraints	~80
SequencingWithinIntervals	Binary x_{jt}; interval feasibility + non-overlap	~80

---

Tier 3: Complex ILP formulation (>100 lines) (34 problems)

These have known ILP formulations but require significant auxiliary variables, linearization, or constraint generation. DefaultSolver would fall back to brute-force unless a dedicated ILP reduction is implemented.

Problem	Why Complex	BF Scale
AcyclicPartition	Color assignment + topological ordering per color class	n^n
BalancedCompleteBipartiteSubgraph	Bipartite completeness → quadratic → McCormick linearization	2^n
BicliqueCover	Biclique validity constraints need product linearization	2^n
BiconnectivityAugmentation	2-connectivity requires flow-based formulation	2^e
BMF	Bilinear W=A·B; product linearization over Boolean semiring	2^(r·c)
BottleneckTravelingSalesman	TSP structure + minimax linearization	n²·2^n
BoundedComponentSpanningForest	Spanning forest + component size bounding (flow/labeling)	3^n
ConsecutiveBlockMinimization	Column permutation + block counting auxiliaries	n!·n
ConsecutiveOnesMatrixAugmentation	Column permutation + augmentation variables	n!·n
ConsecutiveOnesSubmatrix	Row/column selection + "consecutive" linearization	2^c
DisjointConnectingPaths	Multi-commodity flow + vertex-disjointness linking	2^e
FlowShopScheduling	Permutation variables + machine sequencing	n!
HamiltonianPath	Position-based assignment (like TSP, ~130 lines)	n²·2^n
IntegralFlowHomologousArcs	Flow variables + homologous arc coupling	cap^a
IntegralFlowWithMultipliers	Modified conservation with multipliers	cap^a
IsomorphicSpanningTree	Tree selection + isomorphism (hard to linearize)	n!
LengthBoundedDisjointPaths	Multi-commodity flow + length + disjointness	2^(k·n)
LongestCircuit	Position-based (like TSP) + circuit length max	n²·2^n
MinimumCutIntoBoundedSets	Partition variables + cut weight + size bounds	2^n
MinimumTardinessSequencing	Position scheduling + max(0,...) linearization	n^n
MixedChinesePostman	Edge traversal + Euler tour on mixed graph	n²·2^e
OptimalLinearArrangement	Permutation + |π(u)−π(v)| absolute value linearization	n^n
PaintShop	Color assignment + color-change counting	2^n
PartialFeedbackEdgeSet	Remove exactly k edges; topological ordering with big-M	2^e
PathConstrainedNetworkFlow	Integer flow per allowed path; capacity aggregation	cap^p
QuadraticAssignment	Permutation + product linearization x_{ij}·x_{kl}	n!
ResourceConstrainedScheduling	Time-indexed x_{jt} + resource capacity + precedence	d^n
RootedTreeArrangement	Position variables + parent-child ordering	n^n
RootedTreeStorageAssignment	Assignment + capacity/tree structure	u^u
RuralPostman	Edge traversal + connectivity on required edges	n²·2^n
SequencingToMinimizeMaximumCumulativeCost	Permutation + cumulative cost + minimax	n!
SequencingToMinimizeWeightedTardiness	Permutation + max(0,...) tardiness linearization	n!
SequencingWithReleaseTimesAndDeadlines	Release + deadline + non-overlap constraints	n^n
ShortestCommonSupersequence	Position-based alignment for multiple strings	α^L
SparseMatrixCompression	Row grouping + compatibility constraints	k^r
StackerCrane	Directed rural postman + pickup/delivery pairing	n²·2^a
SteinerTreeInGraphs	Flow-based connectivity for Steiner terminals (~150 lines)	2^e
StringToStringCorrection	Edit operation selection + alignment constraints	(2s+1)^b
StrongConnectivityAugmentation	Arc selection + strong connectivity (flow/cut-based)	2^a
SubgraphIsomorphism	Binary mapping + edge preservation	n_h^n_p
TimetableDesign	3-index assignment + conflict/availability	2^(c·p·t)

---

Tier 4: Polynomial-time variants (3 variants)

These have polynomial-time algorithms and should use a specialized solver rather than brute-force or ILP.

Variant	Complexity	Algorithm
MaximumMatching/SimpleGraph/i32	O(n³)	Edmonds' blossom algorithm
KColoring/SimpleGraph/K2	O(n+m)	BFS bipartiteness check
KSatisfiability/K2	O(n+m)	Implication graph / Tarjan SCC

Note: MaximumMatching already has an ILP path, but its polynomial solver is far more efficient.

---

Tier 5: Specialized exact algorithms (4 problems)

These have structure that specialized algorithms exploit better than generic ILP.

Problem	Algorithm	Notes
GroupingBySwapping	DP on permutations / sorting networks	Adjacent-swap structure
KthBestSpanningTree	Iterative Lawler/Yen-style enumeration	Needs k iterations of MST
MinimumDummyActivitiesPert	Series-parallel decomposition	PERT network structure
MultipleChoiceBranching	DP on branching programs	Tree structure

---

Tier 6: PSPACE-complete or harder (2 problems)

ILP fundamentally cannot express alternating quantifiers. These require game-tree search or QSAT solvers.

Problem	Complexity Class	Notes
GeneralizedHex	PSPACE-complete	Two-player game; alpha-beta / MCTS
QuantifiedBooleanFormulas	PSPACE-complete	QSAT solver (QCDCL, expansion-based)

---

Tier 7: Obscure / no natural ILP formulation (11 problems)

Database theory and combinatorial structure problems where ILP is not a natural fit. Brute-force is the only current option.

Problem	Domain	BF Scale	Notes
AdditionalKey	Database theory	2^attrs	FD closure not easily linearized
BoyceCoddNormalFormViolation	Database theory	2^attrs	Structural FD analysis
ComparativeContainment	Set theory	2^universe	Set containment relations
ConjunctiveBooleanQuery	Database theory	domain^vars	Query evaluation
ConjunctiveQueryFoldability	Database theory	complex	Query structural property
ConsecutiveSets	Combinatorics	α^k · s	Ordering/labeling
EnsembleComputation	Set systems	complex	Specialized structure
MinimumCardinalityKey	Database theory	2^attrs	FD closure checking
PrimeAttributeName	Database theory	2^attrs	Structural FD property
SetBasis	Combinatorics	2^(k·u)	Representation constraints
TwoDimensionalConsecutiveSets	Combinatorics	α^α	2D ordering

---

Proposed DefaultSolver dispatch

DefaultSolver::solve(problem) → {
    1. If problem is a polynomial-time variant → specialized algorithm
    2. If problem has a reduction path to ILP   → ILPSolver::solve_via_reduction()
    3. If problem has Tier 2 ILP formulation    → (after implementing) ILPSolver
    4. Otherwise                                → BruteForce::solve()
}

Recommended next steps

1. Implement Tier 2 ILP reductions — 24 problems with textbook formulations. Start with the easiest:

   • MinimumHittingSet → ILP (dual of existing SetCovering→ILP, ~60 lines)
   • ExactCoverBy3Sets → ILP (set partitioning, ~60 lines)
   • NAESatisfiability → ILP (~70 lines)
   • KClique → ILP (adapt existing MaximumClique→ILP, ~65 lines)
   • MinimumFeedbackArcSet → ILP (adapt existing FVS→ILP, ~80 lines)

2. Add poly-time solvers for MaximumMatching (Edmonds'), 2-Coloring (BFS), 2-SAT (SCC)

3. Incrementally implement Tier 3 ILP reductions for the most commonly used problems (HamiltonianPath, QuadraticAssignment, FlowShopScheduling, etc.)

4. Research PSPACE solvers for GeneralizedHex and QBF (game-tree search, QSAT)

[GiggleLiu]

Tier 3 ILP batch: 2 problems deferred

During design review for the Tier 3 ILP batch (39 of 41 problems), two problems were identified as requiring separate treatment:

PartialFeedbackEdgeSet → ILP

The standard MTZ ordering approach enforces full acyclicity (forest), but the problem only requires eliminating cycles of length ≤ L. For L < n, MTZ over-constrains and can reject valid solutions. A correct static ILP requires cycle enumeration (hitting-set on all simple cycles of length ≤ L), which is exponential worst-case. Needs dedicated design work — possibly lazy constraint generation or a different formulation approach.

RootedTreeArrangement → ILP

The model has a compound config space dims() = vec![n; 2*n] — first n entries encode a parent array (rooted tree), second n entries encode a vertex-to-tree-node bijection. The ILP must simultaneously encode tree structure, bijective mapping, and stretch bounds. This is the most complex extraction among all 41 problems and warrants its own PR.

Both will be filed as separate [Rule] issues.

[zazabap]

ILP reduction -> Customized Solver -> Brute Force Three steps to guarantee high efficient solver exists.