About Lagrangian methods in integer optimization

DOI10.1007/s10479-005-3447-9zbMath1091.90048OpenAlexW2003973127WikidataQ118165501 ScholiaQ118165501MaRDI QIDQ817183

Antonio Frangioni

Publication date: 7 March 2006

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/11568/94953

zbMATH Keywords

integer linear programsLagrangian dual

Mathematics Subject Classification ID

Integer programming (90C10) Optimality conditions and duality in mathematical programming (90C46) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Related Items (42)

Algorithmic innovations and software for the dual decomposition method applied to stochastic mixed-integer programs ⋮ A cross-decomposition scheme with integrated primal-dual multi-cuts for two-stage stochastic programming investment planning problems ⋮ The min-up/min-down unit commitment polytope ⋮ A Lagrangian heuristic for concave cost facility location problems: the plant location and technology acquisition problem ⋮ A Lagrangian heuristic for the multicommodity capacitated location problem with balancing requirements ⋮ Deterministic electric power infrastructure planning: mixed-integer programming model and nested decomposition algorithm ⋮ Calculating the best dual bound for problems with multiple Lagrangian relaxations ⋮ Solving a dynamic facility location problem with partial closing and reopening ⋮ Improving problem reduction for 0-1 multidimensional knapsack problems with valid inequalities ⋮ A stabilized structured Dantzig-Wolfe decomposition method ⋮ A multiperiod drayage problem with customer-dependent service periods ⋮ Lagrangian heuristic for a class of the generalized assignment problems ⋮ Combining (Integer) Linear Programming Techniques and Metaheuristics for Combinatorial Optimization ⋮ Lagrangian bounds for large‐scale multicommodity network design: a comparison between Volume and Bundle methods ⋮ A Lagrangian approach for the minimum spanning tree problem with conflicting edge pairs ⋮ Time-flexible min completion time variance in a single machine by quadratic programming ⋮ A Lagrangian heuristics for balancing the average weighted completion times of two classes of jobs in a single-machine scheduling problem ⋮ Refinement of Lagrangian bounds in optimization problems ⋮ Lagrangian Heuristics for Large-Scale Dynamic Facility Location with Generalized Modular Capacities ⋮ Consensus-based Dantzig-Wolfe decomposition ⋮ Feasibility jump: an LP-free Lagrangian MIP heuristic ⋮ Incremental Bundle Methods using Upper Models ⋮ Stochastic dual dynamic programming applied to nonconvex hydrothermal models ⋮ Electric power infrastructure planning under uncertainty: stochastic dual dynamic integer programming (SDDiP) and parallelization scheme ⋮ The Vehicle Routing Problem with Floating Targets: Formulation and Solution Approaches ⋮ On parallelizing dual decomposition in stochastic integer programming ⋮ Large-scale unit commitment under uncertainty: an updated literature survey ⋮ On the complexity of the unit commitment problem ⋮ Minimizing value-at-risk in single-machine scheduling ⋮ A new cross decomposition method for stochastic mixed-integer linear programming ⋮ Bundle methods for sum-functions with ``easy components: applications to multicommodity network design ⋮ Computation of approximate \(\alpha \)-points for large scale single machine scheduling problem ⋮ Perspective cuts for a class of convex 0-1 mixed integer programs ⋮ A Lagrangian bound for many-to-many assignment problems ⋮ Studying properties of Lagrangian bounds for many-to-many assignment problems ⋮ Decomposition and shortest path problem formulation for solving the hydro unit commitment and scheduling in a hydro valley ⋮ Branch-and-price-and-cut for large-scale multicommodity capacitated fixed-charge network design ⋮ A Lagrangian approach to chance constrained routing with local broadcast ⋮ On the choice of explicit stabilizing terms in column generation ⋮ 0-1 reformulations of the multicommodity capacitated network design problem ⋮ New approaches for optimizing over the semimetric polytope ⋮ Large-scale unit commitment under uncertainty

Uses Software

• IPM

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• New bundle methods for solving Lagrangian relaxation dual problems
• Combinatorial approaches to multiflow problems
• Partitioning procedures for solving mixed-variables programming problems
• On improvements to the analytic center cutting plane method
• Efficient cuts in Lagrangean `relax-and-cut' schemes
• A bundle Bregman proximal method for convex nondifferentiable minimization
• Multicommodity network flows: The impact of formulation on decomposition
• Solving nonlinear multicommodity flow problems by the analytic center cutting plane method
• The volume algorithm revisited: relation with bundle methods
• Stochastic programming with integer variables
• Discrete facility location and routing of obnoxious activities.
• The volume algorithm: Producing primal solutions with a subgradient method
• An application-oriented guide for designing Lagrangean dual ascent algorithms
• Bounds for probabilistic integer programming problems
• Lagrangean relaxation. (With comments and rejoinder).
• New variants of bundle methods
• Complexity estimates of some cutting plane methods based on the analytic barrier
• Ergodic, primal convergence in dual subgradient schemes for convex programming
• Solving semidefinite quadratic problems within nonsmooth optimization algorithms
• New approaches for optimizing over the semimetric polytope
• Decomposition Principle for Linear Programs
• The Cutting-Plane Method for Solving Convex Programs
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• Lagrangean decomposition: A model yielding stronger lagrangean bounds
• Progress Made in Solving the Multicommodity Flow Problem
• On Smoothing Exact Penalty Functions for Convex Constrained Optimization
• Subgradient Methods for the Service Network Design Problem
• A Bundle Type Dual-Ascent Approach to Linear Multicommodity Min-Cost Flow Problems
• A Specialized Interior-Point Algorithm for Multicommodity Network Flows
• Lagrangian Solution Techniques and Bounds for Loosely Coupled Mixed-Integer Stochastic Programs
• Dual-ascent methods for large-scale multicommodity flow problems
• A Dual-Ascent Procedure for Large-Scale Uncapacitated Network Design
• Validation of subgradient optimization
• Generalized Bundle Methods
• Lower Bounding Procedures for Multiperiod Telecommunications Network Expansion Problems
• A Decomposition Algorithm for Local Access Telecommunications Network Expansion Planning
• A 2n Constraint Formulation for the Capacitated Minimal Spanning Tree Problem
• An exponential‐function reduction method for block‐angular convex programs
• The traveling-salesman problem and minimum spanning trees: Part II
• Geometry of cuts and metrics
• A geometric study of dual gaps, with applications
• Bundle-based relaxation methods for multicommodity capacitated fixed charge network design
• Bundle methods in stochastic optimal power management: A disaggregated approach using preconditioners

This page was built for publication: About Lagrangian methods in integer optimization