SCRO / Journées de l'optimisation
HEC Montréal, 2931 mai 2023
CORSJOPT2023
HEC Montréal, 29 — 31 mai 2023
SPI Stochastic Programming I
29 mai 2023 10h30 – 12h10
Salle: Xerox Canada (jaune)
Présidée par Bita Payami
4 présentations

10h30  10h55
BranchandBenderscut algorithm for Multicommodity Network Design under Stochastic Interdictions
This paper presents a trilevel mathematical model for designing resilient multicommodity networks. In this problem, the designer first selects the design decisions (arc installation) and the flow decisions in normal conditions by considering the effects of worstcase disruptions (intentional attacks). Next, the interdictor interdicts some arcs of the network to cause maximum damage. After the interdiction, the designer optimizes the network over surviving arcs. We consider the stochastic design model as the designer does not have information about the interdictor’s budget. We solve the trilevel stochastic model with branchandBenderscut algorithm improved by enhancement techniques such as Paretooptimal cuts, penalty reformulation, valid inequalities, warm start, and variable fixing. We show that the enhancement techniques reduce CPU time by up to 51%. We also demonstrate that the stochastic design provides a more resilient network than the deterministic design when the budget of the interdictor is unknown.

10h55  11h20
Effective Solution Approaches for a Lot Sizing Problem with Bounded Inventory and Stochastic Times
We consider a lot sizing problem with bounded inventory and with stochastic production and setup times following a given probability distribution. The aim of this problem is to minimize the total cost including the regular production costs plus the expected overtime costs. Demands are met using a single capacitated machine which can produce several different items in each time period. More specifically, the machine capacity is consumed both by production and by setup operations. In this setting, overtime costs are incurred in case the machine is used beyond its capacity. Additionally, the level of the inventory at the end of each time period is assumed to be bounded. The proposed problem is formulated as a twostage stochastic programming with recourse decisions. Two approximate solution approaches are developed. In the first approach, initial solutions are obtained by solving the classical capacitated lot sizing problem with deterministic overtime and bounded inventory, and then improved by applying a tabu search algorithm. The second approach is based on solving the stochastic programming with a set of sample scenarios. The computational experiments are conducted on wellknown problem instances and comprehensive analyses are provided.

11h20  11h45
Leveraging Decision Diagrams to Solve Twostage Stochastic Programs with Binary Recourse and Logical Linking Constraints
We convexify the second stage of twostage stochastic programs (2SPs) with binary recourse using binary decision diagrams (BDDs) to make the problem amenable to Benders decomposition algorithm. More specifically, we first generalize an existing BDDbased approach to allow settings where logical expressions of the firststage solutions enforce constraints in the second stage. We also propose a complementary problem where secondstage objective coefficients are impacted by logical expressions of the firststage decisions, and develop a distinct BDDbased algorithm to solve this novel problem class. We extend this work by incorporating conditional valueatrisk and we propose, to our knowledge, the first decomposition method for 2SPs with binary recourse and a risk measure. We apply these methods to a novel stochastic dominating set problem and present numerical results to demonstrate the effectiveness of the proposed methods.

11h45  12h10
A Study on managing the impact of climate change on Scheduled Service Network Design
We address scheduled service network design with resource and revenue management problem with uncertainty on the supply side of the freight transportation system, whereas previous research often addressed the source of uncertainty on the demand side of the system. This problem arises in the tactical planning process of consolidationbased freight carriers in barge transportation systems when changes in water levels caused by weather changes jeopardize the regular plan that carriers use to meet a given or estimated shippers’ demand efficiently, profitably, and within quality standards agreed upon with the shippers generating this demand. To address this challenge, we first define a general modeling framework that takes into account the relationship between the services supported by vessels and the water level. We then propose a stochastic modeling approach that uses probability distributions to model water level changes associated with each physical link and moving arc, and we explore various modeling frameworks to manage water level uncertainties in tacticalplanning service network design models.
Keywords:
Scheduled service network design, Revenue and resource management, Stochastic programming,
Barge transportation system