Home  About us  Contact
 

Lagrangian Heuristic (lagrangian + heuristic)

Distribution by Scientific Domains
Mathematics and Statistics60%

Selected Abstracts

Coordinated Capacitated Lot-Sizing Problem with Dynamic Demand: A Lagrangian Heuristic

DECISION SCIENCES, Issue 1 2004
E. Powell Robinson Jr.
ABSTRACT Coordinated replenishment problems are common in manufacturing and distribution when a family of items shares a common production line, supplier, or a mode of transportation. In these situations the coordination of shared, and often limited, resources across items is economically attractive. This paper describes a mixed-integer programming formulation and Lagrangian relaxation solution procedure for the single-family coordinated capacitated lot-sizing problem with dynamic demand. The problem extends both the multi-item capacitated dynamic demand lot-sizing problem and the uncapacitated coordinated dynamic demand lot-sizing problem. We provide the results of computational experiments investigating the mathematical properties of the formulation and the performance of the Lagrangian procedures. The results indicate the superiority of the dual-based heuristic over linear programming-based approaches to the problem. The quality of the Lagrangian heuristic solution improved in most instances with increases in problem size. Heuristic solutions averaged 2.52% above optimal. The procedures were applied to an industry test problem yielding a 22.5% reduction in total costs. [source]

Locating a Surveillance Infrastructure in and Near Ports or on Other Planar Surfaces to Monitor Flows

COMPUTER-AIDED CIVIL AND INFRASTRUCTURE ENGINEERING, Issue 2 2010
Pitu B. Mirchandani
This article addresses the problem of locating surveillance radars to cover a given target surface that may have barriers through which radar signals cannot penetrate. The area of coverage of a radar is assumed to be a disc, or a partial disc when there are barriers, with a known radius. The article shows that the corresponding location problems relate to two well studied problems: the set-covering model and the maximal covering problem. In the first problem, the minimum number of radars is to be located to completely cover the target area; in the second problem a given number M of radars are to be located to cover the target area as much as possible. Based on a discrete representation of the target area, a Lagrangian heuristic and a two-stage procedure with a conquer-and-divide scaling are developed to solve the above two models. The computational experiences reported demonstrate that the developed method solves well the radar location problems formulated here. [source]

A two-echelon inventory-location problem with service considerations

NAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 8 2009
Ho-Yin Mak
Abstract We study the problem of designing a two-echelon spare parts inventory system consisting of a central plant and a number of service centers each serving a set of customers with stochastic demand. Processing and storage capacities at both levels of facilities are limited. The manufacturing process is modeled as a queuing system at the plant. The goal is to optimize the base-stock levels at both echelons, the location of service centers, and the allocation of customers to centers simultaneously, subject to service constraints. A mixed integer nonlinear programming model (MINLP) is formulated to minimize the total expected cost of the system. The problem is NP-hard and a Lagrangian heuristic is proposed. We present computational results and discuss the trade-off between cost and service. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009 [source]

Outbound supply chain network design with mode selection and lead time considerations

NAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 3 2007
Erdem Eskigun
Abstract We present a large-scale network design model for the outbound supply chain of an automotive company that considers transportation mode selection (road vs. rail) and explicitly models the relationship between lead times and the volume of flow through the nodes of the network. We formulate the problem as a nonlinear zero-one integer program, reformulate it to obtain a linear integer model, and develop a Lagrangian heuristic for its solution that gives near-optimal results in reasonable time. We also present scenario analyses that examine the behavior of the supply chain under different parameter settings and the performance of the solution procedures under different experimental conditions. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007 [source]

Minimum-weight rooted not-necessarily-spanning arborescence problem

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 2 2002
V. Venkata Rao
Abstract In this paper, we propose the problem of identifying a minimum-weight rooted not-necessarily-spanning arborescence (MRA) in a directed rooted acyclic graph with weights on arcs. We show this problem to be NP-hard and formulate it as a zero,one integer program. We develop a heuristic H to construct a rooted arborescence (RA) in a given graph G, giving an upper bound. We also formulate a Lagrangian problem, LMRA, by relaxing one set of constraints of the zero,one integer program. For a given set of Lagrange multipliers, LMRA can be easily solved to obtain a lower bound. Then, we propose a Lagrangian heuristic, L, that generates both a lower bound and an upper bound in each iteration. The above heuristics were tested with 50 test problems. We also compared the performance of L with a general-purpose optimization package, CPLEX, using 12 test problems. The results show that L was able to identify an optimal solution in almost all cases. CPLEX found an optimal solution in all cases, but was not able to verify optimality in some instances. © 2002 Wiley Periodicals, Inc. [source]