« MiniZinc/FlatZinc version 0.8 släppt | Main | Mats Anderssons tävling kring fotbolls-EM 2008 - ett MiniZinc-genererat tips »

juni 02, 2008

Nya MiniZinc-modeller, flera global constraints, däribland clique

Sedan anteckningen Några fler MiniZinc-modeller, t.ex. Smullyans Knights and Knaves-problem i förra veckan har några fler modeller skapats. Samtliga modeller finns att ladda ner från My MiniZinc page.

Denna gång är det förvisso några pyssel men fokus har varit att implementera global constraints från den fantastiska samligen Global Constraints Catalogue.

Pyssel

Samtliga desa pyssel är från de kommenterade exemplen i det första kapitlet från boken Problem Solving Through Recreational Mathematics av Bonnie Averbach och Orin Chein (ISBN: 9780486409177).

Av enkelhet är filerna döpta efter exemplets namngivning. Den specifika problemformuleringen finns i mzn-filen.
- Exempel 1.2. Enkelt problem om tre damer som sitter vid ett bridgebord och byter kort. Det gäller att avgöra hur de sitter.
- Exempel 1.3. Här ska man avgöra namnet på hustrur och hästar till 5 olika män.
- Exempel 1.4. Svårare variant av 1.2. Fem män med olika yrken spelar poker. Här gäller det att avgöra yrke och position vid bordet.
- Exempel 1.5. Nim, ganska generell. Problemet är att avgöra vilken strategi som garanterar vinst, men här visas endast alla giltiga drag (man får alltså dra egna slutsatser om strategier).

Global constraints etc

Så har det skapats några global constraint som finns i Global Constraints Catalogue eller sådana som är lite mer generella. Samtliga modeller innehåller ett enkelt exempel, för det mesta är det exemplet som finns i katalogen.


clique
Jag börjar med clique eftersom det är en av mina favorit-constraints, och att det tog en stund att får det rätt.

Modell och exempel finns i clique.mzn. Se även Global constraint-entry.

clique är ett begrepp från grafteorin som innebär att samtliga noder inom denna klick är kopplade till varandra. (Det är ungefär det vi menar med det vardagliga "klick" för att beskriva en social struktur, ett gäng, ett kotteri, etc.)

Ibland är problemet att hitta den största klicken i en graf, men ibland räcker det bara med en klick, vilken som helst av en viss storlek.

Exempel på clique
Låt oss leka lite med exemplet från GC-katalogen. Det är 5 noder som har följande kopplingar:

1 är kopplad till 2,4
2 är kopplad till 1,3,5
3 är kopplad till 2,5
4 är kopplad till 1,5
5 är kopplad till 2,3,4

Modellen arbetar med en matrisrepresentation av grafen, och visas i koden nedan.

Här är hela modellen.


include "globals.mzn"
int: num_nodes;
array[1..num_nodes, 1..num_nodes] of 0..1: g; % the graph (as a matrix)

var set of 1..num_nodes: s; % the clique
var int: c = card(s); % size of the clique

%
% clique(clique size, the clique, the graph)
%
% Note: I have added the clique in the parameters list.
%
predicate clique(var int: c, var set of int: s, array[int, int] of int: g) =
let {
int: n = card(index_set_1of2(g)),
array[1..n] of var bool: s_bool
}
in
link_set_to_booleans(s, s_bool)
/\
forall(i,j in 1..n where i != j) (
(s_bool[i] /\ s_bool[j]) -> ( g[i,j] > 0)
)
/\
c = card(s)
;

solve maximize c;

constraint
% s = {1,2,3} /\ % Exempel 1
clique(c, s, g)

% /\ % Example 2
% c >= 2
;

%
% data
%
num_nodes = 5;
g = [
% 1 2 3 4 5
1,1,0,1,0, % 1
1,1,1,0,1, % 2
0,1,1,0,1, % 3
1,0,0,1,1, % 4
0,1,1,1,1, % 5
];

Exempel på några problem med clique

Med constrainten clique kan man nu lösa bl.a. följande problem:

1. Är {1,2,3} en klick i denna graf?

solve satisfy;

constraint
s = {1,2,3}
/\
clique(c, s, g)
;

Svaret är: "No solution". Det är alltså ingen clique.


2. Visa samtliga klickar som är större än 2.
Det görs med denna constraint-sektion:


clique(c, s, g)
/\
c >= 2

dvs här har vi inte fixerat s (själva klicken). En massa lösningar skrivs nu ut.


3. Vilken är den största klicken och hur stor är den?
Här används solve maximize eftersom vi är ute efter den största av något (nämligen klickens storlek, c). För att effektivisera sökningen kan man begränsa till att undersöka klickar av storlek 2 eller större.


solve maximize c;
% ...
constraint
clique(c, s, g)
/\
c >= 2
;

Svar: Den största klicken är {2,3,5} och den är över 3 noder.
Not: Med solve maximize får man endast en lösning. Det är möjligt att det finns andra cliques som är lika stora. Då måste man ändra modellen till:

solve satisfy;
% ...
constraint
clique(c, s, g)
/\
c >= 3
;

I denna graf finns dock ingen annan clique med tre eller flera noder än {2,3,5}.


Noteras kan att det i modellen även finns en slumpgenererad graf på 100 noder. I den grafen finns 3515 olika klickar >= 3 (dock inklusive "subklickar"). Det finns fyra klickar av storlek 6. Det sistnämnda problemet tar cirka 5 sekunder att lista ut.

Övriga global constraints

Här är listingen av några andra global constraints. Beskrivning och länk till global constraints-katalogen finns i modellen.

* all_differ_from_at_least_k_pos

* all_min_dist

* alldifferent_cst

* alldifferent_except_0

* alldifferent_modulo

* alldifferent_on_intersection

* alldifferent_partition

* alldifferent_same_value

* alldifferent_soft
Modellen implementerar två varianter:
- soft_all_different_ctr
- soft_alldifferent_var

* change

* circular_change

* common
Modellen implementerar:
- common
- used_by

* count_ctr
Notera att MiniZinc har en count constraint i globals.mzn, men den är inte så generell som katalogens. Min modell är mer generell.

* distance_between

* inflexions

* k_alldifferent

* longest_change

* nchange

* period

* sum_ctr

Och så några generella constraints som inte finns i GC-katalogen:

* runs: Antalet runs i en vektor. En run är ett segment av en vektor som består av samma värde.

* fix_points: Antalet fixpoints i en vektor, dvs antalet positioner där värdet är samma som dess position.

Matris-operationer

Modellen transpose innehåller några matrisoperationer: - transpose - scalar_add - scalar_mult

Det var dessa matrisoperationer som jag behövde för tillfället.

En trevlig sak med constraint-programming är - som vi sett ovan och som jag skrivit om tidigare - att man "vända på" ett problem. I transpose-modellen finns en 4x4-matris (x) som man gör en transpose på (roterar 90 grader), varpå man gör en skalär addition på dessa två matriser (originalmatrisen + den transponerade).

Låt x vara originalmatrisen, t vara den transposerade matrisen och slutligen p vara resultatet av p = x + t (skalär addition av x och p).

Då kan vi lösa några olika problem.

1. Givet x, räkna ut p
Detta är det normala problemet: Räkna ut p om vi har x (och därmed t).


int: n;
array[1..n, 1..n] of var 1..10: x;
array[1..n, 1..n] of var 1..10: t;
array[1..n, 1..n] of var int: p;

solve satisfy;

%
% definition av transpose och scalar_add
% ....

constraint
x = [1,1,1,1,
2,2,2,2,
3,3,3,3,
4,4,4,4]
/\
transpose(x,t)
/\
scalar_add(x,t,p)
;

Här räknas både t och p ut med ledning av de värden som vi givit x.


2. Givet p, räkna ut x och t
Det är nu det börjar bli skoj!

Vi låter nu x och t vara variabler (dvs deklarerar dem inte) och fixerar endast p (resultatet av x + t). Hur många olika lösningar x + t = p med en fix matrix p finns det?


% ....

constraint
transpose(x,t)
/\
scalar_add(x,t,p)
/\
p =
[2, 3, 4, 5,
3, 4, 5, 6,
4, 5, 6, 7,
5, 6, 7, 8]

Svar: Det finns 2880 lösningar.


Slutord (för dagens skörd)


Global Constraint Catalogue innehåller för närvarande över 300 global constraints och jag har bara implementerat en bråkdel av dem. Flera kommer med stor sannolikhet att modelleras, i alla fall sådana som verkar nyttiga/skoj och går att göra i MiniZinc. Det finns några mer avancerade grafteoretiska constraints som är svåra att implementera i MiniZinc, som saknar rekursioner och dynamiskt växande listor.


Posted by hakank at juni 2, 2008 08:02 EM Posted to Constraint Programming