throbber
From: AAAI-96 Proceedings. Copyright © 1996, AAAI (www.aaai.org). All rights reserved.
`
`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

This document is available on Docket Alarm but you must sign up to view it.


Or .

Accessing this document will incur an additional charge of $.

After purchase, you can access this document again without charge.

Accept $ Charge
throbber

Still Working On It

This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.

Give it another minute or two to complete, and then try the refresh button.

throbber

A few More Minutes ... Still Working

It can take up to 5 minutes for us to download a document if the court servers are running slowly.

Thank you for your continued patience.

This document could not be displayed.

We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.

Your account does not support viewing this document.

You need a Paid Account to view this document. Click here to change your account type.

Your account does not support viewing this document.

Set your membership status to view this document.

With a Docket Alarm membership, you'll get a whole lot more, including:

  • Up-to-date information for this case.
  • Email alerts whenever there is an update.
  • Full text search for other cases.
  • Get email alerts whenever a new case matches your search.

Become a Member

One Moment Please

The filing “” is large (MB) and is being downloaded.

Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.

Your document is on its way!

If you do not receive the document in five minutes, contact support at support@docketalarm.com.

Sealed Document

We are unable to display this document, it may be under a court ordered seal.

If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.


Access Government Site

We are redirecting you
to a mobile optimized page.





Document Unreadable or Corrupt

Refresh this Document
Go to the Docket

We are unable to display this document.

Refresh this Document
Go to the Docket