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