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 The ECLiPSe Constraint Logic Programming System. 15% The Initial Developer of the Original Code is Cisco Systems, Inc. 16% Portions created by the Initial Developer are 17% Copyright (C) 2006 Cisco Systems, Inc. All Rights Reserved. 18% 19% Contributor(s): 20% 21% END LICENSE BLOCK 22 23%---------------------------------------------------------------------- 24\chapter{The Integer Sets Library} 25\label{icsets} 26\index{library!ic_sets|(} 27%HEVEA\cutdef[1]{section} 28%---------------------------------------------------------------------- 29 30 31%---------------------------------------------------------------------- 32\section{Why Sets} 33%---------------------------------------------------------------------- 34 35\index{finite sets} 36The {\em ic_sets} library is a solver for constraints over the domain 37of finite sets of integers. 38Modelling with sets is useful for problems where one is not 39interested in each item as a specific individual, but in a 40collection of item where no specific distinction is made and thus 41where symmetries among the element values need to be avoided. 42 43 44%---------------------------------------------------------------------- 45\section{Finite Sets of Integers} 46%---------------------------------------------------------------------- 47 48In the context of the {\em ic_sets} library, (ground) integer sets are 49simply sorted, duplicate-free lists of integers e.g. 50\begin{quote}\begin{verbatim} 51SetOfThree = [1,3,7] 52EmptySet = [] 53\end{verbatim}\end{quote} 54Lists which contain non-integers, are unsorted or contain duplicates, 55are not sets in the sense of this library. 56 57 58%---------------------------------------------------------------------- 59\section{Set Variables} 60\index{set variable} 61%---------------------------------------------------------------------- 62 63%\subsection{Declaring} 64Set variables are variables which can eventually take a ground integer 65set as their value. They are characterized by a lower bound (the set 66of elements that are definitely in the set) and an upper bound (the 67set of elements that may be in the set). A set variable can be 68declared as follows: 69\begin{quote}\begin{verbatim} 70SetVar :: []..[1,2,3,4,5,6,7] 71\end{verbatim}\end{quote} 72%If the lower bound is the empty set (like in this case) this can be written as 73%\begin{verbatim} 74% SetVar subset [1,2,3,4,5,6,7] 75%\end{verbatim} 76If the lower bound is the empty set and the upper bound is a set of 77consecutive integers, one can also declare it like 78\begin{quote}\begin{verbatim} 79intset(SetVar, 1, 7) 80\end{verbatim}\end{quote} 81which is equivalent to the above. 82\quickref{Declaring Set Variables}{ 83\begin{description} 84\item[\biptxtrefni{?Set :: ++Lwb..++Upb}{::/2!ic_sets}{../bips/lib/ic_sets/NN-2.html}] 85\index{::/2@\texttt{::/2}!ic_sets} Set is an integer set within the given bounds 86\item[\biptxtref{intset(?Set, +Min, +Max)}{intset/3}{../bips/lib/ic_sets/intset-3.html}] 87 Set is a set containing numbers between Min and Max 88\item[\biptxtref{intsets(?Sets, ?N, +Min, +Max)}{intsets/4}{../bips/lib/ic_sets/intsets-4.html}] 89 Sets is a list of N sets containing numbers between Min and Max 90\end{description} 91} 92 93The system prints set variables in a particular way, for instance: 94\begin{quote}\begin{verbatim} 95?- lib(ic_sets). 96?- X :: [2,3]..[1,2,3,4]. 97X = X{[2, 3] \/ ([] .. [1, 4]) : _308{[2 .. 4]}} 98\end{verbatim}\end{quote} 99The curly brackets contain the description of the current domain 100of the set variable in the form of 101\begin{enumerate} 102\item the lower bound of the set (values which definitely are in the set) 103\item the union symbol \verb.\/. 104\item the set of optional values (which may or may not be in the set) 105\item a colon 106\item a finite domain variable indicating the admissible cardinality for the set 107\end{enumerate} 108 109 110%---------------------------------------------------------------------- 111\section{Constraints} 112%---------------------------------------------------------------------- 113 114\index{membership constraint} 115\index{cardinality constraint} 116The constraints that {\em ic_sets} implements are the usual relations 117over sets. 118The membership (in/2, notin/2) and cardinality constraints 119(\#/2) establish 120relationships between set variables and integer variables: 121\quickref{Membership and Cardinality Constraints}{ 122\begin{description} 123\item[\biptxtrefni{?X in ?Set}{in/2!ic_sets}{../bips/lib/ic_sets/in-2.html}] 124 \index{in/2@\texttt{in/2}!ic_sets} The integer X is member of the integer set Set 125\item[\biptxtrefni{?X notin ?Set}{notin/2!ic_sets}{../bips/lib/ic_sets/notin-2.html}] 126 \index{notin/2@\texttt{notin/2}!ic_sets} The integer X is not a member of the integer set Set 127%\item[\biptxtref{membership_booleans(?Set, ?BoolArr)}{membership_booleans/2!ic_sets}{../bips/lib/ic_sets/membership_booleans-2.html}] 128% BoolArr is an array of booleans describing Set 129\item[\biptxtrefni{\#(?Set, ?Card)}{\#/2!ic_sets}{../bips/lib/ic_sets/H-2.html}] 130 \index{\#/2@\texttt{\#/2}!ic_sets} Card is the cardinality of the integer set Set 131\end{description} 132} 133\begin{quote}\begin{verbatim} 134?- X ::[]..[1, 2, 3], 2 in X, 3 in X, #(X, 2). 135X = [2, 3] 136Yes (0.01s cpu) 137 138?- X :: []..[1, 2, 3, 4], 3 in X, 4 notin X. 139X = X{[3] \/ ([] .. [1, 2]) : _2161{1 .. 3}} 140Yes (0.00s cpu) 141\end{verbatim}\end{quote} 142Possible constraints between two sets are equality, inclusion/subset 143and disjointness: 144\index{inclusion constraint} 145\index{disjointness constraint} 146\index{subset constraint} 147\begin{quote}\begin{verbatim} 148?- X subset [1, 2, 3, 4]. 149X = X{([] .. [1, 2, 3, 4]) : _2139{0 .. 4}} 150Yes (0.00s cpu) 151 152?- X :: []..[1, 2, 3, 4], Y :: []..[3, 4, 5, 6], X subset Y. 153X = X{([] .. [3, 4]) : _2176{0 .. 2}} 154Y = Y{([] .. [3, 4, 5, 6]) : _2367{0 .. 4}} 155There are 4 delayed goals. 156Yes (0.00s cpu) 157 158?- X :: [2] .. [1, 2, 3, 4], Y :: [3] .. [1, 2, 3, 4], X disjoint Y. 159X = X{[2] \/ ([] .. [1, 4]) : _2118{1 .. 3}} 160Y = Y{[3] \/ ([] .. [1, 4]) : _2213{1 .. 3}} 161There are 2 delayed goals. 162Yes (0.00s cpu) 163\end{verbatim}\end{quote} 164\quickref{Basic Set Relations}{ 165\begin{description} 166\item[\biptxtrefni{?Set1 sameset ?Set2}{sameset/2!ic_sets}{../bips/lib/ic_sets/sameset-2.html}] 167 \index{sameset/2@\texttt{sameset/2}!ic_sets} The sets Set1 and Set2 are equal 168\item[\biptxtrefni{?Set1 disjoint ?Set2}{disjoint/2!ic_sets}{../bips/lib/ic_sets/disjoint-2.html}] 169 \index{disjoint/2@\texttt{disjoint/2}!ic_sets} The integer sets Set1 and Set2 are disjoint 170\item[\biptxtrefni{?Set1 includes ?Set2}{includes/2!ic_sets}{../bips/lib/ic_sets/includes-2.html}] 171 \index{includes/2@\texttt{includes/2}!ic_sets} Set1 includes (is a superset) of the integer set Set2 172\item[\biptxtrefni{?Set1 subset ?Set2}{subset/2!ic_sets}{../bips/lib/ic_sets/subset-2.html}] 173 \index{subset/2@\texttt{subset/2}!ic_sets} Set1 is a (non-strict) subset of the integer set Set2 174\item[\biptxtrefni{intersection(?Set1, ?Set2, ?Set3)}{intersection/3!ic_sets}{../bips/lib/ic_sets/intersection-3.html}] 175 \index{intersection/3@\texttt{intersection/3}!ic_sets} Set3 is the intersection of the integer sets Set1 and Set2 176\item[\biptxtrefni{union(?Set1, ?Set2, ?Set3)}{union/3!ic_sets}{../bips/lib/ic_sets/union-3.html}] 177 \index{union/3@\texttt{union/3}!ic_sets} Set3 is the union of the integer sets Set1 and Set2 178\item[\biptxtrefni{difference(?Set1, ?Set2, ?Set3)}{difference/3!ic_sets}{../bips/lib/ic_sets/difference-3.html}] 179 Set3 is the difference of the integer sets Set1 and Set2 180\item[\biptxtrefni{symdiff(?Set1, ?Set2, ?Set3)}{symdiff/3!ic_sets}{../bips/lib/ic_sets/symdiff-3.html}] 181 \index{symdiff/3@\texttt{symdiff/3}!ic_sets} Set3 is the symmetric difference of the integer sets Set1 and Set2 182\end{description} 183} 184Possible constraints between three sets are for example 185intersection, union, difference and symmetric difference. 186For example: 187\begin{quote}\begin{verbatim} 188?- X :: [2, 3] .. [1, 2, 3, 4], 189 Y :: [3, 4] .. [3, 4, 5, 6], 190 ic_sets : intersection(X, Y, Z). 191X = X{[2, 3] \/ ([] .. [1, 4]) : _2127{2 .. 4}} 192Y = Y{[3, 4] \/ ([] .. [5, 6]) : _2222{2 .. 4}} 193Z = Z{[3] \/ ([] .. [4]) : _2302{[1, 2]}} 194There are 6 delayed goals. 195Yes (0.00s cpu) 196\end{verbatim}\end{quote} 197\Note{Note that we needed to qualify the intersection/3 constraint with 198the {\em ic_sets} module prefix because of a name conflict with a predicate from 199the {\em lists} library of the same name.} 200\Note{Note the lack of a complement constraint: this is because the complement 201of a finite set is infinite and cannot be represented. Complements can be 202modelled using an explicit universal set and a difference constraint.} 203 204\ignore{ 205\subsection{Domain Access} 206 207\begin{description} 208\item[\biptxtref{potential_members(?Set, -List)}{potential_members/2}{../bips/lib/ic_sets/potential_members-2.html}] 209 List is the list of elements of whose membership in Set is currently uncertain 210\item[\biptxtref{set_range(?Set, -Lwb, -Upb)}{set_range/3}{../bips/lib/ic_sets/set_range-3.html}] 211 Lwb and Upb are the current lower and upper bounds on Set 212\end{description} 213} 214 215Finally, there are a number of n-ary constraints that apply to lists of sets: 216disjointness, union and intersection. For example: 217\quickref{N-ary Set Relations}{ 218\begin{description} 219\item[\biptxtref{all_disjoint(+Sets)}{all_disjoint/1}{../bips/lib/ic_sets/all_disjoint-1.html}] 220 Sets is a list of integers sets which are all disjoint 221\item[\biptxtref{all_union(+Sets, ?SetUnion)}{all_union/2}{../bips/lib/ic_sets/all_union-2.html}] 222 SetUnion is the union of all the sets in the list Sets 223\item[\biptxtref{all_intersection(+Sets, ?SetIntersection)}{all_intersection/2}{../bips/lib/ic_sets/all_intersection-2.html}] 224 SetIntersection is the intersection of all the sets in the list Sets 225\end{description} 226} 227\begin{quote}\begin{verbatim} 228?- intsets(Sets, 5, 1, 5), all_intersection(Sets, Common). 229Sets = [_2079{([] .. [1, 2, 3, 4, 5]) : _2055{0 .. 5}}, ... ] 230Common = Common{([] .. [1, 2, 3, 4, 5]) : _3083{0 .. 5}} 231There are 24 delayed goals. 232Yes (0.00s cpu) 233\end{verbatim}\end{quote} 234 235 236 237%---------------------------------------------------------------------- 238%\section{Set Expressions} 239%---------------------------------------------------------------------- 240 241In most positions where a set or set variable is expected one can also 242use a set expression. A set expression is composed from ground sets 243(integer lists), set variables, and the following set operators: 244\begin{quote}\begin{verbatim} 245Set1 /\ Set2 % intersection 246Set1 \/ Set2 % union 247Set1 \ Set2 % difference 248\end{verbatim}\end{quote} 249When such set expressions occur, they are translated into auxiliary 250\bipref{intersection/3}{../bips/lib/ic_sets/intersection-3.html}, 251\bipref{union/3}{../bips/lib/ic_sets/union-3.html} and 252\bipref{difference/3}{../bips/lib/ic_sets/difference-3.html} 253constraints, respectively. 254 255 256%---------------------------------------------------------------------- 257\section{Search Support} 258%---------------------------------------------------------------------- 259 260The 261\bipref{insetdomain/4}{../bips/lib/ic_sets/insetdomain-4.html} 262predicate can be used to enumerate all ground instantiations of a set 263variable, much like 264\bipref{indomain/1}{../bips/lib/ic/indomain-1.html} 265in the finite domain case. 266Here is an example of the default enumeration strategy: 267\begin{quote}\begin{verbatim} 268?- X::[]..[1,2,3], insetdomain(X,_,_,_), writeln(X), fail. 269[1, 2, 3] 270[1, 2] 271[1, 3] 272[1] 273[2, 3] 274[2] 275[3] 276[] 277\end{verbatim}\end{quote} 278Other enumeration strategies can be selected (see the Reference Manual 279on insetdomain/4). 280 281 282%\begin{description} 283%\item[\biptxtref{insetdomain(?Set, ?CardSel, ?ElemSel, ?Order)}{insetdomain/4}{../bips/lib/ic_sets/insetdomain-4.html}] 284% Instantiate Set to a possible value 285%\end{description} 286 287 288%---------------------------------------------------------------------- 289\section{Example} 290%---------------------------------------------------------------------- 291 292\index{Steiner problem} 293The following program computes so-called Steiner triplets. 294The problem is to compute triplets of numbers between 1 and N, 295such that any two triplets have at most one element in common. 296\begin{code} 297:- lib(ic_sets). 298:- lib(ic). 299 300steiner(N, Sets) :- 301 NB is N * (N-1) // 6, % compute number of triplets 302 intsets(Sets, NB, 1, N), % initialise the set variables 303 ( foreach(S,Sets) do 304 #(S,3) % constrain their cardinality 305 ), 306 ( fromto(Sets,[S1|Ss],Ss,[]) do 307 ( foreach(S2,Ss), param(S1) do 308 #(S1 /\verb.\. S2, C), % constrain the cardinality 309 C #=< 1 % of pairwise intersections 310 ) 311 ), 312 label_sets(Sets). % search 313 314label_sets([]). 315label_sets([S|Ss]) :- 316 insetdomain(S,_,_,_), 317 label_sets(Ss). 318\end{code} 319Running this program yields the following first solution: 320\begin{quote}\begin{verbatim} 321?- steiner(9,X). 322 323X = [[1, 2, 3], [1, 4, 5], [1, 6, 7], [1, 8, 9], 324 [2, 4, 6], [2, 5, 8], [2, 7, 9], [3, 4, 9], 325 [3, 5, 7], [3, 6, 8], [4, 7, 8], [5, 6, 9]] More? (;) 326\end{verbatim}\end{quote} 327 328 329%---------------------------------------------------------------------- 330\section{Weight Constraints} 331\label{weight-constraint} 332\index{weight constraint} 333%---------------------------------------------------------------------- 334 335\index{knapsack} 336\index{bin packing} 337Another constraint between sets and integers is the weight/3 constraint. 338It allows the association of weights to set elements, and can help when 339solving problems of the knapsack or bin packing type. 340The constraint takes a set and an array of element weights and 341constrains the weight of the whole set: 342\begin{quote}\begin{verbatim} 343?- ic_sets:(Container :: [] .. [1, 2, 3, 4, 5]), 344 Weights = [](20, 34, 9, 12, 19), 345 weight(Container, Weights, W). 346Container = Container{([] .. [1, 2, 3, 4, 5]) : _2127{0 .. 5}} 347Weights = [](20, 34, 9, 12, 19) 348W = W{0 .. 94} 349There is 1 delayed goal. 350Yes (0.01s cpu) 351\end{verbatim}\end{quote} 352By adding a capacity limit and a search primitive, we can solve a 353knapsack problem: 354\begin{quote}\begin{verbatim} 355?- ic_sets:(Container :: [] .. [1, 2, 3, 4, 5]), 356 Weights = [](20, 34, 9, 12, 19), 357 weight(Container, Weights, W), 358 W #=< 50, 359 insetdomain(Container,_,_,_). 360Weights = [](20, 34, 9, 12, 19) 361W = 41 362Container = [1, 3, 4] 363More (0.00s cpu) 364\end{verbatim}\end{quote} 365 366By using the heuristic options provided by insetdomain, we can 367implement a greedy heuristic, which finds the optimal solution 368(in terms of greatest weight) straight away: 369\index{greedy heuristic} 370\begin{quote}\begin{verbatim} 371?- ic_sets:(Container :: [] .. [1, 2, 3, 4, 5]), 372 Weights = [](20, 34, 9, 12, 19), 373 weight(Container, Weights, W), 374 W #=< 50, 375 insetdomain(Container,decreasing,heavy_first(Weights),_). 376W = 48 377Container = [1, 3, 5] 378Weights = [](20, 34, 9, 12, 19) 379More (0.00s cpu) 380\end{verbatim}\end{quote} 381\quickref{Set Weight Constraint}{ 382\begin{description} 383\item[\biptxtref{weight(?Set, ++ElementWeights, ?Weight)}{weight/3}{../bips/lib/ic_sets/weight-3.html}] 384 According to the array of element weights, the weight of set Set1 is Weight 385\end{description} 386} 387 388 389\section{Exercises} 390 391\begin{enumerate} 392 393\item 394 395Consider the knapsack problem in section~\ref{weight-constraint}. 396Suppose that the items each have an associated profit, namely 17, 38, 18, 10 397and 5, respectively. Which items should be included to maximise profit? 398 399 400\item 401 402Write a predicate which, given a list of sizes of items and a list of 403capacities of buckets, returns a list of (ground) sets indicating which 404items should go into each bucket. Obviously each item should go into 405exactly one bucket. 406 407Try it out with 5 items of sizes 20, 34, 9, 12 and 19, into 3 buckets of 408sizes 60, 20 and 20. 409 410\end{enumerate} 411 412\index{library!ic_sets|)} 413 414%HEVEA\cutend 415