We consider mixed-integer stochastic linear programs, which, under some Markovian assumptions, can be
solved using Dynamic Programming principles. Were the problem convex, we could use the Stochastic Dual
Dynamic Programming (SDDP) algorithm, shown to be efficient in solving large-scale problems. Unfortunately,
relaxing all integrality constraints performs poorly. Moreover, if the problem is too large e.g., with more than a
few time steps, the extensive formulation becomes intractable.
In order to strike a balance between a complete relaxation and the exact problem, we propose to relax
partially the integrality constraints. To take advantage of the structure of the problem, if we relax the integrality
constraints in a node, then we also relax them in all its descendants: this whole section of the initial scenario tree
can be approximated using SDDP. Then, we solve the extensive formulation of a stochastic sub-tree T , where
we keep the integrality constraints in the nodes in T , while the leaves of T leverage the SDDP algorithm, to
solve the problem.
Naturally, the problem formulation gets more complex as the size of T gets larger. Further, the choice of
nodes in T might be decisive to get a good lower-bound fast, but more importantly better first-stage integer
decisions. Therefore, we propose different heuristics to iteratively grow the sub-tree T , inspired by branching
methods in integer programming. We then compare the obtained strategies tested on different simple examples
inspired by production problems with either shared resource constraints, minimum uptime/downtime constraints
or counters constraints.

The vehicle scheduling problem (VSP) is one of the sub-problems of public transport
planning. It aims to minimize operational costs while assigning exactly one bus per
timetabled trip and respecting the capacity of each depot. Public transport planning is
subject to various endogenous and exogenous causes of uncertainty, notably
affecting travel time and energy consumption. Despite the uncertainties involved, the
VSP and its variants are usually solved deterministically to address trackability
issues. However, considering deterministic travel time in the VSP can compromise
schedule adherence, whereas considering deterministic energy consumption in the
electric VSP (E-VSP) may lead to solutions with sub-optimal true costs (including
recourse costs and the cost of ownership of battery electric buses).
This presentation proposes a methodological framework aimed at integrating
uncertainties, specifically travel time and energy consumption uncertainties, into the
VSP. Three distinct stochastic, data-driven mathematical models and branch-and-
price algorithms are introduced to address two variations of the problem: the multi-
depot VSP (MDVSP) and the electric VSP (E-VSP). The objective is to find bus
schedules that offer a good trade-off between operational costs and service reliability,
as well as between operational costs and battery degradation in electric buses.

This study addresses a production planning problem considering end products that are obtained through the blending of components. We approach the problem using mathematical programming formulations assuming integrated lot sizing decisions for components purchase and end products production over a finite planning horizon. The objective is to minimize setup, production, purchase, inventory, and lost sales costs, while incorporating constraints related to inventory balance, machine capacity, and quality standards. We extend the deterministic approaches explored in the literature by incorporating demand uncertainty through a two-stage stochastic programming formulation. The proposed formulation is designed to identify stochastic solutions based on the static uncertainty strategy derived from stochastic lot sizing problems. Our solution methodology encompasses an approximation procedure using finite samples to estimate bounds and identify stochastic candidate solutions for the problem. Enhancements are explored for the optimization routines, including adjustable strategies by fixing the value of some first-stage variables based on multiple candidate solutions, Benders decomposition techniques employed with a commercial solver, and specialized algorithms. Finally, we conduct a numerical evaluation of our proposed approaches through computational experiments using test instances based on randomly generated data. This research contributes insights into using stochastic lot sizing strategies for addressing demand uncertainty in integrated production planning and blending problems.