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(timeout).
31:-lib(lists).
32:-lib(cpviz).
33
34:-local struct(boat(nr,cap,crew,sorting)).
35
36top:-
37        problem(10,Hosts,Guests),
38        once(model(Hosts,Guests,6,credit,"Viz_bin_CREDIT")),
39
40        true.
41
42model(Hosts,Guests,NrPeriods,Method,Output):-
43        seed(0),
44        writeq(Hosts),nl,
45        writeq(Guests),nl,
46        length(Hosts,NrHosts),
47        length(Guests,NrGuests),
48        dim(Matrix,[NrGuests,NrPeriods]),
49        Matrix[1..NrGuests,1..NrPeriods] :: 1..NrHosts,
50
51        create_visualization([output:Output,
52                              range_to:2000],Handle),
53        add_visualizer(Handle,
54                       domain_matrix(Matrix),
55                       [group:1,
56                        display:text]),
57        
58        (for(I,1,NrGuests),
59         param(Matrix,NrPeriods) do
60            ic:alldifferent(Matrix[I,1..NrPeriods])
61        ),
62
63        (for(J,1,NrPeriods),
64         param(Matrix,NrPeriods,NrGuests,Guests,Hosts,Handle) do
65            make_bins(Hosts,Bins),
66            bin_packing(Matrix[1..NrGuests,J],Guests,Bins),
67            X is NrPeriods+2+((J-1)//2)*(11+2),
68            Y is ((J-1) mod 2)*15,
69            add_visualizer(Handle,
70                           bin_packing(Matrix[1..NrGuests,J],Guests,Bins),
71                           [x:X,y:Y])
72        ),
73
74        (for(I,1,NrGuests-1),
75         param(Matrix,NrGuests,NrPeriods) do
76            (for(I1,I+1,NrGuests),
77             param(Matrix,NrPeriods,I) do
78                card_eq(Matrix[I,1..NrPeriods],
79                        Matrix[I1,1..NrPeriods],1)
80            )
81        ),
82        extract_array(Handle,col,1,Matrix,List),
83        root(Handle),
84        assign(Method,List,Matrix,NrPeriods,NrGuests,Handle),
85        solution(Handle),
86        close_visualization(Handle),
87        viz(Handle, _).
88
89assign(naive,List,_Matrix,_NrPeriods,_NrGuests,Handle):-
90        !,
91        search(List,1,input_order,tree_indomain(Handle,_),complete,[]).
92
93assign(first_fail,List,_Matrix,_NrPeriods,_NrGuests,Handle):-
94        !,
95        search(List,1,first_fail,tree_indomain(Handle,_),complete,[]).
96assign(layered,_,Matrix,NrPeriods,NrGuests,Handle):-
97        !,
98        repeat,
99        (for(J,1,NrPeriods),
100         param(Matrix,NrGuests,Handle) do
101            writeln(period(J)),
102            collection_to_list(Matrix[1..NrGuests,J],Vars),
103            Start is (J-1)*NrGuests+1,
104            indices(Vars,Start,J,1,List),
105            once(search(List,1,first_fail,tree_indomain(Handle,_),
106                        complete,[]))
107        ),
108        !.
109assign(credit,_,Matrix,NrPeriods,NrGuests,Handle):-
110        !,
111        repeat,
112        (for(J,1,NrPeriods),
113         param(Matrix,NrGuests,Handle) do
114            collection_to_list(Matrix[1..NrGuests,J],Vars),
115            Start is (J-1)*NrGuests+1,
116            indices(Vars,Start,J,1,List),
117            NSq is NrGuests*NrGuests,
118            once(search(List,1,first_fail,tree_indomain(Handle,_),
119                        credit(NSq,10),[]))
120        ),
121        !.
122assign(layered_random,_,Matrix,NrPeriods,NrGuests,Handle):-
123        !,
124        repeat,
125        (for(J,1,NrPeriods),
126         param(Matrix,NrGuests,Handle) do
127            writeln(period(J)),
128            collection_to_list(Matrix[1..NrGuests,J],Vars),
129            Start is (J-1)*NrGuests+1,
130            indices(Vars,Start,J,1,List),
131            NSq is NrGuests*NrGuests,
132            once(search(List,1,first_fail,tree_indomain_random(Handle,_),
133                        credit(NSq,10),[]))
134        ),
135        !.
136
137indices([],_,_,_,[]).
138indices([X|X1],N,J,K,[t(X,N,group(1,K-J))|T1]):-
139        N1 is N+1,
140        K1 is K+1,
141        indices(X1,N1,J,K1,T1).
142
143make_bins(HostCapacity,Bins):-
144        (foreach(Cap,HostCapacity),
145         foreach(B,Bins) do
146            B :: 0..Cap
147        ).
148
149card_eq(Vector1,Vector2,Card):-
150        collection_to_list(Vector1,List1),
151        collection_to_list(Vector2,List2),
152        (foreach(X,List1),
153         foreach(Y,List2),
154         fromto(0,A,A+B,Term) do
155            #=(X,Y,B)
156        ),
157        eval(Term) #=< Card.
158
159problem(Instance,HostCapacity,GuestSize):-
160        problem_data(Instance,List),
161        findall(boat{nr:Nr,cap:Cap,crew:Crew,sorting:Space},
162                (boat(Nr,Cap,Crew),
163                 Space is (Cap-Crew)*100+Crew,
164                 memberchk(Nr,List)),Hosts),
165        findall(boat{nr:Nr,cap:Cap,crew:Crew,sorting:Space},
166                (boat(Nr,Cap,Crew),
167                 Space is (Cap-Crew)*100+Crew,
168                 not memberchk(Nr,List)),Guests),
169        sort(sorting of boat,>=,Hosts,SortedHosts),
170        sort(crew of boat,>=,Guests,SortedGuests),
171        
172        guest_pattern(SortedGuests,GuestSize),
173        host_capacity(SortedHosts,HostCapacity).
174
175host_capacity(Hosts,HostCapacity):-
176        (foreach(boat{cap:Cap,crew:Crew},Hosts),
177         foreach(Capacity,HostCapacity) do
178            Capacity is Cap-Crew
179        ).
180
181guest_pattern(Guests,Height):-
182        (foreach(boat{crew:Crew},Guests),
183         foreach(Crew,Height) do
184            true
185        ).
186
187boat(1 , 6 , 2).
188boat(2 , 8 , 2).
189boat(3 , 12 , 2).
190boat(4 , 12 , 2).
191boat(5 , 12 , 4).
192boat(6 , 12 , 4).
193boat(7 , 12 , 4).
194boat(8 , 10 , 1).
195boat(9 , 10 , 2).
196boat(10 , 10 , 2).
197boat(11 , 10 , 2).
198boat(12 , 10 , 3).
199boat(13 , 8 , 4).
200boat(14 , 8 , 2).
201boat(15 , 8 , 3).
202boat(16 , 12 , 6).
203boat(17 , 8 , 2).
204boat(18 , 8 , 2).
205boat(19 , 8 , 4).
206boat(20 , 8 , 2).
207boat(21 , 8 , 4).
208boat(22 , 8 , 5).
209boat(23 , 7 , 4).
210boat(24 , 7 , 4).
211boat(25 , 7 , 2).
212boat(26 , 7 , 2).
213boat(27 , 7 , 4).
214boat(28 , 7 , 5).
215boat(29 , 6 , 2).
216boat(30 , 6 , 4).
217boat(31 , 6 , 2).
218boat(32 , 6 , 2).
219boat(33 , 6 , 2).
220boat(34 , 6 , 2).
221boat(35 , 6 , 2).
222boat(36 , 6 , 2).
223boat(37 , 6 , 4).
224boat(38 , 6 , 5).
225boat(39 , 9 , 7).
226boat(40 , 0 , 2).
227boat(41 , 0 , 3).
228boat(42 , 0 , 4 ).
229
230% problem 1-9  are from Symmetry breaking paper
231problem_data(1,[2,3,4,5,6,7,8,9,10,11,12,14,16]).
232problem_data(2,[3,4,5,6,7,8,9,10,11,12,13,14,16]).
233problem_data(3,[3,4,5,6,7,8,9,10,11,12,14,15,16]).
234problem_data(4,[3,4,5,6,7,8,9,10,11,12,14,16,25]).
235problem_data(5,[3,4,5,6,7,8,9,10,11,12,14,16,23]).
236problem_data(6,[3,4,5,6,7,8,9,10,11,12,15,16,25]).
237problem_data(7,[1,3,4,5,6,7,8,9,10,11,12,14,16]).
238problem_data(8,[3,4,5,6,7,8,9,10,11,12,16,25,26]).
239problem_data(9,[3,4,5,6,7,8,9,10,11,12,14,16,30]).
240% this is my favorite host selection
241problem_data(10,[1,2,3,4,5,6,7,8,9,10,11,12,14]).
242% problems 11-16 are problems 1-6 from Van Hentenryck/Michel
243problem_data(11,[1,2,3,4,5,6,7,8,9,10,11,12,16]).
244problem_data(12,[1,2,3,4,5,6,7,8,9,10,11,12,13]).
245problem_data(13,[1,3,4,5,6,7,8,9,10,11,12,13,19]).
246problem_data(14,[3,4,5,6,7,8,9,10,11,12,13,25,26]).
247problem_data(15,[1,2,3,4,5,6,7,8,9,10,11,19,21]).
248problem_data(16,[1,2,3,4,5,6,7,8,9,16,17,18,19]).
249
250problem_data(20,[3,4,5,6,7,8,9,10,11,12,16,39]).
251