Lagrangean heuristics for location problems

DOI10.1016/0377-2217(93)90118-7zbMath0768.90045OpenAlexW2169855002MaRDI QIDQ1804069

John E. Beasley

Publication date: 29 June 1993

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(93)90118-7

zbMATH Keywords

Lagrangean relaxation\(p\)-medianLagrangean heuristicssubgradient optimisationcapacitated warehouse locationuncapacitated warehouse location

Mathematics Subject Classification ID

Discrete location and assignment (90B80) Boolean programming (90C09) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (96)

On statistical bounds of heuristic solutions to location problems ⋮ A Lagrangian heuristic for the capacitated plant location problem with single source constraints ⋮ A study on the budget constrained facility location model considering inventory management cost ⋮ A cutting plane algorithm for the capacitated facility location problem ⋮ Logistics distribution centers location problem and algorithm under fuzzy environment ⋮ Advanced greedy randomized adaptive search procedure for the obnoxious \(p\)-median problem ⋮ Dynamic supply chain design with inventory ⋮ BEAMR: an exact and approximate model for the \(p\)-median problem ⋮ Optimal political districting ⋮ Developing effective meta-heuristics for a probabilistic location model via experimental design ⋮ Optimization of production allocation and transportation of customer orders for a leading forest products company ⋮ Efficient primal-dual heuristic for a dynamic location problem ⋮ A hybrid multistart heuristic for the uncapacitated facility location problem ⋮ Solving a dynamic facility location problem with partial closing and reopening ⋮ A multiobjective evolutionary approach for linearly constrained project selection under uncertainty ⋮ The \(p\)-median problem: a survey of metaheuristic approaches ⋮ A branch-and-price algorithm for the capacitated facility location problem ⋮ A perturbation-based heuristic for the capacitated multisource Weber problem ⋮ The min-p robust optimization approach for facility location problem under uncertainty ⋮ Computational study of large-scale \(p\)-median problems ⋮ Unnamed Item ⋮ Imposing Contiguity Constraints in Political Districting Models ⋮ Mathematical programming based heuristics for the 0--1 MIP: a survey ⋮ An exact algorithm for the capacitated facility location problems with single sourcing ⋮ A Lagrangian search method for the \(P\)-median problem ⋮ A cut-and-solve based algorithm for the single-source capacitated facility location problem ⋮ Matheuristics: survey and synthesis ⋮ Lagrangean‐based solution approaches for the generalized problem of locating capacitated warehouses ⋮ Optimizing a multi-echelon location-inventory problem with joint replenishment: a Lipschitz \(\epsilon\)-optimal approach using Lagrangian relaxation ⋮ A hypergraph multi-exchange heuristic for the single-source capacitated facility location problem ⋮ Lagrangian Heuristics for Large-Scale Dynamic Facility Location with Generalized Modular Capacities ⋮ The capacitated plant location problem with multiple facilities in the same site ⋮ The balanced \(p\)-median problem with unitary demand ⋮ On a class of subadditive duals for the uncapacitated facility location problem ⋮ A multi-commodity, multi-plant, capacitated facility location problem: Formulation and efficient heuristic solution. ⋮ Upper and lower bounds for the single source capacitated location problem. ⋮ A hybrid approach using an artificial bee algorithm with mixed integer programming applied to a large-scale capacitated facility location problem ⋮ Branch and peg algorithms for the simple plant location problem. ⋮ Resource planning and a depot location model for electric power restoration. ⋮ A variable neighborhood search heuristic for the design of multicommodity production-distribution networks with alternative facility configurations ⋮ Scatter search for the single source capacitated facility location problem ⋮ An exact cooperative method for the uncapacitated facility location problem ⋮ Observations on some heuristic methods for the capacitated facility location problem ⋮ RAMP algorithms for the capacitated facility location problem ⋮ A dual RAMP algorithm for single source capacitated facility location problems ⋮ Experiments with primal - dual decomposition and subgradient methods for the uncapacitatied facility location problem ⋮ A Langrangean heuristic for the \(p_ k\)-median dynamic location problem ⋮ A facility neighborhood search heuristic for capacitated facility location with single-source constraints and flexible demand ⋮ Stochastic facility location with general long-run costs and convex short-run costs ⋮ A computational study of a nonlinear minsum facility location problem ⋮ Fast bounding procedures for large instances of the simple plant location problem ⋮ An aggregation heuristic for large scale p-median problem ⋮ An application of a Lagrangian-type relaxation for the uncapacitated facility location problem ⋮ Solving the simple plant location problem by genetic algorithm ⋮ Branch and peg algorithms for the simple plant location problem ⋮ Fuzzy programming and profit and cost allocation for a production and transportation problem ⋮ Bounds for the single source modular capacitated plant location problem ⋮ Solving the uncapacitated facility location problem using tabu search ⋮ A simple filter-and-fan approach to the facility location problem ⋮ Decomposition and dynamic cut generation in integer linear programming ⋮ A capacitated facility location problem with constrained backlogging probabilities ⋮ Facility location models for distribution system design ⋮ Capacitated facility location problem with general setup cost ⋮ Planning and coordination of production and distribution facilities for multiple commodities ⋮ Outbound supply chain network design with mode selection, lead times and capacitated vehicle distribution centers ⋮ Defining tabu list size and aspiration criterion within tabu search methods ⋮ On the use of genetic algorithms to solve location problems ⋮ An aggressive reduction scheme for the simple plant location problem ⋮ Confidence in heuristic solutions? ⋮ Exact solution methods for uncapacitated location problems with convex transportation costs ⋮ Near-optimal large-scale k-medoids clustering ⋮ Massively parallel analog tabu search using neural networks applied to simple plant location problems ⋮ Mean value cross decomposition for nonlinear convex problems ⋮ A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs ⋮ Maximization of submodular functions: theory and enumeration algorithms ⋮ A tree search algorithm for the crew scheduling problem ⋮ A Lagrangean heuristic for the facility location problem with staircase costs ⋮ A feasibility-ensured Lagrangian heuristic for general decomposable problems ⋮ Driving tabu search with case-based reasoning ⋮ Unnamed Item ⋮ A multiperiod two-echelon multicommodity capacitated plant location problem ⋮ Stronger \(K\)-tree relaxations for the vehicle routing problem ⋮ An exact method for the two-echelon, single-source, capacitated facility location problem ⋮ Lagrangian heuristics for the two-echelon, single-source, capacitated facility location problem ⋮ Resource-constrained management of heterogeneous assets with stochastic deterioration ⋮ Designing reliable tree networks with two cable technologies ⋮ An effective heuristic for large-scale capacitated facility location problems ⋮ A multilevel search algorithm for the maximization of submodular functions applied to the quadratic cost partition problem ⋮ A Lagrangian relax-and-cut approach for the two-stage capacitated facility location problem ⋮ Lagrangean Relaxation-Based Techniques for Solving Facility Location Problems ⋮ Solving large-scale uncapacitated facility location problems with evolutionary simulated annealing ⋮ Locating repair shops in a stochastic environment ⋮ A repeated matching heuristic for the single-source capacitated facility location problem ⋮ A continuous location-allocation problem with zone-dependent fixed cost ⋮ Metaheuristic applications on discrete facility location problems: a survey ⋮ Non delayed relax-and-cut algorithms

Uses Software

• OR-Library

Cites Work

• Unnamed Item
• Lagrangean relaxation and constraint generation procedures for capacitated plant location problems with single sourcing
• A heuristic lagrangean algorithm for the capacitated plant location problem
• A comparison of heuristics and relaxations for the capacitated plant location problem
• A Lagrangean dual ascent algorithm for simple plant location problems
• A method for solving to optimality uncapacitated location problems
• Heuristics for the capacitated plant location model
• A comparison of two dual-based procedures for solving the p-median problem
• Principal direction search: A new method of search for unconstrained LP formulations
• A note on solving large p-median problems
• Location problems
• A heuristic Lagrangean algorithm for the capacitated plant location problem - A comment
• A partial dual algorithm for the capacitated warehouse location problem
• ADD-heuristics' starting procedures for capacitated plant location models
• Facility location models for distribution planning
• Efficient algorithms for the capacitated concentrator location problem
• A new Lagrangian relaxation approach to the generalized assignment problem
• An algorithm for solving large capacitated warehouse location problems
• On the exact solution of large-scale simple plant location problems
• A tree search algorithm for the p-median problem
• Extensions to a Lagrangean relaxation approach for the capacitated warehouse location problem
• Fast primal and dual heuristics for the \(p\)-median location problem
• On the use of tree indexing methods in transportation algorithms
• The capacitated plant location problem
• An algorithm for set covering problem
• The simple plant location problem: Survey and synthesis
• Kapazitätsplanung in Netzwerken. Ein Überblick über neuere Modelle und Verfahren. (Resource-constrained project planning in networks. A survey on new models and methods)
• A dual simplex algorithm for the canonical representation of the uncapacitated facility location problem
• A Multiplier Adjustment Method for the Generalized Assignment Problem
• p-Medians and Multi-Medians
• A Fast Algorithm For The Greedy Interchange For Large-Scale Clustering And Median Location Problems
• State of the Art—Location on Networks: A Survey. Part I: The p-Center and p-Median Problems
• State of the Art—Location on Networks: A Survey. Part II: Exploiting Tree Network Structure
• An Algorithm for the Fixed-Charge Assigning Users to Sources Problem
• A Lagrangian Relaxation Heuristic for Capacitated Facility Location with Single-Source Constraints
• A Cross Decomposition Algorithm for Capacitated Facility Location
• A Dual-Based Add Heuristic for Uncapacitated Facility Location
• Probabilistic Analysis of a Relaxation for the k-Median Problem
• Lagrangian Relaxation and the Single-Source Capacitated Facility-Location Problem
• Technical Note—An Improved Dual Based Algorithm for the Generalized Assignment Problem
• A Dual-Based Procedure for Uncapacitated Facility Location
• A Dual-Bounded Algorithm for the p-Median Problem
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• Linear Relaxations of the Capacitated Warehouse Location Problem
• Note—Single and Double Vertex Substitution in Heuristic Procedures for the p-Median Problem
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• Technical Note—An Algorithm for the p-Median Problem
• Modeling Facility Location Problems as Generalized Assignment Problems
• An all Zero-One Algorithm for a Certain Class of Transportation Problems
• Heuristic Methods for Estimating the Generalized Vertex Median of a Weighted Graph
• An Algorithm for Assigning Uses to Sources in a Special Class of Transportation Problems

This page was built for publication: Lagrangean heuristics for location problems