You are here

Research Topics

Statistical Constraint

The objective of statistical constraints is to develop constraints and propagators on the common statistical objects such as the mean, variance, median, percentile, histogram…. These constraints are used for example to balance the workload between persons in assignment problems.

Stochastic Programming

Life is uncertain. In fact, decisions are rarely made under certainty. Stochastic Programming (SP) is part of the mathematical programming and operations research that (studies how to) model optimization problems by taking (relevant) uncertainty into account. In this research group, we are mainly interested in stochastic vehicle routing and online combinatorial optimization problems in logistic applications.

Subgraph Isomorphism

A subgraph isomorphism problem consists in deciding if there exists a copy of a pattern graph in a target graph. This problem is known to be NP-complete. In this research we focuss on the following topics.

  • Structured domains (Graph and Maps)
  • Design of specific filters for subgraph isomorphism
  • Symmetry breaking in subgraph isomorphism
  • Decomposition in subgraph isomorphism
  • Comparison with state-of-the art techniques and algorithms

Synthesis of Local Search models for scheduling applications

The goal of this work is to automatically generate appropriate local search models for various scheduling problems. The generation covers the neighbourhood and the metaheuristic. It is based on a static analysis of the problem at work. The problems are presented using modelling facilities constructed on top of the Comet programming language.

Trafic engineering techniques for data center networks

Traffic engineering (TE) consists in improving the performance of the telecomunication networks which is evaluated by a large number of criteria. The ultimate objective is to avoid congestion in the network by keeping its links from being overloaded. In large Ethernet networks, such as data centers, improving the performance of the traditional switching protocols is a crucial but very challenging task due to an exploration in the size of solution space and the complexity. Hence, exact methods are inappropriate even for reasonable size networks.

Very Large-Scale Neighborhoods

In Local Search, one defines - for each solution S of the problem - a set N(S) of solutions similar to S. These solutions are often built by making small changes to S. N(S) is called the neighborhood of S. In order to solve a problem, one starts from an initial solution S_0, select one neighbor in S_1 = N(S_0) and move to it. It goes on by moving from solution to one of its neighbor until some termination criteria is met (e.g. no solution of increasing quality can be found in the neighborhood of the current solution).