problemreductions/models/algebraic/
ilp.rs

1//! Integer Linear Programming (ILP) problem implementation.
2//!
3//! ILP optimizes a linear objective over integer variables subject to linear constraints.
4//! This is a fundamental "hub" problem that many other NP-hard problems can be reduced to.
5//!
6//! The type parameter `V` determines the variable domain:
7//! - `ILP<bool>`: binary variables (0 or 1)
8//! - `ILP<i32>`: non-negative integer variables (0..2^31-1)
9
10use crate::registry::{FieldInfo, ProblemSchemaEntry};
11use crate::traits::{OptimizationProblem, Problem};
12use crate::types::{Direction, SolutionSize};
13use serde::{Deserialize, Serialize};
14use std::marker::PhantomData;
15
16inventory::submit! {
17    ProblemSchemaEntry {
18        name: "ILP",
19        module_path: module_path!(),
20        description: "Optimize linear objective subject to linear constraints",
21        fields: &[
22            FieldInfo { name: "num_vars", type_name: "usize", description: "Number of integer variables" },
23            FieldInfo { name: "constraints", type_name: "Vec<LinearConstraint>", description: "Linear constraints" },
24            FieldInfo { name: "objective", type_name: "Vec<(usize, f64)>", description: "Sparse objective coefficients" },
25            FieldInfo { name: "sense", type_name: "ObjectiveSense", description: "Optimization direction" },
26        ],
27    }
28}
29
30/// Sealed trait for ILP variable domains.
31///
32/// `bool` = binary variables (0 or 1), `i32` = non-negative integers (0..2^31-1).
33pub trait VariableDomain: 'static + Clone + std::fmt::Debug + Send + Sync {
34    /// Number of possible values per variable (used by `dims()`).
35    const DIMS_PER_VAR: usize;
36    /// Name for the variant system (e.g., "bool", "i32").
37    const NAME: &'static str;
38}
39
40impl VariableDomain for bool {
41    const DIMS_PER_VAR: usize = 2;
42    const NAME: &'static str = "bool";
43}
44
45impl VariableDomain for i32 {
46    const DIMS_PER_VAR: usize = (i32::MAX as usize) + 1;
47    const NAME: &'static str = "i32";
48}
49
50/// Comparison operator for linear constraints.
51#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
52pub enum Comparison {
53    /// Less than or equal (<=).
54    Le,
55    /// Greater than or equal (>=).
56    Ge,
57    /// Equal (==).
58    Eq,
59}
60
61impl Comparison {
62    /// Check if the comparison holds between lhs and rhs.
63    pub fn holds(&self, lhs: f64, rhs: f64) -> bool {
64        match self {
65            Comparison::Le => lhs <= rhs,
66            Comparison::Ge => lhs >= rhs,
67            Comparison::Eq => (lhs - rhs).abs() < 1e-9,
68        }
69    }
70}
71
72/// A linear constraint: sum of (coefficient * variable) {<=, >=, ==} rhs.
73///
74/// The constraint is represented sparsely: only non-zero coefficients are stored.
75#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
76pub struct LinearConstraint {
77    /// Sparse representation: (var_index, coefficient) pairs.
78    pub terms: Vec<(usize, f64)>,
79    /// Comparison operator.
80    pub cmp: Comparison,
81    /// Right-hand side constant.
82    pub rhs: f64,
83}
84
85impl LinearConstraint {
86    /// Create a new linear constraint.
87    pub(crate) fn new(terms: Vec<(usize, f64)>, cmp: Comparison, rhs: f64) -> Self {
88        Self { terms, cmp, rhs }
89    }
90
91    /// Create a less-than-or-equal constraint.
92    pub fn le(terms: Vec<(usize, f64)>, rhs: f64) -> Self {
93        Self::new(terms, Comparison::Le, rhs)
94    }
95
96    /// Create a greater-than-or-equal constraint.
97    pub fn ge(terms: Vec<(usize, f64)>, rhs: f64) -> Self {
98        Self::new(terms, Comparison::Ge, rhs)
99    }
100
101    /// Create an equality constraint.
102    pub fn eq(terms: Vec<(usize, f64)>, rhs: f64) -> Self {
103        Self::new(terms, Comparison::Eq, rhs)
104    }
105
106    /// Evaluate the left-hand side of the constraint for given variable values.
107    pub fn evaluate_lhs(&self, values: &[i64]) -> f64 {
108        self.terms
109            .iter()
110            .map(|&(var, coef)| coef * values.get(var).copied().unwrap_or(0) as f64)
111            .sum()
112    }
113
114    /// Check if the constraint is satisfied by given variable values.
115    pub fn is_satisfied(&self, values: &[i64]) -> bool {
116        let lhs = self.evaluate_lhs(values);
117        self.cmp.holds(lhs, self.rhs)
118    }
119
120    /// Get the set of variable indices involved in this constraint.
121    pub fn variables(&self) -> Vec<usize> {
122        self.terms.iter().map(|&(var, _)| var).collect()
123    }
124}
125
126/// Optimization direction for the ILP.
127#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
128pub enum ObjectiveSense {
129    /// Maximize the objective function.
130    Maximize,
131    /// Minimize the objective function.
132    Minimize,
133}
134
135/// Integer Linear Programming (ILP) problem.
136///
137/// An ILP consists of:
138/// - A set of integer variables with a domain determined by `V`
139/// - Linear constraints on those variables
140/// - A linear objective function to optimize
141/// - An optimization sense (maximize or minimize)
142///
143/// # Type Parameter
144///
145/// - `V = bool`: binary variables (0 or 1)
146/// - `V = i32`: non-negative integer variables
147///
148/// # Example
149///
150/// ```
151/// use problemreductions::models::algebraic::{ILP, LinearConstraint, ObjectiveSense};
152/// use problemreductions::Problem;
153///
154/// // Create a simple binary ILP: maximize x0 + 2*x1
155/// // subject to: x0 + x1 <= 3, x0, x1 binary
156/// let ilp = ILP::<bool>::new(
157///     2,
158///     vec![LinearConstraint::le(vec![(0, 1.0), (1, 1.0)], 3.0)],
159///     vec![(0, 1.0), (1, 2.0)],
160///     ObjectiveSense::Maximize,
161/// );
162///
163/// assert_eq!(ilp.num_variables(), 2);
164/// ```
165#[derive(Debug, Clone, Serialize, Deserialize)]
166#[serde(bound(serialize = "", deserialize = ""))]
167pub struct ILP<V: VariableDomain = bool> {
168    /// Number of variables.
169    pub num_vars: usize,
170    /// Linear constraints.
171    pub constraints: Vec<LinearConstraint>,
172    /// Sparse objective coefficients: (var_index, coefficient).
173    pub objective: Vec<(usize, f64)>,
174    /// Optimization direction.
175    pub sense: ObjectiveSense,
176    #[serde(skip)]
177    _marker: PhantomData<V>,
178}
179
180impl<V: VariableDomain> ILP<V> {
181    /// Create a new ILP problem.
182    pub fn new(
183        num_vars: usize,
184        constraints: Vec<LinearConstraint>,
185        objective: Vec<(usize, f64)>,
186        sense: ObjectiveSense,
187    ) -> Self {
188        Self {
189            num_vars,
190            constraints,
191            objective,
192            sense,
193            _marker: PhantomData,
194        }
195    }
196
197    /// Create an empty ILP with no variables.
198    pub fn empty() -> Self {
199        Self::new(0, vec![], vec![], ObjectiveSense::Minimize)
200    }
201
202    /// Evaluate the objective function for given variable values.
203    pub fn evaluate_objective(&self, values: &[i64]) -> f64 {
204        self.objective
205            .iter()
206            .map(|&(var, coef)| coef * values.get(var).copied().unwrap_or(0) as f64)
207            .sum()
208    }
209
210    /// Check if all constraints are satisfied for given variable values.
211    pub fn constraints_satisfied(&self, values: &[i64]) -> bool {
212        self.constraints.iter().all(|c| c.is_satisfied(values))
213    }
214
215    /// Check if a solution is feasible (satisfies constraints).
216    pub fn is_feasible(&self, values: &[i64]) -> bool {
217        values.len() == self.num_vars && self.constraints_satisfied(values)
218    }
219
220    /// Convert a configuration (Vec<usize>) to integer values (Vec<i64>).
221    /// For bool: config 0→0, 1→1. For i32: config index = value.
222    fn config_to_values(&self, config: &[usize]) -> Vec<i64> {
223        config.iter().map(|&c| c as i64).collect()
224    }
225
226    /// Get the number of variables.
227    pub fn num_variables(&self) -> usize {
228        self.num_vars
229    }
230
231    /// Get the number of variables.
232    pub fn num_vars(&self) -> usize {
233        self.num_variables()
234    }
235
236    /// Get the number of constraints.
237    pub fn num_constraints(&self) -> usize {
238        self.constraints.len()
239    }
240}
241
242impl<V: VariableDomain> Problem for ILP<V> {
243    const NAME: &'static str = "ILP";
244    type Metric = SolutionSize<f64>;
245
246    fn dims(&self) -> Vec<usize> {
247        vec![V::DIMS_PER_VAR; self.num_vars]
248    }
249
250    fn evaluate(&self, config: &[usize]) -> SolutionSize<f64> {
251        let values = self.config_to_values(config);
252        if !self.is_feasible(&values) {
253            return SolutionSize::Invalid;
254        }
255        SolutionSize::Valid(self.evaluate_objective(&values))
256    }
257
258    fn variant() -> Vec<(&'static str, &'static str)> {
259        vec![("variable", V::NAME)]
260    }
261}
262
263impl<V: VariableDomain> OptimizationProblem for ILP<V> {
264    type Value = f64;
265
266    fn direction(&self) -> Direction {
267        match self.sense {
268            ObjectiveSense::Maximize => Direction::Maximize,
269            ObjectiveSense::Minimize => Direction::Minimize,
270        }
271    }
272}
273
274crate::declare_variants! {
275    ILP<bool> => "2^num_vars",
276    ILP<i32> => "num_vars^num_vars",
277}
278
279#[cfg(test)]
280#[path = "../../unit_tests/models/algebraic/ilp.rs"]
281mod tests;
problemreductions/models/algebraic/ilp.rs

problemreductions/models/algebraic/
ilp.rs
