converge_optimization/packs/constraint_programming/
solver.rs

1//! Solver for Constraint Programming pack
2//!
3//! Simple backtracking with constraint propagation.
4
5use super::types::*;
6use converge_pack::gate::GateResult as Result;
7use converge_pack::gate::{ProblemSpec, ReplayEnvelope, SolverReport};
8
9pub struct BacktrackingSolver;
10
11impl BacktrackingSolver {
12    pub fn solve(
13        &self,
14        input: &ConstraintProgrammingInput,
15        spec: &ProblemSpec,
16    ) -> Result<(ConstraintProgrammingOutput, SolverReport)> {
17        let n = input.variables.len();
18        let mut best_assignment: Option<Vec<i64>> = None;
19        let mut best_obj: Option<i64> = None;
20        let mut current = vec![0i64; n];
21
22        Self::backtrack(input, 0, &mut current, &mut best_assignment, &mut best_obj);
23
24        let (assignments, feasible, objective_value) = match best_assignment {
25            Some(values) => {
26                let assignments: Vec<CpAssignment> = input
27                    .variables
28                    .iter()
29                    .zip(values.iter())
30                    .map(|(var, &val)| CpAssignment {
31                        name: var.name.clone(),
32                        value: val,
33                    })
34                    .collect();
35                (assignments, true, best_obj)
36            }
37            None => (vec![], false, None),
38        };
39
40        let output = ConstraintProgrammingOutput {
41            assignments,
42            feasible,
43            objective_value,
44        };
45
46        let replay = ReplayEnvelope::minimal(spec.seed());
47        let obj_val = objective_value.unwrap_or(0) as f64;
48        let report = SolverReport::optimal("backtracking-cp-v1", obj_val, replay);
49
50        Ok((output, report))
51    }
52
53    fn backtrack(
54        input: &ConstraintProgrammingInput,
55        depth: usize,
56        current: &mut Vec<i64>,
57        best: &mut Option<Vec<i64>>,
58        best_obj: &mut Option<i64>,
59    ) {
60        let n = input.variables.len();
61        if depth == n {
62            if Self::all_constraints_satisfied(input, current) {
63                let obj = input.objective.as_ref().map(|o| {
64                    let idx = input
65                        .variables
66                        .iter()
67                        .position(|v| v.name == o.variable)
68                        .unwrap_or(0);
69                    current[idx]
70                });
71
72                let dominated = match (&input.objective, obj, *best_obj) {
73                    (Some(o), Some(cur), Some(prev)) => {
74                        if o.maximize {
75                            cur <= prev
76                        } else {
77                            cur >= prev
78                        }
79                    }
80                    _ => false,
81                };
82
83                if !dominated {
84                    *best = Some(current.clone());
85                    *best_obj = obj;
86                }
87            }
88            return;
89        }
90
91        let var = &input.variables[depth];
92        for val in var.min..=var.max {
93            current[depth] = val;
94            if Self::partial_constraints_satisfied(input, current, depth) {
95                Self::backtrack(input, depth + 1, current, best, best_obj);
96            }
97        }
98    }
99
100    fn all_constraints_satisfied(input: &ConstraintProgrammingInput, vals: &[i64]) -> bool {
101        input
102            .constraints
103            .iter()
104            .all(|c| Self::check_constraint(input, vals, c, input.variables.len()))
105    }
106
107    fn partial_constraints_satisfied(
108        input: &ConstraintProgrammingInput,
109        vals: &[i64],
110        depth: usize,
111    ) -> bool {
112        input
113            .constraints
114            .iter()
115            .all(|c| Self::check_constraint(input, vals, c, depth + 1))
116    }
117
118    fn check_constraint(
119        input: &ConstraintProgrammingInput,
120        vals: &[i64],
121        constraint: &CpConstraint,
122        assigned_count: usize,
123    ) -> bool {
124        let var_index =
125            |name: &str| -> Option<usize> { input.variables.iter().position(|v| v.name == name) };
126
127        match constraint.constraint_type {
128            ConstraintType::LessThan => {
129                let left = constraint.args.get("left").and_then(|v| v.as_str());
130                let right = constraint.args.get("right").and_then(|v| v.as_str());
131                match (left.and_then(&var_index), right.and_then(&var_index)) {
132                    (Some(li), Some(ri)) if li < assigned_count && ri < assigned_count => {
133                        vals[li] < vals[ri]
134                    }
135                    _ => true,
136                }
137            }
138            ConstraintType::NotEqual => {
139                let left = constraint.args.get("left").and_then(|v| v.as_str());
140                let right = constraint.args.get("right").and_then(|v| v.as_str());
141                match (left.and_then(&var_index), right.and_then(&var_index)) {
142                    (Some(li), Some(ri)) if li < assigned_count && ri < assigned_count => {
143                        vals[li] != vals[ri]
144                    }
145                    _ => true,
146                }
147            }
148            ConstraintType::SumEquals => {
149                let vars: Vec<usize> = constraint
150                    .args
151                    .get("variables")
152                    .and_then(|v| v.as_array())
153                    .map(|arr| {
154                        arr.iter()
155                            .filter_map(|v| v.as_str().and_then(&var_index))
156                            .collect()
157                    })
158                    .unwrap_or_default();
159                let target = constraint
160                    .args
161                    .get("value")
162                    .and_then(|v| v.as_i64())
163                    .unwrap_or(0);
164
165                if vars.iter().all(|&i| i < assigned_count) {
166                    let sum: i64 = vars.iter().map(|&i| vals[i]).sum();
167                    sum == target
168                } else {
169                    true
170                }
171            }
172        }
173    }
174}
converge_optimization/packs/constraint_programming/solver.rs

converge_optimization/packs/constraint_programming/
solver.rs
