|
|
 |
|
Jeudi 6 Novembre
| Heure: |
10:30 - 12:00 |
| Lieu: |
Salle D215, Université de Villetaneuse |
| Résumé: |
Aircraft routing: periodicity and complexity |
| Description: |
Frédéric Meunier The aircraft routing problem is one of the most relevant problems of operations research applied to aircraft management. It involves assigning flights to aircraft while ensuring regular visits to maintenance bases. This work examines two aspects of the problem.
First, we explore the relationship between periodic instances, where flights are the same every day, and periodic solutions. The literature has implicitly assumed without discussion that instances necessitate periodic solutions, and even periodic solutions in a stronger form, where every two airplanes perform either the exact same cyclic sequence of flights, or completely disjoint cyclic sequences. However, enforcing such periodicity may eliminate feasible solutions. We prove that, when regular maintenance is required at most every four days, there always exist periodic solutions of this form. Second, we consider the computational hardness of the problem. Even if many papers in this area refer to the NP-hardness of the aircraft routing problem, such a result is only available in the literature for periodic instances. We establish its NP-hardness for a non-periodic version. Polynomiality of a special but natural case is also established.
Joint work with Axel Parmentier and Nour ElHouda Tellache |
Mardi 18 Novembre
| Heure: |
14:00 - 16:00 |
| Lieu: |
Salle G201 |
| Résumé: |
Partitioning a Graph into Connected Components |
| Description: |
Hande Yaman In this talk, we study problems that involve partitioning the vertices of an undirected graph into a given number of pairwise disjoint sets such that each set induces a connected subgraph. We first propose valid inequalities, which extend and generalize the ones in the literature, and report on computational experiments demonstrating their use (joint work with P. Moura and R. Leus). Then, we extend this problem to also compute a spanning tree for each set of the partition such that the weight of the heaviest tree is minimized. We investigate the complexity of this problem and present formulations and solution methods, which we compare with an experimental study (joint work with M. Davari and P. Moura). Finally, we consider a practical problem encountered in power system restoration, which involves partitioning a power network into connected subnetworks, one for each black start generator, such that the restoration time is minimized. We propose a solution method that uses a new formulation and properties of optimal solutions and report computational results (joint work with H. Çal?k and D. Van Hertem). |
Jeudi 20 Novembre
| Heure: |
10:30 - 12:00 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Frank-Wolfe methods for convex quadratic optimization |
| Description: |
Mathieu Besançon I will go over some recent results on Frank-Wolfe methods, presenting the core aspects of the algorithms and highlight properties of the algorithms that make them relevant for convex quadratic optimization, despite the first-order access to the objective. In particular, we will go over the active set identification property some Frank-Wolfe variants enjoy and a use of linear system or linear optimization solvers to accelerate convergence and reach finite-time guarantees.
I will then present one application to sparse flow decomposition for RNA-seq data analysis. |
|
|
