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

scirs2_optimize/integer/
mod.rs
