Structural Properties and approximations with guarantees
We carry out research to establish structural properties and performance-guaranteed approximations of combinatorial optimization and other computing problems. This include complexity and approximability analysis, theoretical comparisons of linearization schemes, piecewise linear and polynomial approximations, polyhedral and graph theoretical studies
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. linearization, provides useful insights. Third, efficient and accurate approximation with guarantees are proposed for validated computing. These topics are detailed below.
Structural properties and complexity of Combinatorial Optimization problems
Approximation results for parallel machine scheduling with additional resources
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.
Tractable CSP classes addressed by Carbonnel's theorem
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
Formulations, LP relaxations and polyhedral studies
Extended formulation for a biobjective vehicle routing prolem
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
Approximation with error bounds for non-linear problems
Piecewise linear formulation of univariate non-linear constraints
The team proposes approximations with error bounds for different non-linear problems. A piecewise linear bounding approach of univariate non-linear functions was successfully applied to mixed integer non-linear programming (MINLP). In this case, the MINLP can be efficiently solved with an arbitrary precision by solving two mixed-integer linear programs.
Another research topic concerns efficient polynomial approximations with bounded errors for solving ordinary differential equations and validated computing.
Polynomial approximations for validated computing
