JOPT2025

HEC Montreal, 12 — 14 May 2025

JOPT2025

HEC Montreal, 12 — 14 May 2025

Schedule Authors My Schedule

Decomposition Methods I

May 12, 2025 03:30 PM – 05:10 PM

Location: BMO (Green)

Chaired by Mario José Basallo Triana

4 Presentations

  • 03:30 PM - 03:55 PM

    Power transmission network expansion planning: A semidefinite programming Benders Decomposition approach

    • Elmira Fathipasandideh, presenter,
    • Hanane Dagdougui, Ecole Polytechnique de Montréal

    The transmission network expansion planning (TNEP) problem is inherently complex due to its nonlinear
    and non-convex nature, arising from the inclusion of AC power flow constraints, discrete investment decisions, and multiple operating scenarios. These characteristics make the problem computationally challenging, especially when scaling to larger systems with multistage planning horizons. Addressing this complexity requires advanced methodologies that balance solution accuracy and computational efficiency. This paper presents a
    novel two-step framework for TNEP that first applies Benders decomposition to separate the investment and operational decisions, followed by semidefinite linearization to reformulate the operational subproblems. The proposed approach enhances solution quality by ensuring convexity in the subproblems and improves computational efficiency through decomposition. Numerical results on 6-bus, 10-bus, and 24-bus test systems demonstrate
    that the proposed method achieves superior performance compared to existing approaches in terms of solution accuracy and computational efficiency

  • 03:55 PM - 04:20 PM

    Integrated Optimal Inventory Sharing Policy for Waste Reduction in Retail Grocery: A Benders Decomposition Approach

    • Fatemeh Keshavarz Ghorbani, University of Windsor
    • Guoqing Zhang, presenter, University of Windsor
    • Kevin Li, University of Windsor

    We propose an integrated optimal inventory sharing policy for retailers participating in both donation initiatives and third-party online platforms. To model this innovation, we develop a multi-stage stochastic-robust programming framework that incorporates the stochastic demand of the primary channel and the robust demand for imperfect products in the third-party channel. We employ an accelerated two-phase Benders decomposition to address the NP-hard nature of the multi-stage scenario-based MILP problem. Given the structure of the master problem, we decompose and solve it in two phases, significantly reducing computational time. We demonstrate that the proposed solution method reduces computational time significantly.

  • 04:20 PM - 04:45 PM

    A Relaxation-Based Decomposition Approach for Solving a Supported-Evacuation Problem in Wildfires

    • Shahryar Moradi, presenter, University of Ottawa
    • Antoine Sauré, University of Ottawa
    • Jonathan Patrick, Telfer School of Management, University of Ottawa

    In response to the continuing threat of wildfires, advanced disaster management strategies have been developed to mitigate their severe consequences. Among these, evacuation planning has become particularly crucial when time constraints heighten the need for immediate disaster response. While there is a rich body of literature on self-evacuation planning, little has been written about supported-evacuation which concerns the evacuation of individuals who are unable to self-evacuate—such as patients in hospitals and long-term care facilities, and people with disabilities. To address this gap, this paper presents a novel two-stage stochastic optimization approach that accounts for multiple patient groups, diverse vehicle types, different medical facilities, and time windows. It incorporates facility location and vehicle routing decisions with the goal of maximizing the number of rescued patients within time windows in a cost-efficient manner. We develop two optimization models depending on whether the evacuation vehicles can be treated independently and possibility of partial route disruptions. Given the NP-hard nature of the problem, we propose an innovative solution methodology based on a Logic-Based Benders Decomposition approach enhanced with Combinatorial Benders Cuts, a neighborhood search, and valid inequalities. The proposed solution approach is able to achieve high-quality solutions for realistically-sized instances of the problem within reasonable time frames of a few minutes. To highlight the advantages of the proposed approach, we compare its performance with that of three alternative evacuation policies through extensive numerical experiments. The results demonstrate significant improvements regarding shelter location decisions, vehicle usage, and total traveling times. Data collected during a community wildfire drill performed in Roxborough Park, Colorado (USA) are used as a reference for creating a realistic case study to evaluate the performance of the different solution approaches.

  • 04:45 PM - 05:10 PM

    A Benders Decomposition Algorithm for the Hub Network Design Problem with Quality-of-Service Considerations

    • MARIO JOSÉ Basallo Triana, presenter, HEC Montreal - CIRRELT
    • Cordeau Jean-François, HEC Montreal, Department of Logistics and Operations Management
    • Navneet Vidyarthi, Concordia University

    The hub network design problem involves locating hub facilities and determining transportation flows through a transportation network. Hubs act as consolidation centers, capturing large volumes of flow and reducing transportation costs. While hub networks are designed to enhance consolidation opportunities, they are also susceptible to congestion, which can compromise customer service quality. In practice, congestion and long waiting times are common, making incorporating quality-of-service considerations into the strategic network design process essential. We present MILP formulations for the hub network design problem that account for quality-of-service considerations. We propose a Benders decomposition algorithm to solve a relaxation of the problem, along with a heuristic to obtain integer solutions. Several algorithmic refinements are proposed, including a Benders branch-and-cut implementation. The Benders decomposition demonstrates a significant advantage over Gurobi for the same relaxation, with the benefits becoming more pronounced as network size increases.

Back