Seminars_2025_aug_dec

In this thesis, we are interested in problems that can be formulated as a sequence of decisions, where dynamic programming is a suitable modeling paradigm. To solve large-scale problems, we study aggregation and disaggregation methods that allow us to construct relaxations of the problem, which are solved to obtain optimistic solutions to these problems. Iterative algorithms are then designed from these relaxations, where the relaxations provide less optimistic solutions as the number of iterations increases. In this thesis, we first provide a literature review of the aggregation and disaggregation methods in the context of dynamic programming formulations. Then, we propose a problem modeling the aggregation of vertices in decision graphs of dynamic programs to construct relaxations and show that many aggregation methods in the literature are special cases of this problem. We then study an application of network flow formulations in a decision hypergraph, and extend some aggregation methods to this case. To validate our approaches, we present computational results on a set of different problems and compare them to similar approaches in the literature. We conclude this thesis with a discussion on the results obtained and propose some perspectives for future work.

We study the Vehicle Routing Problem with Stochastic Demands (VRPSD), which involves optimizing delivery routes for vehicles with limited capacity to serve customers whose demands are unknown when designing the routes. The routes are designed taking into account the possibility that a route may have too much demand for the capacity of a vehicle to be delivered, in that case recourse actions can be taken, inducing a cost. This problem seeks to minimize routing costs and the expected recourse costs.

This thesis focuses on the modeling and solution methods for facility location and network design problems under uncertainty, with a particular emphasis on robust optimization with integer recourse. The application studied concerns the blood supply chain in the context of disasters, where demand is uncertain, infrastructures may be damaged, and an emergency response must be implemented.

In this work, we developed several mathematical formulations based on discrete uncertainty sets, incorporating different risk measures: the expectation, the Conditional Value-at-Risk (CVaR), and the worst-case approach. To solve these models, we implemented decomposition techniques, including Benders decomposition (in its multi-cut and stabilized variants) and the Column-and-Constraint Generation (CCG) algorithm. To improve solution quality, especially for large-scale instances, we also proposed an adjustable robust model based on continuous uncertainty sets. Using different types of sets, we applied affine decision rules as well as a static approach for recourse decisions in order to ensure tractability.

We study a robust extensible bin packing problem with budgeted uncertainty, under a budgeted uncertainty model where item sizes are defined to lie in the intersection of a box with a one-norm ball. We propose a scenario generation algorithm for this problem, which alternates between solving a master robust bin-packing problem with a finite uncertainty set and solving a separation problem. We first show that the separation is strongly NP-hard given solutions to the continuous relaxation of the master problem. Then, focusing on the separation problem for the integer master problem, we show that this problem becomes a special case of the continuous convex knapsack problem, which is known to be weakly NP-hard. Next, we prove that our special case when each of the functions is piecewise linear, having only two pieces, remains NP-hard. We develop a pseudo-polynomial dynamic program (DP) and a fully polynomial-time approximation scheme (FPTAS) for our special case whose running times match those of a binary knapsack FPTAS. Finally, our computational study shows that the DP can be significantly more efficient in practice compared with solving the problem with specially ordered set (SOS) constraints using advanced mixed-integer (MIP) solvers. Our experiments also demonstrate the application of our separation problem method to solving the robust extensible bin packing problem, including the evaluation of deferring the exact solution of the master problem, separating based on approximate master solutions in intermediate iterations. Finally, a case-study, based on real elective surgery data, demonstrates the potential advantage of our model compared with the actual schedule and optimal nominal schedules.

Vehicle routing problems (VRPs) are a fundamental piece of logistics planning. Exact methods for the classic capacitated VRP (CVRP) have seen significant advancements over the last ten years, pushing the boundaries of problem sizes that can be efficiently solved to optimality. Standard benchmark CVRP instances having hundreds of customers can be solved to proven optimality within seconds or a few minutes. Nevertheless, the picture is far less promising for other CVRP variants, especially variants that embed delivery decisions in the modelling. For some of these problems, instances with fewer than one hundred – or even a few dozen – customers can be challenging enough. We develop Branch-cut-and-price (BCP) algorithms, the current state-of-the-art approach for solving CVRP problems exactly, for two VRP variants with delivery decisions, namely the split delivery VRP with (SDVRPTW) or without time windows (SDVRP), and the inventory routing problem (IRP). For these problems, the best performing approaches in the literature are mainly Branch-and-cut (B&C) algorithms. Thus, we aim at designing BCP algorithms, adapting state-of-the-art BCP algorithmic components designed for the CVRP to these problems, to assess whether these algorithms can solve large instances and be competitive with tailored B&C for these problems.

On considère des tâches devant être exécutées chaque semaine à des horaires précis, ainsi qu’un certain nombre de travailleurs indiscernables chargés de les accomplir. Nous abordons le problème de l’affectation de ces tâches périodiques de manière équilibrée, c’est-à-dire de façon à ce que chaque travailleur réalise chaque tâche avec la même fréquence sur le long terme. Deux versions de ce problème sont considérées : la version de base, où la seule contrainte est qu’un travailleur ne peut pas effectuer deux tâches simultanément, et la version étendue, où l’on peut introduire des contraintes supplémentaires restreignant les plannings hebdomadaires valides.

In this work, we study a variant of the Vehicle Routing Problem with Time Windows (VRPTW), which integrates two operationally relevant features: flexible departure times from the depot and strict limits on route duration. The resulting problem, termed VRPTW with Route Duration Constraint (VRPTWDC), introduces a scheduling dimension that makes the routing computationally challenging and largely unexplored in the literature. We develop an exact branch-cut-and-price algorithm, having as its main feature a bi-bidirectional labeling algorithm for solving the complex pricing subproblem. Indeed, as the only previously proposed efficient labeling algorithm for the VRPTWDC has a mistake, we provide rigorous proofs of its correctness. Computational experiments on benchmark instances demonstrate the effectiveness of the approach.

Nous étudions un problème de découpe avec restes réutilisables et incertitudes sur les demandes. Dans la littérature, une formulation stochastique à deux étapes du problème a était proposé. Nous introduisons une formalisation du problème avec un nombre arbitraire d’étapes. Puis, nous introduisons des méthodes de résolutions exactes axées sur la reformulation du problème en problème de flots dans des graphes ou hypergraphes. Pour les instances du problème avec un grand nombre de scénarios, nous proposons des méthodes de relaxation afin de calculer des bornes inférieures quand la relaxation linéaire ne peux être obtenue. Enfin, nous testons la pertinence de l’approche stochastique à l’aide d’un horizon roulant et en testant différents types d’oracle. Nous comparons nos différentes formulations pour des instances à deux étapes avec les instances de la littérature. Nous comparons également nos bornes inférieures introduites et nous montrons que certaines permettent d’aller plus loin en nombre d’étapes que la relaxation linéaire. Enfin, nous montrons qu’effectuer un horizon roulant avec un oracle à trois étapes permet de faire plus d’économies comparé à un oracle à deux étapes sur les instances de la littérature.