)J.C. Agnèse, N.Bataille, D. Blumstein (
)
E. Bensana, G. Verfaillie ()
J.C. Agnèse, N.Bataille, D. Blumstein ()
: CERT-ONERA, 2, av. E. Belin, BP 4025,
31055 Toulouse Cedex, France
Fax +33 62 25 25 64, E-mail : {bensana,verfail}@cert.fr
: CNES, Centre Spatial de Toulouse, 18 av
E. Belin, 31055 Toulouse Cedex, France
Fax : +33 61 28 26 03, Email : Nicolas.Bataille@cnes.fr
The daily management of an observation satellite like Spot, which consists in deciding every day what photographs will be attempted the next day, is of a great economical importance. But it is a large and difficult combinatorial optimization problem, for which efficient search methods have to be built and assessed. In this paper we describe the problem in the framework of the future Spot5 satellite. This problem can be formulated as a Variable Valued Constraint Satisfaction Problem or as an Integer Linear Programming Problem. Within the VVCSP framework, exact methods to find an optimal solution, like Depth First Branch and Bound or Russian Dolls search and approximate methods to find a good solution, like Greedy Search or Tabu search have been developed and experimented on a set of representative problems. Comparison is also made with results obtained by running the Linear Programming environment CPLEX on the corresponding linear models. The conclusion addresses some lessons which can be drawn from this overview.
The Spot5 daily scheduling problem [1] can be informally described as follows :
associated to each photograph p, which is the result of
the aggregation of several criteria like the client importance,
the demand urgency, the meteorological forecasts ...
of S which is admissible
(hard constraints met) and which maximizes the sum of the weights of the
photographs in 
.
This problem belongs to the class of Discrete Constrained Optimization Problems (it can be seen as a kind of multi-dimensional knapsack problem). It is an NP-hard problem, according to the complexity theory.
The Variable Valuated Constraint Satisfaction Problem framework (VVCSP) is a specialization of the VCSP framework [2] (which is itself an extension of the CSP framework), where each problem can be characterized by a set of variables and a set of constraints. Each variable is characterized by its weight and a finite domain of values (defining its possible instantiation) and containing a special value * (expressing the fact that the variable do not participate to the solution. Each constraint links a subset of variables and defines forbidden combination of values for these variables.
Given an assignment A of all the problem variables, the valuation of A is the sum of the weight of variables instantiated to a value different from the special value *. The standard objective is to produce an assignment with a maximal valuation.
The modeling of the Spot5 scheduling problems, within the VVCSP framework [3] consists in :
for a mono photograph
(values 1, 2 et 3 corresponding to the possibility of using the
front, middle or rear instrument to take the photograph);
The biggest problem, from our data set corresponds to a problem with 1057 variables and 21786 constraints.
The modeling of the Spot5 scheduling problems, within the Integer Linear Programming framework consists in :
to each trial (p being
the photograph and i the instrument) : 
(1
meaning selection, 0 meaning rejection);
, the constraints of non overlapping and respect of
the minimal transition time between two trials
on the same instrument;
, the constraints of limitation of the instantaneous flow of data;
,
the constraint of limitation of the recording capacity (
being
the amount of data to record when photograph p is done on instrument i);
, with 
if
p is a mono photograph and
for stereo (because both trials will be necessarily selected).
Two strategies have been experimented within the VVCSP framework : the standard Depth First Branch and Bound and a new algorithm called Russian Dolls Search (for a detailed presentation see [4]. For the ILP framework, we use an algorithm based on Best First Branch and Bound.
The Depth First Branch and Bound algorithm, which is the equivalent to the Backtrack algorithm widely used within the standard CSP framework [5], presents the following advantages :
Russian Dolls Search [6] is a generalization to the VVCSP framework, of a Spot5 specific algorithm developed by D. Blumstein and J.C. Agnèse for finding optimal solutions. It is in fact build on top of the standard Depth First Branch and Bound.
Given a problem p with n variables; the method, which assumes
a static variable ordering, consists in performing n searches, each one
solving (with the
standard Depth First Branch and Bound strategy)
a subproblem of p limited to a subset of the variables.
The 
problem is limited to the i last variables. Each problem
is solved by using the same
variable ordering, i.e.
from variable 
to n. The optimal valuation is recorded as well
as the corresponding assignment. They will be used when solving
the next problems, to improve the valuation of the partial assignment and thus
to provide better cuts.
This method, which can be surprising since it multiplies by n the number of searches, has proved to be very efficient, mainly because of the quality of the valuation of the partial assignments provided by previous searches.
Best First Branch and Bound is the base for solving Integer Linear Programming problems. The evaluation, at each node, is made by solving the corresponding relaxed problem (integrity constraints removed) with a classic algorithm for Linear Programming like simplex algorithm for instance. In our experiments, we have used the CPLEX environment, which embeds powerful algorithms for this class of problems.
This section presents algorithms which are aimed at providing ``good'' solutions to the problem, but cannot prove optimality. Although not specific of the VVCSP framework, they will be described in this framework to keep an unified presentation (details of algorithms can be found in [4]).
This algorithm works in two phases :
The efficiency of the algorithm depends greatly on the quality of the sort performed in the first step. Trials can be sorted according to (the aim is to maximize the quality of solution and limit the conflicts):
Another variant of the basic algorithm, called Multi Greedy Algorithm, consists in computing several initial schedules, by using different variable orderings (up to five) and performing the improvement phase on the best one.
Tabu Search (see [7] for a detailed presentation) like any other local search
method can certainly be best introduced by taking a geometric analogy of the
search process. Each assignment of all the n variables of the problem
can be considered as a point in the n-dimensional search space.
Each point receives then a valuation
characterizing the goodness of the solution (
means that
the point P
does not represent a feasible solution).
The search process can then be seen as ``moving from point to point'' trying to find points with a better valuation than the best point encountered since then. A first initial and ``feasible'' point can always be found : either the void solution (all variables instantiated to the value 0) or some good initial solution as one provided by the greedy algorithm for example. Each time the search process moves from current to next solution an iteration counter is incremented.
In the search we do not consider completely arbitrary moves (changing lot of values at the same time) but only the simplest ones : only one instantiation is changed at the same time. More precisely, we considered only two types of moves :
This limitation makes that many points in the search space cannot be reached from
a given point P. The set of points that can be reached from the point P via
feasible moves is known as the neighborhood of P or 
.
A move between current solution P and next solution 
can be given a value
. Basically the move selected
at one iteration is
the one in 
which has the best value. A useful remark at this point is
that moves leading to a worse solution
than the preceding one, are still possible, to allow the search to escape from local optimum.
However, due to this possibility, endless cycling is avoided
by forbidding the reverse move for a certain time
after the current iteration. The move is declared tabu for this period
(where the name of the method comes from).
Forbidding certain moves, which are in 
, can be seen
formally as a modification of 
under the constraints induced by the
history
of the search. So the next move is not selected in 
but in a subset
of 
. In the Tabu Search we have
implemented,
the history of the search consists in recording, for each photograph : the last iteration at which the photograph has been inserted or
removed from a solution and the number of insertions tried for it.
This second kind of memory which tracks mid-term behavior of the search is
used to penalize insertion of very frequently inserted moves.
Such penalization induces a way to force some kind of diversification of the
search, guiding the exploration in yet unexplored area of the search space.
The set of available data involves 498 scheduling problems provided by CNES [1] :
To experiment and compare the different methods, 20 representative problems ( available on Internet) have been selected in the different classes : 13 problems ``one orbit'' (54, 29, 42, 28, 5, 404, 408, 412, 11, 503, 505, 507 and 509) and 7 problems ``several orbits'' (1401, 1403, 1405, 1021, 1502, 1504 and 1506). . Tables 1 and 2 present the results obtained on these problems by the five following methods :
Table 1 presents the results on the subset of ``one orbit'' problems (Pb is the problem number and Nv is the number of variables of the problem) For each couple problem-method the first number is the best valuation (sum of the weights of selected photographs), * indicates that optimality has been proved and the second number is the cpu time in seconds.
Table 1: ``one orbit'' problems
Concerning these problems :
Table 2 presents the results on the subset of ``several orbits'' problems (same presentation than for table 1).
Table 2: ``Several orbits'' problems
Concerning these problems :
Results obtained on the whole data set show the efficiency of both Russian Dolls Search for ``one orbit'' problems and Tabu Search in general.
For optimality proof, the Russian Dolls Search, outranks
other methods. Its performances are
summarized in table 3 w.r.t
the size of the problem : the class i-j is the set of problems with
a number of variables Nv such that 
, 
is the
number of problems in the class and 
the number of problems solved
optimally with RDS.
Globally, the procedure solved optimally 85.7 % of the initial data set
(90.8 % for the subset one orbit, 68.4 % on the subset
several orbits).
Table 3: Efficiency of Russian Dolls Search
This table shows also the limitations of the procedure : when problems become large (Nv > 400), efficiency falls. It should be quoted, that the main reason is not the number of variables itself, but the presence of the high arity recording capacity constraint (large problems correspond to ``several orbits'' problems where the recording capacity limitation is enabled).
Starting from the solution provided by the Greedy algorithm, the Tabu Search generally succeeds to substantially improve it. On the subset one orbit, it provides solutions worse than the best known ones on only 10.5% of the problems (the best known solutions are the optimal ones provided by exact methods when they succeed or the best ones whatever method is used).
On the subset several orbits Tabu search improves solutions provided by Greedy search in 56.1 % of the problems.
Exact methods, aimed at finding optimal solutions and proving optimality, fail when problems become too large or in presence of high arity constraints.
Approximate methods can find solutions, whatever the problem size or characteristics. They provide often good solutions but sometimes loose time in trying to improve optimal solutions on small or medium size problems.
Besides experimenting other exact approach (based on Dynamic
Programming principles for example), one of the most interesting prospect is to
investigate a closer cooperation between exact and approximate
methods. We can easily imagine combinations of exact and approximate
methods by using them in sequence or in parallel. But it can be
interesting also to try to make them cooperate at a lower level, like
for example making Linear Programming and Constraint
Satisfaction work together.