Solution approaches, models and algorithms

The ROC team contributes to the different components of a natural solution approach to a Combinatorial Optimisation Problem (COP). We consider three different levels on this dimension.

Characterization of optimal schedules via lattice of permutations

Structural properties and complexity

A COP can be analyzed inde pendently of the intended solution methods and even of the possible problem formulations to establish mathematical or computational properties that will be useful for subsequent solving. A first fundamental point is to determine the computational complexity of the problem and of some relevant subproblems, as these results will subsequently drive the solution approach. Looking at the COP as a mathematical object, other structural properties can be analyzed such as necessary existence conditions, general characterizations of the solution set, extreme cases, dominance relations etc. All these properties may be useful for subsequent solving.

Some publications on strctural properties and complexity

Dantzig-Wolfe decomposition for a vehicle routing problem

Propagation of the switch constraint via network flows

Formulations, decompositions and inference

It is well known from optimization practitioners that finding a good formulation for an NP-hard problem is a fundamental step of the solution process. This conditions the quality of the information one can obtain on the problem, i.e. inference. For an integer programming formulation, we are interested in obtaining a good LP relaxation, possibly after adjunction of valid inequalities. An intermediate step to obtain a good formulation is to obtain a decomposition of the problem. In the Dantzig-Wolfe decomposition context, which allows obtaining good LP relaxations, the team carries out researches to efficiently solve column generation problems. In the CP framework, the decomposition lies in finding the right set of constraints to model the problem, as the propagation algorithms associated with each such constraint will efficiently perform domain reductions. The team aims at finding efficient propagation algorithms for different families of constraints.

Some publications on formulations, decompositions and inference

 

 

Hybrid decoding for multi-objective genetic algorithms

Clause learning based on explanations on global constraints for intelligent tree search

Generic and specific search algorithms

Even if the study of structural properties and inference mechanisms may have reduced the search space, decisions have ultimately to be made so as to obtain an optimal or near-optimal solution. The local search framework where one jumps from a solution to another one via neighborhood mechanisms can be opposed to global exact or approximate search schemes such as metaheuristics and branch-and-bound methods. The team carries out researches in metaheuristic methods and in tree-search methods, with a special focus on hybrid methods and integration of learning mechanisms in search.

Some publications on generic or specific search methods