Objectif

Ce séminaire est organisé en l'honneur de Roberto Wolfler Calvo. Il consiste en une série d'exposés de chercheuses et chercheurs ayant collaboré avec lui.

 

image25.jpg

 

Lieu : Institut Henri Poincaré, Salle E. Noether,11 Rue Pierre et Marie Curie, 75005 Paris

Programme

  • 14h00 - 14h15: Ouverture de la conférence
  • 14h15 - 14h45 : exposé de Sandra U. NGUEVEU
  • 14h45 - 15h15 : exposé de Paolo Gianessi
  • 15h15 - 15h45 : exposé de Francesco Pisanu
  • 15h45 - 16h15 : Pause
  • 16h15 - 16h45 : exposé de Fredéric Meunier
  • 16h45 - 17h15 : exposé de Emiliano Traversi
  • 17h15 - 17h45 : exposé de Diego Delle Donne
  • 17h45 - 20h00 : Cocktail

 

14h15 - 14h45 : Title to appear

Exposé de Sandra U. NGUEVEU

Abstract to appear
 
 

14h45 - 15h15 : Minimizing Energy Cost in a Job-Shop Scheduling Problem under TOU pricing and a power peak limit: a new Method based on a Period-Indexed MILP

Exposé de Paolo Gianessi

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

This talk deals with the problem of assigning periodic tasks to employees in such a way that each employee performs each task with the same frequency in the long term. The motivation comes from a collaboration with the SNCF, the main French railway company. We provide an almost complete solution under the form of a necessary and sufficient condition that can be checked in polynomial time. Possible extensions will also be discussed. Joint work with Héloïse Gachet

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.





 
Personnes connectées : 1 Vie privée
Chargement...