problemreductions/models/optimization/
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
6use crate::graph_types::SimpleGraph;
7use crate::traits::Problem;
8use crate::types::{EnergyMode, ProblemSize, SolutionSize};
9use serde::{Deserialize, Serialize};
10
11/// Variable bounds (None = unbounded in that direction).
12///
13/// Represents the lower and upper bounds for an integer variable.
14/// A value of `None` indicates the variable is unbounded in that direction.
15#[derive(Debug, Clone, Copy, Default, PartialEq, Eq, Serialize, Deserialize)]
16pub struct VarBounds {
17    /// Lower bound (None = -infinity).
18    pub lower: Option<i64>,
19    /// Upper bound (None = +infinity).
20    pub upper: Option<i64>,
21}
22
23impl VarBounds {
24    /// Create bounds for a binary variable: 0 <= x <= 1.
25    pub fn binary() -> Self {
26        Self {
27            lower: Some(0),
28            upper: Some(1),
29        }
30    }
31
32    /// Create bounds for a non-negative variable: x >= 0.
33    pub fn non_negative() -> Self {
34        Self {
35            lower: Some(0),
36            upper: None,
37        }
38    }
39
40    /// Create unbounded variable: -infinity < x < +infinity.
41    pub fn unbounded() -> Self {
42        Self {
43            lower: None,
44            upper: None,
45        }
46    }
47
48    /// Create bounds with explicit lower and upper: lo <= x <= hi.
49    pub fn bounded(lo: i64, hi: i64) -> Self {
50        Self {
51            lower: Some(lo),
52            upper: Some(hi),
53        }
54    }
55
56    /// Check if a value satisfies these bounds.
57    pub fn contains(&self, value: i64) -> bool {
58        if let Some(lo) = self.lower {
59            if value < lo {
60                return false;
61            }
62        }
63        if let Some(hi) = self.upper {
64            if value > hi {
65                return false;
66            }
67        }
68        true
69    }
70
71    /// Get the number of integer values in this bound range.
72    /// Returns None if unbounded in either direction.
73    pub fn num_values(&self) -> Option<usize> {
74        match (self.lower, self.upper) {
75            (Some(lo), Some(hi)) => {
76                if hi >= lo {
77                    Some((hi - lo + 1) as usize)
78                } else {
79                    Some(0)
80                }
81            }
82            _ => None,
83        }
84    }
85}
86
87/// Comparison operator for linear constraints.
88#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
89pub enum Comparison {
90    /// Less than or equal (<=).
91    Le,
92    /// Greater than or equal (>=).
93    Ge,
94    /// Equal (==).
95    Eq,
96}
97
98impl Comparison {
99    /// Check if the comparison holds between lhs and rhs.
100    pub fn holds(&self, lhs: f64, rhs: f64) -> bool {
101        match self {
102            Comparison::Le => lhs <= rhs,
103            Comparison::Ge => lhs >= rhs,
104            Comparison::Eq => (lhs - rhs).abs() < 1e-9,
105        }
106    }
107}
108
109/// A linear constraint: sum of (coefficient * variable) {<=, >=, ==} rhs.
110///
111/// The constraint is represented sparsely: only non-zero coefficients are stored.
112#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
113pub struct LinearConstraint {
114    /// Sparse representation: (var_index, coefficient) pairs.
115    pub terms: Vec<(usize, f64)>,
116    /// Comparison operator.
117    pub cmp: Comparison,
118    /// Right-hand side constant.
119    pub rhs: f64,
120}
121
122impl LinearConstraint {
123    /// Create a new linear constraint.
124    pub fn new(terms: Vec<(usize, f64)>, cmp: Comparison, rhs: f64) -> Self {
125        Self { terms, cmp, rhs }
126    }
127
128    /// Create a less-than-or-equal constraint.
129    pub fn le(terms: Vec<(usize, f64)>, rhs: f64) -> Self {
130        Self::new(terms, Comparison::Le, rhs)
131    }
132
133    /// Create a greater-than-or-equal constraint.
134    pub fn ge(terms: Vec<(usize, f64)>, rhs: f64) -> Self {
135        Self::new(terms, Comparison::Ge, rhs)
136    }
137
138    /// Create an equality constraint.
139    pub fn eq(terms: Vec<(usize, f64)>, rhs: f64) -> Self {
140        Self::new(terms, Comparison::Eq, rhs)
141    }
142
143    /// Evaluate the left-hand side of the constraint for given variable values.
144    pub fn evaluate_lhs(&self, values: &[i64]) -> f64 {
145        self.terms
146            .iter()
147            .map(|&(var, coef)| coef * values.get(var).copied().unwrap_or(0) as f64)
148            .sum()
149    }
150
151    /// Check if the constraint is satisfied by given variable values.
152    pub fn is_satisfied(&self, values: &[i64]) -> bool {
153        let lhs = self.evaluate_lhs(values);
154        self.cmp.holds(lhs, self.rhs)
155    }
156
157    /// Get the set of variable indices involved in this constraint.
158    pub fn variables(&self) -> Vec<usize> {
159        self.terms.iter().map(|&(var, _)| var).collect()
160    }
161}
162
163/// Optimization direction for the ILP.
164#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
165pub enum ObjectiveSense {
166    /// Maximize the objective function.
167    Maximize,
168    /// Minimize the objective function.
169    Minimize,
170}
171
172impl From<EnergyMode> for ObjectiveSense {
173    fn from(mode: EnergyMode) -> Self {
174        match mode {
175            EnergyMode::LargerSizeIsBetter => ObjectiveSense::Maximize,
176            EnergyMode::SmallerSizeIsBetter => ObjectiveSense::Minimize,
177        }
178    }
179}
180
181impl From<ObjectiveSense> for EnergyMode {
182    fn from(sense: ObjectiveSense) -> Self {
183        match sense {
184            ObjectiveSense::Maximize => EnergyMode::LargerSizeIsBetter,
185            ObjectiveSense::Minimize => EnergyMode::SmallerSizeIsBetter,
186        }
187    }
188}
189
190/// Integer Linear Programming (ILP) problem.
191///
192/// An ILP consists of:
193/// - A set of integer variables with bounds
194/// - Linear constraints on those variables
195/// - A linear objective function to optimize
196/// - An optimization sense (maximize or minimize)
197///
198/// # Example
199///
200/// ```
201/// use problemreductions::models::optimization::{ILP, VarBounds, Comparison, LinearConstraint, ObjectiveSense};
202/// use problemreductions::Problem;
203///
204/// // Create a simple ILP: maximize x0 + 2*x1
205/// // subject to: x0 + x1 <= 3, x0, x1 binary
206/// let ilp = ILP::new(
207///     2,
208///     vec![VarBounds::binary(), VarBounds::binary()],
209///     vec![LinearConstraint::le(vec![(0, 1.0), (1, 1.0)], 3.0)],
210///     vec![(0, 1.0), (1, 2.0)],
211///     ObjectiveSense::Maximize,
212/// );
213///
214/// assert_eq!(ilp.num_variables(), 2);
215/// ```
216#[derive(Debug, Clone, Serialize, Deserialize)]
217pub struct ILP {
218    /// Number of variables.
219    pub num_vars: usize,
220    /// Bounds for each variable.
221    pub bounds: Vec<VarBounds>,
222    /// Linear constraints.
223    pub constraints: Vec<LinearConstraint>,
224    /// Sparse objective coefficients: (var_index, coefficient).
225    pub objective: Vec<(usize, f64)>,
226    /// Optimization direction.
227    pub sense: ObjectiveSense,
228}
229
230impl ILP {
231    /// Create a new ILP problem.
232    ///
233    /// # Arguments
234    /// * `num_vars` - Number of variables
235    /// * `bounds` - Bounds for each variable (must have length num_vars)
236    /// * `constraints` - List of linear constraints
237    /// * `objective` - Sparse objective coefficients
238    /// * `sense` - Maximize or minimize
239    ///
240    /// # Panics
241    /// Panics if bounds.len() != num_vars.
242    pub fn new(
243        num_vars: usize,
244        bounds: Vec<VarBounds>,
245        constraints: Vec<LinearConstraint>,
246        objective: Vec<(usize, f64)>,
247        sense: ObjectiveSense,
248    ) -> Self {
249        assert_eq!(
250            bounds.len(),
251            num_vars,
252            "bounds length must match num_vars"
253        );
254        Self {
255            num_vars,
256            bounds,
257            constraints,
258            objective,
259            sense,
260        }
261    }
262
263    /// Create a binary ILP (all variables are 0-1).
264    ///
265    /// This is a convenience constructor for common binary optimization problems.
266    pub fn binary(
267        num_vars: usize,
268        constraints: Vec<LinearConstraint>,
269        objective: Vec<(usize, f64)>,
270        sense: ObjectiveSense,
271    ) -> Self {
272        let bounds = vec![VarBounds::binary(); num_vars];
273        Self::new(num_vars, bounds, constraints, objective, sense)
274    }
275
276    /// Create an empty ILP with no variables.
277    pub fn empty() -> Self {
278        Self {
279            num_vars: 0,
280            bounds: vec![],
281            constraints: vec![],
282            objective: vec![],
283            sense: ObjectiveSense::Minimize,
284        }
285    }
286
287    /// Evaluate the objective function for given variable values.
288    pub fn evaluate_objective(&self, values: &[i64]) -> f64 {
289        self.objective
290            .iter()
291            .map(|&(var, coef)| coef * values.get(var).copied().unwrap_or(0) as f64)
292            .sum()
293    }
294
295    /// Check if all bounds are satisfied for given variable values.
296    pub fn bounds_satisfied(&self, values: &[i64]) -> bool {
297        if values.len() != self.num_vars {
298            return false;
299        }
300        for (i, &value) in values.iter().enumerate() {
301            if !self.bounds[i].contains(value) {
302                return false;
303            }
304        }
305        true
306    }
307
308    /// Check if all constraints are satisfied for given variable values.
309    pub fn constraints_satisfied(&self, values: &[i64]) -> bool {
310        self.constraints.iter().all(|c| c.is_satisfied(values))
311    }
312
313    /// Check if a solution is feasible (satisfies bounds and constraints).
314    pub fn is_feasible(&self, values: &[i64]) -> bool {
315        self.bounds_satisfied(values) && self.constraints_satisfied(values)
316    }
317
318    /// Convert a configuration (Vec<usize>) to integer values (Vec<i64>).
319    /// The configuration encodes variable values as offsets from lower bounds.
320    fn config_to_values(&self, config: &[usize]) -> Vec<i64> {
321        config
322            .iter()
323            .enumerate()
324            .map(|(i, &c)| {
325                let lo = self.bounds.get(i).and_then(|b| b.lower).unwrap_or(0);
326                lo + c as i64
327            })
328            .collect()
329    }
330}
331
332impl Problem for ILP {
333    const NAME: &'static str = "ILP";
334    type GraphType = SimpleGraph;
335    type Weight = f64;
336    type Size = f64;
337
338    fn num_variables(&self) -> usize {
339        self.num_vars
340    }
341
342    fn num_flavors(&self) -> usize {
343        // Return the maximum number of values any variable can take.
344        // For unbounded variables, return usize::MAX.
345        self.bounds
346            .iter()
347            .map(|b| b.num_values().unwrap_or(usize::MAX))
348            .max()
349            .unwrap_or(2)
350    }
351
352    fn problem_size(&self) -> ProblemSize {
353        ProblemSize::new(vec![
354            ("num_vars", self.num_vars),
355            ("num_constraints", self.constraints.len()),
356        ])
357    }
358
359    fn energy_mode(&self) -> EnergyMode {
360        match self.sense {
361            ObjectiveSense::Maximize => EnergyMode::LargerSizeIsBetter,
362            ObjectiveSense::Minimize => EnergyMode::SmallerSizeIsBetter,
363        }
364    }
365
366    fn solution_size(&self, config: &[usize]) -> SolutionSize<f64> {
367        // Convert config to actual integer values
368        let values = self.config_to_values(config);
369
370        // Check bounds validity
371        let bounds_ok = self.bounds_satisfied(&values);
372
373        // Check constraints satisfaction
374        let constraints_ok = self.constraints_satisfied(&values);
375
376        let is_valid = bounds_ok && constraints_ok;
377
378        // Compute objective value
379        let obj = self.evaluate_objective(&values);
380
381        SolutionSize::new(obj, is_valid)
382    }
383}
384
385#[cfg(test)]
386mod tests {
387    use super::*;
388    use crate::solvers::{BruteForce, Solver};
389
390    // ============================================================
391    // VarBounds tests
392    // ============================================================
393
394    #[test]
395    fn test_varbounds_binary() {
396        let bounds = VarBounds::binary();
397        assert_eq!(bounds.lower, Some(0));
398        assert_eq!(bounds.upper, Some(1));
399        assert!(bounds.contains(0));
400        assert!(bounds.contains(1));
401        assert!(!bounds.contains(-1));
402        assert!(!bounds.contains(2));
403        assert_eq!(bounds.num_values(), Some(2));
404    }
405
406    #[test]
407    fn test_varbounds_non_negative() {
408        let bounds = VarBounds::non_negative();
409        assert_eq!(bounds.lower, Some(0));
410        assert_eq!(bounds.upper, None);
411        assert!(bounds.contains(0));
412        assert!(bounds.contains(100));
413        assert!(!bounds.contains(-1));
414        assert_eq!(bounds.num_values(), None);
415    }
416
417    #[test]
418    fn test_varbounds_unbounded() {
419        let bounds = VarBounds::unbounded();
420        assert_eq!(bounds.lower, None);
421        assert_eq!(bounds.upper, None);
422        assert!(bounds.contains(-1000));
423        assert!(bounds.contains(0));
424        assert!(bounds.contains(1000));
425        assert_eq!(bounds.num_values(), None);
426    }
427
428    #[test]
429    fn test_varbounds_bounded() {
430        let bounds = VarBounds::bounded(-5, 10);
431        assert_eq!(bounds.lower, Some(-5));
432        assert_eq!(bounds.upper, Some(10));
433        assert!(bounds.contains(-5));
434        assert!(bounds.contains(0));
435        assert!(bounds.contains(10));
436        assert!(!bounds.contains(-6));
437        assert!(!bounds.contains(11));
438        assert_eq!(bounds.num_values(), Some(16)); // -5 to 10 inclusive
439    }
440
441    #[test]
442    fn test_varbounds_default() {
443        let bounds = VarBounds::default();
444        assert_eq!(bounds.lower, None);
445        assert_eq!(bounds.upper, None);
446    }
447
448    #[test]
449    fn test_varbounds_empty_range() {
450        let bounds = VarBounds::bounded(5, 3); // Invalid: lo > hi
451        assert_eq!(bounds.num_values(), Some(0));
452    }
453
454    // ============================================================
455    // Comparison tests
456    // ============================================================
457
458    #[test]
459    fn test_comparison_le() {
460        let cmp = Comparison::Le;
461        assert!(cmp.holds(5.0, 10.0));
462        assert!(cmp.holds(10.0, 10.0));
463        assert!(!cmp.holds(11.0, 10.0));
464    }
465
466    #[test]
467    fn test_comparison_ge() {
468        let cmp = Comparison::Ge;
469        assert!(cmp.holds(10.0, 5.0));
470        assert!(cmp.holds(10.0, 10.0));
471        assert!(!cmp.holds(4.0, 5.0));
472    }
473
474    #[test]
475    fn test_comparison_eq() {
476        let cmp = Comparison::Eq;
477        assert!(cmp.holds(10.0, 10.0));
478        assert!(!cmp.holds(10.0, 10.1));
479        assert!(!cmp.holds(9.9, 10.0));
480        // Test tolerance
481        assert!(cmp.holds(10.0, 10.0 + 1e-10));
482    }
483
484    // ============================================================
485    // LinearConstraint tests
486    // ============================================================
487
488    #[test]
489    fn test_linear_constraint_le() {
490        // x0 + 2*x1 <= 5
491        let constraint = LinearConstraint::le(vec![(0, 1.0), (1, 2.0)], 5.0);
492        assert_eq!(constraint.cmp, Comparison::Le);
493        assert_eq!(constraint.rhs, 5.0);
494
495        // x0=1, x1=2 => 1 + 4 = 5 <= 5 (satisfied)
496        assert!(constraint.is_satisfied(&[1, 2]));
497        // x0=2, x1=2 => 2 + 4 = 6 > 5 (not satisfied)
498        assert!(!constraint.is_satisfied(&[2, 2]));
499    }
500
501    #[test]
502    fn test_linear_constraint_ge() {
503        // x0 + x1 >= 3
504        let constraint = LinearConstraint::ge(vec![(0, 1.0), (1, 1.0)], 3.0);
505        assert_eq!(constraint.cmp, Comparison::Ge);
506
507        assert!(constraint.is_satisfied(&[2, 2])); // 4 >= 3
508        assert!(constraint.is_satisfied(&[1, 2])); // 3 >= 3
509        assert!(!constraint.is_satisfied(&[1, 1])); // 2 < 3
510    }
511
512    #[test]
513    fn test_linear_constraint_eq() {
514        // x0 + x1 == 2
515        let constraint = LinearConstraint::eq(vec![(0, 1.0), (1, 1.0)], 2.0);
516        assert_eq!(constraint.cmp, Comparison::Eq);
517
518        assert!(constraint.is_satisfied(&[1, 1])); // 2 == 2
519        assert!(!constraint.is_satisfied(&[1, 2])); // 3 != 2
520        assert!(!constraint.is_satisfied(&[0, 1])); // 1 != 2
521    }
522
523    #[test]
524    fn test_linear_constraint_evaluate_lhs() {
525        let constraint = LinearConstraint::le(vec![(0, 3.0), (2, -1.0)], 10.0);
526        // 3*x0 - 1*x2 with x=[2, 5, 7] => 3*2 - 1*7 = -1
527        assert!((constraint.evaluate_lhs(&[2, 5, 7]) - (-1.0)).abs() < 1e-9);
528    }
529
530    #[test]
531    fn test_linear_constraint_variables() {
532        let constraint = LinearConstraint::le(vec![(0, 1.0), (3, 2.0), (5, -1.0)], 10.0);
533        assert_eq!(constraint.variables(), vec![0, 3, 5]);
534    }
535
536    #[test]
537    fn test_linear_constraint_out_of_bounds() {
538        // Constraint references variable 5, but values only has 3 elements
539        let constraint = LinearConstraint::le(vec![(5, 1.0)], 10.0);
540        // Missing variable defaults to 0, so 0 <= 10 is satisfied
541        assert!(constraint.is_satisfied(&[1, 2, 3]));
542    }
543
544    // ============================================================
545    // ObjectiveSense tests
546    // ============================================================
547
548    #[test]
549    fn test_objective_sense_from_energy_mode() {
550        assert_eq!(
551            ObjectiveSense::from(EnergyMode::LargerSizeIsBetter),
552            ObjectiveSense::Maximize
553        );
554        assert_eq!(
555            ObjectiveSense::from(EnergyMode::SmallerSizeIsBetter),
556            ObjectiveSense::Minimize
557        );
558    }
559
560    #[test]
561    fn test_energy_mode_from_objective_sense() {
562        assert_eq!(
563            EnergyMode::from(ObjectiveSense::Maximize),
564            EnergyMode::LargerSizeIsBetter
565        );
566        assert_eq!(
567            EnergyMode::from(ObjectiveSense::Minimize),
568            EnergyMode::SmallerSizeIsBetter
569        );
570    }
571
572    // ============================================================
573    // ILP tests
574    // ============================================================
575
576    #[test]
577    fn test_ilp_new() {
578        let ilp = ILP::new(
579            2,
580            vec![VarBounds::binary(), VarBounds::binary()],
581            vec![LinearConstraint::le(vec![(0, 1.0), (1, 1.0)], 1.0)],
582            vec![(0, 1.0), (1, 2.0)],
583            ObjectiveSense::Maximize,
584        );
585        assert_eq!(ilp.num_vars, 2);
586        assert_eq!(ilp.bounds.len(), 2);
587        assert_eq!(ilp.constraints.len(), 1);
588        assert_eq!(ilp.objective.len(), 2);
589        assert_eq!(ilp.sense, ObjectiveSense::Maximize);
590    }
591
592    #[test]
593    #[should_panic(expected = "bounds length must match num_vars")]
594    fn test_ilp_new_mismatched_bounds() {
595        ILP::new(
596            3,
597            vec![VarBounds::binary(), VarBounds::binary()], // Only 2 bounds for 3 vars
598            vec![],
599            vec![],
600            ObjectiveSense::Minimize,
601        );
602    }
603
604    #[test]
605    fn test_ilp_binary() {
606        let ilp = ILP::binary(
607            3,
608            vec![],
609            vec![(0, 1.0), (1, 1.0), (2, 1.0)],
610            ObjectiveSense::Minimize,
611        );
612        assert_eq!(ilp.num_vars, 3);
613        assert!(ilp.bounds.iter().all(|b| *b == VarBounds::binary()));
614    }
615
616    #[test]
617    fn test_ilp_empty() {
618        let ilp = ILP::empty();
619        assert_eq!(ilp.num_vars, 0);
620        assert!(ilp.bounds.is_empty());
621        assert!(ilp.constraints.is_empty());
622        assert!(ilp.objective.is_empty());
623    }
624
625    #[test]
626    fn test_ilp_evaluate_objective() {
627        let ilp = ILP::binary(
628            3,
629            vec![],
630            vec![(0, 2.0), (1, 3.0), (2, -1.0)],
631            ObjectiveSense::Maximize,
632        );
633        // 2*1 + 3*1 + (-1)*0 = 5
634        assert!((ilp.evaluate_objective(&[1, 1, 0]) - 5.0).abs() < 1e-9);
635        // 2*0 + 3*0 + (-1)*1 = -1
636        assert!((ilp.evaluate_objective(&[0, 0, 1]) - (-1.0)).abs() < 1e-9);
637    }
638
639    #[test]
640    fn test_ilp_bounds_satisfied() {
641        let ilp = ILP::new(
642            2,
643            vec![VarBounds::bounded(0, 5), VarBounds::bounded(-2, 2)],
644            vec![],
645            vec![],
646            ObjectiveSense::Minimize,
647        );
648        assert!(ilp.bounds_satisfied(&[0, 0]));
649        assert!(ilp.bounds_satisfied(&[5, 2]));
650        assert!(ilp.bounds_satisfied(&[3, -2]));
651        assert!(!ilp.bounds_satisfied(&[6, 0])); // x0 > 5
652        assert!(!ilp.bounds_satisfied(&[0, 3])); // x1 > 2
653        assert!(!ilp.bounds_satisfied(&[0])); // Wrong length
654    }
655
656    #[test]
657    fn test_ilp_constraints_satisfied() {
658        let ilp = ILP::binary(
659            3,
660            vec![
661                LinearConstraint::le(vec![(0, 1.0), (1, 1.0)], 1.0), // x0 + x1 <= 1
662                LinearConstraint::ge(vec![(2, 1.0)], 0.0),          // x2 >= 0
663            ],
664            vec![],
665            ObjectiveSense::Minimize,
666        );
667        assert!(ilp.constraints_satisfied(&[0, 0, 1]));
668        assert!(ilp.constraints_satisfied(&[1, 0, 0]));
669        assert!(ilp.constraints_satisfied(&[0, 1, 1]));
670        assert!(!ilp.constraints_satisfied(&[1, 1, 0])); // x0 + x1 = 2 > 1
671    }
672
673    #[test]
674    fn test_ilp_is_feasible() {
675        let ilp = ILP::binary(
676            2,
677            vec![LinearConstraint::le(vec![(0, 1.0), (1, 1.0)], 1.0)],
678            vec![(0, 1.0), (1, 1.0)],
679            ObjectiveSense::Maximize,
680        );
681        assert!(ilp.is_feasible(&[0, 0]));
682        assert!(ilp.is_feasible(&[1, 0]));
683        assert!(ilp.is_feasible(&[0, 1]));
684        assert!(!ilp.is_feasible(&[1, 1])); // Constraint violated
685        assert!(!ilp.is_feasible(&[2, 0])); // Bounds violated
686    }
687
688    // ============================================================
689    // Problem trait tests
690    // ============================================================
691
692    #[test]
693    fn test_ilp_num_variables() {
694        let ilp = ILP::binary(5, vec![], vec![], ObjectiveSense::Minimize);
695        assert_eq!(ilp.num_variables(), 5);
696    }
697
698    #[test]
699    fn test_ilp_num_flavors_binary() {
700        let ilp = ILP::binary(3, vec![], vec![], ObjectiveSense::Minimize);
701        assert_eq!(ilp.num_flavors(), 2);
702    }
703
704    #[test]
705    fn test_ilp_num_flavors_mixed() {
706        let ilp = ILP::new(
707            3,
708            vec![
709                VarBounds::binary(),
710                VarBounds::bounded(0, 5),
711                VarBounds::bounded(-1, 1),
712            ],
713            vec![],
714            vec![],
715            ObjectiveSense::Minimize,
716        );
717        assert_eq!(ilp.num_flavors(), 6); // Max is 6 (from 0-5)
718    }
719
720    #[test]
721    fn test_ilp_num_flavors_unbounded() {
722        let ilp = ILP::new(
723            2,
724            vec![VarBounds::binary(), VarBounds::unbounded()],
725            vec![],
726            vec![],
727            ObjectiveSense::Minimize,
728        );
729        assert_eq!(ilp.num_flavors(), usize::MAX);
730    }
731
732    #[test]
733    fn test_ilp_num_flavors_empty() {
734        let ilp = ILP::empty();
735        assert_eq!(ilp.num_flavors(), 2); // Default when empty
736    }
737
738    #[test]
739    fn test_ilp_problem_size() {
740        let ilp = ILP::binary(
741            4,
742            vec![
743                LinearConstraint::le(vec![(0, 1.0)], 1.0),
744                LinearConstraint::le(vec![(1, 1.0)], 1.0),
745            ],
746            vec![],
747            ObjectiveSense::Minimize,
748        );
749        let size = ilp.problem_size();
750        assert_eq!(size.get("num_vars"), Some(4));
751        assert_eq!(size.get("num_constraints"), Some(2));
752    }
753
754    #[test]
755    fn test_ilp_energy_mode() {
756        let max_ilp = ILP::binary(2, vec![], vec![], ObjectiveSense::Maximize);
757        let min_ilp = ILP::binary(2, vec![], vec![], ObjectiveSense::Minimize);
758
759        assert!(max_ilp.energy_mode().is_maximization());
760        assert!(min_ilp.energy_mode().is_minimization());
761    }
762
763    #[test]
764    fn test_ilp_solution_size_valid() {
765        // Maximize x0 + 2*x1 subject to x0 + x1 <= 1
766        let ilp = ILP::binary(
767            2,
768            vec![LinearConstraint::le(vec![(0, 1.0), (1, 1.0)], 1.0)],
769            vec![(0, 1.0), (1, 2.0)],
770            ObjectiveSense::Maximize,
771        );
772
773        // Config [0, 1] means x0=0, x1=1 => obj = 2, valid
774        let sol = ilp.solution_size(&[0, 1]);
775        assert!(sol.is_valid);
776        assert!((sol.size - 2.0).abs() < 1e-9);
777
778        // Config [1, 0] means x0=1, x1=0 => obj = 1, valid
779        let sol = ilp.solution_size(&[1, 0]);
780        assert!(sol.is_valid);
781        assert!((sol.size - 1.0).abs() < 1e-9);
782    }
783
784    #[test]
785    fn test_ilp_solution_size_invalid() {
786        // x0 + x1 <= 1
787        let ilp = ILP::binary(
788            2,
789            vec![LinearConstraint::le(vec![(0, 1.0), (1, 1.0)], 1.0)],
790            vec![(0, 1.0), (1, 2.0)],
791            ObjectiveSense::Maximize,
792        );
793
794        // Config [1, 1] means x0=1, x1=1 => obj = 3, but invalid (1+1 > 1)
795        let sol = ilp.solution_size(&[1, 1]);
796        assert!(!sol.is_valid);
797        assert!((sol.size - 3.0).abs() < 1e-9);
798    }
799
800    #[test]
801    fn test_ilp_solution_size_with_offset_bounds() {
802        // Variables with non-zero lower bounds
803        let ilp = ILP::new(
804            2,
805            vec![VarBounds::bounded(1, 3), VarBounds::bounded(-1, 1)],
806            vec![],
807            vec![(0, 1.0), (1, 1.0)],
808            ObjectiveSense::Maximize,
809        );
810
811        // Config [0, 0] maps to x0=1, x1=-1 => obj = 0
812        let sol = ilp.solution_size(&[0, 0]);
813        assert!(sol.is_valid);
814        assert!((sol.size - 0.0).abs() < 1e-9);
815
816        // Config [2, 2] maps to x0=3, x1=1 => obj = 4
817        let sol = ilp.solution_size(&[2, 2]);
818        assert!(sol.is_valid);
819        assert!((sol.size - 4.0).abs() < 1e-9);
820    }
821
822    #[test]
823    fn test_ilp_brute_force_maximization() {
824        // Maximize x0 + 2*x1 subject to x0 + x1 <= 1, x0, x1 binary
825        let ilp = ILP::binary(
826            2,
827            vec![LinearConstraint::le(vec![(0, 1.0), (1, 1.0)], 1.0)],
828            vec![(0, 1.0), (1, 2.0)],
829            ObjectiveSense::Maximize,
830        );
831
832        let solver = BruteForce::new();
833        let solutions = solver.find_best(&ilp);
834
835        // Optimal: x1=1, x0=0 => objective = 2
836        assert_eq!(solutions.len(), 1);
837        assert_eq!(solutions[0], vec![0, 1]);
838    }
839
840    #[test]
841    fn test_ilp_brute_force_minimization() {
842        // Minimize x0 + x1 subject to x0 + x1 >= 1, x0, x1 binary
843        let ilp = ILP::binary(
844            2,
845            vec![LinearConstraint::ge(vec![(0, 1.0), (1, 1.0)], 1.0)],
846            vec![(0, 1.0), (1, 1.0)],
847            ObjectiveSense::Minimize,
848        );
849
850        let solver = BruteForce::new();
851        let solutions = solver.find_best(&ilp);
852
853        // Optimal: x0=1,x1=0 or x0=0,x1=1 => objective = 1
854        assert_eq!(solutions.len(), 2);
855        for sol in &solutions {
856            let size = ilp.solution_size(sol);
857            assert!(size.is_valid);
858            assert!((size.size - 1.0).abs() < 1e-9);
859        }
860    }
861
862    #[test]
863    fn test_ilp_brute_force_no_feasible() {
864        // x0 >= 1 AND x0 <= 0 (infeasible)
865        let ilp = ILP::binary(
866            1,
867            vec![
868                LinearConstraint::ge(vec![(0, 1.0)], 1.0),
869                LinearConstraint::le(vec![(0, 1.0)], 0.0),
870            ],
871            vec![(0, 1.0)],
872            ObjectiveSense::Minimize,
873        );
874
875        let solver = BruteForce::new();
876        let solutions = solver.find_best(&ilp);
877
878        // No feasible solutions
879        assert!(solutions.is_empty());
880    }
881
882    #[test]
883    fn test_ilp_unconstrained() {
884        // Maximize x0 + x1, no constraints, binary vars
885        let ilp = ILP::binary(
886            2,
887            vec![],
888            vec![(0, 1.0), (1, 1.0)],
889            ObjectiveSense::Maximize,
890        );
891
892        let solver = BruteForce::new();
893        let solutions = solver.find_best(&ilp);
894
895        // Optimal: both = 1
896        assert_eq!(solutions.len(), 1);
897        assert_eq!(solutions[0], vec![1, 1]);
898    }
899
900    #[test]
901    fn test_ilp_equality_constraint() {
902        // Minimize x0 subject to x0 + x1 == 1, binary vars
903        let ilp = ILP::binary(
904            2,
905            vec![LinearConstraint::eq(vec![(0, 1.0), (1, 1.0)], 1.0)],
906            vec![(0, 1.0)],
907            ObjectiveSense::Minimize,
908        );
909
910        let solver = BruteForce::new();
911        let solutions = solver.find_best(&ilp);
912
913        // Optimal: x0=0, x1=1 => objective = 0
914        assert_eq!(solutions.len(), 1);
915        assert_eq!(solutions[0], vec![0, 1]);
916    }
917
918    #[test]
919    fn test_ilp_multiple_constraints() {
920        // Maximize x0 + x1 + x2 subject to:
921        //   x0 + x1 <= 1
922        //   x1 + x2 <= 1
923        // Binary vars
924        let ilp = ILP::binary(
925            3,
926            vec![
927                LinearConstraint::le(vec![(0, 1.0), (1, 1.0)], 1.0),
928                LinearConstraint::le(vec![(1, 1.0), (2, 1.0)], 1.0),
929            ],
930            vec![(0, 1.0), (1, 1.0), (2, 1.0)],
931            ObjectiveSense::Maximize,
932        );
933
934        let solver = BruteForce::new();
935        let solutions = solver.find_best(&ilp);
936
937        // Optimal: x0=1, x1=0, x2=1 => objective = 2
938        assert_eq!(solutions.len(), 1);
939        assert_eq!(solutions[0], vec![1, 0, 1]);
940    }
941
942    #[test]
943    fn test_ilp_config_to_values() {
944        let ilp = ILP::new(
945            3,
946            vec![
947                VarBounds::bounded(0, 2),  // 0,1,2
948                VarBounds::bounded(-1, 1), // -1,0,1
949                VarBounds::bounded(5, 7),  // 5,6,7
950            ],
951            vec![],
952            vec![],
953            ObjectiveSense::Minimize,
954        );
955
956        // Config [0,0,0] => [0, -1, 5]
957        assert_eq!(ilp.config_to_values(&[0, 0, 0]), vec![0, -1, 5]);
958        // Config [2,2,2] => [2, 1, 7]
959        assert_eq!(ilp.config_to_values(&[2, 2, 2]), vec![2, 1, 7]);
960        // Config [1,1,1] => [1, 0, 6]
961        assert_eq!(ilp.config_to_values(&[1, 1, 1]), vec![1, 0, 6]);
962    }
963}
problemreductions/models/optimization/ilp.rs

problemreductions/models/optimization/
ilp.rs
