Skip to content
Tutorials Center
My learning

Topics

Lesson 33 of 40 ยท Constraint Logic Programming

Global Constraints and Optimization

Go beyond simple constraints with CLP(FD). Use all_distinct, sum/3, element/3, global_cardinality, tuples_in, circuit and cumulative, and find optimal solutions with labeling min and max.

Simple constraints such as X #\= Y are powerful, but writing a problem as thousands of them is slow and propagates weakly. A global constraint captures a whole pattern in one call, for example "these variables are all different" or "these tasks never use more than two machines at once", and the solver uses specialized algorithms for it. This lesson tours the global constraints in SWI-Prolog's library(clpfd) and then shows how to ask for the best solution instead of just any solution.

The Prolog code is read-only because Prolog is not available on this site. The two runnable examples use the Python stand-in solver from Constraint Logic Programming with CLP(FD) to model the same problems.

Common global constraints

Constraint Meaning
all_distinct(Vs) all variables differ; stronger propagation than all_different/1
sum(Vs, Op, Expr) the sum of the list compares to Expr with #=, #=<, ...
scalar_product(Cs, Vs, Op, Expr) the weighted sum of Vs with integer coefficients Cs
element(I, List, V) V is the I-th element of List (1-based)
global_cardinality(Vs, Pairs) each value K occurs exactly the stated number of times
tuples_in(Tuples, Relation) each tuple of variables is a row of an explicit table
circuit(Succ) the successor list forms a single cycle through all nodes
cumulative(Tasks, Options) tasks never exceed a resource limit at any time
lex_chain(Lists) lists are in lexicographic order (symmetry breaking)
transpose(Matrix, Columns) swap rows and columns (a utility, handy for Sudoku)

A few examples with their answers:

PROLOG
?- sum([A,B,C], #=, 10), [A,B,C] ins 3..4, label([A,B,C]).
A = 3, B = 3, C = 4 ;
A = 3, B = 4, C = 3 ;
A = 4, B = 3, C = 3.

?- element(2, [10,20,30], V).
V = 20.

?- element(I, [10,20,30], 20).
I = 2.

?- length(Xs, 3), Xs ins 1..2, global_cardinality(Xs, [1-2, 2-1]), label(Xs).
Xs = [1, 1, 2] ;
Xs = [1, 2, 1] ;
Xs = [2, 1, 1].

?- tuples_in([[X,Y]], [[1,2],[2,3],[3,4]]), X #> 1, label([X,Y]).
X = 2, Y = 3 ;
X = 3, Y = 4.

?- length(Vs, 3), circuit(Vs), label(Vs).
Vs = [2, 3, 1] ;
Vs = [3, 1, 2].

element/3 is the constraint form of list lookup and is used to index a table with a variable; it works in both directions, as the second query shows. tuples_in/2 turns any table of allowed combinations into a constraint, which is the most general way to describe "these values may only occur together in these patterns". circuit/1 takes Succ, where Succ[i] is the node that follows node i, and forces a single Hamiltonian cycle; it is the core of routing and traveling-salesman models.

all_distinct/1 is the one to learn first. On a Sudoku row of nine variables, all_different/1 only removes a value from the others when one variable is fixed, while all_distinct/1 also spots deeper contradictions, such as three variables sharing only two values. For puzzles with tight rows, that difference decides between instant and impossible.

Global constraints

sum, scalar_product Totals and weighted totals.
all_distinct No repeated values.
element, tuples_in Lookups and allowed tables.
circuit One cycle through every node.

One global constraint beats a pile of small ones.

1 / 2

Optimization with labeling

So far label/1 has produced solutions in arbitrary order. labeling/2 can instead produce them best first, by passing min(Expr) or max(Expr). The solver uses branch and bound: each solution found becomes a bound that every later solution must beat. Classic knapsack:

PROLOG
knapsack(Counts, Value) :-
    Counts = [A, B, C],
    Counts ins 0..3,
    3*A + 4*B + 5*C #=< 10,            % weight limit
    Value #= 4*A + 5*B + 7*C.          % what we want to maximize
PROLOG
?- knapsack(Cs, V), labeling([max(V)], Cs).
Cs = [0, 0, 2],
V = 14 .

The first answer is the best one. To keep only the optimum, call it with once/1. On backtracking, labeling([max(V)], Cs) continues with the remaining solutions in non-increasing order, so it is also a way to list all solutions sorted by value.

The same pattern covers shortest routes (min(Length)), cheapest assignments (min(Cost)) and fewest colors (min(Colors)). Remember to include the cost expression's variable in the problem as a constraint (Value #= ...) so that propagation tracks it as the search proceeds.

Python Knapsack: best solution first (Python stand-in solver)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Scheduling

Scheduling is the home turf of constraint programming. A task has a start, a duration and a resource demand. cumulative/2 says the total demand of the tasks running at any moment never exceeds a limit:

PROLOG
schedule(Starts, End) :-
    Starts = [SA, SB, SC],
    Starts ins 0..20,
    Tasks = [task(SA, 3, EA, 1, _),     % task(Start, Duration, End, Demand, Id)
             task(SB, 2, EB, 1, _),
             task(SC, 4, EC, 1, _)],
    cumulative(Tasks, [limit(1)]),      % one machine
    SB #>= SA + 3,                      % B must come after A
    End #= max(EA, max(EB, EC)),
    labeling([min(End)], Starts).

With a limit of 1 the tasks cannot overlap, and the precedence constraint forces B after A. The optimum makespan is 9: the three durations add up to 9, so there can be no idle time. The next stand-in does the same without cumulative/2, by stating the non-overlap pairs explicitly.

Python Single-machine schedule (Python stand-in solver)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You should see three optimal orders: A, B, C; A, C, B; and C, A, B. Because the goal is to minimize the end of the schedule, solutions with idle gaps never appear among the optimal ones.

Reification and counting

Global constraints compose with the reified connectives from the previous lesson. For example, "at most two of these tasks may be late" is a sum of reified conditions:

PROLOG
at_most_two_late(Ends, Deadlines) :-
    maplist([E, D, L]>>(L #<==> (E #> D)), Ends, Deadlines, Lates),
    sum(Lates, #=<, 2).

Practical advice

  • Prefer the global constraint when one exists: all_distinct over pairwise #\=, sum/3 over a long chain of +.
  • Keep objective variables explicit and constrained (Cost #= ...) so that min/1 and max/1 can prune.
  • Give tight domains; a loose upper bound on a cost variable weakens branch and bound.
  • For large optimization problems, try labeling([ff, min(Cost)], Vars) and consider a time limit with call_with_time_limit/2.
  • Check the model on a small instance with a known optimum before scaling up.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does element(I, [10,20,30], V) express?

    element/3 relates an index and the value at that position, and works in both directions.
  2. 2. Why prefer all_distinct/1 to all_different/1 on tight puzzles?

    all_distinct reasons about the whole set (for example three variables sharing two values), at a higher cost per step.
  3. 3. What does labeling([max(V)], Vars) return first?

    With max(Expr), solutions come best first, so the first answer is optimal.
  4. 4. What does circuit(Succ) enforce?

    circuit/1 models a single tour visiting every node exactly once, the core of routing problems.

Summary

  • Global constraints (all_distinct, sum, element, global_cardinality, tuples_in, circuit, cumulative) express common patterns and propagate strongly.
  • labeling([min(Expr)], Vs) and labeling([max(Expr)], Vs) do branch and bound and return solutions best first.
  • Keep the objective as a constrained variable and use tight domains.
  • Reified constraints combine with sum/3 for counting conditions.

Next: Graph Search and Planning