lagrangian relaxation

A new framework to generate Lagrangian cuts in multistage stochastic mixed-integer programming

  • Christian Füllner
  • Xu Andy Sun
  • Steffen Rebennack
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , , , ,

    Based on recent advances in Benders decomposition and two-stage stochastic integer programming we present a new generalized framework to generate Lagrangian cuts in multistage stochastic mixed-integer linear programming (MS-MILP). This framework can be incorporated into decomposition methods for MS-MILPs, such as the stochastic dual dynamic integer programming (SDDiP) algorithm. We show how different normalization techniques … Read more

    On Lipschitz regularization and Lagrangian cuts in multistage stochastic mixed-integer linear programming

  • Christian Füllner
  • Xu Andy Sun
  • Steffen Rebennack
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , , , ,

    We provide new theoretical insight on the generation of linear and non-convex cuts for value functions of multistage stochastic mixed-integer programs based on Lagrangian duality. First, we analyze in detail the impact that the introduction of copy constraints, and especially, the choice of the accompanying constraint set for the copy variable have on the properties … Read more

    Sensitivity Analysis in Dantzig-Wolfe Decomposition

  • Kouhei Harada
    • Categories Linear Programming Tags , , ,

    Dantzig-Wolfe decomposition is a well-known classical method for solving huge linear optimization problems with a block-angular structure. The most computationally expensive process in the method is pricing: solving block subproblems for a dual variable to produce new columns. Therefore, when we want to solve a slightly perturbated problem in which the block-angular structure is preserved … Read more

    Dual Bounds from Decision Diagram-Based Route Relaxations: An Application to Truck-Drone Routing

  • Z Tang
  • Willem-Jan van Hoeve
    • Categories Integer Programming, Transportation Tags , , , ,

    For vehicle routing problems, strong dual bounds on the optimal value are needed to develop scalable exact algorithms, as well as to evaluate the performance of heuristics. In this work, we propose an iterative algorithm to compute dual bounds motivated by connections between decision diagrams (DDs) and dynamic programming (DP) models used for pricing in … Read more

    Relaxations and Duality for Multiobjective Integer Programming

  • Alex Dunbar
  • Saumya Sinha
  • Andrew J. Schaefer
    • Categories Integer Programming, Multi-Criteria Optimization Tags , , , ,

    Multiobjective integer programs (MOIPs) simultaneously optimize multiple objective func- tions over a set of linear constraints and integer variables. In this paper, we present continuous, convex hull and Lagrangian relaxations for MOIPs and examine the relationship among them. The convex hull relaxation is tight at supported solutions, i.e., those that can be derived via a … Read more

    A Novel Model for Transfer Synchronization in Transit Networks and a Lagrangian-based Heuristic Solution Method

  • Zahra Ansarilari
  • Merve Bodur
  • Amer Shalaby
    • Categories (Mixed) Integer Linear Programming, Transportation Tags , ,

    To realize the benefits of network connectivity in transfer-based transit networks, it is critical to minimize transfer disutility for passengers by synchronizing timetables of intersecting routes. We propose a mixed-integer linear programming timetable synchronization model that incorporates new features, such as dwell time determination and vehicle capacity limit consideration, which have been largely overlooked in … Read more

    Some heuristic methods for the p-median problem with maximum distance constraints. Application to a bi-objective problem.

  • Adrián Esteban-Pérez
  • Jesús Sáez-Aguado
  • Luis A. San-José
    • Categories Facility Planning and Design, Meta Heuristics Tags , , , , ,

    In this work we study the p-median problem with maximum distance constraints (PMPDC) which is a variant of the classical p-median problem (PMP). First of all, we provide some different formulations for (PMPDC) because the heuristics procedures for the (PMPDC) with a formulation based on the approach that modifies the distance matrix that leads to … Read more

    Single Allocation Hub Location with Heterogeneous Economies of Scale

  • Okan Arslan
  • Masoud Chitsaz
  • Gilbert Laporte
  • Andrea Lodi
  • Borzou Rostami
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Combinatorial Optimization Tags , , , , ,

    We study the single allocation hub location problem with heterogeneous economies of scale (SAHLP-h). The SAHLP-h is a generalization of the classical single allocation hub location problem (SAHLP), in which the hub-hub connection costs are piecewise linear functions of the amounts of flow. We model the problem as an integer non-linear program, which we then … Read more

    Multistage Stochastic Demand-side Management for Price-Making Major Consumers of Electricity in a Co-optimized Energy and Reserve Market

  • Anthony Downward
  • Mahbubeh Habibian
  • Golbon Zakeri
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Energy Tags , ,

    In this paper we take an optimization-driven heuristic approach, motivated by dynamic programming, to solve a multistage stochastic optimization of energy consumption for a large manufacturer who is a price-making major consumer of electricity. We introduce a mixed-integer program that co-optimizes consumption bids and interruptible load reserve offers, for such a major consumer over a … Read more

    A decomposition approach for single allocation hub location problems with multiple capacity levels

  • Christoph Buchheim
  • Borzou Rostami
  • Christopher Strothmann
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization Tags , ,

    In this paper we consider an extended version of the classical capacitated single allocation hub location problem in which the size of the hubs must be chosen from a finite and discrete set of allowable capacities. We develop a Lagrangian relaxation approach that exploits the problem structure and decomposes the problem into a set of … Read more