Structure of a Constraint Program

8.2 Structure of a Constraint Program

The typical top-level structure of a constraint program is

solve(Variables) :-
        read_data(Data),
        setup_constraints(Data, Variables),
        labeling(Variables).

where setup_constraints/2 contains the problem model. It creates the variables and the constraints over the variables. This is often, but not necessarily, deterministic. The labeling/1 predicate is the search part of the program that attempts to find solutions by trying all instantiations for the variables. This search is constantly pruned by constraint propagation.

The above program will find all solutions. If the best solution is wanted, a branch-and-bound procedure can be wrapped around the search component of the program:

solve(Variables) :-
        read_data(Data),
        setup_constraints(Data, Variables, Objective),
        branch_and_bound:minimize(labeling(Variables), Objective).

⊙: The branch_and_bound library provides generic predicates that support optimization in conjunction with any ECLⁱPS^e solver. Section 12.1.2 discusses these predicates.