CORS / Optimization Days 

HEC Montréal, May 29-31, 2023


HEC Montreal, 29 — 31 May 2023

Schedule Authors My Schedule

SPI Stochastic Programming I

May 29, 2023 10:30 AM – 12:10 PM

Location: Xerox Canada (yellow)

Chaired by Bita Payami

4 Presentations

  • 10:30 AM - 10:55 AM

    Branch-and-Benders-cut algorithm for Multicommodity Network Design under Stochastic Interdictions

    • Shabnam Mahmoudzadeh Vaziri, presenter, PhD Candidate, Concordia University
    • Onur Kuzgunkaya, Associate Professor, Concordia University
    • Navneet Vidyarthi, Concordia University

    This paper presents a tri-level 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 worst-case 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 tri-level stochastic model with branch-and-Benders-cut algorithm improved by enhancement techniques such as Pareto-optimal 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.

  • 10:55 AM - 11:20 AM

    Effective Solution Approaches for a Lot Sizing Problem with Bounded Inventory and Stochastic Times

    • Duygu Tas, presenter, Sabancı University

    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 two-stage 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 well-known problem instances and comprehensive analyses are provided.

  • 11:20 AM - 11:45 AM

    Leveraging Decision Diagrams to Solve Two-stage Stochastic Programs with Binary Recourse and Logical Linking Constraints

    • Moira MacNeil, presenter, University of Toronto
    • Merve Bodur, University of Toronto

    We convexify the second stage of two-stage 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 BDD-based approach to allow settings where logical expressions of the first-stage solutions enforce constraints in the second stage. We also propose a complementary problem where second-stage objective coefficients are impacted by logical expressions of the first-stage decisions, and develop a distinct BDD-based algorithm to solve this novel problem class. We extend this work by incorporating conditional value-at-risk 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.

  • 11:45 AM - 12:10 PM

    A Study on managing the impact of climate change on Scheduled Service Network Design

    • Bita Payami Shabestari, presenter, Phd student
    • Ioana Bilegan, Assoc.Professor
    • Teodor Gabriel Crainic, Professor
    • Walter Rei, Professor

    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 consolidation-based 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 tactical-planning service network design models.

    Scheduled service network design, Revenue and resource management, Stochastic programming,
    Barge transportation system