The Lagrangian Relaxation Method for Solving Integer Programming Problems
From MaRDI portal
Publication:3919449
DOI10.1287/mnsc.27.1.1zbMath0466.90054OpenAlexW4236384091MaRDI QIDQ3919449
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
algorithmsheuristicsLagrangian relaxationcombinatorial optimizationlower boundbranch and bound algorithmreviewdualized side constraints
Numerical mathematical programming methods (65K05) Integer programming (90C10) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)
Related Items
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, Short-term work scheduling with job assignment flexibility for a multi-fleet transport system, On ascending Vickrey auctions for heterogeneous objects, Solving network manpower problems with side constraints, A Lagrangian heuristic algorithm for a public healthcare facility location problem, A hybrid approach of bundle and Benders applied large mixed linear integer problem, A hop constrained min-sum arborescence with outage costs, The quadratic knapsack problem -- a survey, Separable relaxation for nonconvex quadratic integer programming: Integer diagonalization approach, Discrete global descent method for discrete global optimization and nonlinear integer programming, Lagrangian relaxation guided problem space search heuristics for generalized assignment problems, Discrete global optimization problems with a modified discrete filled function, The combinatorial bandwidth packing problem, Use of Lagrangian decomposition in supply chain planning, Resource leveling in a machine environment, Combining probabilistic algorithms, constraint programming and Lagrangian relaxation to solve the vehicle routing problem, The equity constrained shortest path problem, Time-axis decomposition of large-scale optimal control problems, A coordinated location-inventory model, A theoretical and empirical investigation on the Lagrangian capacities of the \(0\)-\(1\) multidimensional knapsack problem, A dual ascent algorithm for the 1-tree relaxation of the symmetric traveling salesman problem, The traveling salesman problem with flexible coloring, Multi-level production scheduling for a class of flexible machining and assembly systems, The capacitated maximal covering location problem with backup service, A lagrangean based branch-and-cut algorithm for global optimization of nonconvex mixed-integer nonlinear programs with decomposable structures, A decomposition-based pricing method for solving a large-scale MILP model for an integrated fishery, Nonconvex generalized Benders decomposition for stochastic separable mixed-integer nonlinear programs, Tailored Lagrangian relaxation for the open pit block sequencing problem, The min-degree constrained minimum spanning tree problem: formulations and branch-and-cut algorithm, Weighted search in the plane, Computing exact solution to nonlinear integer programming: convergent Lagrangian and objective level cut method, Optimal partitioning of a data set based on the \(p\)-median model, An efficient algorithm for the Lagrangean dual of nonlinear knapsack problems with additional nested constraints, A Lagrangian relaxation-based heuristic for the multi-ship quay crane scheduling problem with ship stability constraints, Multi-level multi-item lot size planning with limited resources and general manufacturing structure., Capacitated emergency facility siting with multiple levels of backup, Ergodic, primal convergence in dual subgradient schemes for convex programming. II: The case of inconsistent primal problems, Higher-level RLT or disjunctive cuts based on a partial enumeration strategy for 0-1 mixed-integer programs, A sliding time window heuristic for open pit mine block sequencing, Hub location-allocation in intermodal logistic networks, An homage to Joseph-Louis Lagrange and Pierre Huard, New Lagrangian relaxation based algorithm for resource scheduling with homogeneous subproblems, On embedding the volume algorithm in a variable target value method., Solving multidimensional knapsack problems with generalized upper bound constraints using critical event tabu search, An algorithm for a separable integer programming problem with cumulatively bounded variables, A Lagrangean dual-based solution method for a special linear programming problem, On an optimization problem with nested constraints, A Benders decomposition based heuristic for the hierarchical production planning problem, Integration of strategic and tactical decisions for vendor selection under capacity constraints, Hub-and-spoke network design and fleet deployment for string planning of liner shipping, Convergent Lagrangian and domain cut method for nonlinear knapsack problems, An exact algorithm for the fixed-charge multiple knapsack problem, Developing work schedules for an inter-city transit system with multiple driver types and fleet types, Models and Lagrangian heuristics for a two-level lot-sizing problem with bounded inventory, The multi-item capacitated lot-sizing problem with safety stocks and demand shortage costs, A Lagrangian relaxation approach to large-scale flow interception problems, An optimization model and a solution algorithm for the many-to-many car pooling problem, A new Lagrangean approach to the pooling problem, Resource-constrained management of heterogeneous assets with stochastic deterioration, A non-delayed relax-and-cut algorithm for scheduling problems with parallel machines, due dates and sequence-dependent setup times, A heuristic lagrangean algorithm for the capacitated plant location problem, A comparison of two dual-based procedures for solving the p-median problem, Solving capacitated clustering problems, A note on solving large p-median problems, Capital budgeting with Benders' decomposition, ASEAN industrial cooperation: The case of multi-product capacity expansion, Modelling a fertiliser distribution system, 'Multidimensional' extensions and a nested dual approach for the m-median problem, A multiperiod min-sum arborescence problem, Optimal planning of a multi-station system with sojourn time constraints, The multidimensional 0-1 knapsack problem -- bounds and computational aspects, Airline crew scheduling: state-of-the-art, Non delayed relax-and-cut algorithms, Lagrangian heuristic for simultaneous subsidization and penalization: implementations on rooted travelling salesman games, Using deep learning to extend the range of air pollution monitoring and forecasting, Lagrangean relaxation. (With comments and rejoinder)., A maximal covering location model in the presence of partial coverage, The multiple bottleneck transportation problem, A Lagrangian heuristic for the capacitated plant location problem with single source constraints, Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context, Descent direction algorithm with multicommodity flow problem for signal optimization and traffic assignment jointly, Development of a hybrid dynamic programming approach for solving discrete nonlinear Knapsack problems, Ranking lower bounds for the bin-packing problem, A monotonic, dual-based bounding procedure for integer programs, An efficient optimisation procedure for the workforce scheduling and routing problem: Lagrangian relaxation and iterated local search, Stochastic hub location problems with Bernoulli demands, The minimum weighted covering location problem with distance constraints, Dynamic supply chain design with inventory, The green capacitated multi-item lot sizing problem with parallel machines, Stochastic programming for qualification management of parallel machines in semiconductor manufacturing, A reformulation-convexification approach for solving nonconvex quadratic programming problems, A two-phase algorithm for the partial accessibility constrained vehicle routing problem, A Lagrangian relaxation approach to simultaneous strategic and tactical planning in supply chain design, Capacitated replenishment and disposal planning for multiple products with resalable returns, Truck synchronization at single door cross-docking terminals, The \(p\)-Lagrangian relaxation for separable nonconvex MIQCQP problems, A hybrid dynamic programming for solving fixed cost transportation with discounted mechanism, The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems, Step fixed-charge solid transportation problem: a Lagrangian relaxation heuristic approach, A matheuristic for a customer assignment problem in direct marketing, A Lagrangian search method for the \(P\)-median problem, Joint chance constrained shortest path problem with Copula theory, Dynamic Lagrangian dual and reduced RLT constructs for solving \(0-1\) mixed-integer programs, A Lagrangian relaxation-based heuristic for the vehicle routing with full container load, A branch-and-bound algorithm for the singly constrained assignment problem, A two-stage algorithm for the closed-loop location-inventory problem model considering returns in E-commerce, An improved Lagrangian relaxation algorithm for the robust generation self-scheduling problem, Lagrangian relaxation for an inventory location problem with periodic inventory control and stochastic capacity constraints, The project scheduling problem with irregular starting time costs, A multiperiod planning model for the capacitated minimal spanning tree problem, Multi-objective routing within large scale facilities using open finite queueing networks, Solving linear programming relaxations associated with Lagrangean relaxations by Fenchel cutting planes, A Lagrangean relaxation approach for the mixed-model flow line sequencing problem, A location-routing problem for the conversion to the ``click-and-mortar retailing: the static case, A distributed computation algorithm for solving portfolio problems with integer variables, Lower and upper bounds for a two-level hierarchical location problem in computer networks, Lagrangian relaxations for multiple network alignment, Solving the facility location and fixed charge solid transportation problem, Decomposition methods for the two-stage stochastic Steiner tree problem, A Lagrangian based heuristic for the design of multipoint linkages in a communication network with unreliable links and node outage costs., Topology optimization via sequential integer programming and canonical relaxation algorithm, Proprietor and customer costs in the incomplete hub location-routing network topology, A multi-item approach to repairable stocking and expediting in a fluctuating demand environment, A new cross decomposition method for stochastic mixed-integer linear programming, Evasive flow capture: a multi-period stochastic facility location problem with independent demand, A column generation heuristic for optimal wireless sensor network design with mobile sinks, Finding discrete global minima with a filled function for integer programming, Reformulation of the support set selection problem in the logical analysis of data, Convergent Lagrangian heuristics for nonlinear minimum cost network flows, Computation of approximate \(\alpha \)-points for large scale single machine scheduling problem, Algorithmic expedients for the \(S\)-labeling problem, An incomplete \(m\)-exchange algorithm for solving the large-scale multi-scenario knapsack problem, Lagrangian relaxation and pegging test for the clique partitioning problem, Problem reduction heuristic for the \(0\)-\(1\) multidimensional knapsack problem, A Lagrangian approach for minimum cost single round robin tournaments, Two-echelon, multi-commodity supply chain network design with mode selection, lead-times and inventory costs, A branch-and-bound algorithm for assembly line worker assignment and balancing problems, A dual bounding scheme for a territory design problem, A joint decomposition method for global optimization of multiscenario nonconvex mixed-integer nonlinear programs, A Lagrangian relaxation approach to solving the integrated pick-up/drop-off point and AGV flowpath design problem, Multi-product lot-sizing with a transportation capacity reservation contract, Data traffic scheduling algorithm for multiuser OFDM system with adaptive modulation considering fairness among users, A scalable global optimization algorithm for stochastic nonlinear programs, Modeling of financial supply chain, Joint optimization of budget allocation and maintenance planning of multi-facility transportation infrastructure systems, Planning capacity and safety stocks in a serial production-distribution system with multiple products, Alternate solution approaches for competitive hub location problems, Solving the maximum edge disjoint path problem using a modified Lagrangian particle swarm optimisation hybrid, A branch-and-bound algorithm for the single machine sequence-dependent group scheduling problem with earliness and tardiness penalties, Efficient generation of performance bounds for a class of traffic scheduling problems, Dynamic programming algorithms and Lagrangian lower bounds for a discrete lot streaming problem in a two-machine flow shop, Lagrangean heuristics for location problems, Bandwidth packing with queuing delay costs: Bounding and heuristic solution procedures, Multiple bottleneck assignment problem, Zero duality gap in integer programming: \(P\)-norm surrogate constraint method, Lagrangian-relaxation-based solution procedures for a multiproduct capacitated facility location problem with choice of facility type, Multiple level production planning in rolling horizon assembly environments, Lagrangean/surrogate relaxation for generalized assignment problems, A Lagrangian-based score for assessing the quality of pairwise constraints in semi-supervised clustering, An algorithm for set covering problem, A feasibility-ensured Lagrangian heuristic for general decomposable problems, Stronger \(K\)-tree relaxations for the vehicle routing problem, Optimization of printed circuit board manufacturing: Integrated modeling and algorithms, The simple plant location problem: Survey and synthesis, Heuristic procedure neural networks for the CMST problem, Design of capacitated degree constrained min-sum arborescence, A multiperiod degree constrained minimal spanning tree problem, Using logical surrogate information in Lagrangean relaxation: An application to symmetric traveling salesman problems, A passenger demand model for airline flight scheduling and fleet routing, Single machine scheduling with symmetric earliness and tardiness penalties, Asynchronous transfer mode networks with parallel links and multiple service classes, A nonlinear Lagrangian dual for integer programming, An efficient optimization procedure for designing a capacitated distribution network with price-sensitive demand, Topological design of a centralized communication network with unreliable links and node outage costs, An algorithm for the planar three-index assignment problem, Application of facility location modeling constructs to vendor selection problems, Production allocation with dual provisioning, Experimentation in optimization, Implementation techniques for the vehicle routing problem, A Lagrangean relaxation method for the constrained assignment problem, Probabilistic properties of the dual structure of the multidimensional knapsack problem and fast statistically efficient algorithms, Comparison of formulations and a heuristic for packing Steiner trees in a graph, Multiple-type, two-dimensional bin packing problems: Applications and algorithms, Unrelated machine scheduling with time-window and machine downtime constraints: An application to a naval battle-group problem, Multi-item capacitated lot-sizing by a cross decomposition based algorithm, A new Lagrangian relaxation approach to the generalized assignment problem, A computational evaluation of two subgradient search methods, A column generation approach to job grouping for flexible manufacturing systems, New heuristic solution procedures for the uniform graph partitioning problem: Extensions and evaluation, Lagrangian relaxation based approaches to capacitated hub-and-spoke network design problem, Lagrangean relaxation for a lower bound to a set partitioning problem with side constraints: Properties and algorithms, Hierarchical approach to the process planning problem, An algorithm for solving large capacitated warehouse location problems, Surrogate duality in a branch-and-bound procedure for integer programming, A large-scale multilocation capacity planning model, A shadow price in integer programming for management decision, Algorithms for railway crew management, Solving large set covering problems for crew scheduling, A heuristic method for lot-sizing in multi-stage systems, Maximal chordal subgraphs, An improved direct descent algorithm for binary knapsack problems, Solving the anti-covering location problem using Lagrangian relaxation, Application of Lagrangian relaxation to computer network control, A primal-dual conjugate subgradient algorithm for specially structured linear and convex programming problems, Lagrangian dual ascent by generalized linear programming, Design of electronic assembly lines: An analytical framework and its application, The scheduling problem where multiple machines compete for a common local buffer, A fixed interval due-date scheduling problem with earliness and due-date costs, An integrated model for the development of marginal water sources in the Negev Desert, A minimal algorithm for the multiple-choice knapsack problem, Exact and approximation algorithms for the operational fixed interval scheduling problem, An exact algorithm for general, orthogonal, two-dimensional knapsack problems, A method for the cutting stock problem with different qualities, A statistical approach to adaptive problem solving, Optimization of multi-feeder (depot) printed circuit board manufacturing with error guarantees., A dynamic programming based algorithm for the crew scheduling problem., A hybrid algorithm for solving network flow problems with side constraints., Optimal bandwidth allocation for bandwidth adaptation in wireless multimedia networks., A heuristic decomposition approach to optimal control in a water supply model, Design of a degree-constrained minimal spanning tree with unreliable links and node outage costs., An algorithm for single machine sequencing with deadlines to minimize total weighted completion time, The multidimensional 0-1 knapsack problem: an overview., Surrogate duality relaxation for job shop scheduling, The design of multiactivity multifacility systems, Locational analysis, The hierarchical network design problem with transshipment facilities, Lagrangean decomposition for integer nonlinear programming with linear constraints, A solution procedure for the file allocation problem with file availability and response time, The \(K\)-coverage concentrator location problem, Flow network design for manufacturing systems layout, Integrating facility layout with process selection and capacity planning, Configuration of fully replicated distributed database system over wide area networks, Locating concentrators in centralized computer networks, Relaxations for probabilistically constrained programs with discrete random variables, A matching-based approach for solving a delivery/pick-up vehicle routing problem with time constraints, Capacitated lot-sizing and scheduling by Lagrangean relaxation, A survey of algorithms for the generalized assignment problem, Scheduling examinations to reduce second-order conflicts, Lagrangian approach for large-scale least absolute value estimation, A decomposition technique for mixed integer programming problems, A scheduling model for the daily operation of an electric power system, An integrated approach to the part selection and machine loading problem in a class of flexible manufacturing systems, File allocation involving worst case response times and link capacities: Model and solution procedure, A due date assignment algorithm for multiproduct manufacturing facilities, A survey of algorithms for the single machine total weighted tardiness scheduling problem, Facilities location in a competitive environment: A Promethee based multiple criteria analysis, Resource constrained assignment problems, Partial termination rule of Lagrangian relaxation for manufacturing cell formation problems, Conditional subgradient optimization -- theory and applications, An adaptation of SH heuristic to the location set covering problem, Relaxation heuristics for a generalized assignment problem, A tree search algorithm for the crew scheduling problem, Air cargo revenue management: Characteristics and complexities, Single machine earliness and tardiness scheduling, A fuzzy programming approach to multiobjective multidimensional 0-1 knapsack problems, Multifleet routing and multistop flight scheduling for schedule perturbation, A multiperiod two-echelon multicommodity capacitated plant location problem, An exact method for the two-echelon, single-source, capacitated facility location problem, A branch and bound algorithm for a production scheduling problem in an assembly system under due date constraints, Lagrangian heuristics for the two-echelon, single-source, capacitated facility location problem, A constrained nonlinear 0-1 program for data allocation, Capacity planning for phased implementation of flexible manufacturing systems under budget restrictions, Lower bounding techniques for frequency assignment, A hybrid genetic/optimization algorithm for a task allocation problem, Algorithms for a multi-level network optimization problem, Application of the scenario aggregation approach to a two-stage, stochastic, common component, inventory problem with a budget constraint, Cellular control of manufacturing systems, A technique for speeding up the solution of the Lagrangean dual, Inexact subgradient methods with applications in stochastic programming, Experiments with parallel branch-and-bound algorithms for the set covering problem, Scheduling identical parallel machines to minimize total weighted completion time, Analyzing tradeoffs between zonal constraints and accessibility in facility location, Studying the effects of production loss due to setup in dynamic production scheduling
