scirs2_optimize/integer/
mod.rs

1//! Integer Programming and Mixed-Integer Optimization
2//!
3//! This module provides algorithms for optimization problems where some or all
4//! variables must take integer values. It implements:
5//!
6//! - [`BranchAndBoundSolver`]: Branch-and-bound for mixed-integer programs
7//! - [`IntegerVariableSet`]: Specification of integer/binary/general integer constraints
8//! - [`CuttingPlaneSolver`]: Gomory cutting plane method for pure integer programs
9//!
10//! # Mixed-Integer Programming (MIP)
11//!
12//! A mixed-integer program has the form:
13//! ```text
14//! minimize    c^T x
15//! subject to  A x <= b      (linear inequality constraints)
16//!             Aeq x = beq   (linear equality constraints)
17//!             lb <= x <= ub (bounds)
18//!             x_I in Z      (integrality constraints for a subset I)
19//! ```
20//!
21//! # References
22//! - Land, A.H. & Doig, A.G. (1960). "An automatic method of solving discrete
23//!   programming problems." Econometrica, 28(3), 497-520.
24//! - Gomory, R.E. (1958). "Outline of an algorithm for integer solutions to
25//!   linear programs." Bulletin of the American Mathematical Society, 64(5), 275-278.
26
27use crate::error::{OptimizeError, OptimizeResult};
28use scirs2_core::ndarray::{Array1, Array2};
29
30pub mod branch_and_bound;
31pub mod cdcl_branching;
32pub mod column_generation;
33pub mod cutting_plane;
34pub mod knapsack;
35pub mod lift_project;
36pub mod lift_project_mip;
37pub mod lp_relaxation;
38pub mod milp_branch_and_bound;
39
40pub use branch_and_bound::{BranchAndBoundOptions, BranchAndBoundSolver};
41pub use cutting_plane::{CuttingPlaneOptions, CuttingPlaneSolver};
42pub use lp_relaxation::LpRelaxationSolver;
43
44/// Type of integer variable constraint
45#[derive(Debug, Clone, Copy, PartialEq, Eq)]
46pub enum IntegerKind {
47    /// Continuous variable (no integrality constraint)
48    Continuous,
49    /// Binary variable: must be 0 or 1
50    Binary,
51    /// General integer variable: must be an integer
52    Integer,
53}
54
55/// Set of integer variable constraints for a MIP problem
56#[derive(Debug, Clone)]
57pub struct IntegerVariableSet {
58    /// Variable types (indexed by variable position)
59    pub kinds: Vec<IntegerKind>,
60}
61
62impl IntegerVariableSet {
63    /// Create a new set with all continuous variables
64    pub fn new(n: usize) -> Self {
65        IntegerVariableSet {
66            kinds: vec![IntegerKind::Continuous; n],
67        }
68    }
69
70    /// Create a set with all integer variables
71    pub fn all_integer(n: usize) -> Self {
72        IntegerVariableSet {
73            kinds: vec![IntegerKind::Integer; n],
74        }
75    }
76
77    /// Create a set with all binary variables
78    pub fn all_binary(n: usize) -> Self {
79        IntegerVariableSet {
80            kinds: vec![IntegerKind::Binary; n],
81        }
82    }
83
84    /// Set variable i to be of given kind
85    pub fn set_kind(&mut self, i: usize, kind: IntegerKind) {
86        if i < self.kinds.len() {
87            self.kinds[i] = kind;
88        }
89    }
90
91    /// Return true if variable i has an integrality constraint
92    pub fn is_integer(&self, i: usize) -> bool {
93        match self.kinds.get(i) {
94            Some(IntegerKind::Integer) | Some(IntegerKind::Binary) => true,
95            _ => false,
96        }
97    }
98
99    /// Number of variables
100    pub fn len(&self) -> usize {
101        self.kinds.len()
102    }
103
104    /// True if no integer variables are defined
105    pub fn is_empty(&self) -> bool {
106        self.kinds.iter().all(|k| *k == IntegerKind::Continuous)
107    }
108}
109
110/// Result from a MIP solve
111#[derive(Debug, Clone)]
112pub struct MipResult {
113    /// Optimal solution
114    pub x: Array1<f64>,
115    /// Optimal objective value
116    pub fun: f64,
117    /// Whether an optimal solution was found
118    pub success: bool,
119    /// Status message
120    pub message: String,
121    /// Number of nodes explored (B&B)
122    pub nodes_explored: usize,
123    /// Number of LP solves
124    pub lp_solves: usize,
125    /// Lower bound on optimal value
126    pub lower_bound: f64,
127}
128
129/// Linear program specification
130#[derive(Debug, Clone)]
131pub struct LinearProgram {
132    /// Objective coefficients: minimize c^T x
133    pub c: Array1<f64>,
134    /// Inequality constraint matrix (A x <= b)
135    pub a_ub: Option<Array2<f64>>,
136    /// Inequality constraint RHS
137    pub b_ub: Option<Array1<f64>>,
138    /// Equality constraint matrix (Aeq x = beq)
139    pub a_eq: Option<Array2<f64>>,
140    /// Equality constraint RHS
141    pub b_eq: Option<Array1<f64>>,
142    /// Lower bounds (default: 0)
143    pub lower: Option<Array1<f64>>,
144    /// Upper bounds (default: infinity)
145    pub upper: Option<Array1<f64>>,
146}
147
148impl LinearProgram {
149    /// Create a new LP with just an objective
150    pub fn new(c: Array1<f64>) -> Self {
151        LinearProgram {
152            c,
153            a_ub: None,
154            b_ub: None,
155            a_eq: None,
156            b_eq: None,
157            lower: None,
158            upper: None,
159        }
160    }
161
162    /// Number of variables
163    pub fn n_vars(&self) -> usize {
164        self.c.len()
165    }
166}
167
168/// Check if a value is integer (within tolerance)
169#[inline]
170pub fn is_integer_valued(v: f64, tol: f64) -> bool {
171    (v - v.round()).abs() <= tol
172}
173
174/// Find the most fractional variable index
175pub fn most_fractional_variable(x: &[f64], var_set: &IntegerVariableSet) -> Option<usize> {
176    let mut best_idx = None;
177    let mut best_frac = -1.0_f64;
178    for (i, &xi) in x.iter().enumerate() {
179        if var_set.is_integer(i) {
180            let frac = (xi - xi.floor()).abs();
181            let frac = frac.min(1.0 - frac); // distance from nearest integer
182            if frac > 1e-8 && frac > best_frac {
183                best_frac = frac;
184                best_idx = Some(i);
185            }
186        }
187    }
188    best_idx
189}
190
191#[cfg(test)]
192mod tests {
193    use super::*;
194
195    #[test]
196    fn test_integer_variable_set_creation() {
197        let ivs = IntegerVariableSet::new(5);
198        assert_eq!(ivs.len(), 5);
199        assert!(ivs.is_empty());
200        for i in 0..5 {
201            assert!(!ivs.is_integer(i));
202        }
203    }
204
205    #[test]
206    fn test_integer_variable_set_all_integer() {
207        let ivs = IntegerVariableSet::all_integer(3);
208        assert!(!ivs.is_empty());
209        for i in 0..3 {
210            assert!(ivs.is_integer(i));
211        }
212    }
213
214    #[test]
215    fn test_integer_variable_set_mixed() {
216        let mut ivs = IntegerVariableSet::new(4);
217        ivs.set_kind(1, IntegerKind::Integer);
218        ivs.set_kind(3, IntegerKind::Binary);
219        assert!(!ivs.is_integer(0));
220        assert!(ivs.is_integer(1));
221        assert!(!ivs.is_integer(2));
222        assert!(ivs.is_integer(3));
223    }
224
225    #[test]
226    fn test_is_integer_valued() {
227        assert!(is_integer_valued(3.0, 1e-8));
228        assert!(is_integer_valued(3.0000000001, 1e-7));
229        assert!(!is_integer_valued(3.5, 1e-8));
230        assert!(!is_integer_valued(3.1, 1e-8));
231    }
232
233    #[test]
234    fn test_most_fractional_variable() {
235        let x = vec![1.0, 2.6, 3.1, 0.5];
236        let ivs = IntegerVariableSet::all_integer(4);
237        let idx = most_fractional_variable(&x, &ivs);
238        // x[3] = 0.5 is most fractional (distance 0.5 from nearest integer)
239        assert_eq!(idx, Some(3));
240    }
241
242    #[test]
243    fn test_linear_program_construction() {
244        use scirs2_core::ndarray::array;
245        let c = array![1.0, -2.0, 3.0];
246        let lp = LinearProgram::new(c);
247        assert_eq!(lp.n_vars(), 3);
248    }
249}
scirs2_optimize/integer/mod.rs

scirs2_optimize/integer/
mod.rs
