problemreductions/solvers/ilp/
solver.rs

1//! ILP solver implementation using HiGHS.
2
3use crate::models::algebraic::{Comparison, ObjectiveSense, VariableDomain, ILP};
4use crate::rules::{ReduceTo, ReductionResult};
5use good_lp::{default_solver, variable, ProblemVariables, Solution, SolverModel, Variable};
6
7/// An ILP solver using the HiGHS backend.
8///
9/// This solver solves Integer Linear Programming problems directly using the HiGHS solver.
10///
11/// # Example
12///
13/// ```rust,ignore
14/// use problemreductions::models::algebraic::{ILP, LinearConstraint, ObjectiveSense};
15/// use problemreductions::solvers::ILPSolver;
16///
17/// // Create a simple binary ILP: maximize x0 + 2*x1 subject to x0 + x1 <= 1
18/// let ilp = ILP::<bool>::new(
19///     2,
20///     vec![LinearConstraint::le(vec![(0, 1.0), (1, 1.0)], 1.0)],
21///     vec![(0, 1.0), (1, 2.0)],
22///     ObjectiveSense::Maximize,
23/// );
24///
25/// let solver = ILPSolver::new();
26/// if let Some(solution) = solver.solve(&ilp) {
27///     println!("Solution: {:?}", solution);
28/// }
29/// ```
30#[derive(Debug, Clone, Default)]
31pub struct ILPSolver {
32    /// Time limit in seconds (None = no limit).
33    pub time_limit: Option<f64>,
34}
35
36impl ILPSolver {
37    /// Create a new ILP solver with default settings.
38    pub fn new() -> Self {
39        Self::default()
40    }
41
42    /// Create an ILP solver with a time limit.
43    pub fn with_time_limit(seconds: f64) -> Self {
44        Self {
45            time_limit: Some(seconds),
46        }
47    }
48
49    /// Solve an ILP problem directly.
50    ///
51    /// Returns `None` if the problem is infeasible or the solver fails.
52    /// The returned solution is a configuration vector where each element
53    /// is the variable value (config index = value).
54    pub fn solve<V: VariableDomain>(&self, problem: &ILP<V>) -> Option<Vec<usize>> {
55        let n = problem.num_vars;
56        if n == 0 {
57            return Some(vec![]);
58        }
59
60        // Create integer variables with bounds from variable domain
61        let mut vars_builder = ProblemVariables::new();
62        let vars: Vec<Variable> = (0..n)
63            .map(|_| {
64                let mut v = variable().integer();
65                v = v.min(0.0);
66                v = v.max((V::DIMS_PER_VAR - 1) as f64);
67                vars_builder.add(v)
68            })
69            .collect();
70
71        // Build objective expression
72        let objective: good_lp::Expression = problem
73            .objective
74            .iter()
75            .map(|&(var_idx, coef)| coef * vars[var_idx])
76            .sum();
77
78        // Build the model with objective
79        let unsolved = match problem.sense {
80            ObjectiveSense::Maximize => vars_builder.maximise(&objective),
81            ObjectiveSense::Minimize => vars_builder.minimise(&objective),
82        };
83
84        // Create the solver model
85        let mut model = unsolved.using(default_solver);
86
87        // Add constraints
88        for constraint in &problem.constraints {
89            // Build left-hand side expression
90            let lhs: good_lp::Expression = constraint
91                .terms
92                .iter()
93                .map(|&(var_idx, coef)| coef * vars[var_idx])
94                .sum();
95
96            // Create the constraint based on comparison type
97            let good_lp_constraint = match constraint.cmp {
98                Comparison::Le => lhs.leq(constraint.rhs),
99                Comparison::Ge => lhs.geq(constraint.rhs),
100                Comparison::Eq => lhs.eq(constraint.rhs),
101            };
102
103            model = model.with(good_lp_constraint);
104        }
105
106        // Solve
107        let solution = model.solve().ok()?;
108
109        // Extract solution: config index = value (no lower bound offset)
110        let result: Vec<usize> = vars
111            .iter()
112            .map(|v| {
113                let val = solution.value(*v);
114                val.round().max(0.0) as usize
115            })
116            .collect();
117
118        Some(result)
119    }
120
121    /// Solve any problem that reduces to `ILP<bool>`.
122    ///
123    /// This method first reduces the problem to a binary ILP, solves the ILP,
124    /// and then extracts the solution back to the original problem space.
125    ///
126    /// # Example
127    ///
128    /// ```no_run
129    /// use problemreductions::prelude::*;
130    /// use problemreductions::solvers::ILPSolver;
131    ///
132    /// // Create a problem that reduces directly to ILP.
133    /// let problem = MaximumSetPacking::<i32>::new(vec![
134    ///     vec![0, 1],
135    ///     vec![1, 2],
136    ///     vec![3, 4],
137    /// ]);
138    ///
139    /// // Solve using ILP solver
140    /// let solver = ILPSolver::new();
141    /// if let Some(solution) = solver.solve_reduced(&problem) {
142    ///     println!("Solution: {:?}", solution);
143    /// }
144    /// ```
145    pub fn solve_reduced<P>(&self, problem: &P) -> Option<Vec<usize>>
146    where
147        P: ReduceTo<ILP<bool>>,
148    {
149        let reduction = problem.reduce_to();
150        let ilp_solution = self.solve(reduction.target_problem())?;
151        Some(reduction.extract_solution(&ilp_solution))
152    }
153}
154
155#[cfg(test)]
156#[path = "../../unit_tests/solvers/ilp/solver.rs"]
157mod tests;
problemreductions/solvers/ilp/solver.rs

problemreductions/solvers/ilp/
solver.rs
