1% BEGIN LICENSE BLOCK
2% Version: CMPL 1.1
3%
4% The contents of this file are subject to the Cisco-style Mozilla Public
5% License Version 1.1 (the "License"); you may not use this file except
6% in compliance with the License.  You may obtain a copy of the License
7% at www.eclipse-clp.org/license.
8% 
9% Software distributed under the License is distributed on an "AS IS"
10% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.  See
11% the License for the specific language governing rights and limitations
12% under the License. 
13% 
14% The Original Code is  CPViz Constraint Visualization System
15% The Initial Developer of the Original Code is  Helmut Simonis
16% Portions created by the Initial Developer are
17% Copyright (C) 2009-2010 Helmut Simonis
18% 
19% Contributor(s): 	Helmut Simonis, 4C, Univerity College Cork, Cork
20%			
21% 
22% END LICENSE BLOCK
23% ----------------------------------------------------------------------
24:-module(top).
25
26:-export(top/0).
27
28:-lib(ic).
29:-lib(ic_global).
30:-lib(ic_global_gac).
31:-lib(timeout).
32:-lib(lists).
33:-lib(cpviz).
34
35:-local struct(boat(nr,cap,crew,sorting)).
36
37top:-
38        problem(10,Hosts,Guests),
39%        once(model(Hosts,Guests,6,naive,"Viz_party_NAIVE")),
40%        once(model(Hosts,Guests,6,first_fail,"Viz_party_FF")),
41%        once(model(Hosts,Guests,6,layered,"Viz_party_LAYERED")),
42        once(model(Hosts,Guests,6,credit,"Viz_party_CREDIT")),
43        once(model(Hosts,Guests,6,layered_random,"Viz_party_RANDOM")),
44
45        true.
46
47model(Hosts,Guests,NrPeriods,Method,Output):-
48        seed(0),
49        writeq(Hosts),nl,
50        writeq(Guests),nl,
51        length(Hosts,NrHosts),
52        length(Guests,NrGuests),
53        dim(Matrix,[NrGuests,NrPeriods]),
54        Matrix[1..NrGuests,1..NrPeriods] :: 1..NrHosts,
55
56        create_visualization([output:Output,
57                              range_to:2000],Handle),
58        add_visualizer(Handle,
59                       domain_matrix(Matrix),
60                       [group:1,
61                        display:text]),
62        
63        (for(I,1,NrGuests),
64         param(Matrix,NrPeriods) do
65            ic:alldifferent(Matrix[I,1..NrPeriods])
66        ),
67
68        (for(J,1,NrPeriods),
69         param(Matrix,NrHosts,NrPeriods,NrGuests,Guests,Hosts,Handle) do
70            make_bins(Hosts,Bins),
71%            bin_packing_alone(Matrix[1..NrGuests,J],Guests,Bins),
72            bin_packing(Matrix[1..NrGuests,J],Guests,Bins),
73            X is NrPeriods+2+((J-1)//3)*(NrHosts+2),
74            Y is ((J-1) mod 3)*13,
75            add_visualizer(Handle,
76                           vector(Bins),
77                           [group:other,
78                            x:X,
79                            y:Y])
80        ),
81
82        (for(I,1,NrGuests-1),
83         param(Matrix,NrGuests,NrPeriods) do
84            (for(I1,I+1,NrGuests),
85             param(Matrix,NrPeriods,I) do
86                card_eq(Matrix[I,1..NrPeriods],
87                        Matrix[I1,1..NrPeriods],1)
88            )
89        ),
90        extract_array(Handle,col,1,Matrix,List),
91        root(Handle),
92        assign(Method,List,Matrix,NrPeriods,NrGuests,Handle),
93        solution(Handle),
94        close_visualization(Handle),
95        viz(Handle, _).
96
97assign(naive,List,_Matrix,_NrPeriods,_NrGuests,Handle):-
98        !,
99        search(List,1,input_order,tree_indomain(Handle,_),complete,[]).
100
101assign(first_fail,List,_Matrix,_NrPeriods,_NrGuests,Handle):-
102        !,
103        search(List,1,first_fail,tree_indomain(Handle,_),complete,[]).
104assign(layered,_,Matrix,NrPeriods,NrGuests,Handle):-
105        !,
106        repeat,
107        (for(J,1,NrPeriods),
108         param(Matrix,NrGuests,Handle) do
109            writeln(period(J)),
110            collection_to_list(Matrix[1..NrGuests,J],Vars),
111            Start is (J-1)*NrGuests+1,
112            indices(Vars,Start,J,1,List),
113            once(search(List,1,first_fail,tree_indomain(Handle,_),
114                        complete,[]))
115        ),
116        !.
117assign(credit,_,Matrix,NrPeriods,NrGuests,Handle):-
118        !,
119        repeat,
120        (for(J,1,NrPeriods),
121         param(Matrix,NrGuests,Handle) do
122            writeln(period(J)),
123            collection_to_list(Matrix[1..NrGuests,J],Vars),
124            Start is (J-1)*NrGuests+1,
125            indices(Vars,Start,J,1,List),
126            NSq is NrGuests*NrGuests,
127            once(search(List,1,first_fail,tree_indomain(Handle,_),
128                        credit(NSq,10),[]))
129        ),
130        !.
131assign(layered_random,_,Matrix,NrPeriods,NrGuests,Handle):-
132        !,
133        repeat,
134        (for(J,1,NrPeriods),
135         param(Matrix,NrGuests,Handle) do
136            writeln(period(J)),
137            collection_to_list(Matrix[1..NrGuests,J],Vars),
138            Start is (J-1)*NrGuests+1,
139            indices(Vars,Start,J,1,List),
140            NSq is NrGuests*NrGuests,
141            once(search(List,1,first_fail,tree_indomain_random(Handle,_),
142                        credit(NSq,10),[]))
143        ),
144        !.
145
146indices([],_,_,_,[]).
147indices([X|X1],N,J,K,[t(X,N,group(1,K-J))|T1]):-
148        N1 is N+1,
149        K1 is K+1,
150        indices(X1,N1,J,K1,T1).
151
152make_bins(HostCapacity,Bins):-
153        (foreach(Cap,HostCapacity),
154         foreach(B,Bins) do
155            B :: 0..Cap
156        ).
157
158card_eq(Vector1,Vector2,Card):-
159        collection_to_list(Vector1,List1),
160        collection_to_list(Vector2,List2),
161        (foreach(X,List1),
162         foreach(Y,List2),
163         fromto(0,A,A+B,Term) do
164            #=(X,Y,B)
165        ),
166        eval(Term) #=< Card.
167
168problem(Instance,HostCapacity,GuestSize):-
169        problem_data(Instance,List),
170        findall(boat{nr:Nr,cap:Cap,crew:Crew,sorting:Space},
171                (boat(Nr,Cap,Crew),
172                 Space is (Cap-Crew)*100+Crew,
173                 memberchk(Nr,List)),Hosts),
174        findall(boat{nr:Nr,cap:Cap,crew:Crew,sorting:Space},
175                (boat(Nr,Cap,Crew),
176                 Space is (Cap-Crew)*100+Crew,
177                 not memberchk(Nr,List)),Guests),
178        sort(sorting of boat,>=,Hosts,SortedHosts),
179        sort(crew of boat,>=,Guests,SortedGuests),
180        
181        guest_pattern(SortedGuests,GuestSize),
182        host_capacity(SortedHosts,HostCapacity).
183
184host_capacity(Hosts,HostCapacity):-
185        (foreach(boat{cap:Cap,crew:Crew},Hosts),
186         foreach(Capacity,HostCapacity) do
187            Capacity is Cap-Crew
188        ).
189
190guest_pattern(Guests,Height):-
191        (foreach(boat{crew:Crew},Guests),
192         foreach(Crew,Height) do
193            true
194        ).
195
196boat(1 , 6 , 2).
197boat(2 , 8 , 2).
198boat(3 , 12 , 2).
199boat(4 , 12 , 2).
200boat(5 , 12 , 4).
201boat(6 , 12 , 4).
202boat(7 , 12 , 4).
203boat(8 , 10 , 1).
204boat(9 , 10 , 2).
205boat(10 , 10 , 2).
206boat(11 , 10 , 2).
207boat(12 , 10 , 3).
208boat(13 , 8 , 4).
209boat(14 , 8 , 2).
210boat(15 , 8 , 3).
211boat(16 , 12 , 6).
212boat(17 , 8 , 2).
213boat(18 , 8 , 2).
214boat(19 , 8 , 4).
215boat(20 , 8 , 2).
216boat(21 , 8 , 4).
217boat(22 , 8 , 5).
218boat(23 , 7 , 4).
219boat(24 , 7 , 4).
220boat(25 , 7 , 2).
221boat(26 , 7 , 2).
222boat(27 , 7 , 4).
223boat(28 , 7 , 5).
224boat(29 , 6 , 2).
225boat(30 , 6 , 4).
226boat(31 , 6 , 2).
227boat(32 , 6 , 2).
228boat(33 , 6 , 2).
229boat(34 , 6 , 2).
230boat(35 , 6 , 2).
231boat(36 , 6 , 2).
232boat(37 , 6 , 4).
233boat(38 , 6 , 5).
234boat(39 , 9 , 7).
235boat(40 , 0 , 2).
236boat(41 , 0 , 3).
237boat(42 , 0 , 4 ).
238
239% problem 1-9  are from Symmetry breaking paper
240problem_data(1,[2,3,4,5,6,7,8,9,10,11,12,14,16]).
241problem_data(2,[3,4,5,6,7,8,9,10,11,12,13,14,16]).
242problem_data(3,[3,4,5,6,7,8,9,10,11,12,14,15,16]).
243problem_data(4,[3,4,5,6,7,8,9,10,11,12,14,16,25]).
244problem_data(5,[3,4,5,6,7,8,9,10,11,12,14,16,23]).
245problem_data(6,[3,4,5,6,7,8,9,10,11,12,15,16,25]).
246problem_data(7,[1,3,4,5,6,7,8,9,10,11,12,14,16]).
247problem_data(8,[3,4,5,6,7,8,9,10,11,12,16,25,26]).
248problem_data(9,[3,4,5,6,7,8,9,10,11,12,14,16,30]).
249% this is my favorite host selection
250problem_data(10,[1,2,3,4,5,6,7,8,9,10,11,12,14]).
251% problems 11-16 are problems 1-6 from Van Hentenryck/Michel
252problem_data(11,[1,2,3,4,5,6,7,8,9,10,11,12,16]).
253problem_data(12,[1,2,3,4,5,6,7,8,9,10,11,12,13]).
254problem_data(13,[1,3,4,5,6,7,8,9,10,11,12,13,19]).
255problem_data(14,[3,4,5,6,7,8,9,10,11,12,13,25,26]).
256problem_data(15,[1,2,3,4,5,6,7,8,9,10,11,19,21]).
257problem_data(16,[1,2,3,4,5,6,7,8,9,16,17,18,19]).
258
259problem_data(20,[3,4,5,6,7,8,9,10,11,12,16,39]).
260