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{An Overview of the Constraint Libraries} 25%HEVEA\cutdef[1]{section} 26%---------------------------------------------------------------------- 27 28%---------------------------------------------------------------------- 29\section{Introduction} 30%---------------------------------------------------------------------- 31In this section we shall briefly summarize the constraint solving 32libraries of \eclipse which will be discussed in the rest of this tutorial. 33%No examples are given here - each solver has its own documentation 34%with examples for the interested reader. 35 36 37%---------------------------------------------------------------------- 38\section{Implementations of Domains and Constraints} 39%---------------------------------------------------------------------- 40 41\subsection{Suspended Goals: {\em suspend}} 42\index{suspend} 43\label{shortsecsuspend} 44The constraint solvers of { \eclipse } are all implemented using suspended 45goals. 46The simplest implementation of any constraint is to suspend it 47until all its variables are sufficiently instantiated, and then test it. 48 49The {\em suspend} solver implements this behaviour for all 50the mathematical constraints of { \eclipse }, 51$>=$, $>$, $=:=$, =\bsl=, $=<$ and $<$. 52 53 54\subsection{Interval Solver: {\em ic}} 55\index{ic} 56\label{shortsecic} 57The standard constraint solver offered by most constraint programming 58systems is the {\em finite domain} solver, which applies constraint 59propagation techniques developed in the AI community \cite{VanHentenryck}. 60{ \eclipse } supports finite domain constraints via the {\em ic} 61library\footnote{and the {\em fd} library which will not be addressed in this tutorial}. 62The library implements finite domains of integers, together with a basic 63set of constraints. 64 65In addition, {\em ic} also allows {\em continuous domains} 66(in the form of numeric intervals), and constraints 67(equations and inequations) between expressions involving 68variables with continuous domains. 69These expressions can contain non-linear functions such as $sin$ and built-in 70constants such as $pi$. 71%The user can also specify any piecewise linear unary function and {\em ic} 72%will apply interval reasoning on that. 73Integrality is treated as a constraint, and it is possible to mix 74continuous and integral variables in the same constraint. 75Specialised search techniques 76({\em splitting} \cite{VanHentenryck:95} and {\em squashing} 77\cite{lhomme96boosting}) support 78the solving of problems with continuous variables. 79 80Most constraints are also available in reified form, providing 81a convenient way of combining several primitive constraints. 82 83Note that the {\em ic} library itself implements only a standard, 84basic set of arithmetic constraints. 85Many more finite domain 86constraints can be defined, which have uses in specific applications. 87The behaviour of these constraints is to prune the finite domains of 88their variables, in just the same way as the standard constraints. 89\eclipse{} offers several further libraries which implement such 90constraints using the underlying domain of the {\em ic} library. 91 92 93\subsection{Global Constraints: {\em ic\_global}} 94\index{ic_global} 95\label{shortsecglobal} 96\label{secglobalcstr} 97One such library is {\em ic\_global}. 98It supports a variety of constraints, each of which takes as an argument 99a list of finite domain variables, of unspecified length. 100Such constraints are called ``global'' constraints \cite{beldiceanu}. 101Examples of such constraints, available from the {\em ic\_global} library 102are 103\verb0alldifferent/10, \verb0maxlist/20, \verb0occurrences/30 and 104\verb0sorted/20. 105For more details see section \ref{secglobal} in chapter \ref{chapicintro}. 106 107 108\subsection{Scheduling Constraints: {\em ic_cumulative, ic_edge_finder}} 109\index{cumulative} 110\index{edge_finder} 111\label{shortsecsched} 112There are several { \eclipse } libraries implementing global constraints for 113scheduling applications. 114The constraints take a list 115of tasks (start times, durations and resource needs), and a maximum 116resource level. They reduce the finite domains of the task start times 117by reasoning on resource bottlenecks \cite{lepape}. Three { \eclipse } libraries 118implementing scheduling constraints are 119{\em ic_cumulative}, {\em ic_edge\_finder} and {\em ic_edge\_finder3}. 120They implement the same constraints declaratively, but with 121different time complexity and strength of propagation. 122For more details see the library documentation in the Reference Manual. 123 124 125 126\subsection{Finite Integer Sets: {\em ic_sets}} 127\index{ic_sets} 128\label{shortsecsets} 129The {\em ic_sets} library 130implements constraints over the domain of finite 131sets of integers\footnote{ 132the other set solvers lib(conjunto) and lib(fd_sets) are similar but not 133addressed in this tutorial}. 134The constraints are the usual relations over sets, 135e.g.\ membership, inclusion, intersection, union, disjointness. 136In addition, there are constraints between sets and integers, e.g.\ 137cardinality and weight constraints. For those, the {\em ic_sets} library 138cooperates with the {\em ic} library. 139For more details see chapter \ref{icsets}. 140 141 142 143 144\subsection{Linear Constraints: {\em eplex}} 145\index{eplex} 146\label{shortseceplex} 147{\em eplex} supports a tight integration \cite{Bockmayr} between an 148external linear programming (LP) / mixed integer programming (MIP) 149solver (XPRESS \cite{Dash} or CPLEX \cite{ILOG}) and { \eclipse }. 150Constraints as well as variables can be handled by the external LP/MIP 151solver, by a propagation solver like {\em ic}, or by both. 152Optimal solutions and other solution porperties can be returned to 153\eclipse{} as required. 154Search can be carried out either in \eclipse{} or in the external solver. 155For more details see chapter \ref{chapeplex}. 156 157 158 159\subsection{Constraints over symbols: {\em ic\_symbolic}} 160\index{ic_symbolic} 161\label{shortsecsymbolic} 162The {\em ic\_symbolic} library supports variables ranging over ordered 163symbolic domains (e.g. the names of products, the names of the weekdays), 164and constraints over such variables. It is implemented by mapping such 165variables and constraints to variables over integers and {\em ic}-constraints. 166 167 168%---------------------------------------------------------------------- 169\section{User-Defined Constraints} 170%---------------------------------------------------------------------- 171\subsection{Generalised Propagation: {\em propia}} 172\index{propia} 173\label{shortsecpropia} 174The predicate {\em infers} takes as one argument 175any user-defined predicate, and as a second argument a form of 176propagation to be applied to that predicate. 177 178This functionality enables the user to turn any predicate into a 179constraint \cite{LeProvost93b}. The forms of propagation include finite 180domains and intervals. 181For more details see chapter \ref{chappropiachr}. 182 183\subsection{Constraint Handling Rules: {\em ech}} 184\index{ech} 185\index{chr} 186\label{shortsecech} 187The user can also specify predicates using rules with guards 188\cite{Fruehwirth}. 189They delay until the guard is entailed or disentailed, and then 190execute or terminate accordingly. 191 192This functionality enables the user to implement constraints in a way 193that is clearer than directly using the underlying {\em suspend} 194library. 195For more details see chapter \ref{chappropiachr}. 196 197 198%---------------------------------------------------------------------- 199\section{Search and Optimisation Support} 200%---------------------------------------------------------------------- 201 202\subsection{Tree Search Methods: {\em ic_search}} 203\index{ic_search} 204\label{shortsecsearch} 205\eclipse{} has built-in backtracking and is therefore well suited for 206performing depth-first tree search. 207With combinatorial problems, naive depth-first search is usually not 208good enough, even in the presence of constraint propagation. 209It is usually necessary to apply heuristics, and if the problems are 210large, one may even need to resort to incomplete search. 211The {\em ic_search} contains a collection of predefined, easy-to-use 212search heuristics as well as incomplete tree search strategies, applicable 213to problems involving {\em ic} variables. 214For more details see chapter \ref{chapsearch}. 215 216 217\subsection{Optimisation: {\em branch_and_bound}} 218\index{branch_and_bound} 219\label{shortsecbb} 220Solvers that are based on constraint propagation are typically only 221concerned with satisfiability, i.e.\ with finding some or all solutions 222to a problems. 223The branch-and-bound method is a general technique to build optimisation 224on top of a satisfiability solver. 225The \eclipse{} {\em branch_and_bound} library is a solver-independent 226implementation of the branch-and-bound method, and provides a number 227of options and variants of the basic technique. 228 229 230%---------------------------------------------------------------------- 231\section{Hybridisation Support} 232%---------------------------------------------------------------------- 233\subsection{Repair and Local Search: {\em repair}} 234\index{repair} 235\label{shortsecrepair} 236The {\em repair} library allows a {\em tentative} value to be 237associated with any variable \cite{cp99wkshoptalk}. 238This tentative value may violate constraints on the variable, in which 239case the constraint is recorded in a list of violated constraints. 240The repair library also supports propagation {\em invariants} 241\cite{Localizer}. 242Using invariants, if a variable's tentative 243value is changed, the consequences of this change can be propagated to 244any variables whose tentative values depend on the changed one. 245The use of tentative values in search is illustrated in chapter \ref{chaprepair}. 246 247 248\subsection{Hybrid: {\em ic\_probing\_for\_scheduling}} 249\index{probing_for_scheduling} 250\label{shortsecprobing} 251For scheduling applications where the cost is dependent on each start 252time, a combination of solvers can be very powerful. 253For example, we can use finite domain 254propagation to reason on 255resources and linear constraint solving to reason on cost \cite{HaniProbe}. 256The {\em probing\_for\_scheduling} library supports such a combination, 257via a similar user interface to the {\em cumulative} constraint mentioned 258above in section \ref{secglobalcstr}. 259For more details see chapter \ref{chaphybrid}. 260 261 262%---------------------------------------------------------------------- 263\section{Other Libraries} 264%---------------------------------------------------------------------- 265The solvers described above are just a few of the many libraries 266available in ECLiPSe and listed in the \eclipse{} library directory. 267Any \eclipse{} user who has implemented a constraint solver is 268encouraged to make it available to the user community and publicise 269it via the {\tt eclipse-users@icparc.ic.ac.uk} mailing list! 270Comments and suggestions on the existing libraries are also welcome! 271 272 273%\bibliographystyle{alpha} 274%\bibliography{solver_intro} 275 276%\end{document} 277 278%HEVEA\cutend 279