rooc/solvers/
binary_solver.rs

1use crate::make_constraints_map_from_assignment;
2use crate::math::{Comparison, OptimizationType, VariableType};
3use crate::solvers::common::{find_invalid_variables, Assignment, LpSolution, SolverError};
4use crate::transformers::LinearModel;
5use copper::views::ViewExt;
6use copper::*;
7use num_traits::ToPrimitive;
8
9/// Solves a binary linear programming problem.
10///
11/// Takes a linear model containing only boolean variables and returns an optimal solution
12/// or an error if the problem cannot be solved.
13///
14/// # Arguments
15/// * `lp` - The linear programming model to solve, must contain only boolean variables
16///
17/// # Returns
18/// * `Ok(LpSolution<bool>)` - The optimal solution if found
19/// * `Err(SolverError)` - Various error conditions that prevented finding a solution
20///
21/// # Example
22/// ```rust
23/// use rooc::{VariableType, Comparison, OptimizationType, solve_binary_lp_problem, LinearModel};
24///
25/// let mut model = LinearModel::new();
26/// model.add_variable("x1", VariableType::Boolean);
27/// model.add_variable("x2", VariableType::Boolean);
28///
29/// // Add constraint: x1 + x2 <= 1
30/// model.add_constraint(vec![1.0, 1.0], Comparison::LessOrEqual, 1.0);
31///
32/// // Set objective: maximize x1 + 2*x2
33/// model.set_objective(vec![1.0, 2.0], OptimizationType::Max);
34///
35/// let solution = solve_binary_lp_problem(&model).unwrap();
36/// ```
37pub fn solve_binary_lp_problem(lp: &LinearModel) -> Result<LpSolution<bool>, SolverError> {
38    let non_binary_variables =
39        find_invalid_variables(lp.domain(), |var| matches!(var, VariableType::Boolean));
40    if !non_binary_variables.is_empty() {
41        return Err(SolverError::InvalidDomain {
42            expected: vec![VariableType::Boolean],
43            got: non_binary_variables,
44        });
45    }
46    let mut m = Model::default();
47    let vars: Vec<_> = m.new_vars_binary(lp.domain().len()).collect();
48
49    for (i, constraint) in lp.constraints().iter().enumerate() {
50        let lhs = constraint
51            .coefficients()
52            .iter()
53            .zip(vars.iter())
54            .map(|(c, v)| c.to_i32().map(|c| v.times(c)))
55            .collect::<Option<Vec<_>>>();
56        if lhs.is_none() {
57            return Err(SolverError::TooLarge {
58                name: format!("variable in constraint {}", i + 1),
59                value: *constraint
60                    .coefficients()
61                    .iter()
62                    .find(|c| c.to_f64().is_none())
63                    .unwrap_or(&0.0),
64            });
65        }
66        let lhs = m.sum_iter(lhs.unwrap());
67        let rhs = constraint.rhs().to_i32();
68        if rhs.is_none() {
69            return Err(SolverError::TooLarge {
70                name: format!("right hand side of constraint {}", i + 1),
71                value: constraint.rhs(),
72            });
73        }
74        let rhs = rhs.unwrap();
75        match constraint.constraint_type() {
76            Comparison::LessOrEqual => {
77                m.less_than_or_equals(lhs, rhs);
78            }
79            Comparison::Equal => {
80                m.equals(lhs, rhs);
81            }
82            Comparison::GreaterOrEqual => {
83                m.greater_than_or_equals(lhs, rhs);
84            }
85            Comparison::Less => {
86                m.less_than(lhs, rhs);
87            }
88            Comparison::Greater => {
89                m.greater_than(lhs, rhs);
90            }
91        }
92    }
93    let objective = lp
94        .objective()
95        .iter()
96        .zip(vars.iter())
97        .map(|(c, v)| c.to_i32().map(|c| v.times(c)))
98        .collect::<Option<Vec<_>>>();
99    if objective.is_none() {
100        return Err(SolverError::TooLarge {
101            name: "objective function variable".to_string(),
102            value: *lp
103                .objective()
104                .iter()
105                .find(|c| c.to_f64().is_none())
106                .unwrap_or(&0.0),
107        });
108    }
109    let objective = m.sum_iter(objective.unwrap());
110    let solution = match lp.optimization_type() {
111        OptimizationType::Max => m.maximize(objective),
112        OptimizationType::Min => m.minimize(objective),
113        OptimizationType::Satisfy => m.solve(),
114    };
115    match solution {
116        None => Err(SolverError::DidNotSolve),
117        Some(solution) => {
118            let var_names = lp.variables();
119            let mut assignment = solution
120                .get_values_binary(&vars)
121                .iter()
122                .zip(var_names.iter())
123                .map(|(v, n)| Assignment {
124                    name: n.clone(),
125                    value: *v,
126                })
127                .collect::<Vec<Assignment<bool>>>();
128            let coeffs = assignment
129                .iter()
130                .map(|v| if v.value { 1.0 } else { 0.0 })
131                .collect();
132            let constraints = make_constraints_map_from_assignment(lp, &coeffs);
133
134            let value = solution[objective] as f64 + lp.objective_offset();
135            assignment.sort_by(|a, b| a.name.cmp(&b.name));
136            let sol = LpSolution::new(assignment, value, constraints);
137            Ok(sol)
138        }
139    }
140}
rooc/solvers/binary_solver.rs

rooc/solvers/
binary_solver.rs
