The Lagrangian Relaxation Method for Solving Integer Programming Problems

DOI10.1287/MNSC.27.1.1zbMath0466.90054OpenAlexW4236384091MaRDI QIDQ3919449

Marshall L. Fisher

Publication date: 1981

Published in: Management Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/mnsc.27.1.1

zbMATH Keywords

algorithmsheuristicsLagrangian relaxationcombinatorial optimizationlower boundbranch and bound algorithmreviewdualized side constraints

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Integer programming (90C10) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)

Related Items (only showing first 100 items - show all)

An exact algorithm for the budget-constrained multiple knapsack problem ⋮ Efficient Learning of Interpretable Classification Rules ⋮ A study on the budget constrained facility location model considering inventory management cost ⋮ Parametric problems on graphs of bounded tree-width ⋮ Heuristics for the multi-resource generalized assignment problem ⋮ A class of convergent primal-dual subgradient algorithms for decomposable convex programs ⋮ Supply capacity acquisition and allocation with uncertain customer demands ⋮ Applying available-to-promise (ATP) concept in mixed-model assembly line sequencing problems in a make-to-order (MTO) environment: problem extension, model formulation and Lagrangian relaxation algorithm ⋮ Combinatorial Heuristics for Inventory Routing Problems ⋮ Integrated Stochastic Optimal Self-Scheduling for Two-Settlement Electricity Markets ⋮ Optimizing production capacity and safety stocks in general acyclic supply chains ⋮ Multi-modal cargo logistics distribution problem: decomposition of the stochastic risk-averse models ⋮ Generalizations, formulations and subgradient based heuristic with dynamic programming procedure for target set selection problems ⋮ Lagrangian solution of maximum dispersion problems ⋮ Heuristicas de descomposicion lagrangiana para algunos problemas de localizacion discreta ⋮ Unnamed Item ⋮ Combining (Integer) Linear Programming Techniques and Metaheuristics for Combinatorial Optimization ⋮ Matheuristics: survey and synthesis ⋮ A Survey of the Generalized Assignment Problem and Its Applications ⋮ Generalized Bottleneck Problems^∗ ⋮ Incorporating Aggregate Diversity in Recommender Systems Using Scalable Optimization Approaches ⋮ A branch-and-bound algorithm for the precedence-constrained minimum-cost arborescence problem ⋮ A Lagrangean Relaxation Scheme for Structured Linear Programs With Application To Multicommodity Network Flows ⋮ Steiner problem in networks: A survey ⋮ Graphical-structure-based models for routing problems ⋮ A Combinatorial Auction Framework for Solving Decentralized Scheduling Problems (Extended Abstract) ⋮ The edge-disjoing steiner problem in graphs ⋮ Dynamic-demand capacitated facility location problems with and without relocation ⋮ A combination of Lagrangian relaxation and column generation for order batching in steelmaking and continuous-casting production ⋮ A SIMPLE LOWER BOUND FOR TOTAL COMPLETION TIME MINIMIZATION IN A TWO-MACHINE FLOWSHOP ⋮ Solving TSP through the Integration of OR and CP Techniques ⋮ Analysis of a linearization heuristic for single-machine scheduling to maximize profit ⋮ Modelling and solving an FMS part selection problem ⋮ Experiments with primal - dual decomposition and subgradient methods for the uncapacitatied facility location problem ⋮ A Lagrangian-Based Algorithm for a Combinatorial Motion Planning Problem ⋮ A CONVEX SUBMODEL WITH APPLICATION TO SYSTEM DESIGN ⋮ A modified subgradient algorithm for Lagrangean relaxation ⋮ The selection and scheduling of telecommunication calls with time windows ⋮ Discrete filled function method for discrete global optimization ⋮ A hierarchical approach for metal parts fabrication ⋮ A 3-flip neighborhood local search for the set covering problem ⋮ Decomposition and dynamic cut generation in integer linear programming ⋮ LP-based heuristics for the capacitated lot-sizing problem: The interaction of model formulation and solution algorithm ⋮ Capacity planning with congestion effects ⋮ Lagrangian duality applied to the vehicle routing problem with time windows ⋮ Planning and coordination of production and distribution facilities for multiple commodities ⋮ Towards strong duality in integer programming ⋮ Linear programming and Lagrangian relaxation heuristics for designing a material flow network on a block layout ⋮ Decomposition of Petri nets and Lagrangian relaxation for solving routing problems for AGVs ⋮ A class of stochastic programs with decision dependent uncertainty ⋮ Fund allocation model for pipe repair maintenance in water distribution networks. ⋮ Workface planning in synchronous production systems ⋮ Mathematical Modeling of Scheduling Problems ⋮ Dynamic scheduling in manufacturing systems using Brownian approximations ⋮ Real-world extensions to scheduling algorithms based on Lagrangian relaxation ⋮ Partitioning a matrix with non-guillotine cuts to minimize the maximum cost ⋮ A management system for decompositions in stochastic programming ⋮ An inventory-routing problem with the objective of travel time minimization ⋮ Impact analysis of maritime cabotage legislations on liner hub-and-spoke shipping network design ⋮ Upper and lower bounding procedures for the multiple knapsack assignment problem ⋮ Steel-making process scheduling using Lagrangian relaxation ⋮ Distance confined path problem and separable integer programming ⋮ Recovery of primal solutions when using subgradient optimization methods to solve Lagrangian duals of linear programs ⋮ Cross decomposition for mixed integer programming ⋮ An linear programming based lower bound for the simple assembly line balancing problem ⋮ A path relinking approach with ejection chains for the generalized assignment problem ⋮ Covering Problems ⋮ Lagrangean Relaxation-Based Techniques for Solving Facility Location Problems ⋮ ATM network design for corporate networks ⋮ An efficient lagrangean relaxation scheme for linear and integer equal flow problems ⋮ Generalized nonlinear Lagrangian formulation for bounded integer programming ⋮ Solving the subproblem in the lagrangian dual of separable discrete programs with linear constraints ⋮ Some computational results on real 0-1 knapsack problems ⋮ A cross-decomposition scheme with integrated primal-dual multi-cuts for two-stage stochastic programming investment planning problems ⋮ An implicit enumeration algorithm for the passenger service planning problem: application to the Taiwan railways administration line ⋮ Exact algorithms for single-machine scheduling with time windows and precedence constraints ⋮ A two-level approach to large mixed-integer programs with application to cogeneration in energy-efficient buildings ⋮ Two exact algorithms for the traveling umpire problem ⋮ A Lagrangian heuristic for an integrated lot-sizing and fixed scheduling problem ⋮ Decomposition based hybrid metaheuristics ⋮ Practical solutions for a dock assignment problem with trailer transportation ⋮ On solving the Lagrangian dual of integer programs via an incremental approach ⋮ Models and algorithms for network reduction ⋮ Enhanced models and improved solution for competitive biofuel supply chain design under land use constraints ⋮ Convergence and computational analyses for some variable target value and subgradient deflection methods ⋮ Combinatorial Benders cuts for decomposing IMRT fluence maps using rectangular apertures ⋮ Meta-heuristics for dynamic lot sizing: a review and comparison of solution approaches ⋮ The production routing problem: a review of formulations and solution algorithms ⋮ Incorporating location, inventory and price decisions into a supply chain distribution network design problem ⋮ Combining simulated annealing with Lagrangian relaxation and weighted Dantzig-Wolfe decomposition for integrated design decisions in wireless sensor networks ⋮ A trust region target value method for optimizing nondifferentiable Lagrangian duals of linear programs ⋮ An improved Lagrangian relaxation-based heuristic for a joint location-inventory problem ⋮ Local search heuristics for the mobile facility location problem ⋮ Exploiting nested inequalities and surrogate constraints ⋮ Heuristics for the multi-item capacitated lot-sizing problem with lost sales ⋮ A hybridized Lagrangian relaxation and simulated annealing method for the course timetabling problem ⋮ A hybrid Lagrangian-simulated annealing-based heuristic for the parallel-machine capacitated lot-sizing and scheduling problem with sequence-dependent setup times ⋮ Improving problem reduction for 0-1 multidimensional knapsack problems with valid inequalities ⋮ The stochastic location model with risk pooling ⋮ A matrix generation approach for eigenvalue optimization

This page was built for publication: The Lagrangian Relaxation Method for Solving Integer Programming Problems