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

problemreductions/models/algebraic/
ilp.rs
