Project overview
Operations research can be regarded as a collection of useful tools and techniques for optimizing complex systems and decision-making. As most of the members of our team have an operations research background, we have a broad spectrum of general-purpose techniques in our toolbox. In addition, we have developed deeper skills in some of those techniques by means of our range of theoretical and practical experience.
Integer programming
Integer programming formulations can often be strengthened by gaining a deeper understanding of the specific polyhedral structure of the problem at hand. Indeed, if we know nontrivial valid inequalities and facets of the integer hull of the solutions, we can speed up the resolution of the integer program by introducing additional cuts in order to reduce the search space for the optimal solution. This technique is known as branch-and-cut, and we have used this approach in particular to accelerate CPLEX for resolving complex workforce scheduling problems.
Symmetries in linear programming
Polyhedron with a cyclic symmetry
group C3Symmetry is usually welcomed in many scientific areas, especially in mathematics. However, in integer programming, the reverse seems to be true; highly symmetric integer programs often turn out to be particularly hard to solve. Branch-and-bound or branch-and-cut algorithms are commonly used to solve integer programs, and they work efficiently only if the bulk of the branches of the search tree can be pruned. As symmetry in integer programs usually entails many equivalent solutions, the branches belonging to these solutions cannot be pruned, which leads to a very poor performance of the algorithm. In the current literature most approaches for addressing symmetry in linear programming rely on the branch-and-bound algorithm, or they are only applicable to select problems. We approach the topic from a more general and algebraic angle inspired by the field of group theory. The main objective is to develop a better understanding of the role of symmetry in the context of linear and integer programming.
Graph theory / Combinatorial algorithms
Reduction to 3D problem with saddle
configuration over bounded domainCertain problems can be modelled as optimization problems on graphs. This
is the case for distribution/flow problems, transportation problems, resource
allocation problems, matching problems, frequence assignment and many others.
Some of the problems are classical combinatorial problems and can be solved
efficiently to optimality by means of combinatorial algorithms. Others are
more involved but can be approximated by clever algorithm design. We
have experience with exact approaches, approximation techniques and heuristic
solutions for problems ranging from facility location to inventory control.
Robust optimization
Usually, the complex optimization problems we want to solve are subject to various types of uncertainty (e.g. uncertainty of the data, of the outcome) and we want to ensure that we take this into account in our decision process, i.e. that the solution we provide to a specific problem remains feasible and reasonably good under various perturbations. Robust optimization is a framework that allows one to include uncertainty as part of the formulation. Starting with some reasonable hypotheses regarding the uncertainty sets, one can solve those problems efficiently. We have experienced robust optimization formulations of corporate portfolio optimization problems and risk management problems in the pharma sector.
Stochastic optimization
If the changes in the input can be significant, one is not interested in generating
a robust solution but rather generating a solution that guarantees a certain
stochastic measure such as a best average performance. In that case, we move
to the space of stochastic optimization. As one would expect, this field of
study is extremely broad, but we have developed stochastic optimization expertise
in the specific context of inventory control, thanks to our development around
DIOS.