Abstract : Here is the program of the day. Note that some swapping of the slots is possible.

Abstract : We consider the problem of minimizing the sum of univariate nonconvex functions on a polyhedral domain. We introduce an iterative method with optimality guarantees given an arbitrary numerical precision target. It relies on a precision-driven refinement procedure that computes an optimal domain partitioning at each iteration. We provide a formal proof of the convergence and scalability of our method. We show for example that in the worst case, our method performs O(log(n)) iterations, where n is the maximum number of iterations required by other state-of-the-art methods based on adaptive multivariate partitioning algorithms to achieve the desired precision. Numerical results confirm that our method scales better than a naive variant of the method that avoids performing successive iterations in exchange of solving a much larger mixed-integer linear program. A key component of the algorithm is the computation of optimal precision-driven initialization and precision-driven refinement of piecewise linear approximations of nonlinear functions. The resulting subproblems are semi-infinite programs that can be solved efficiently by leveraging the previously developed Julia-based package LinA (http://homepages.laas.fr/sungueve/LinA.html).

Abstract : Optimal transport (OT) has recently gained a lot of interest in machine learning. It is a natural tool to compare in a geometrically faithful way probability distributions. It finds applications in both supervised learning (using geometric loss functions) and unsupervised learning (to perform generative model fitting). OT is however plagued by several issues, and in particular: (i) the curse of dimensionality, since it might require a number of samples which grows exponentially with the dimension, (ii) sensitivity to outliers, since it prevents mass creation and destruction during the transport (iii) impossibility to transport between two disjoint spaces. In this talk, I will review several recent proposals to address these issues, and showcase how they work hand-in-hand to provide a comprehensive machine learning pipeline. The three key ingredients are: (i) entropic regularization which defines computationally efficient loss functions in high dimensions (ii) unbalanced OT, which relaxes the mass conservation to make OT robust to missing data and outliers, (iii) the Gromov-Wasserstein formulation, introduced by Sturm and Memoli, which is a non-convex quadratic optimization problem defining transport between disjoint spaces. More information and references can be found on the website of our book "Computational Optimal Transport" https://optimaltransport.github.io/

Abstract : We introduce the Train Timetabling Problem (TTP) that consists in defining the optimal schedule for a set of trains in a railway network. TTP has to be solved at tactical level several months before the timetables are made public. We present Integer Linear Programming models for the TTP, which are based on the representation of the problem on a time-expanded graph, and propose decomposition algorithms to compute (heuristic) solutions. We then show how they can be extended to include skip-stop planning strategies and passenger-centric objectives to tackle real-life case studies.

Abstract : This talk will discuss the application of job shop scheduling to reschedule trains during rail operations. Dr. D'Ariano will briefly describe the potential of mathematical models plus advanced scheduling and routing algorithms based on the alternative graph representation with consideration of railway business rules and objectives. He will present computational results on a case study in collaboration with industrial partners.

Abstract : The Capacitated Location-Routing Problem consists in, given a set of locations and a set of customers, determine in which locations one should install depots with limited capacity, and for each depot, design a number of routes to supply customer demands. We provide a formulation that includes depot variables, edge variables, assignment variables and an exponential number of route variables, together with some new families of valid inequalities, leading to a branch-cut-and-price algorithm. The main original methodological contribution of this work is a family of non-robust cuts, which we call the Route Load Knapsack Cuts. They are defined over the route variables, devised to strengthen the depot capacity constraints. We explore the monotonicity and the superadditivity properties of those cuts to adapt the labeling algorithm, used in the pricing, for handling the additional dual variables efficiently. Computational experiments show that several Capacitated Location-Routing previously unsolved instances from the literature can now be solved to optimality. Additional experiments with hard instances of the Vehicle Routing Problem with Capacitated Multiple Depots and with instances of the Vehicle Routing Problem with Time Windows and Shifts indicate that the newly proposed cuts are also effective for those problems.

Abstract : We present results on the theoretical complexity of branch-and-bound, cutting plane, and branch-and-cut algorithms in linear/convex mixed-integer optimization. In particular, we study the relative efficiency of branch-and-bound and cutting plane algorithms, showing conditions under which one method can dominate the other, depending on which cutting plane paradigm and branching scheme one chooses. We also give general conditions under which a cutting plane strategy and a branching scheme give a provably exponential advantage in efficiency when combined into branch-and-cut. This yields some rigorous underpinnings to the empirically observed phenomenon that combining cutting planes and branching into a branch-and-cut framework can be orders of magnitude more efficient than employing these tools on their own. The efficiency of these algorithms is evaluated using two concrete measures: number of iterations and sparsity of the constraints used in the intermediate linear/convex programs.