Expand ILP solver support to more problem types

[GiggleLiu]

Summary

The ILP solver infrastructure is now in place with support for IndependentSetT and VertexCoverT. This issue tracks expanding ILP support to additional problem types.

Current State

The ToILP trait and ILPSolver are implemented with:

• IndependentSetT: max Σ wᵢxᵢ s.t. xᵤ + xᵥ ≤ 1 ∀(u,v)∈E
• VertexCoverT: min Σ wᵢxᵢ s.t. xᵤ + xᵥ ≥ 1 ∀(u,v)∈E

Planned Problem Support

Graph Problems (Easy - Linear Constraints)

• CliqueT - Similar to IS but on complement graph

  • max Σ wᵢxᵢ s.t. xᵤ + xᵥ ≤ 1 ∀(u,v)∉E

• DominatingSet - Minimization with coverage constraints

  • min Σ wᵢxᵢ s.t. xᵥ + Σᵤ∈N(v) xᵤ ≥ 1 ∀v

• Matching - Edge selection with vertex degree constraints

  • max Σ wₑxₑ s.t. Σₑ∋v xₑ ≤ 1 ∀v

Set Problems (Easy - Linear Constraints)

• SetPacking - Similar to IS on hypergraph

  • max Σ wᵢxᵢ s.t. Σⱼ∈S xⱼ ≤ 1 ∀ overlapping sets S

• SetCovering - Similar to VC on hypergraph

  • min Σ wᵢxᵢ s.t. Σⱼ∈covering(e) xⱼ ≥ 1 ∀ elements e

Satisfiability (Medium)

• Satisfiability (SAT) - Feasibility problem
  • Σ literals ≥ 1 per clause (literals are xᵢ or 1-xᵢ)

Complex Problems (Harder - Requires Linearization)

• MaxCut - Quadratic objective needs linearization

  • max Σ wᵢⱼ(xᵤ + xᵥ - 2xᵤxᵥ)
  • Requires: auxiliary variables yᵤᵥ = xᵤ·xᵥ with McCormick constraints

• Coloring - Multi-valued variables

  • Requires: binary encoding xᵢₖ (vertex i has color k)
  • Constraints: Σₖ xᵢₖ = 1, xᵢₖ + xⱼₖ ≤ 1 ∀(i,j)∈E

• QUBO/SpinGlass - Quadratic optimization

  • Requires linearization similar to MaxCut

Implementation Notes

1. For linear problems, extend the ILPConstraintSpec trait pattern used for IS/VC
2. For problems with different structures (SAT, Set problems), implement ToILP directly
3. For quadratic problems, implement linearization helpers

References

• ILP Formulations for Graph Problems
• Linearization Techniques

[GiggleLiu]

Implemented in commits d85af0c..6b3c9c0:

• ILP is now a first-class problem type with VarBounds, LinearConstraint, and ILP structs
• Implemented ReduceTo<ILP> reductions for 7 problem types:
  • IndependentSet
  • VertexCover
  • Clique
  • DominatingSet
  • Matching
  • SetPacking
  • SetCovering
• ILPSolver now has solve(&ILP) and solve_reduced<P: ReduceTo<ILP>>(&P) methods
• Removed legacy ToILP, ILPFormulation, ILPConstraintSpec traits

All 761 tests pass.