Seminars_2024_aug_dec

Cette recherche est menée pour examiner une approche d’optimisation distributionnellement robuste appliquée au problème de dimensionnement de lots avec des retards de production et une incertitude de rendement sous des ensembles d’ambiguïté par événement. Les ensembles d’ambiguïté basés sur les moments, Wasserstein et le clustering K-Means sont utilisés pour représenter la distribution des rendements. Des stratégies de décision statiques et statiques-dynamiques sont également considérées pour le calcul d’une solution. Dans cette présentation, la performance de différents ensembles d’ambiguïté sera présentée afin de déterminer un plan de production qui soit satisfaisant et robuste face aux changements de l’environnement. Il sera montré, à travers une expérience numérique, que le modèle reste traitable pour tous les ensembles d’ambiguïté considérés et que les plans de production obtenus demeurent efficaces pour différentes stratégies et contextes décisionnels.

Real-world industrial applications frequently confront the task of decision-making under uncertainty. The classical paradigm for these complex problems is to use both machine learning (ML) and combinatorial optimization (CO) in a sequential and independent manner. ML learns uncertain quantities based on historical data, which are then used used as an input for a specific CO problem. Decision-focused learning is a recent paradigm, which directly trains the ML model to make predictions that lead to good decisions. This is achieved by integrating a CO layer in a ML pipeline, which raises several theoretical and practical challenges.

Hub Labeling (HL) is a state-of-the-art method for answering shortest-distance queries between node pairs in weighted graphs. It provides very fast query times but also requires considerable additional space to store the label information. Recently, a generalization of HL, called Landmark Hub Labeling (LHL), has been proposed, that conceptionally allows a storage of fewer label information without compromising the optimality of the query result. However, query answering with LHL was shown to be slower than with HL, both in theory and practice. Furthermore, it was not clear whether there are graphs with a substantial space reduction when using LHL instead of HL.

Separable states are multipartite quantum states that can be written as a convex combination of product states. Product states are multipartite quantum states that can be written as a tensor product of states in each space. Quantum state separable problem is an NP-hard problem but fundamental for quantum information theory. We propose two relaxation techniques for this problem. In the view of commutative optimization, we treat the states as matrices of multilinear complex polynomials. Our relaxation technique is found similar to that for complex bilinear polynomials arising in the Alternating Current Optimal Power Flow problem. In the view of non-commutative optimization, we treat the states as tensor products of bounded Positive Semi-definite variables. We propose a generalized McCormick relaxations using linear matrix inequalities. These two relaxations will be the key component to drive an exact branch-and-cut algorithm.

On s’intéresse au problème d’optimiser une fonction objectif \(g(W x) + c^T x\) pour \(x\) entier, où chaque coordonnée de \(x\) est contrainte dans un intervalle. On suppose que la matrice \(W\) est à coefficient entiers de valeur absolue bornée par \(\Delta\), et qu’elle projette \(x\) sur un espace de petite dimension \(m << n\). Ce problème est une généralisation du résultat de Hunkenschröder et al. dans lequel \(g\) est séparable convexe, et \(x\) est dans un \(0-1\) hypercube.

Column elimination is an exact algorithm to solve discrete optimization problems via a ‘column’ formulation in which variables represent a combinatorial structure such as a machine schedule or truck route. Column elimination works with a relaxed set of columns, from which infeasible ones are iteratively eliminated. As the total number of columns can typically be exponentially large, we use relaxed decision diagrams to compactly represent and manipulate the set of columns. In this talk, we provide an introduction to the column elimination method and present recent algorithmic improvements resulting in competitive performance on large-scale vehicle routing problems. Specifically, our approach closes a large vehicle routing benchmark instance with 1,000 locations for the first time.

Due to the complexity of real-world planning processes addressed by major transportation companies, decisions are often made considering subsequent problems at the strategic, tactical, and operational planning phases. However, these problems still prove to be individually very challenging. This talk will present two examples of tactical transportation problems motivated by industrial applications: the Train Timetabling Problem (TTP) and the Service Network Scheduling Problem (SNSP). The TTP aims at scheduling a set of trains, months to years before actual operations, at every station of their path through a given railway network while respecting safety headways. The SNSP determines the number of vehicles and their departure times on each arc of a middle-mile network while minimizing the sum of vehicle and late commodity delivery costs. For these two problems, the consideration of capacity and uncertainty in travel times are discussed. We present models and solution approaches including MILP formulations, Tabu search, Constraint Programming techniques, and a Progressive Hedging metaheuristic.

In the Kidney Exchange Problem (KEP), we consider a pool of altruistic donors and incompatible patient-donor pairs. Kidney exchanges can be modelled in a directed weighted graph as circuits starting and ending in an incompatible pair or as paths starting at an altruistic donor. The weights on the arcs represent the medical benefit which measures the quality of the associated transplantation. For medical reasons, circuits and paths are of limited length and are associated with a medical benefit to perform the transplants. The aim of the KEP is to determine a set of disjoint kidney exchanges of maximal medical benefit or maximal cardinality (all weights equal to one).

In this talk we present an information discovery framework in optimization under uncertainty. In this framework, uncertain parameters are assumed to be “discoverable” by the decision-maker under a given discovery (query) budget. The decision-maker therefore decides which parameters to discover (query) in a first stage then solves an optimization problem with the discovered uncertain parameters at hand in a second stage. We model this problem as a two-stage stochastic program and develop decomposition algorithms for its solution. Notably, one of the algorithms we propose reposes on a Dantzig-Wolfe reformulation of the recourse problem. This allows to treat the cases where the recourse problem involves binary decisions without relying on integer L-Shaped cuts. In its implementation, this approach requires to couple Benders’ and Dantzig-Wolfe reformulation with the subproblems of the Benders’ algorithm being solved using the column generation algorithm. We present some preliminary results on the kidney exchange problem under uncertainty of the compatibility information.

Our work aims to quantify the benefit of storage flexibilities such as a battery on several short term electricity markets. We especially focus on two different markets, the intraday market (ID) and the activation market of the automatic Frequency Restoration Reserve (aFRR), also known as the secondary reserve. We propose algorithms to optimize the management of a small battery (<= 5 MWh) on these markets. In this talk, we first present the modeling of the problem, then we show some theoretical results and numerical simulations. We conclude by listing some limitations of the method.

Un paradigme usuel pour l’étude d’algorithmes online est l’analyse compétitive, qui correspond à étudier le pire cas d’un algorithme sur toutes ses entrées possibles. Cependant, une telle analyse peut parfois être trop grossière pour être réellement intéressante. Pour contourner ce problème, il est possible de considérer des algorithmes aléatoires - c’est-à-dire des algorithmes dont le comportement est aléatoire. Cet exposé présentera des méthodes computationnelles pour étudier les algorithmes aléatoires dans le problème classique du online bin stretching, à partir d’outils de théorie des jeux et de programmation linéaire.