benders decomposition

Formulations and Decomposition Methods for the Incomplete Hub Location Problem With and Without Hop-Constraints

  • R.S. Camargo
  • J. F. Campbell
  • Gilberto Miranda
  • M. E. O' Kelly
    • Categories Airline Optimization, Applications - OR and Management Sciences, Transportation Tags , , , ,

    The incomplete hub location problem with and without hop-constraints is modeled using a Leontief substitution system approach. The Leontief formalism provides a set of important theoretical properties and delivers formulations with tight linear bounds that can explicitly incorporate hop constraints for each origin-destination pair of demands. Furthermore, the proposed formulations are amenable to a Benders … Read more

    Combinatorial Benders Cuts for Assembly Line Balancing Problems with Setups

  • Sener Akpinar
  • Tolga Bektas
  • Atabak Elmi
    • Categories Combinatorial Optimization Tags , , , ,

    The classical assembly line balancing problem consists of assigning assembly work to workstations. In the presence of setup times that depend on the sequence of tasks assigned to each workstation, the problem becomes more complicated given that two interdependent problems, namely assignment and sequencing, must be solved simultaneously. The hierarchical nature of these two problems … Read more

    A Benders Decomposition Approach for the Charging Station Location Problem with Plug-in Hybrid Electric Vehicles

  • Okan Arslan
  • Oya Ekin Karasan
    • Categories Cutting Plane Approaches, Facility Planning and Design, Network Optimization Tags , , , , ,

    The flow refueling location problem (FRLP) locates $p$ stations in order to maximize the flow volume that can be accommodated in a road network respecting the range limitations of the vehicles. This paper introduces the charging station location problem with plug-in hybrid electric vehicles (CSLP-PHEV) as a generalization of the FRLP. We consider not only … Read more

    A two-level SDDP Solving Strategy with Risk-Averse multivariate reservoir Storage Levels for Long Term power Generation Planning

  • Andre Diniz
  • Maria Elvira P. Maceira
  • D.D. Penna
  • C. L. Vasconcellos
    • Categories Applications - OR and Management Sciences, Stochastic Programming Tags , ,

    Power generation planning in large-scale hydrothermal systems is a complex optimization task, specially due to the high uncertainty in the inflows to hydro plants. Since it is impossible to traverse the huge scenario tree of the multi-stage problem, stochastic dual dynamic programming (SDDP) is the leading optimization technique to solve it, originally from an expected-cost … Read more

    Efficient approaches for the robust network loading problem

  • Sara Mattia
  • Michael Poss
    • Categories (Mixed) Integer Linear Programming, Network Optimization, Robust Optimization Tags , , , ,

    We consider the Robust Network Loading problem with splittable flows and demands that belong to the budgeted uncertainty set. We compare the optimal solution cost and computational cost of the problem when using static routing, volume routing, affine routing, and dynamic routing. For the first three routing types, we compare the compact formulation with a … Read more

    A Generalization of Benders’ Algorithm for Two-Stage Stochastic Optimization Problems With Mixed Integer Recourse

  • Anahita Hassanzadeh
  • Ted K. Ralphs
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags ,

    We describe a generalization of Benders’ method for solving two-stage stochastic linear optimization problems in which there are both continuous and integer variables in the first and second stages. Benders’ method relies on finding effective lower approximations for the value function of the second-stage problem. In this setting, the value function is a discontinuous, non-convex, … Read more

    The unrooted set covering connected subgraph problem differentiating between HIV envelope sequences

  • Stephen J. Maher
  • John M Murray
    • Categories (Mixed) Integer Linear Programming, Biomedical Applications Tags , , ,

    This paper presents a novel application of operations research techniques to the analysis of HIV env gene sequences, aiming to identify key features that are possible vaccine targets. These targets are identified as being critical to the transmission of HIV by being present in early transmitted (founder) sequences and absent in later chronic sequences. Identifying … Read more

    Chance-Constrained Multi-Terminal Network Design Problems

  • Yongjia Song
  • Minjiao Zhang
    • Categories Integer Programming, Network Optimization, Stochastic Programming Tags , , ,

    We consider a reliable network design problem under uncertain edge failures. Our goal is to select a minimum-cost subset of edges in the network to connect multiple terminals together with high probability. This problem can be seen as a stochastic variant of the Steiner tree problem. We propose a scenario-based Steiner cut formulation, and a … Read more

    Chance Constrained Mixed Integer Program: Bilinear and Linear Formulations, and Benders Decomposition

  • Yu An
  • Bo Zeng
  • Ludwig Kuznia
    • Categories Integer Programming, Stochastic Programming Tags , , , , ,

    In this paper, we study chance constrained mixed integer program with consideration of recourse decisions and their incurred cost, developed on a finite discrete scenario set. Through studying a non-traditional bilinear mixed integer formulation, we derive its linear counterparts and show that they could be stronger than existing linear formulations. We also develop a variant … Read more

    Decomposition Algorithms for Two-Stage Chance-Constrained Programs

  • Simge Küçükyavuz
  • James R. Luedtke
  • Xiao Liu
    • Categories Branch and Cut Algorithms, Integer Programming, Stochastic Programming Tags , , ,

    We study a class of chance-constrained two-stage stochastic optimization problems where second-stage feasible recourse decisions incur additional cost. In addition, we propose a new model, where “recovery” decisions are made for the infeasible scenarios to obtain feasible solutions to a relaxed second-stage problem. We develop decomposition algorithms with specialized optimality and feasibility cuts to solve … Read more