problemreductions/models/algebraic/
ilp.rs

1//! Integer Linear Programming (ILP) intermediate representation.
2//!
3//! ILP stores integer variables with explicit possibly-unbounded intervals,
4//! sparse linear constraints, and a linear objective. The type parameters
5//! select the integer variable domain and coefficient type independently.
6
7use crate::registry::{ConstructionError, FieldInfo, ProblemSchemaEntry, VariantDimension};
8use crate::traits::{EvaluationError, Problem};
9use crate::types::{
10    i64_to_exact_f64, Extremum, NumericArithmeticError, NumericSize, WeightElement,
11};
12use serde::{Deserialize, Deserializer, Serialize};
13use std::fmt::Debug;
14use std::marker::PhantomData;
15
16inventory::submit! {
17    ProblemSchemaEntry {
18        name: "ILP",
19        display_name: "ILP",
20        aliases: &[],
21        dimensions: &[
22            VariantDimension::new("variable", "bool", &["bool", "i64"]),
23            VariantDimension::new("coefficient", "i64", &["i64", "f64"]),
24        ],
25        category: crate::registry::ProblemCategory::Algebraic,
26        module_path: module_path!(),
27        description: "Optimize a linear objective over bounded or unbounded integer variables",
28        fields: &[
29            FieldInfo { name: "variables", type_name: "Vec<IntegerVariable>", description: "Integer variable bounds; null means an unbounded side" },
30            FieldInfo { name: "constraints", type_name: "Vec<LinearConstraint<C>>", description: "Sparse finite linear constraints" },
31            FieldInfo { name: "objective", type_name: "Vec<(usize, C)>", description: "Sparse finite objective coefficients" },
32            FieldInfo { name: "sense", type_name: "ObjectiveSense", description: "Optimization direction" },
33        ],
34    }
35}
36
37/// Static certificate for a homogeneous ILP variable domain.
38pub trait VariableDomain: 'static + Clone + Debug + Send + Sync {
39    /// Name used by the registered variant dimension.
40    const NAME: &'static str;
41
42    /// Default stored variable used by homogeneous formulations.
43    fn default_variable() -> IntegerVariable;
44
45    /// Validate that stored bounds satisfy this static certificate.
46    fn validate_variables(variables: &[IntegerVariable]) -> Result<(), ConstructionError>;
47}
48
49/// Numeric domain shared by an ILP's constraints, right-hand sides, and objective.
50pub trait ILPCoefficient:
51    NumericSize + WeightElement<Sum = Self> + Copy + Debug + Send + Sync
52{
53    /// Name used by the registered variant dimension.
54    const NAME: &'static str;
55
56    /// Convert an integer variable value into this coefficient domain.
57    fn from_integer(value: i64) -> Result<Self, EvaluationError>;
58
59    /// Compare a finite evaluated row with its right-hand side.
60    fn satisfies(lhs: Self, comparison: Comparison, rhs: Self) -> bool;
61}
62
63impl ILPCoefficient for i64 {
64    const NAME: &'static str = "i64";
65
66    fn from_integer(value: i64) -> Result<Self, EvaluationError> {
67        Ok(value)
68    }
69
70    fn satisfies(lhs: Self, comparison: Comparison, rhs: Self) -> bool {
71        match comparison {
72            Comparison::Le => lhs <= rhs,
73            Comparison::Ge => lhs >= rhs,
74            Comparison::Eq => lhs == rhs,
75        }
76    }
77}
78
79impl ILPCoefficient for f64 {
80    const NAME: &'static str = "f64";
81
82    fn from_integer(value: i64) -> Result<Self, EvaluationError> {
83        i64_to_exact_f64(value).map_err(|_| {
84            EvaluationError::InexactFloatConversion(
85                "transporting an integer variable into an f64 ILP expression".into(),
86            )
87        })
88    }
89
90    fn satisfies(lhs: Self, comparison: Comparison, rhs: Self) -> bool {
91        let tolerance = 1e-9 * lhs.abs().max(rhs.abs()).max(1.0);
92        match comparison {
93            Comparison::Le => lhs <= rhs + tolerance,
94            Comparison::Ge => lhs >= rhs - tolerance,
95            Comparison::Eq => (lhs - rhs).abs() <= tolerance,
96        }
97    }
98}
99
100impl VariableDomain for bool {
101    const NAME: &'static str = "bool";
102
103    fn default_variable() -> IntegerVariable {
104        IntegerVariable::binary()
105    }
106
107    fn validate_variables(variables: &[IntegerVariable]) -> Result<(), ConstructionError> {
108        if variables
109            .iter()
110            .any(|variable| variable.lower_bound != Some(0) || variable.upper_bound != Some(1))
111        {
112            return Err(ConstructionError::Conversion(
113                "binary ILP variables must have bounds [0, 1]".into(),
114            ));
115        }
116        Ok(())
117    }
118}
119
120impl VariableDomain for i64 {
121    const NAME: &'static str = "i64";
122
123    fn default_variable() -> IntegerVariable {
124        IntegerVariable::nonnegative()
125    }
126
127    fn validate_variables(_variables: &[IntegerVariable]) -> Result<(), ConstructionError> {
128        Ok(())
129    }
130}
131
132/// Bounds of one mathematical integer variable.
133#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize)]
134pub struct IntegerVariable {
135    lower_bound: Option<i64>,
136    upper_bound: Option<i64>,
137}
138
139impl<'de> Deserialize<'de> for IntegerVariable {
140    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
141    where
142        D: Deserializer<'de>,
143    {
144        #[derive(Deserialize)]
145        struct Bounds {
146            lower_bound: Option<i64>,
147            upper_bound: Option<i64>,
148        }
149
150        let bounds = Bounds::deserialize(deserializer)?;
151        Self::new(bounds.lower_bound, bounds.upper_bound).map_err(serde::de::Error::custom)
152    }
153}
154
155impl IntegerVariable {
156    /// Construct an integer variable. `None` denotes the corresponding
157    /// infinite bound.
158    pub fn new(
159        lower_bound: Option<i64>,
160        upper_bound: Option<i64>,
161    ) -> Result<Self, ConstructionError> {
162        if lower_bound
163            .zip(upper_bound)
164            .is_some_and(|(lower, upper)| lower > upper)
165        {
166            return Err(ConstructionError::Conversion(
167                "integer variable lower bound exceeds its upper bound".into(),
168            ));
169        }
170        Ok(Self {
171            lower_bound,
172            upper_bound,
173        })
174    }
175
176    /// A binary integer variable in `[0, 1]`.
177    pub const fn binary() -> Self {
178        Self {
179            lower_bound: Some(0),
180            upper_bound: Some(1),
181        }
182    }
183
184    /// A non-negative integer variable in `[0, +∞)`.
185    pub const fn nonnegative() -> Self {
186        Self {
187            lower_bound: Some(0),
188            upper_bound: None,
189        }
190    }
191
192    /// A free integer variable in `(-∞, +∞)`.
193    pub const fn free() -> Self {
194        Self {
195            lower_bound: None,
196            upper_bound: None,
197        }
198    }
199
200    /// Finite lower bound, or `None` for negative infinity.
201    pub const fn lower_bound(self) -> Option<i64> {
202        self.lower_bound
203    }
204
205    /// Finite upper bound, or `None` for positive infinity.
206    pub const fn upper_bound(self) -> Option<i64> {
207        self.upper_bound
208    }
209
210    /// Whether a mathematical value belongs to this interval.
211    pub fn contains(self, value: i64) -> bool {
212        self.lower_bound.is_none_or(|lower| value >= lower)
213            && self.upper_bound.is_none_or(|upper| value <= upper)
214    }
215}
216
217/// Comparison operator for a linear constraint.
218#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
219pub enum Comparison {
220    /// Less than or equal (`<=`).
221    Le,
222    /// Greater than or equal (`>=`).
223    Ge,
224    /// Equal (`==`).
225    Eq,
226}
227
228/// One sparse linear constraint.
229#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
230pub struct LinearConstraint<C = i64> {
231    terms: Vec<(usize, C)>,
232    comparison: Comparison,
233    rhs: C,
234}
235
236impl<C> LinearConstraint<C> {
237    fn new(terms: Vec<(usize, C)>, comparison: Comparison, rhs: C) -> Self {
238        Self {
239            terms,
240            comparison,
241            rhs,
242        }
243    }
244
245    /// Create a less-than-or-equal constraint.
246    pub fn le(terms: Vec<(usize, C)>, rhs: C) -> Self {
247        Self::new(terms, Comparison::Le, rhs)
248    }
249
250    /// Create a greater-than-or-equal constraint.
251    pub fn ge(terms: Vec<(usize, C)>, rhs: C) -> Self {
252        Self::new(terms, Comparison::Ge, rhs)
253    }
254
255    /// Create an equality constraint.
256    pub fn eq(terms: Vec<(usize, C)>, rhs: C) -> Self {
257        Self::new(terms, Comparison::Eq, rhs)
258    }
259
260    /// Canonical sparse row terms.
261    pub fn terms(&self) -> &[(usize, C)] {
262        &self.terms
263    }
264
265    /// Row comparison operator.
266    pub const fn comparison(&self) -> Comparison {
267        self.comparison
268    }
269
270    /// Row right-hand side.
271    pub fn variables(&self) -> impl Iterator<Item = usize> + '_ {
272        self.terms.iter().map(|&(variable, _)| variable)
273    }
274}
275
276impl<C: ILPCoefficient> LinearConstraint<C> {
277    /// Stored right-hand side.
278    pub fn rhs(&self) -> C {
279        self.rhs
280    }
281
282    /// Evaluate the left-hand side in the coefficient domain.
283    pub fn evaluate_lhs(&self, values: &[i64]) -> Result<C, EvaluationError> {
284        self.terms
285            .iter()
286            .try_fold(C::zero(), |sum, &(variable, coefficient)| {
287                let value = values.get(variable).copied().ok_or_else(|| {
288                    EvaluationError::InvalidConfiguration(format!(
289                        "an ILP constraint references variable {variable}, but the assignment has {} values",
290                        values.len()
291                    ))
292                })?;
293                let value = C::from_integer(value)?;
294                let product = C::checked_mul_sum(
295                    coefficient,
296                    value,
297                    "multiplying a term in an ILP constraint",
298                )?;
299                C::checked_add_to_sum(sum, product, "summing an ILP constraint")
300            })
301    }
302
303    /// Check whether this row is satisfied.
304    pub fn is_satisfied(&self, values: &[i64]) -> Result<bool, EvaluationError> {
305        let lhs = self.evaluate_lhs(values)?;
306        Ok(C::satisfies(lhs, self.comparison, self.rhs))
307    }
308}
309
310/// Optimization direction.
311#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
312pub enum ObjectiveSense {
313    /// Maximize the objective.
314    Maximize,
315    /// Minimize the objective.
316    Minimize,
317}
318
319/// Integer Linear Programming model.
320#[derive(Debug, Clone, Serialize)]
321pub struct ILP<V: VariableDomain = bool, C: ILPCoefficient = i64> {
322    variables: Vec<IntegerVariable>,
323    constraints: Vec<LinearConstraint<C>>,
324    objective: Vec<(usize, C)>,
325    sense: ObjectiveSense,
326    #[serde(skip)]
327    marker: PhantomData<V>,
328}
329
330#[derive(Deserialize)]
331struct ILPData<C> {
332    variables: Vec<IntegerVariable>,
333    constraints: Vec<LinearConstraint<C>>,
334    objective: Vec<(usize, C)>,
335    sense: ObjectiveSense,
336}
337
338impl<'de, V, C> Deserialize<'de> for ILP<V, C>
339where
340    V: VariableDomain,
341    C: ILPCoefficient + Deserialize<'de>,
342{
343    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
344    where
345        D: Deserializer<'de>,
346    {
347        let data = ILPData::<C>::deserialize(deserializer)?;
348        Self::with_variables(data.variables, data.constraints, data.objective, data.sense)
349            .map_err(serde::de::Error::custom)
350    }
351}
352
353impl<V: VariableDomain, C: ILPCoefficient> ILP<V, C> {
354    /// Construct a homogeneous model using the domain certificate's standard
355    /// variable interval: binary `[0, 1]` or integer `[0, +∞)`.
356    pub fn new(
357        num_variables: usize,
358        constraints: Vec<LinearConstraint<C>>,
359        objective: Vec<(usize, C)>,
360        sense: ObjectiveSense,
361    ) -> Result<Self, ConstructionError> {
362        Self::with_variables(
363            vec![V::default_variable(); num_variables],
364            constraints,
365            objective,
366            sense,
367        )
368    }
369
370    /// Construct a model with explicit possibly-unbounded variable intervals.
371    pub fn with_variables(
372        variables: Vec<IntegerVariable>,
373        constraints: Vec<LinearConstraint<C>>,
374        objective: Vec<(usize, C)>,
375        sense: ObjectiveSense,
376    ) -> Result<Self, ConstructionError> {
377        V::validate_variables(&variables)?;
378        let num_variables = variables.len();
379        let constraints = constraints
380            .into_iter()
381            .enumerate()
382            .map(|(index, constraint)| normalize_constraint(constraint, num_variables, index))
383            .collect::<Result<_, _>>()?;
384        let objective = normalize_objective(objective, num_variables)?;
385        Ok(Self {
386            variables,
387            constraints,
388            objective,
389            sense,
390            marker: PhantomData,
391        })
392    }
393
394    /// Empty model.
395    pub fn empty() -> Self {
396        Self::new(0, vec![], vec![], ObjectiveSense::Minimize)
397            .expect("the empty ILP satisfies all construction invariants")
398    }
399
400    /// Stored variables and their bounds.
401    pub fn variables(&self) -> &[IntegerVariable] {
402        &self.variables
403    }
404
405    /// Canonical sparse constraints.
406    pub fn constraints(&self) -> &[LinearConstraint<C>] {
407        &self.constraints
408    }
409
410    /// Canonical sparse objective.
411    pub fn objective(&self) -> &[(usize, C)] {
412        &self.objective
413    }
414
415    /// Optimization direction.
416    pub const fn sense(&self) -> ObjectiveSense {
417        self.sense
418    }
419
420    /// Number of variables.
421    pub fn num_variables(&self) -> usize {
422        self.variables.len()
423    }
424
425    /// Canonical size getter alias.
426    pub fn num_vars(&self) -> usize {
427        self.num_variables()
428    }
429
430    /// Number of constraints.
431    pub fn num_constraints(&self) -> usize {
432        self.constraints.len()
433    }
434
435    /// Number of non-zero row coefficients.
436    pub fn num_nonzeros(&self) -> usize {
437        self.constraints
438            .iter()
439            .map(|constraint| constraint.terms.len())
440            .sum()
441    }
442
443    /// Evaluate the objective in the coefficient domain.
444    pub fn evaluate_objective(&self, values: &[i64]) -> Result<C, EvaluationError> {
445        self.objective
446            .iter()
447            .try_fold(C::zero(), |sum, &(variable, coefficient)| {
448                let integer = values.get(variable).copied().ok_or_else(|| {
449                    EvaluationError::InvalidConfiguration(format!(
450                        "the ILP objective references variable {variable}, but the assignment has {} values",
451                        values.len()
452                    ))
453                })?;
454                let value = C::from_integer(integer)?;
455                let product = C::checked_mul_sum(
456                    coefficient,
457                    value,
458                    "multiplying a term in the ILP objective",
459                )?;
460                C::checked_add_to_sum(
461                    sum,
462                    product,
463                    "summing the ILP objective",
464                )
465            })
466    }
467
468    /// Check stored variable intervals and all rows.
469    pub fn is_feasible(&self, values: &[i64]) -> Result<bool, EvaluationError> {
470        if values.len() != self.variables.len() {
471            return Err(EvaluationError::InvalidConfiguration(
472                "variable assignment length does not match the ILP".into(),
473            ));
474        }
475        if self
476            .variables
477            .iter()
478            .zip(values)
479            .any(|(&variable, &value)| !variable.contains(value))
480        {
481            return Ok(false);
482        }
483        for constraint in &self.constraints {
484            if !constraint.is_satisfied(values)? {
485                return Ok(false);
486            }
487        }
488        Ok(true)
489    }
490}
491
492fn construction_arithmetic_error(
493    error: NumericArithmeticError,
494    context: String,
495) -> ConstructionError {
496    match error {
497        NumericArithmeticError::IntegerOverflow => ConstructionError::IntegerOverflow(context),
498        NumericArithmeticError::NonFiniteResult => ConstructionError::NonFiniteFloat(context),
499    }
500}
501
502fn normalize_constraint<C: ILPCoefficient>(
503    constraint: LinearConstraint<C>,
504    num_variables: usize,
505    constraint_index: usize,
506) -> Result<LinearConstraint<C>, ConstructionError> {
507    let mut terms = constraint.terms;
508    constraint
509        .rhs
510        .validate_element("ILP constraint right-hand side")?;
511    for &(variable, coefficient) in &terms {
512        if variable >= num_variables {
513            return Err(ConstructionError::Conversion(format!(
514                "ILP constraint {constraint_index} references variable {variable}, but the model has {num_variables} variables"
515            )));
516        }
517        coefficient.validate_element("ILP constraint coefficient")?;
518    }
519    terms.sort_by_key(|&(variable, _)| variable);
520    let mut normalized: Vec<(usize, C)> = Vec::with_capacity(terms.len());
521    for (variable, coefficient) in terms {
522        if let Some((previous_variable, previous_coefficient)) = normalized.last_mut() {
523            if *previous_variable == variable {
524                *previous_coefficient = previous_coefficient
525                    .checked_add_value(coefficient)
526                    .map_err(|error| {
527                        construction_arithmetic_error(
528                            error,
529                            format!(
530                        "merging duplicate variable {variable} in ILP constraint {constraint_index}"
531                    ),
532                        )
533                    })?;
534                continue;
535            }
536        }
537        normalized.push((variable, coefficient));
538    }
539    normalized.retain(|&(_, coefficient)| !coefficient.is_zero());
540    Ok(LinearConstraint::new(
541        normalized,
542        constraint.comparison,
543        constraint.rhs,
544    ))
545}
546
547fn normalize_objective<C: ILPCoefficient>(
548    mut objective: Vec<(usize, C)>,
549    num_variables: usize,
550) -> Result<Vec<(usize, C)>, ConstructionError> {
551    for &(variable, coefficient) in &objective {
552        if variable >= num_variables {
553            return Err(ConstructionError::Conversion(format!(
554                "ILP objective references variable {variable}, but the model has {num_variables} variables"
555            )));
556        }
557        coefficient.validate_element("ILP objective coefficient")?;
558    }
559    objective.sort_by_key(|&(variable, _)| variable);
560    let mut normalized: Vec<(usize, C)> = Vec::with_capacity(objective.len());
561    for (variable, coefficient) in objective {
562        if let Some((previous_variable, previous_coefficient)) = normalized.last_mut() {
563            if *previous_variable == variable {
564                *previous_coefficient = previous_coefficient
565                    .checked_add_value(coefficient)
566                    .map_err(|error| {
567                        construction_arithmetic_error(
568                            error,
569                            format!("merged objective coefficient of variable {variable}"),
570                        )
571                    })?;
572                continue;
573            }
574        }
575        normalized.push((variable, coefficient));
576    }
577    normalized.retain(|&(_, coefficient)| !coefficient.is_zero());
578    Ok(normalized)
579}
580
581impl<V: VariableDomain, C: ILPCoefficient> Problem for ILP<V, C> {
582    const NAME: &'static str = "ILP";
583    type Solution = Vec<i64>;
584    type Value = Extremum<C>;
585
586    crate::problem_parameters![
587        ("num_constraints", num_constraints),
588        ("num_nonzeros", num_nonzeros),
589        ("num_vars", num_vars),
590    ];
591
592    fn evaluate(&self, solution: &Self::Solution) -> Result<Self::Value, EvaluationError> {
593        if !self.is_feasible(solution)? {
594            return Ok(match self.sense {
595                ObjectiveSense::Maximize => Extremum::maximize(None),
596                ObjectiveSense::Minimize => Extremum::minimize(None),
597            });
598        }
599        let objective = self.evaluate_objective(solution)?;
600        Ok(match self.sense {
601            ObjectiveSense::Maximize => Extremum::maximize(Some(objective)),
602            ObjectiveSense::Minimize => Extremum::minimize(Some(objective)),
603        })
604    }
605
606    fn variant() -> Vec<(&'static str, &'static str)> {
607        vec![("variable", V::NAME), ("coefficient", C::NAME)]
608    }
609}
610
611crate::declare_variants! {
612    default ILP<bool, i64> => "2^num_vars",
613    ILP<i64, i64> => "num_vars^num_vars",
614    ILP<bool, f64> => "2^num_vars",
615    ILP<i64, f64> => "num_vars^num_vars",
616}
617
618#[cfg(feature = "example-db")]
619pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
620    vec![crate::example_db::specs::ModelExampleSpec {
621        id: "ilp",
622        instance: Box::new(
623            ILP::<i64, i64>::new(
624                2,
625                vec![
626                    LinearConstraint::le(vec![(0, 1), (1, 1)], 5),
627                    LinearConstraint::le(vec![(0, 4), (1, 7)], 28),
628                ],
629                vec![(0, -5), (1, -6)],
630                ObjectiveSense::Minimize,
631            )
632            .expect("canonical ILP construction must succeed"),
633        ),
634        optimal_config: serde_json::json!(vec![3, 2]),
635        optimal_value: serde_json::json!({
636            "sense": "Minimize",
637            "value": -27,
638        }),
639    }]
640}
641
642#[cfg(test)]
643#[path = "../../unit_tests/models/algebraic/ilp.rs"]
644mod tests;
problemreductions/models/algebraic/ilp.rs

problemreductions/models/algebraic/
ilp.rs
