Structural properties and approximations with guarantees

A Combinatorial Optimization Problem (COP) can be analyzed independently 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. This includes complexity and approximability studies. Secondly, in view of solving the problem via off-the-shelf mixed-integer linear programming or constraint programming solver, a theoretical analysis of the different mathematical formulations, e.g. linearizations, provides useful insights. Third, efficient and accurate approximation with guarantees are proposed for validated computing. These topics are detailed below.

 Approximation results for parallel machine scheduling with additional resources

 Tractable CSP classes addressed by Carbonnel's theorem

Structural properties and complexity of Combinatorial Optimization problems

A first fundamental point is to determine the computational complexity of the problem and of some relevant subproblems, as these results subsequently drive the solution approach. Polynomial-time approximation schemes are also designed for NP-hard problems. Major results of the team in this domain include polynomial-time methods to test for membership of a CSP in a selection of major tractable classes. Looking at the COP as a mathematical object, especially in the graph theoretical framework, other structural properties are analyzed such as necessary existence conditions, general characterizations of the solution set, extreme cases, dominance relations etc.

Some publications on structural properties and complexity

Extended formulation for a biobjective vehicle routing prolem

Formulations, LP relaxations and polyhedral studies

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, trough Benders and/or Dantzig-Wolfe decomposition.


Some publications on formulations, LP relaxations and polyhedral studies

Piecewise linear formulation of univariate non-linear constraints

Polynomial approximations for validated computing

Approximation wih error bounds for non-linear problems

The team proposes approximations with error bounds for different non-linear problems. A piecewise linear bounding approach of univariate non-linear functions was successsfully applied to mixed integer non linear programming (MINLP). In this case, the MINLP can be eficiently solved with an arbitrary precision by solving two mixed-integer linear programs. Efficient polynomial approximations with bounded errors are used for solutions of some ordinary differential equations and validated computing.


Some publications on approximations with error bounds