`
`r so
`
`timizati
`
`s
`
`Gdrard Verfaillie and Michel Lemaitre
`CERT/ONERA
`2 av. Edouard Belin, BP 4025
`3 1055 Toulouse Cedex, France
`{ verfaillie,
`lemaitre}@cert.fr
`
`INRA
`Chemin de Borde Rouge, Auzeville, BP 27
`3 1326 Castanet Tolosan Cedex, France
`tschiex@toulouse.inra.fr
`
`Abstract
`If the Constraint Satisfaction framework has been extended
`to deal with Constraint Optimization problems, it appears
`that optimization is far more complex than satisfaction. One
`of the causes of the inefficiency of complete tree search
`methods, like Depth First Branch and Bound, lies in the poor
`quality of the lower bound on the global valuation of a partial
`assignment, even when using Forward Checking techniques.
`In this paper, we introduce the Russian Doll Search algorithm
`which replaces one search by n successive searches on nested
`subproblems (n being the number of problem variables),
`records the results of each search and uses them later, when
`solving larger subproblems, in order to improve the lower
`bound on the global valuation of any partial assignment.
`On small random problems and on large real scheduling
`problems, this algorithm yields surprisingly good results,
`which greatly improve as the problems get more constrained
`and the bandwidth of the used variable ordering diminishes.
`
`The Constraint Satisfaction framework
`is now
`(CSP)
`and solve numerous Artificial
`widely used
`to represent
`Intelligence problems
`(planning,
`scheduling,
`diagnosis,
`design.
`. . ). But it appears that most problems are combi-
`nations of imperative requirements, user preferences and
`uncertainties. They are not pure constraint
`satisfaction
`problems, but constraint satisfaction and optimization prob-
`lems : some constraints have strictly
`to be met, the others
`have preferably
`to be met.
`In order to take these aspects into account, several exten-
`sions of the classical framework have been proposed: possi-
`biZistic,fuzzy, additive, probabilistic . . . CSP. In (Bistarelli,
`Montanari, & Rossi 1995) and (Schiex, Fargier, & Verfaillie
`1995), two general algebraic frameworks,
`that cover most of
`these extensions, have been proposed. We will use the sec-
`ond of these, the so-called Valued Constraint Satisfaction
`Problems framework
`(VCSP), as a basis for our work.
`Depth First Branch and Bound, which aims at finding a
`provenly optimal
`solution,
`is the natural extension of the
`Backtrack algorithm
`in this framework.
`It is well known
`that the quality of the bound used by this kind of algorithm
`is crucial:
`the better the bound,
`the smaller
`the search tree.
`As shown in (Schiex, Fargier, & Verfaillie 1995), if Back-
`ward and Forward Checking are easily extended
`to provide
`in the VCSP framework,
`bounds
`it is much more difficult
`with Arc Consistency. Furthermore,
`if the bound provided
`
`by Forward Checking is better
`than the one provided by
`Backward Checking, it still remains
`too optimistic,
`espe-
`cially at the beginning of the search, when few variables are
`the Depth First Branch and
`assigned. As a consequence,
`Bound algorithm may explore huge subtrees which do not
`contain any complete assignment better than the best found
`so far.
`on small random VCSPs show that opti-
`Experiments
`mization
`is much more difficult
`than satisfaction:
`unlike
`in the classical CSP framework,
`complexity
`does not de-
`crease beyond
`the frontier between consistent
`and incon-
`sistent problems; worse, this frontier defines the beginning
`of a continuous
`and steep increase
`in complexity,
`as graph
`connectivity
`or constraint
`tightness
`increases. These results
`are confirmed by experiments on large real problems. Even
`when satisfaction
`can easily be decided, optimization
`on
`the same problems
`is often out of reach within a reasonable
`time.
`The idea of the Russian Doll Search is to replace one
`search by n successive
`searches on nested subproblems,
`where n is the number of variables
`in the problem:
`given
`an ordering of the problem variables,
`the first subproblem
`involves
`the last variable only, the ith subproblem
`involves
`from the n -
`all the variables
`i + lth variable
`to the last,
`and the nth subproblem
`is the whole problem. At first sight,
`replacing one search by n searches using
`the same Depth
`First Branch and Bound algorithm may seem counterpro-
`ductive. But the key to the efficiency of this method
`lies
`in the recording,
`for each subproblem,
`of the quality of an
`optimal assignment,
`and the ability, when the same static
`variable ordering
`is used, to use this information
`to improve
`the bound provided by Forward Checking. This improve-
`ment, which is particularly
`noticeable
`at the beginning
`of
`the search, allows the search tree to be pruned much earlier.
`Each search being much shorter, the sum of the costs of the
`n searches
`is often better than the cost of a classical Depth
`First Branch and Bound, even if the latter can benefit from
`a dynamic variable ordering.
`to the VCSP framework,
`After an introduction
`to the
`Branch and Bound algorithms,
`and to the various existing
`the Russian Doll algorithm
`bounds, we describe
`in detail.
`Then we consider some related algorithms and theoretical
`results. Finally, we present some experimental
`results ob-
`
`Constraint Satisfaction
`
`181
`
`Page 1 of 7
`
`Elekta Exhibit 1055
`
`
`
`tained on small random problems and on large real schedul-
`ing problems.
`
`Valued Constraint Satisfaction Problems
`As a classical CSP is defined as a pair P =
`(V, C),
`where V is a set of variables
`and C a set of constraints,
`a VCSP (Schiex, Fargier, & Verfaillie 1995) can be defined
`as a quadruple P = (V, C, S, cp), where:
`V is a set of variables;
`C is a set of constraints;
`is a quintuple
`itself
`S is a valuation
`structure, which
`(E, +‘, I, T, @), where E is a set, + is a total order on
`in E, T is the maximum
`E, I
`is the minimum
`element
`in E and @ is a binary closed operation on E,
`element
`which satisfies the following properties:
`commutativity,
`associativity, monotonicity
`according
`to +, I as identity
`and T as absorbing element;
`from C to E.
`cp is an application
`The set E is used to define a gradual notion of constraint
`The elements of E, so-called
`violation and inconsistency.
`valuations, can be compared using
`the total order + and
`combined using the operation 8. The minimum
`element
`I
`is used to express constraint
`satisfaction
`and consistency,
`the maximum element T is used to express imperative con-
`straint violation and complete
`inconsistency.
`The applica-
`tion cp assigns a valuation
`to each constraint. This valuation
`to T in
`expresses
`the importance of the constraint
`(equal
`case of imperative constraint).
`and C&l (A) be the set
`Let A be a complete assignment
`of the constraints violated by A. The valuation q(A) of A
`is the combination
`of the valuations of all the constraints
`in
`Giol (A):
`
`is then to find a complete assignment
`The standard objective
`of minimum valuation. The valuation q(P) of a problem
`P is the valuation of such an assignment.
`Let A be a partial assignment.
`is
`Its global valuation
`the minimum
`valuation obtainable by extending
`it on the
`unassigned
`variables or, in other words,
`the valuation of
`the problem P restricted by the partial assignment A. The
`valuation of a problem P is the global valuation of the empty
`assignment.
`such as classical CSP, possibilis-
`Specific frameworks,
`tic CSP, additive CSP, probabilistic CSP, lexicographic
`CSP. . . can be produced by instantiating
`the valuation struc-
`ture S. For example,
`in additive CSP, E is the set of the
`natural
`integers, enlarged with a special element +oo, + is
`0, T = +OCI and @
`the natural order > on integers,
`I=
`the usual addition + (> and + being extended
`in order to
`the special element +cm). Partial CSP,
`take into account
`studied in (Freuder & Wallace 1992), is a particular case of
`additive CSP, where all the constraints
`are non imperative
`and have the same valuation
`(equal to 1).
`
`182
`
`Constraint Satisfaction
`
`Branch and Bound methods
`Backtrack is the usual algorithm
`to find a complete con-
`in the classical CSP framework. Depth
`sistent assignment
`First Branch and Bound, described
`in algorithm 1, is its nat-
`ural extension
`to find a complete assignment
`of minimum
`in the VCSP framework.
`valuation
`
`function DFBB(Zb;,it, ubinit, LOWER-BOUND)
`return DFBBI(lbi,it, ub;,it, 0, LOWER-BOUND)
`
`function DFBBI(Zb;,;t, ubinit, i, LOWER-BOUND)
`The problem to solve includes the variables in Ii. .n].
`i =
`0 with the usual DFBB algorithm.
`0 5
`i 5 n - 1 with
`the RDS algorithm (see algorithm 2). An assignment A of
`the problem variables, of minimum valuation p(A),
`such that
`is sought.
`If such an assignment
`lbinit 5 p(A) + ubinit,
`exists, it is recorded and its valuation is returned; otherwise,
`failure is returned. For clarity’s sake, it is assumed that all
`the variables have d values and that static variable and value
`orderings are used. LOWER-BOW is a functional parameter
`which determines the way of computing a lower bound Zb on
`the global valuation of a partial assignment. It is equal to LB1
`or LB2 with the usual DFBB algorithm (see Equations 1 and 2)
`or to LB3 with the RDS algorithm (see Equation 4). ];..w] is the
`set of assigned variables. v is the current variable. ub is the
`valuation of the best assignment of the problem variables found
`so far.
`lb, ub, v, success
`search-depth :
`xv = n {a better complete assignment has been found} then
`success, ub t
`true, lb {the upper bound ub is updated}
`record the current assignment A
`if Zbinit 4 ub then go search-width else go end-search
`
`t
`
`I, ubinit, i, false
`
`1
`else
`
`1
`
`A[w t 2, + l] f- 0
`go search-width
`
`search-width :
`if A[v] = d {all the domain values have been tried} then
`1 {a backtrack occurs}
`V+-V-
`if v=i then go end-search else go search-width
`
`1
`else
`
`1
`
`A[v] t A[v] + 1
`i, v)
`Zb +-LOWER-BoUm(A,
`if Zb + ub then go search-depth else go search-width
`
`end-search :
`if success then return ub else return failure
`
`Algorithm 1: Depth First Branch and Bound
`
`Let us assume that any complete assignment, whose val-
`to ubinit, is unacceptable
`uation
`is higher
`than or equal
`and that it is known,
`for any reason,
`that there is no com-
`is lower than Zbinit. The
`plete assignment, whose valuation
`is to find a complete assignment A, of minimum
`problem
`valuation q(A),
`such that Zbinit 5 v(A) 4 ubinit. By
`default, Zbinit = I and ubinit = T.
`for a complete
`At any moment,
`the algorithm
`searches
`assignment whose valuation
`is lower than a current upper
`
`Page 2 of 7
`
`
`
`bound ub. This upper bound
`is initialized with the value
`ubinit and decreases during the search: each time a complete
`is lower than ub, is found,
`assignment, whose valuation
`its
`valuation
`is used as a new upper bound.
`a lower bound lb on the global valuation of
`It maintains
`the current partial assignment A, and backtracks each time
`ub -: lb, since there then exists no complete extension of A
`is lower than ub.
`whose valuation
`is
`It ends when a complete assignment, whose valuation
`equal to Zbinit, is found or when no complete assignment
`is lower than ub could be found.
`.
`whose valuation
`There are three main ways of improving
`this algorithm:
`(1) to choose an adequate variable ordering to reduce the tree
`the lower bound Zb; (2) to choose
`size or to rapidly
`increase
`an adequate value ordering
`to rapidly
`find good complete
`and therefore decrease the upper bound ub; (3)
`assignments
`to compute a high lower bound (function LOWER-BOUND)
`on the valuation of any partial assignment,
`to cut earlier
`branches. Russian Doll Search uses this last
`unproductive
`way to improve Depth First Branch and Bound.
`
`Partial Assignment Valuation
`Backward Checking is the simplest way of bounding
`the
`global valuation of a partial assignment A, by only taking
`the constraints which are assigned’ by A. Let
`into account
`Cass-viOl (A) be the set of constraints assigned and violated
`by A. We obtain
`the bound LB 1 (A), also called the local
`valuation of A:
`
`LB@)
`
`= LBb,(A)
`
`=
`
`cpw
`
`(1)
`
`($9
`cECa,s-viol(A)
`Forward Checking is an attempt to improve
`this bound, by
`taking into account the constraints which are quasi-assigned
`by A i.e., such that only one variable
`is unassigned.
`Let
`V’(A) be the set of the variables which are not assigned by
`A. If v is an element of V’(A), let d(v) be its domain.
`If
`let Cqasssviol (A, v, val) be the
`val is an element of d(v),
`set of the constraints which are not completely assigned by
`A but assigned and violated by A u {(v, val)}. We obtain
`the bound LB~ (A):
`
`Lb(A) = Lb,(A) @Lqc(A)
`(2)
`LBjc(A) =
`0
`[ min ALBb,(A,w,val)]
`vEV'(A)valEd(v)
`@
`cp(c>
`cECQ(LSS--V,O~(A1~.~a~)
`
`ALBbc(A,v,val) =
`
`where ALBUM (A, v, val)
`in local valuation
`is the increase
`which would result from the assignment of the value vul to
`the variable v.
`Since, for each A, LB1 (A) li\ LBZ (A), Forward Check-
`ing provides a better bound
`than Backward Checking and
`yields more pruning. Moreover, even when no backtrack
`(LB~(A) + ub), values can be safely removed
`is possible
`from the domains of the unassigned variables. Let v be an
`unassigned variable and vul be one of its values. This value
`can be removed
`if:
`‘A constraint is assigned iff all its variables are assigned.
`
`LBbc(A) @ ALBbc(A,val)
`
`k
`
`ub
`
`But Forward Checking remains
`espe-
`too optimistic,
`cially at the beginning
`of the search,
`since
`it does not
`take
`into account
`constraints
`between unassigned
`vari-
`In the CSP framework, Arc Consistency embed-
`ables.
`ded in a Backtrack algorithm
`(Haralick & Elliot 1980;
`Sabin & Freuder 1994) does so. But, as it has been shown,
`in (Bistarelli, Montanari, & Rossi 1995) and
`(Schiex,
`it to the VCSP frame-
`Fargier, & Verfaillie 1993, extending
`work is difficult, at least with a strictly monotonic operation
`(additive, lexicographic orprobabilistic CSP), since the cor-
`responding problem becomes NP-complete. Directed Arc
`Consistency Counts (Wallace 1994) are a way of taking into
`account constraints between unassigned variables. Russian
`Doll Search can be seen as another simple, but powerful,
`way of doing so.
`
`The Russian Doll Search, described
`in algorithm 2, assumes
`It performs n successive searches
`a static variable ordering.
`on nested subproblems
`as russian dolls2, where n is the
`number of variables
`in the problem. The first subproblem
`only involves
`the last variable,
`the ith subproblem
`involves
`all the variables
`from the n -
`i + 1 th variable and the nth
`subproblem
`is the whole problem.
`Each search uses the
`Depth First Branch and Bound algorithm described
`in Al-
`gorithm 1, with the same static variable ordering. The global
`result
`is obtained with the last search, but the optimal as-
`signments of all the solved subproblems,
`along with their
`valuation, are systematically
`recorded in order to help future
`searches.
`
`function RDS(ubi,it)
`The problem to solve includes n variables. An assignment A
`of the probiem variables, of minimum valuation p(A),
`such
`+ ub init, is sought. If such an assignment exists,
`that v(A)
`its valuation is returned; otherwise, failure is returned. T-CL+]
`is the valuation of the subproblem limited to the variables in
`]i..n].
`rds[n] tl
`foreach i from n - 1 downto 0 do
`Zb’ + rds[i + l]
`ub’ t UPPER-BOUND(ubi,;t,
`ub t DFBBr(lb’, ub’, i,LB3)
`if ub # failure then ~ds[i] tub
`I
`return ub
`
`else return failure
`
`lb’, ;)
`
`Algorithm 2: Russian Doll Search
`
`First, each search can use the valuation of the previous
`subproblem
`to bound
`the valuation of the current-one:
`let
`
`2We could also have called this method Chinese Box Search.
`
`Constraint Satisfaction
`
`183
`
`Page 3 of 7
`
`
`
`and P” be the current one
`P’ be the previous
`subproblem
`(P’ c PI’); let cp (P’) and ‘p( P”) be their valuations and C’
`that appear in P”, but not in P’,
`be the set of the constraints
`it is obvious
`that:
`
`is used in the function UPPER-BOUND to
`This inequation
`give a better value of the initial upper-bound ubinit.
`Each search can also use the optimal assignment produced
`by the previous
`search as a value heuristic
`for the current
`search:
`for each variable,
`try first the value
`it had in this
`previously optimal assignment.
`since each search uses the
`Finally, and most importantly,
`same static order, it can use the valuations of all the previous
`subproblems
`to improve
`the bound on the global valuation
`of any partial assignment A. Let P’(A) be the subproblem
`to the variables which are not assigned by A and
`limited
`p(P’(A))
`its previously
`recorded valuation3. We obtain
`the new bound I&(A):
`
`(4)
`
`LB3 (A) = L&c(A) @L+(A) @Lki,(A)
`W-c@)
`=
`dP’(4)
`that LB3 (A) is a lower bound on the valu-
`To be convinced
`ation of any partial assignment A, it is sufficient
`to observe
`that the subsets of constraints
`taken
`into account by each
`(LBbC, LBfc and LB,&
`are dis-
`of its three components
`junct (provided
`there is no unary constraint)
`and that each
`component
`is itself a lower bound on the best valuation of
`the corresponding
`subset of constraints,
`for all the possible
`complete extensions of A.
`In the particular case of binary CSPs, Figure 1 shows how
`constraints
`contribute
`to each component of the bound.
`In
`this case, we obtain a partition of the set of the problem
`In the general case of n-ary
`constraints
`in three subsets.
`CSPs, constraints which
`involve assigned and unassigned
`variables, but are not quasi-assigned,
`are still ignored by the
`bound LB3.
`for each A, LBl(A) 5 LBz(A) 5 LB3(A), the
`Since,
`bound provided by the Russian Doll Search is better than the
`bound provided by Forward Checking or Backward Check-
`ing. This improvement
`should be all the more dramatic as
`P’(A) is large i.e., at the beginning of the search, when the
`bound provided by Forward Checking or Backward Check-
`ing is very poor. Let us also note that, when no backtrack
`is possible,
`the component LB,.&A)
`can also be added to
`LBbc (A) in Equation 3 in order to remove more values from
`the domains of the unassigned variables.
`
`elated algorithms and theoretical results
`the Russian Doll Search
`Let us note a similarity between
`method and Dynamic Programming. Like Dynamic Pro-
`gramming, Russian Doll Search solves subproblems
`in or-
`But, whereas Dynamic
`der to solve the whole problem.
`
`31n algorithms 1 and 2, A is the assignment of the variables in
`is the subproblem limited to the variables in ]w..n]
`]i..w], P’(A)
`and (p(P’(A)) = ~ds[v].
`
`184
`
`Constraint Satisfaction
`
`-A-
`
`2
`
`-
`
`P’(A) -
`
`Figure 1: Constraints taken into account by each compo-
`(1) Backward Checking, (2) Forward
`nent of the bound:
`Checking, (3) Russian Doll Search (previous search)
`
`Programming directly combines
`the results obtained on sub-
`to get the result of the whole problem, Russian
`problems
`Doll Search only uses them as bounds during
`its search.
`is imposed on the constraint graph
`Note that if no constraint
`structure), Dynamic
`structure
`(such as a tree or hyper-tree
`space to solve VC-
`Programming would need exponential
`SPS.
`the Russian Doll
`Let us also note a similarity between
`Search method and the Depth First Iterative Deepening al-
`gorithms (Korf 1985). As with Depth First Iterative Deep-
`ening, search is performed at increasing depth. But the main
`is the use, with the Russian Doll Search, of the re-
`difference
`sults of the previous
`iterations
`in order to improve
`the lower
`bound on the global valuation of any partial assignment.
`It is moreover easy to recover a traditional
`result of the
`Zterative Deepening algorithms:
`since, on a problem
`in-
`volving n variables and d values per variable, a Depth First
`in the worst case dn ter-
`Branch and Bound search examines
`minal nodes, the n successive
`searches of the Russian Doll
`in the worst case N = d + d2 + . . . + d”
`Search examine
`if d > 1,O < $ < 1 and we have:
`terminal nodes;
`
`< d”
`
`= d”
`
`. &
`
`= d”
`
`d
`. d _ 1
`
`+O” 1
`’ 1
`. x(--)’
`N = d” - k(-$
`iso
`i=o
`terminal nodes,
`the number of examined
`The ratio between
`in the worst cases, by the Russian Doll Search and the usual
`Depth First Branch and Bound is then
`less than
`-&,
`a
`number which is itself less than or equal to 2 and decreases
`as d increases.
`on
`in experiments
`In practice and as it can be observed
`the
`random and real problems
`(see the two next sections),
`iterations of the Russian Doll
`synergy between successive
`Search, and mainly
`the improvement
`of the lower bound
`on the global valuation of a partial assignment,
`can rapidly
`offset this unfavourable
`ratio.
`let us con-
`this phenomenon,
`In order to better understand
`two partial binary CSPs, denoted
`sider two extreme cases:
`by L,,
`and Ptight, each of them involving n variables, d
`values per variable and e = n(n - 1) /2 constraints
`(com-
`plete constraint graph); whereas each constraint of Ploo,,
`allows all the possible pairs of values, each constraint of
`of Pl,,,,
`the valuations
`and
`fright allows none of them;
`Ptight are respectively
`equal to 0 and e.
`the usual Depth First Branch and Bound
`With &ose,
`only examines one terminal node, whereas the Russian Doll
`Search examines n. The ratio is equal to n on behalf of the
`former.
`
`Page 4 of 7
`
`
`
`with Ptight , the usual Depth First Branch and Bound ex-
`amines dn terminal nodes with the lower bound LB1 (Back-
`ward Checking) and still d”-l with the lower bound LB2
`(Forward Checking).
`Since,
`in this case, LB3 provides
`the Russian Doll Search with the exact global valuation
`the Russian Doll
`e of each assignment of the first variable,
`Search examines nd terminal nodes. The ratio is now equal
`to nldny2 on behalf of the latter.
`These examples
`show that, if the Russian DoZZ Search
`may be more expensive
`in some cases, it may bring expo-
`nential savings
`in other cases.
`
`andody Generated
`on
`We first present
`results which have been obtained
`random partial CSPs. These problems have
`small binary
`been randomly generated according
`to the model described
`in (Smith 1994), slightly modified
`in order to produce prob-
`lems of limited bandwidth. Let us recall that the four pa-
`rameters of this model are n (the number of variables), d
`(the domain size, equal for all the variables),
`c (the graph
`connectivity)
`and t (the constraint
`tightness,
`equal for all
`the constraints).
`Let us also recall that the bandwidth of a graph (Zabih
`1990) is the minimum
`bandwidth
`on all its possible ver-
`tex orderings and that the bandwidth of an ordering
`is the
`maximum distance, according
`to this ordering, between
`two
`connected vertices. Computing
`the bandwidth of a graph is
`an N P-complete problem.
`The method we chose for generating CsPs of limited
`bandwidth b was as follows: given n, d, c, t and b, let 0
`be a variable ordering;
`let S be the set of all the pairs of
`variables, which are separated by a distance
`lower than or
`to 0; randomly select c.n(n- 1) /2 pairs
`equal to b according
`of variables
`in S and randomly generate a binary constraint
`of tigthness
`t for each selected pair.
`This method guarantees
`that the bandwidth of the order-
`ing 0, and therefore
`the graph bandwidth,
`is lower
`than
`or equal to b. Let us note that not all the combinations
`of
`n, c and b are allowed:
`a small bandwidth
`implies a small
`relation holds between n,
`connectivity
`since the following
`a md b: (n-- b)(n - b - 1) < n(n - l)(l
`- c).
`We compare
`two algorithms:
`a Depth First Branch and Bound (bb), using
`the lower
`bound LB2 on the global valuation of a partial assignment
`defined in Equation 2 and the following dynamic variable
`and value orderings:
`- given the generation variable ordering, among the vari-
`ables of minimum current domain size, choose the first
`variable of maximum degree;
`if A is the partial current assignment and v the variable
`to be assigned, choose the first value which minimizes
`ALBUM (A, v, val) i.e., the value which yields the small-
`est increase
`in local valuation
`of the current partial
`assignment;
`a Russian Doll Search (rds), using the lower bound LB3
`on the global valuation of a partial assignment
`defined
`
`-
`
`in Equation 4, the static generation variable
`the following dynamic value ordering:
`
`ordering
`
`the variable had in the optimal
`the value
`- first choose
`found on the previous
`subproblem,
`then
`assignment
`use the same heuristics as with the Depth First Branch
`and Bound algorithm.
`the most efficient
`These orderings
`are,
`in each case,
`have been writ-
`Algorithms
`of those we experimented.
`ten in Common Lisp and tests have been performed with
`on a Spare 5 workstation with
`the CMUCL implementation
`32Mb of memory.
`In order to get a first global view of the relative effi-
`ciency of bb and rds, we carried out preliminary
`exper-
`iments with n = 20, d = 5, c = 0.1,0.3,0.5,0.7,0.9,
`t = 0.1,0.3,0.5,0.7,0.9,
`b = 4,10,16,
`and 20 randomly
`generated problems
`for each combination
`of c, t and b. In
`Figure 2, we point, using a plus sign, at the combinations
`of c, t and b for which rds is better than bb, in terms of the
`number of problems more rapidly solved.
`
`t +
`u
`
`c-l
`
`0.1
`
`0.3
`
`0.5
`
`0.7
`
`0.9
`
`0.7
`
`0.9
`
`10
`16
`16
`
`-
`-
`-
`
`-
`-
`-
`
`+
`+
`+
`
`+
`+
`+
`
`+
`+
`+
`
`Figure 2: A global view of the areas where the Russian Doll
`Search is more eficient than the usual Depth First Branch
`and Bound
`
`than bb on the most
`It. appears that rds is more efficient
`inconsistent
`problems
`(great values of c and t), which are
`also the hardest
`to solve.
`It also appears
`that graph band-
`width is important,
`since, for a given combination
`of c and
`t, rds may be more efficient than bb with only a small value
`of b.
`degree
`In order to judge the influence of the inconsistency
`of the problem on the relative efficiency of bb and rds,
`we carried out more systematic experiments with n = 20,
`d = 5, c = 0.7, b = 10, t varying
`from 0.1 to 0.9 in steps
`of 0.1, 100 randomly generated problems
`for each value of
`t and a time limit of 500 seconds per problem. Note that,
`with these problems,
`the frontier between consistency
`and
`is about t = 0.2. Figure 3 shows, for both
`inconsistency
`the mean cpu time and the number of problems
`algorithms,
`solved within the time limit.
`It appears that rds gets more efficient as constraint
`tight-
`ness increases. Moreover, whereas the number of problems
`solved by bb suddenly diminishes
`as constraint
`tightness
`
`Constraint Satisfaction
`
`185
`
`Page 5 of 7
`
`
`
`700 ,
`
`I
`
`600
`
`x = tightness, y = mean CPU time (in seconds)
`I
`I
`I
`I
`I
`f
`
`I
`rds +
`bb -+-.
`
`I
`
`0.1
`
`0.2
`
`0.3
`
`0.4
`
`0.5
`
`0.6
`
`0.7
`
`0.8
`
`0.9
`
`,
`
`100
`
`x = tightness, y = number of problems solved within 500 seconds
`T
`T--T
`T ‘\
`T
`T
`T
`\ ‘\
`
`rds +
`bb -+-.
`
`0
`0.1
`
`I
`0.2
`
`I
`0.3
`
`I
`0.4
`
`I
`0.5
`
`I
`0.6
`
`I
`0.7
`
`4%
`‘\
`-.
`, --.,
`0.9
`0.8
`
`1
`
`Figure 3: Influence of constraint tightness
`
`increases, nearly all the problems generated are solved by
`rds within 500 seconds.
`In order to assess the influence of the graph bandwidth
`on the relative efficiency of bb and rds, we performed other
`experiments with n = 20, d = 5, c = t = 0.5, b varying
`from 6 to 18 in steps of 2 and 100 randomly generated
`for each value of b. Figure 4 shows the mean cpu
`problems
`time for both algorithms.
`It appears that graph bandwidth
`is
`since rds becomes
`important,
`less efficient as it increases.
`
`80
`
`70 -
`
`x = graph bandwidth, y = mean cpu time (in seconds)
`I
`I
`I
`I
`I
`rds -e-
`bb -+-. _
`
`6
`
`8
`
`10
`
`12
`
`14
`
`16
`
`18
`
`Figure 4: Influence of graph bandwidth
`
`186
`
`Constraint Satisfaction
`
`-
`
`Earth Observation Satellite Scheduling
`Problems
`the results which have been obtained on
`We now present
`large real scheduling problems and, more precisely, on daily
`management problems
`for an earth observation
`satellite, for
`which the idea of the Russian Doll Search was originally
`(Agn&e et al. 1995). These problems can be
`conceived
`roughly described as follows:
`given a set S of photographs which can be taken the next
`day from at least one of the three instruments, w.r.t. the
`satellite
`trajectory; given, for each photograph, a weight
`expressing
`its importance;
`non overlapping
`constraints:
`given a set of imperative
`and minimal
`transition
`time between
`two successive pho-
`tographs on the same instrument,
`limitation on the instan-
`taneous data flow through
`the satellite
`telemetry;
`find an admissible
`subset S’ of S (imperative constraints
`met) which maximizes
`the sum of the weights of the
`photographs
`in S’.
`They can be casted as additive CSPs by:
`a variable v with each photograph p; asso-
`associating
`ciating with v a domain d to express
`the different ways
`of achieving p and adding
`to d a special value, called
`rejection value, to express the possibility of not selecting
`p; then associating with v an unary constraint
`forbidding
`the rejection value, with a valuation equa1 to the weight
`of P;
`(binary and ternary)
`as imperative constraints
`translating
`the constraints of non overlapping
`and minimal
`transition
`time between
`two photographs on the same instrument,
`and of limitation on the instantaneous
`data flow;
`On these problems, we compare:
`bb using the lower bound LB2 on the global valuation of
`a partial assignment and the following variable and value
`orderings:
`the
`the variables of maximum weight, choose
`- among
`first according
`to the chronological
`photograph order-
`ing; when only one value remains
`in a variable domain,
`immediately
`assign
`this variable
`this value (dynamic
`ordering);
`last choose the rejection value
`ordering);
`rds using the lower bound LB3 on the global valuation of a
`partial assignment,
`slightly modified
`in order to take into
`account unary constraints,
`and the following variable and
`value orderings:
`to the chronological
`- choose the first variable according
`photograph ordering, since the bandwidth of this order-
`ing is naturally
`small
`in scheduling problems
`(static
`ordering);
`the variable had in the optimal
`the value
`- first choose
`found on the previous
`subproblem; when
`assignment
`is not the rejection value,
`this value
`last choose
`the
`rejection value (static ordering);
`
`in each domain
`
`(static
`
`Page 6 of 7
`
`
`
`These orderings are, in each case, the most efficient we
`Figure 5 shows
`the results we obtained
`experimented.
`on eight typical problems
`(data can be downloaded
`from
`ftp://ftp.cert.fr/pub/lemaitre/LVCSP/Pbs/SPOT5/).
`A row
`The
`three
`following
`is associated with each problem.
`columns give the number n of variables,
`the number e of
`constraints and the bandwidth b of the chronological
`order-
`ing for the largest independent
`subproblem4. The four last
`columns give the results of bb and rds, using a time limit
`of 1800 seconds per independent
`subproblem.
`For each
`algorithm,
`the first column shows the valuation of the best
`assignment
`found within the time limit and the second one
`the cpu time used to get this result. A * sign points out
`provenly optimal valuations.
`
`<
`n
`100
`199
`300
`364
`105
`240
`
`e
`610
`2032
`4048
`9744
`403
`2002
`
`b
`33
`62
`77
`150
`30
`59
`
`val
`48
`3076
`15078
`21096
`8095
`12088
`
`time
`1800
`1800
`1800
`1800
`1800
`1800
`
`rds
`
`val
`49*
`3082”
`16102”
`22120”
`9096”
`13100”
`
`time
`0.5
`14
`29
`86
`2.5
`15
`
`;:;
`
`/ ii::
`
`/ :;i
`
`// :;:;:
`
`/ :i::
`
`)/ :;:;::
`
`1 ::6
`
`I/
`
`Figure 5: Results on earth observation satellite scheduling
`problems
`
`It appears that, whereas bb solves none of the eight prob-
`the time limit, rds solves all of them.
`lems within
`It also
`appears that it solves them all the more easily as the band-
`width of the chronological
`ordering
`it uses is small.
`
`Conclusion
`Although Depth First Branch and Bound tree search al-
`allow Constraint Optimization problems
`gorithms
`to be
`dealt with, extensions of Backward and Forward Checking,
`which do not take into account constraints between unas-
`signed variables, provide
`the search with bounds, which
`are too optimistic,
`so long as it does not reach the depths
`of the tree. The practical
`result
`is an enormous waste of
`time and an inability
`to solve even small problems within a
`reasonable
`time.
`The Russian Doll Search algorithm we have described
`in
`this paper is an extremely
`simple and yet powerful method
`of taking into account constraints