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.