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