This work addresses the job shop scheduling problem under energy considerations, more specifically the minimization of the total energy cost under a Time-of-Use pricing and a limit on the peak of the power consumption, denoted as Jm|Pmax|TEC. The most efficient approach up-to-date to this recently introduced problem relies on a Mixed-Integer Linear Programming formulation which makes use of traditional time-indexed variables, resulting in difficulties with instances with a large time horizon.
To overcome this aspect, we propose for the Jm|Pmax|TEC a Branch&Cut approach based on a period-indexed MILP formulation and the lazy separation of power limit violation constraints.
The method is then enhanced with different families of valid inequalities to improve the linear relaxation bound of the MILP model.
Computational experiments and numerical results are presented to show that this new method outperforms the previously best known one.
This is a joint work with Marouane Felloussi et Xavier Delorme.

15h15 - 15h45 : Hard problems on box-totally dual integral polyhedra

Exposé de Francesco Pisanu

 A rational linear system is totally dual integral (TDI) if for every integer linear function for which the optimum is finite the associated dual problem has an integer optimal solution. A TDI system is box-TDI if adding any rational bounds on the variables preserves its TDIness. Box-TDI systems are systems that yield strong min-max relations such as the one involved in the Max Flow-Min Cut Theorem of Ford and Fulkerson.  Cook proved that box-TDIness is a polyhedral property, therefore polyhedra that can be described by box-TDI systems are called box-TDI polyhedra.
Box-TDI polyhedra characterize the following generalization of the well-known totally unimodular matrices. A matrix is totally equimodular (TE) if for each subset of linearly independent rows, the corresponding nonzero maximal minors have the same absolute value. A matrix A is TE if and only if any polyhedron described by A is box-TDI for each rational RHS.
In this work, we prove that the problem of deciding whether a given polyhedron is box-TDI is co-NP-complete. We also prove that the edge-vertex incidence matrix of any graph is TE. As a consequence of Karp's hardness result on the maximum stable set problem, this implies that integer programming over box-TDI polyhedra is NP-hard.

This is a joint work with Patrick Chervet, Roland Grappe, Mathieu Lacroix, and Roberto Wolfer Calvo.

16h15 - 16h45 : Balanced assignments of periodic tasks

Exposé de Frédéric Meunier

16h45 - 17h15 : Machine Learning Guided Optimization for Demand Responsive Transport Systems

Exposé d'Emiliano Traversi

Most of the time, objective functions used for solving static combinatorial optimization problems cannot deal efficiently with their real-time counterparts. It is notably the case of Shared Mobility Systems where the dispatching framework must adapt itself dynamically to the demand. More precisely, in the context of Demand Responsive Transport (DRT) services, various objective functions have been proposed in the literature to optimize the vehicles routes. However, these objective functions are limited in practice because they discard the dynamic evolution of the demand. To overcome such a limitation, we propose a Machine Learning Guided Optimization methodology to build a new objective function based on simulations and historical data. This way, we are able to take the demand’s dynamic evolution into account. We also present how to design the main components of the proposed framework to fit a DRT application: data generation and evaluation, training process and model optimization. We show the efficiency of our proposed methodology on real-world instances, obtained in a collaboration with Padam Mobility, an international company developing Shared Mobility System.

17h15 - 17h45 : A branch-and-price algorithm for the Minimum Sum Coloring Problem

Exposé de Diego Delle Donne

A proper coloring of a given graph is an assignment of a positive integer number(color) to each vertex such that two adjacent vertices receive different colors. This paper
studies the Minimum Sum Coloring Problem (MSCP), which asks for finding a proper coloring while minimizing the sum of the colors assigned to the vertices. We propose
the first branch-and-price algorithm to solve the MSCP to proven optimality. The newly developed exact approach is based on an Integer Programming (IP) formulation with
an exponential number of variables which is tackled by column generation. We present extensive computational experiments, on synthetic and benchmark DIMACS graphs from the literature, to compare the performance of our newly developed branch-and-price algorithm against three compact IP formulations. On synthetic graphs, our algorithm outperforms the compact formulations in terms of: (i) number of solved instances, (ii) running times and (iii) exit gaps obtained when optimality is not achieved. For the DIMACS instances, our algorithm is competitive with the best compact formulation and provides very strong dual bounds.