AOC: Algorithms and Combinatorial Optimization

Head of AOC Team : Franck Butelle

The AOC team was issued in 2010 from two research domains of the former OCAD team: Combinatorial Optimization, and Parallel and Distributed Computing. The team is organized along three axes:

  • Optimization on graphs,
  • Mathematical Programming,
  • Parallel and Distributed Computing.

These three research axes are strongly linked together. The first one mainly deals with optimization problems in graphs with focus on complexity, polyedral theory and approximation. It also addresses optimization problems on specific huge graphs that arise in various fields such has data mining, image processing and distributed computing.

The second axis deals with the design and analysis (both theoretical and empirical) of mathematical programming approaches and algorithms. Both exact and heuristic approaches for solving hard combinatorial optimization problems are developed. Moreover, both mixed integer linear programming and mixed integer non linear programming are studied.

The third axis deals with problems intersecting three strongly linked domains: distributed middleware and architecture, distributed programming and distributed algorithms.

An interesting characteristic of the AOC team is that its expertise covers a broad spectrum of topics either horizontal (from graph theory to heuristics) or vertical (from algorithm design to detailed implementation). It is unusual in Europe and all over the world to find an equivalent spectrum.

The strengths of the team are the quantity and quality of publications together with open source software development. Researchers of the team have published in high-level international journals and conferences as, for example, JGT, TCS, Mathematical Programming, Operations Research, International Journal of Grid and High Performance Computing, Concurrency and Computation: Practice and Experience, and SODA, INOC, IPDPS, and are editors or authors of several international books on these topics. As for software we developed, for example, PastGrid, BonjourGrid, COGITO (a joint project with SNCF) or BiqCrunch. The team actively participates in national projects (in some cases, as principal coordinator) and has several international collaborations. The international expertise of the team is also assessed by its ability to attract international researchers as visiting scholars or to cover temporary positions (PhDs and postdocs).