eyeprolog

Global constraints over integers

How do whole-problem constraints describe tables, schedules, costs, and tours?

Some conditions are about a whole group of variables at once: “these values must form one round trip”, “this pair must come from a table”. CLP(Z) calls them global constraints. This example puts four of them to work in four small puzzles.

Run it in the playground · Source

The question

Each clause of advanced_clpz/2 poses one small problem:

table: which partner values are compatible with 4?
schedule: at what times can three tasks start without overlapping?
cardinality: how can three slots be filled with two 1s and one 3, and what does each choice cost?
circuit: which successor list visits four places in one tour?

A compatibility table and a tour

advanced_clpz(table, compatible(4, Y, Distinct)) :-
  tuples_in([[X, Y]], [[1, 2], [1, 5], [4, 0], [4, 3]]),
  X = 4,
  nvalue(Distinct, [X, Y]),
  labeling([], [Y]).

advanced_clpz(circuit, successors(Values)) :-
  Values = [A, B, _, _],
  circuit(Values),
  A #= 2,
  B #= 3,
  labeling([ff], Values).

tuples_in/2 restricts a pair to the rows of a table; nvalue/2 counts distinct values. In circuit/1, position i holds the successor of place i, and the whole list must form a single cycle through all places.

A schedule and a costed assignment

advanced_clpz(schedule, starts([A, B, C])) :-
  [A, B, C] ins 0..3,
  lex_chain([[A, B], [B, C]]),
  serialized([A, B, C], [1, 2, 1]),
  A #< B,
  B #< C,
  labeling([ff], [A, B, C]).

advanced_clpz(cardinality, assignment(Values, Cost, Order)) :-
  Values = [_, _, _],
  global_cardinality(Values, [1-2, 3-1],
    [cost(Cost, [[5, 1], [2, 4], [3, 6]])]),
  labeling([ff], Values),
  zcompare(Order, Cost, 10).

serialized/2 keeps tasks with durations 1, 2, and 1 from overlapping. global_cardinality/3 fixes how often each value occurs and charges a cost per slot and value. zcompare/3 compares that cost with 10.

The answer

eyeprolog examples/clpz-global-constraints.pl

advanced_clpz(table, compatible(4, 0, 2)).
advanced_clpz(table, compatible(4, 3, 2)).
advanced_clpz(schedule, starts([0, 1, 3])).
advanced_clpz(cardinality, assignment([1, 1, 3], 13, >)).
advanced_clpz(cardinality, assignment([1, 3, 1], 12, >)).
advanced_clpz(cardinality, assignment([3, 1, 1], 6, <)).
advanced_clpz(circuit, successors([2, 3, 4, 1])).

Two table partners for 4, one schedule, three costed assignments, and the single tour 1 → 2 → 3 → 4 → 1.

The reason

step(advanced_clpz(table, compatible(4, 0, 2)),
     rule(1),
     ['Y' = 0, 'Distinct' = 2, 'X' = 4],
     [tuples_in([[4, 0]], [[1, 2], [1, 5], [4, 0], [4, 3]]),
      4 = 4,
      nvalue(2, [4, 0]),
      labeling([], [0])]).
step(tuples_in([[4, 0]], [[1, 2], [1, 5], [4, 0], [4, 3]]), builtin, [], []).

compatible(4, 0, 2) holds by the first rule: [4, 0] is a row of the table, and the pair has two distinct values. Each constraint appears with its final values filled in.

The check

condition('C1', resolution, ok, 7).
condition('C5', re_decision, ok, 40).
steps(47).
recomputed(34).
composed(6).
trusted(0).
verdict(checked).

All 7 rule steps resolve, and the checker recomputes 34 constraint steps on their ground values: once the variables are bound, each global constraint is a plain test. The 6 control steps are the branches the compiled constraints took, each composed from the goals it rests on. Nothing is trusted.

Try it

Remove B #= 3 from the circuit clause. A second tour appears: successors([2, 4, 1, 3]).
Add [4, 7] to the compatibility table and predict the new answers.
Change the task durations in serialized/2 to [2, 2, 1]. Does a schedule within 0..3 still exist?

Learn more in The Art of EyeProlog, Chapter 24.

This site is open source. Improve this page.