Solving Constraint Optimization Problems in Anytime Contexts

1 Introduction

It is today indisputable that Constraint Programming (CP) fulfills industrial needs of optimization off-line. Many sys­ tems which use this technology are already operational in different fields of activity, such as planning, scheduling and resource allocation. In on-line optimization context, prob­ lems dynamically change according to the evolution of the external environment, and their resolution must respect strong temporal constraints (anytime contexts). However, CP is not yet adapted for solving such on-line problems : no guaran­ tee is supplied on the execution times, and current CP solvers do not lend themselves to the combination with other search methods which seem better adapted to respect temporal con­ straints, such as stochastic search methods.

Our objective is to conceive anytime algorithms based on CP and to guarantee the following main properties : to pro­ duce in a very short time solutions of good quality, and more importantly to improve them gradually as computation time increases. To our knowledge, our proposal is one of the first attempt to efficiently address the problem of building anytime algorithms with Constraint Programming.

This paper presents a new hybrid method, called VNS/LDS+CP, dedicated to the efficient computation of high quality solutions (possibly suboptimal) in · an anytime con­ text. Our method combines a Variable Neighborhood Search [Hansen and Mladenovic, 1997] (it performs moves like local search), and a Limited Discrepancy Search [Harvey and Gins­ berg, 1995] with Constraint Propagation to efficiently guide the search.

Patrice Boizumault

GREYC, CNRS UMR 6072, Universite de Caen F-14032 Caen Cedex- France patrice.boizumault@info.unicaen.fr

Section 2 describes the general context in which we take place. Section 3 reviews the hybridization of search algo­ rithms . and justifies our first choices. Section 4 details our proposal (VNS/LDS+CP). Section 5, gives computational ex­ periments on CELAR benchmarks ; both mechanisms of VNS/LDS+CP are then finely studied. Section 6 shows how VNS/LDS+CP has been successfully applied to solve a diffi­ cult network problem. Finally, we conclude and draw a few perspectives.

2 Anytime constraint optimization context

2.1 Anytime algorithms

The term anytime algorithm was coined by Dean and Boddy in the mid-1980s in the context of their work on time­ dependent planning [Boddy and Dean, 1994]. Contrary to a standard algorithm, where no result is available until its end­ ing, an anytime algorithm can be stopped, at any time, to pro­ vide a solution of increasing quality over time.

Performance profiles describe the evolution of the solution quality (produced by the algorithm) as a function of the com­ putation time. They provide a more precise description of the performances and of the behavior of an algorithm than the best known solution reported by usual algorithms. In the se­ quel of this paper, we consider mean performance profiles : such curves are built empirically by collecting statistics on the performance of the algorithm over many input instances.

There are two kinds of anytime algorithms, namely, in­ terruptible and contract algorithms [Zilberstein, 1996]. A contract algorithm requires that the computing time must be known prior to its activation. It must produce a solution within a contract of time, and if it is interrupted before the end of the contract, there is no guarantee about the quality of the solution. However, for an interruptible algorithm, no information is (a priory) available about the allowed compu­ tation time, and a solution may be asked for at any time. The algorithm must always provide a good solution, and more im­ portantly, continue to refine it.

In this paper we are interested by the design of interruptible algorithms, since every interruptible algorithm is trivially a contract algorithm, but the converse is not so immediate.

2.2 Valued Constraint Satisfaction Problems

The Valued CSP (VCSP) [Bistarelli et al., 1999; Schiex et al., 1995] framework is an extension of the CSP (Constraint Sa tisfaction Problem) framework, which allows over-constrained problems or preferences between solutions to be dealt with.

More formally, whereas a CSP is defined as a triplet (V, D, C), where V is a set of variables, D a set of finite domains associated to the variables and C a set of constraints between the variables, a VCSP can be defined as a CSP pro­ vided with a valuation structure S and a valuation function <p. The valuation structureS is a triplet (E, >-, ® ), where Eisa valuation set, >- a total order onE, T and j_ the maxi­ mum and the minimum element in E and ® a binary operation closed on E. The valuation function <p, defined from C to E, associates a valuation to each constraint; the valuation of a constraint denotes its importance.

Let A be an assignment of all the variables and Cunsat (A) be the set of the constraints unsatisfied by A. The valuation of A is the aggregation of the valuation of all the constraints in C,.nsat(A) : <p(A) = ® <p( c) forcE C,.nsat(A).

The objective is to find a complete assignment with mini­ mum valuation. Specific frameworks depend on the retained operator ® : Classical CSP (A); Possibilistic CSP (max); Lexi­ cographic CSP (U on multi-sets); Weighted CSP (~).As many real-life problems use an additive criterion, we only consider weighted CSP (WCSP) in the sequel of this paper. From an algorithmic point of view, WCSPs are generally the most dif­ ficult to solve [Schiex eta!., 1995].

3 Hybridizations of algorithms

3.1 Complete search vs local search

Exact (or complete) tree search methods, such as Branch and Bound, are able to produce both an optimal solution, and a proof of optimality. But, because of their exponential worst­ case behavior, they may be extremely time consuming. More­ over, it has been experimentally observed that, due to their systematic way of exploring the search space, the quality of their intermediate solutions is usually very poor.

Due to their opportunistic way of exploring the search space, approximate (or incomplete) methods, based on stochastic local search (as Simulated Annealing, Tabu Search), can provide good solutions within a reasonable com­ puting time. But, such methods do not guide fast enough the search towards the best neighbor solutions. Indeed, they may waste a lot of time trying to improve the current solution with no success ; this is the case when they remain blocked in local minima during a prohibitive time. Such situation is not suit­ able in an anytime context, since the quality of solutions has to be improved gradually as fast as possible, as the comput­ ing time increases. Moreover, pure local search algorithms generally require a lot of time to adjust their noise parame­ ters ; their efficiency strongly depends on the value of these parameters, which are generally application-dependent.

3.2 Hybrid algorithms

Hybrid algorithms [Focacci eta!.,] provide appropriate com­ promises between both kinds of search. More precisely, they are very efficient by combining the advantages of both con­ straint propagation (complete search) and opportunistic ex­ ploration of the search space (local search).

Algorithm 1: The general VNS/LDS+CP algorithm

I 2 3 VNS (pi: Problem, Size , discrep : Integer, Str : Strategy) begin end size t- Size s' f-- InitialAssignment (pi) s f-- /J. ub f-- Cost (s') fori f-- 1 to MAXMOVES do l r ei f-- Relax (s,siz e,Str) II relax solutiOn s f-- Rebu~ld (s,rel,dis crt!p) II rebuzld solutwn if Cost (s) < Cost (s') then L ·''f-., size f-- ControlNeighborhoodSi ze (size) returns ·

Intertwined hybridizations are the most attractive and rel­ evant hybridizations of algorithms where both complete and local search are closely mingled during computation. The first kind of such hybrid algorithms belongs to the family of local search methods and uses ideas from CP in order to make large neighborhoods (LNS [Shaw, 1998]) more tractable. A second kind belongs to the family of exact search and uses some local search principles to improve the partial solutions at each node of the search tree [Prestwich, 2000] or to ex­ plore a set of solutions close to the greedy path in a search tree [ Caseau et a!., 1999].

3.3 Hybrid algorithms for anytime contexts

VNS/LDS+CP is an Intertwined hybridization algorithm. From local search, we have retained a Variable Neighborhood Search (VNS) which extends the principle of large neigh­ borhoods (LNS) by dynamically adjusting the neighborhood size, when the current solution is a local optimum. This choice will partially remedy to the weaknesses of pure lo­ cal search methods. Indeed, the more the neighborhood is potentially large the more there are chances that it contains good solutions and thus improves quickly the current solu­ tion. However, as neighborhoods grow larger, finding the best neighbor may require a too expensive computational ef­ fort. So, we have selected the LDS partial search combined with constraint propagation (lower bounds computation) to efficiently explore these neighborhoods.

4 The VNS/LDS+CP Method

VNS/LDS+CP is basically a local search method, as depicted in algorithm 1. It differs from classic local search methods by the size of the neighborhoods, which is adjusted dynamically during the search. It starts with an initial complete assignment s*; then, at each move, it relaxes (or unassigns variables) a large part of the current solution s and then rebuilds it (re­ assigns variables) by selecting the best neighbor that strictly improves the cost of the current solution. The algorithm ends when the maximum number of local moves (MAXMOVES) is reached.

LDS explores the neighborhood defined by the relaxed part of the solution. It benefits from constraint propagation based on lower bounds computation, and on dynamic heuristics for variable and value ordering. Moreover, only judicious neigh­ borhoods, related to conflict variables (i.e. variables occur-

Algorithm 2: Relaxing and rebuilding a solution

Relax (s :Solution, size: Integer, Str: Strategy) begin end v t- GenerateNeighborhood (s,Str) rel t- ¢ while I rel I :j. size and v :j. 0 do l x t- RandomElement (v) rei t- rei U { x} vt-v\{x} return rei Rebuild (s : Solution, rel : VarSet, discr ep : Integer) begin end if I r el I = 0 then I if Cost ( s) -< ub then L ub t- Cost (s) BestSolution t- s else x; +- ChooseVariables (rel) Dx · t- SortDomain (x;) k~O for j t- 1 a DomainSize(x ;) and k ::; di screp do l ··(i]t-Dx;Li] lb t- LB(s ,xi) if lb -< ub then L Rebuild(s,rel \{xi}, discrep- k) kt-k+l return BestSolution

ing in violated constraints), are considered. Such a choice prevents LOS from modifying the value of conflict variables.

4.1 Relaxing a solution

Algorithm 2 describes how to select the variables to be re­ laxed. The function of line ( 1) computes the set v of current variables candidate to relaxation, according to a strategy Str. A basic strategy is to select all the variables that are in con­ flict. size elements of v are randomly chosen to constitute rel the set of variables to be relaxed. This choice enables a balance between choosing variables according to a specific strategy and completely at random. Experiments have shown that the introduction of some randomness enables the search to escape quickly from local minima.

4.2 Control of the Neighborhood Size

Initially, the neighborhood size (size) takes a minimum value. To control the neighborhood size, different strategies have been implemented. The best strategy we have found, in­ creases systematically size by one, each time the method does not improve the cost of the current solution.

4.3 Rebuilding a solution

Algorithm 2 defines the function Rebuild. The global vari­ ables ub and lb record the upper and lower bounds of the prob­ lem optimum. LB(s,x;) computes a lower bound of the sub­ problem, limited to the variables after i (i included). discrep sets the maximum number of choices that we can diverge from the heuristic (discrepancies).

Limited Discrepancy Search

The idea of LOS [Harvey and Ginsberg, 1995] is to explore heuristically good solutions that might be at a limited dis­ tance from greedy solution. LOS ensures a more balanced exploration of the search tree, and speeds up the reconstruction step, thus improving the performance profile of our method. LOS starts from the solution computed by the value heuristic, and successively explores solutions by increasing the number of discrepancies, until the fixed maximal number of discrep­ ancies is reached.

We have used a generalized version of LOS for n-ary trees. The discrepancy is measured according to the rank of the value chosen for every variable in the order given by the heuristic on values. We count a single discrepancy for the second cheapest value of one variable, two discrepancies for either the third cheapest value of one variable, or the second cheapest value of two variables, and so on. We only perform one iteration of LOS, for a fixed discrepancy. This prevents re-visiting leaf nodes.

Constraint Propagation

One of the main strengths of our approach lies in the use of constraint propagation to prune useless sub-trees and to guide the choice of values during the reconstruction, while keeping this step fast enough. At each node of the search tree, lower bounds are computed in order to locally exclude all partial solutions which cannot lead to complete assignments ofbetter valuation than the current best solution. To our knowledge, no method based on large neighborhoods (in particular VNS) uses such a mechanism.

To compute lower bounds, we have adapted the following algorithms [Larrosa eta/., 1999] for WCSPs : (i) Partial For­ ward Checking and Directed Arc Consistency (PFC-DAC), all the constraints are directed, and DAC are computed from a di­ rected constraint graph (we have used specific data-structures to relax the condition of static variable ordering on DAC) ; (ii) Reversible DAC (PFC-RDAC), constraints directions can change dynamically during search, looking for a good di­ rected graph causing a high lower bound ; (iii) Maintaining Reversible DAC (PFC-MRDAC), DAC are maintained during search, propagating the effect of value pruning.

Variables and Values heuristics

Our heuristic for variable ordering first selects the variable having the lowest ratio domain cardinality divided by future degree. Constraint propagation, based on Forward Checking + Directed Arc Consistency, allows us to use a dynamic min­ imum inconsistency count value ordering. During search, for each value, so-called Inconsistency Counts (ic) and Directed Arc Consistency counts (dac) which record the look-ahead ef­ fects on future (unassigned) variables, are computed. Values are selected by their increasing ic + dac.

5 Experimentations on CELAR Benchmarks

5.1 Instances of CELAR

The CELAR (French Centre d'Electronique de l'Armement) has made available a set of 11 instances of the Radio Link Fre­ quency Assignment Problem (RLFAP) [Cabon eta/., 1999]. Most of them can be naturally cast as binary WCSPs. For our experiments, we have selected instance 6 (which involves 200 variables, having an average of 40 values in their domain, and 1322 constraints), instance 7 (which involves 400 variables, having an average of 40 values in their domain, and 2866 con­ straints), and instance 6-Sub1 (which involves 28 variables, having an average of 40 values in their domain, and 314 con­ straints) extracted from instance 6. These instances (6 and 7) are the most difficult ones. Whereas the optimum of instances 6 and 6-Sub1 are known (respectively 3389 and 2669), the optimum of instance 7 is still unknown; the best known upper bound is equal to 343592.

5.2 Experimental Methodology

Our method has 4 parameters : the maximum number of local moves (MAXMOVES), the initial neighborhood size (size), the number of discrepancies (discrep), and the propagation scheme. For all experiments, MAXMOVES has been set to 150 and size to 4 ; it is the best value we have found among the following set of values : {2, 3, 4, 5, 6}. We car­ ried out experiments with different values of discrepancies ( discrep E { 2, 3, 4, 5}) and with three different propagation mechanisms: PFC-DAC, PFC-RDAC and PFC-MRDAC.

For each combination of parameter settings, we ran VNS/LDS+CP 50 times on the considered instances. Dur­ ing each run, the best cost of the current solution has been recorded at regular time intervals (10 seconds). All plotted figures are mean performance profiles over the 50 runs. The methods have been implemented in chaco [Laburthe, 2000].

CPU time in seconds

Figure 2: Comparing performance profiles.

5.3 Setting parameters for VNS/LDS+CP

Number of discrepancies

Figure 1 (top) shows the performance profiles obtained with PFC-DAC, for different settings of discrep on instance 6. Performance profiles for discrep = 2 and 3 are almost the same. We give only the curve associated to discrep = 3. Re­ sults indicate, as expected, that the number of discrepancies has a great impact on the quality of the computed solutions. LDS with (discrep = 4) gives the best results. The poor re­ sults for (discrep > 4) are probably due to the fact that our value ordering does not make so many mistakes. Indeed, we exploit the propagation scheme to guide the value choices. Thus, few discrepancies are necessary to repair heuristic er­ rors. In contrast, for low discrepancies (discrep ::; 3), the value heuristic too closely limits the solutions we can find, and so, it provides poor guidance to good solutions. For the instance 7, discrep = 4 is also the best value.

Propagation mechanism

We turn now to choose the propagation scheme which pro­ duces significant lower bounds and, as global effect, leads to a better behavior of our method. Figure 1 (bottom) reports the performance profiles obtained for the three propagation algorithms, with discrep = 4 on instance 6. LDS with PFC­ DAC leads to very substantial profits. Because of the over­ head of propagation over small neighborhoods these bene­ fits decrease clearly when using stronger propagation (PFC- RDAC and PFC-MRDAC). Indeed, compared to PFC-DAC, the two other propagation schemes perform more work per node to finally obtain results very close to PFC-DAC. So, the more complex and time-consuming propagation schemes do not pay-off for this context.

5.4 Comparisons and discussion

We have compared VNS/LDS+CP (discrep = 4 with PFC­ DAC) with LNS/CP/GR [Lobjois eta/., 2000], another hybrid method which also relies on solving VCSPs in an interruptible context, and also with two standard versions of Simulated­ Annealing (SA) : Quick and Medium.

LNS/CP/GR is based on the principle of LNS with neigh­ borhood size being constant during all the search. To rebuild the relaxed variables, it uses a greedy algorithm combined with constraint propagation. But this propagation (performed variable per variable) is only used for selecting the best val­ ues for each variable, which is fundamentally different from our CP based on usual propagation for WCSP. For instances 6 and 7, the percentage of unassigned variables represents 40% of the total number of variables [Lobjois et al., 2000].

Figure 2 compares the performances of the four methods. The performance profile of VNS/LDS+CP is always better than those of the two versions of SA. At the beginning, the profile ofVNS/LDS+CP is very close to that ofLNS/CP/GR. But after few seconds of computation (~ 20 seconds on in­ stance 6 and ~ 35 seconds on instance 7), VNS/LDS+CP becomes very effective and always provides solutions of bet­ ter quality, thus clearly outperforming LNS/CP/GR on both instances. This behavior can be explained by the fact that, at the beginning, the size of the neighborhood is relatively small and consequently the benefits of constraint propaga­ tion are poor. But as soon as this size becomes sufficiently large, our propagation mechanism (lower bounds computa­ tion) produces more pruning, and becomes very effective. This leads to a better compromise between quality and time for VNS/LDS+CP. This confirms our choice for computing significant lower bounds. Note however, the good anytime behavior of LNS/CP /GR compared with those of SA.

5.5 Study of mechanisms VNS and LDS+CP

In order to evaluate the contribution of each component of VNS/LDS+CP we have carried out experiments on instance 6-Sub1 , with MAXMOVES = 150, and size= 4; the two other instances being out of reach from complete searches. Five methods have been compared : the Depth First Branch and Bound (DFBB), LDS with only one iteration, two variants of LNS (LNS/CP/GR and LNS/LDS+CP) which mainly differ by their reconstruction mechanism, and VNS/LDS+CP. For the two variants of LNS, the best percentage of unassigned variables represents 60% of the total number of variables.

Once again, discrep = 4 constitutes the best parameter setting for VNS/LDS+CP. The behavior of VNS/LDS+CP is quite similar to those observed on instances 6 and 7, which clearly offers better performance profiles than the other com­ peting methods. On this instance, VNS/LDS+CP almost finds the optimum in a very short time at each run. We can draw some remarks :

• pure LDS (or only one iteration of LDS) is completely inefficient in an anytime context, even if LDS leads to better performance profiles than DFBB.
• the efficiency of VNS/LDS+CP is certainly partly due to the reconstruction mechanism. Indeed, the compar­ ison between performance profiles of LNS/CP/GR and LNS/LDS+CP show that, with an effective propagation (lower bounds computation) combined with LDS, LNS obtains a gain in quality of 7% after 20 seconds.
• the use of variable size neighborhoods is a key point in the efficiency of VNS/LDS+CP. Indeed, it produces better performance profiles than LNS/LDS+CP. After 2 seconds, VNS obtains a gain in quality of 9% ; this gain reaches a value of .5% after 15 seconds. This amelio­ ration comes from the speed of the exploration of rela­ tively small neighborhoods (in particular during the first moves ofVNS). This greatly improves the quality of the computed upper bound which will enable a better prun­ ing at the next reconstruction step. This is not the case for LNS, which needs much more time to obtain good upper bounds, due to the important size of the neighbor­ hoods.

To evaluate the improvement speed of the quality of solutions provided by VNS and LNS, figure 4 compares VNS/LDS+CP and LNS/LDS+CP, in term of the average per­ centage of improvement, Qp(t), with respect to the initial cost, C0 , and in term of the number of attempted moves (in percentage). Qp(t) = 100 . (Co- C(t))jC0 , where C(t) is the valuation of the best solution found at each instant t.

As depicted in figure 4, VNS/LDS+CP provides the better improvement of the initial cost C0 . This difference in quality (in favor of VNS) is very significant during the first instants. After only 4 seconds of computation, VNS improves Co by 35%, with a percentage of attempted moves equal to 4% of MAXMOVES. For comparison, LNS needs 15 seconds and practically three times more oflocal moves(~ 14%) to reach the same improvement of quality. Moreover, the number of moves attempted by LNS grows larger with time, while for VNS this number remains low and quasi constant.

6 Resource allocation in ATM networks

VNS/LDS+CP has been successfully applied to a real-life anytime resource allocation problem. This application, de­ veloped for France Telecom R&D, takes place in an AIM (Asynchronous Transfer Mode) network administration con­ text. The problem consists in planning demands of connec­ tion over a period of one year. Reservations must be com­ puted within at most one minute per demand.

A new demand is accepted if both bandwidth requirements and quality of service are satisfied. If not, we try to reroute some already accepted connections in order to find a route for the new demand. If rerouting fails, the demand is re­ jected. First, a routing heuristic computes shortest paths which minimize capacity violations on the links. From these violations, a sub-area of the network that can be modified by rerouting some already accepted connections is deter­ mined and modelled as a VCSP. Then, rerouting is performed with VNS/LDS+CP. Experimental results show that rerout­ ing with VNS/LDS+CP enables to admit an average of 67% of demands that are rejected with a greedy algorithm without rerouting [Loudni et a!., 2003].

7 Conclusions and further work

VNS/LDS+CP is a new hybrid method for solving constraint optimization problems (modelled as VCSPs) in an anytime context. It has been successfully applied to a real-life any­ time resource allocation problem in AIM networks (67% of rejected demands are now accepted).

Experiments on the CELAR benchmarks have shown that VNS/LDS+CP provides better performance profiles than the other competing methods. Moreover, our method is robust : for all considered instances, the best parameters setting is al­ ways the same. Finally, VNS-LDS+CP is stable : the distri­ bution of the medians 1/4, 1/2 and 3/4 shows that the vari­ ation of the evolution of solution quality is negligible within the fifty runs. However, the difference between the best run and those of the medians is relatively distant for instance 7.

From an anytime point of view, in addition to the proper­ ties of monotonicity, interruptibility and measurable quality, our performance profiles also verify the important property of diminishing returns, which guarantees that the improvement in solution quality is larger at the early stages of computation.

Performance profiles show a decelerating phase leading to a quasi stable plateau. To escape from this plateau, we intend to study two possibilities : to cooperate with other efficient pure local search method [Voudouris and Tsang, 1998] or to re-start our method.

In this paper we have mainly focused on the design of any­ time algorithms. Works remain to be done concerning tech­ niques for monitoring and control (see [Hansen and Zither­ stein, 2001 ]). We are currently investigating such techniques for meta-level control. The use of nogoods would help to ob­ tain more relevant neighborhoods.