lagrangian decomposition

Tricks from the Trade for Large-Scale Markdown Pricing: Heuristic Cut Generation for Lagrangian Decomposition

  • Robert Streeck
  • Andreas Schmitt
  • Torsten Gellert
  • Asya Dipkaya
  • Vladimir Fux
  • Tim Januschowski
  • Timo Berthold
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences Tags , , , ,

    In automated decision making processes in the online fashion industry, the ‘predict-then-optimize’ paradigm is frequently applied, particularly for markdown pricing strategies. This typically involves a mixed-integer optimization step, which is crucial for maximizing profit and merchandise volume. In practice, the size and complexity of the optimization problem is prohibitive for using off-the-shelf solvers for mixed … Read more

    Statistical performance of subgradient step-size update rules in Lagrangian relaxations of chance-constrained optimization models

  • Charlotte Ritter
  • Bismark Singh
    • Categories Stochastic Programming Tags , , , ,

    Lagrangian relaxation schemes, coupled with a subgradient procedure, are frequently employed to solve chance-constrained optimization models. The subgradient procedure typically relies on a step-size update rule. Although there is extensive research on the properties of these step-size update rules, there is little consensus on which rules are most suited in practice. This is especially so … Read more

    Scalable Timing-Aware Network Design via Lagrangian Decomposition

  • Cristiana L. Lara
  • Jochen Koenemann
  • Yisu Nie
  • Cid C. de Souza
    • Categories Applications - OR and Management Sciences, Scheduling, Transportation Tags , , , ,

    This paper addresses instances of the temporal fixed-charge multi-commodity flow (tfMCF) problem that arise in a very large scale dynamic transportation application. We model the tfMCF as a discrete-time Resource Task Network (RTN) with cyclic schedule, and formulate it as a mixed-integer program. These problems are notoriously hard to solve due to their time-expanded nature, … Read more

    Lagrangian relaxation based heuristics for a chance-constrained optimization model of a hybrid solar-battery storage system

  • Bismark Singh
  • Bernard Knueven
    • Categories Energy, Stochastic Programming Tags , , , , , , , ,

    We develop a stochastic optimization model for scheduling a hybrid solar-battery storage system. Solar power in excess of the promise can be used to charge the battery, while power short of the promise is met by discharging the battery. We ensure reliable operations by using a joint chance constraint. Models with a few hundred scenarios … Read more

    Pseudo basic steps: Bound improvement guarantees from Lagrangian decomposition in convex disjunctive programming

  • Dimitri J. Papageorgiou
  • Francisco Trespalacios
    • Categories (Mixed) Integer Nonlinear Programming Tags , , , ,

    An elementary, but fundamental, operation in disjunctive programming is a basic step, which is the intersection of two disjunctions to form a new disjunction. Basic steps bring a disjunctive set in regular form closer to its disjunctive normal form and, in turn, produce relaxations that are at least as tight. An open question is: What … Read more

    AN INEXACT PERTURBED PATH-FOLLOWING METHOD FOR LAGRANGIAN DECOMPOSITION IN LARGE-SCALE SEPARABLE CONVEX OPTIMIZATION

  • Moritz Diehl
  • Ion Necoara
  • Carlo Savorgnan
  • Quoc Tran-Dinh
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Parallel Algorithms Tags , , , , ,

    This paper studies an inexact perturbed path-following algorithm in the framework of Lagrangian dual decomposition for solving large-scale separable convex programming problems. Unlike the exact versions considered in the literature, we propose to solve the primal subproblems inexactly up to a given accuracy. This leads to an inexactness of the gradient vector and the Hessian … Read more