Modelling¶
The Rust guide follows the Python guide chapter by chapter, with the
same problems and the same examples. Every piece of code in it is taken from tests/rust_guide,
which cargo test compiles and runs, so it matches the library.
A problem is a Problem: variables with finite integer domains, and constraints over them.
Everything else in the library starts from a problem. The constraints are built by functions of
aicad::constraints that add them to a problem: all_different, not_equals, equal (in
aicad::modelling), among, at_least, sum, gcc, regular, table and disjunctive.
The model¶
add_variables creates variables and returns their indices, so a roster of 3 nurses over 5 days is
three lists of five. The constraints take the problem, the indices of their scope and their
parameters. In the Python guide the same model is built with int_vars and Model.add.
use aicad::constraints::{among, gcc, regular};
use aicad::modelling::{Problem, equal};
const DAYS: usize = 5;
const NURSES: usize = 3;
const OFF: isize = 0;
const DAY: isize = 1;
const NIGHT: isize = 2;
/// The shift roster of a small team: `roster[n][d]` is the shift of nurse `n` on day `d`.
pub fn roster_problem() -> Problem {
let mut problem = Problem::default();
let roster: Vec<_> = (0..NURSES)
.map(|_| problem.add_variables(DAYS, vec![OFF, DAY, NIGHT]))
.collect();
// Every day has exactly one nurse on the night shift and one or two on the day shift.
for d in 0..DAYS {
let column = roster.iter().map(|nurse| nurse[d]).collect();
gcc(&mut problem, column, vec![(NIGHT, 1, 1), (DAY, 1, 2)]);
}
// A nurse works at most five days a week.
for row in &roster {
among(&mut problem, row.clone(), vec![DAY, NIGHT], 0, 5);
}
// A night shift is never directly followed by a day shift. State 0 is "not after a night",
// state 1 is "after a night"; the columns of the table are the sorted values of the domain
// (off, day, night), and `None` forbids a transition.
let after_night = vec![
vec![Some(0), Some(0), Some(1)], // state 0: off -> 0, day -> 0, night -> 1
vec![Some(0), None, Some(1)], // state 1: off -> 0, day is forbidden, night -> 1
];
for row in &roster {
regular(
&mut problem,
row.clone(),
after_night.clone(),
0,
vec![0, 1],
);
}
// The first nurse is on leave on the last day.
equal(&mut problem, roster[0][DAYS - 1], OFF);
problem
}
regular states a pattern on a sequence of variables with an automaton: here a night shift is never
directly followed by a day shift. State 0 is “not after a night”, state 1 is “after a night”; the
columns of the table are the sorted values of the domain (off, day, night), and None forbids a
transition. Constructors panic, with a message that names the problem, on input that cannot mean
anything, such as a repeated variable in the scope of all_different.
Checking an assignment¶
An assignment lists one value per variable, in the order of their indices. Problem::is_solution
tells whether it satisfies every constraint, and is_satisfied of a constraint whether it satisfies
that one.
let problem = roster_problem();
println!(
"{} variables, {} constraints",
problem.number_variables(),
problem.number_constraints()
);
// An assignment lists one value per variable, in the order of their indices.
let everyone_off = vec![OFF; problem.number_variables()];
assert!(!problem.is_solution(&everyone_off));
let violated = problem
.iter_constraints()
.filter(|&c| !problem[c].is_satisfied(&everyone_off))
.count();
println!(
"{violated} of {} constraints are violated",
problem.number_constraints()
);
Finding a solution is the job of the next chapters.