problemreductions/solvers/ilp/
solver.rs

1//! ILP solver implementation using HiGHS.
2
3use super::adapter::HighsAdapter;
4use crate::models::algebraic::{Bounded, ILP};
5use crate::solvers::registry::solver_capability_registry;
6use crate::solvers::ExactProblemKey;
7use crate::traits::Problem;
8
9/// A failure to produce an ILP solution optimal within backend numerical tolerances.
10#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
11pub enum ILPSolveError {
12    /// The source problem has no feasible solution.
13    #[error("the problem is infeasible")]
14    Infeasible,
15    /// The objective is unbounded.
16    #[error("the ILP objective is unbounded")]
17    Unbounded,
18    /// The configured time limit was reached before optimality was proven.
19    #[error("the ILP solver reached its time limit before proving optimality")]
20    Timeout,
21    /// The selected backend failed for another reason.
22    #[error("the ILP backend failed: {0}")]
23    BackendFailure(String),
24    /// Type-erased dispatch received a value other than a supported ILP variant.
25    #[error("the ILP backend requires bool/i64 variables and i64/f64 coefficients")]
26    UnsupportedProblemType,
27    /// No ILP pipeline is registered for the exact problem variant.
28    #[error("no ILP pipeline is registered for {0}")]
29    MissingPipeline(String),
30    /// The solver capability registry is invalid.
31    #[error("solver capability registry is invalid: {0}")]
32    InvalidRegistry(String),
33    /// A registered pipeline returned a solution for a different source type.
34    #[error("registered ILP pipeline returned the wrong solution type for {0}")]
35    PipelineTypeMismatch(String),
36    /// HiGHS reported an optimal solution that is invalid after integer rounding.
37    #[error("the ILP backend returned an invalid rounded solution: {0}")]
38    InvalidSolution(String),
39    /// An exact integer in the model cannot be transported through the f64 backend API.
40    #[error("the ILP backend cannot represent an exact model integer: {0}")]
41    InexactTransport(#[from] crate::types::ExactI64ToF64Error),
42    /// A target witness could not be mapped back to the source problem.
43    #[error(transparent)]
44    Extraction(#[from] crate::rules::ExtractionError),
45    /// A registered reduction could not construct its target instance.
46    #[error(transparent)]
47    Reduction(#[from] crate::rules::ReductionError),
48}
49
50/// An ILP solver using the HiGHS backend.
51///
52/// Registered reductions map a source problem to a native `ILP<V, C>` terminal,
53/// which the HiGHS adapter converts for execution before source solution extraction.
54/// Optimality and infeasibility are assessed within HiGHS numerical tolerances.
55/// Zero MIP gaps do not make floating-point solving mathematically exact.
56///
57/// # Example
58///
59/// ```rust
60/// use problemreductions::models::algebraic::{ILP, LinearConstraint, ObjectiveSense};
61/// use problemreductions::solvers::ILPSolver;
62///
63/// // Create a simple binary ILP: maximize x0 + 2*x1 subject to x0 + x1 <= 1
64/// let ilp = ILP::<bool, f64>::new(
65///     2,
66///     vec![LinearConstraint::le(vec![(0, 1.0), (1, 1.0)], 1.0)],
67///     vec![(0, 1.0), (1, 2.0)],
68///     ObjectiveSense::Maximize,
69/// )?;
70///
71/// let solver = ILPSolver::new();
72/// let solution = solver.solve(&ilp)?;
73/// println!("Solution: {:?}", solution);
74/// # Ok::<(), Box<dyn std::error::Error>>(())
75/// ```
76#[derive(Debug, Clone, Default)]
77pub struct ILPSolver {
78    /// Time limit in seconds (None = no limit).
79    pub time_limit: Option<f64>,
80}
81
82impl ILPSolver {
83    /// Create a new ILP solver with default settings.
84    pub fn new() -> Self {
85        Self::default()
86    }
87
88    /// Create an ILP solver with a time limit.
89    pub fn with_time_limit(seconds: f64) -> Self {
90        Self {
91            time_limit: Some(seconds),
92        }
93    }
94
95    /// Solve a problem through its registered ILP pipeline.
96    ///
97    /// Returns a classified error when the problem is infeasible, the time
98    /// limit is reached, the pipeline is missing, or the backend fails.
99    pub fn solve<P>(&self, problem: &P) -> Result<P::Solution, ILPSolveError>
100    where
101        P: Problem + 'static,
102        P::Solution: 'static,
103    {
104        let key = ExactProblemKey::new(P::NAME, crate::export::variant_to_map(P::variant()));
105        let registry = solver_capability_registry()
106            .map_err(|error| ILPSolveError::InvalidRegistry(error.to_string()))?;
107        let pipeline = registry
108            .lookup(&key)
109            .ilp
110            .ok_or_else(|| ILPSolveError::MissingPipeline(key.label()))?;
111        let solution = pipeline.solve_typed(problem, self)?;
112        problem
113            .evaluate(&solution)
114            .map_err(|error| ILPSolveError::InvalidSolution(error.to_string()))?;
115        Ok(solution)
116    }
117
118    /// Solve a type-erased supported ILP variant directly.
119    pub(crate) fn solve_dyn(&self, any: &dyn std::any::Any) -> Result<Vec<i64>, ILPSolveError> {
120        if let Some(ilp) = any.downcast_ref::<ILP<bool, i64>>() {
121            return HighsAdapter::new(self.time_limit).solve(ilp);
122        }
123        if let Some(ilp) = any.downcast_ref::<ILP<i64, i64, Bounded>>() {
124            return HighsAdapter::new(self.time_limit).solve(ilp);
125        }
126        if let Some(ilp) = any.downcast_ref::<ILP<i64, i64>>() {
127            return HighsAdapter::new(self.time_limit).solve(ilp);
128        }
129        if let Some(ilp) = any.downcast_ref::<ILP<bool, f64>>() {
130            return HighsAdapter::new(self.time_limit).solve(ilp);
131        }
132        if let Some(ilp) = any.downcast_ref::<ILP<i64, f64>>() {
133            return HighsAdapter::new(self.time_limit).solve(ilp);
134        }
135        Err(ILPSolveError::UnsupportedProblemType)
136    }
137}
138
139#[cfg(test)]
140#[path = "../../unit_tests/solvers/ilp/solver.rs"]
141mod tests;
problemreductions/solvers/ilp/solver.rs

problemreductions/solvers/ilp/
solver.rs
