Add HiGHS ILP solver support

[GiggleLiu]

Summary

Add an optional Integer Linear Programming (ILP) solver using HiGHS via the good_lp crate. This would enable exact solving of problems for small-medium instances and help verify reduction correctness.

Motivation

• BruteForce solver is exponential and only works for tiny instances
• ILP solvers can handle much larger instances efficiently
• Useful for testing and verification of reductions

Proposed Implementation

Dependencies

[features]
ilp = ["good_lp"]

[dependencies]
good_lp = { version = "1.8", features = ["highs"], optional = true }

Solver API

#[cfg(feature = "ilp")]
pub struct ILPSolver {
    time_limit: Option<f64>,
}

impl Solver for ILPSolver {
    fn find_best<P: Problem>(&self, problem: &P) -> Vec<Vec<usize>>;
}

Problem-specific formulations

Each problem type would need an ILP formulation:

Problem	Formulation
IndependentSet	max Σ wᵢxᵢ s.t. xᵤ + xᵥ ≤ 1 ∀(u,v)∈E
VertexCovering	min Σ wᵢxᵢ s.t. xᵤ + xᵥ ≥ 1 ∀(u,v)∈E
SetPacking	max Σ wᵢxᵢ s.t. Σ xⱼ ≤ 1 ∀ overlapping sets
MaxCut	max Σ wᵢⱼ(xᵤ + xᵥ - 2xᵤxᵥ) (linearized)
SAT	feasibility: Σ literals ≥ 1 per clause

Options

1. Trait-based: Add ToILP trait that problems implement
2. Generic: Use CSP constraints/objectives to generate ILP automatically
3. Specific: Implement ILP formulation per problem type

Tasks

• Add good_lp with highs feature as optional dependency
• Create ILPSolver struct with configuration options
• Implement ILP formulations for graph problems (IS, VC, MaxCut)
• Implement ILP formulations for set problems (SetPacking, SetCovering)
• Implement ILP formulations for SAT
• Add integration tests comparing ILP vs BruteForce results
• Add documentation and examples

References

• good_lp crate
• HiGHS solver

[GiggleLiu]

Implemented in commit 8dcc22b. See #6 for future ILP expansion plans.