V. SONIA, W. Romain, H. Wattez
The unsplittable multicommodity flow problem appears in various applications such as in telecommunication networks and smart urban mobility. We focus on energy efficiency in wireless networks. Given a bi-directed graph, unsplittable traffic demands. We seek to find a unique routing path for each demand that minimizes the total energy cost under capacity and demand constraints. This problem generalizes the bin packing and disjoint path problems which are NP-hard. To efficiently solve this NP-hard combinatorial problem, we consider different approaches and compare empirically their performances. The first approach is based on the polyhedral study of the problem. We use the bin packing structure of our problem to develop new valid inequalities. We also propose new approaches combining the efficiency of constraint programming, pseudo-Boolean and SAT solvers with mathematical programming methods.
Palabras clave: Unsplittable multicommodity flow problems, valid inequalities, pseudoboolean reasoning, constraint programming
Programado
Modelos y Métodos de la Investigación Operativa
9 de junio de 2022 17:10
A16
