Efficient Approximation Algorithms For The Pareto Set With Provable Guarantees

The purpose of this task is to establish practically efficient algorithms with provable guarantees for problem (P1). The main types of guarantees we consider are:
(G1) quality of the generated subset
(G2) running time

Our research objective is to aim at reinforcing the links between the two streams of research previously mentioned (metaheuristics and theoretical approximation). Our general approach is to adopt a theoretical perspective and try to make it operational.

In our context, ensuring (G1) means that any efficient solution (and thus any solution) is (1+e)-dominated by at least one solution from the subset. Satisfying (G2) means that the running time of the proposed algorithm is polynomial in the size of the input and, possibly, in 1/e.

Subtask 4.1 Efficient implementation of theoretical approximation algorithms
Ideally, it would be desirable to impose both (G1) and (G2), which amounts to implementing efficiently a theoretical approximation algorithm (see task 2). In some preliminary works, applied to the multiobjective knapsack problem for which theoretical fptas are known, we showed recently that a practically efficient implementation is possible while preserving the status of fptas [BHV07]. This was obtained using an extended dynamic programming approach. Examining other combinatorial optimization problems under the same perspective is a natural research question. Rather than focusing on fptas only, it would be interesting to investigate how to adapt ptas or even other approximation algorithms, e.g. with constant ratio.

Another interesting question is to establish algorithms imposing both (G1) and (G2) but also restrictions on the size of the generated set. A recent work towards this direction was made by Vassilvitskii and Yannakakis [VY05] who propose an algorithm which, for any error e, provides an (1+e)-approximate solution using as few points as possible.

Subtask 4.2 Efficient algorithms with provable guarantee on the quality of the subset
If we look for practically very efficient algorithms we must accept to relax some of the prior theoretical guarantees. Since (G1) is the essence of our approach, we may accept to relax (G2) so as to obtain practically faster algorithms. In a preliminary work in the field of multiobjective search in state space graphs, we showed recently that relaxing (G2) makes it indeed possible to obtain better resolution times compared to a pure fptas [PS08]. In this subtask, the purpose is to check whether we can derive algorithms that are competitive (in terms of running time) with metaheuristics, while ensuring a prior guarantee on the quality of the generated subset.

More generally, we shall devote a specific attention to the extension of general exploration techniques, such as dynamic programming and branch and bound, to the approximation of the Pareto set.

Subtask 4.3 Study of the biobjective case
On another research direction, we plan to focus on the biobjective case. It is well known that this allows us to use data structures leading to more efficient computational implementations. More specifically, in the biobjective approximation context, the (1+e)-dominance relation used for approximation has also very specific properties which become false as soon as three objectives are considered. This suggests looking, in the biobjective case, for approximations verifying additional properties, which are minimal in some sense. The main objective here is to develop other concepts of approximation.

In order to validate the algorithms proposed in the different subtasks, we plan to use instances from the library (task 1). We plan to compare our algorithms with metaheuristics and exact methods (developed in task 3 or based on commercial solvers like CPLEX) on the instances of the library. The validation concerns mainly the running time, since we stressed that all our proposed algorithms should respect (G1). Unlike for metaheuristics, we are not faced with the difficulty of evaluating the quality of the generated subset which is guaranteed by construction. In particular, we do not need to know the exact Pareto set to evaluate the quality of the generated subset (this can be done only on rather small size instances). However, when possible, it is also interesting to check experimentally the difference between the a priori guarantee and the (better) a posteriori guarantee.