Solving the Undirected Multicommodity Flow Problem Using a Shortest Path Based Pricing Algorithm. J.W. Mamer, R.D. McBride. 2002.
The undirected multicommodity flow problem is encountered in the solution to traffic-scheduling problems related to computer, communication, railroad, and other networks. We show how to formulate this problem as a piecewise linear optimization problem (with piecewise linear convex functions in both the objective and the constraints). We discuss how EMNET, a primal basis partitioning simplex algorithm, was modified so as to efficiently solve these problems using a pricing procedure that we call “shortest path pricing.” Extremely good solution times for some very large problems are presented. The solutions are not only obtained quickly, but also with a fraction of the number of pivots that are needed for the standard simplex method.
Inventory Policies for Sequences of Multi-Item Demands with No Backorders Permitted. J.W. Mamer, S.A. Smith. Supply Chain Structures: Coordination, Information, and Optimization. J.S. Song, D. Yao (eds.). 427-449. Kluwer Academic Publishers. December 2001.
Sequences of multi-item demands arise naturally in the analysis of repair kit planning and mission provisioning. There are constraints on the aggregate value, weight, and volume of items placed in inventory, the objective is to maximize either the expected number of demands that can be met or the probability that a sequence of demands of a given length can be filled. Each demand requires a different (and possibly overlapping) set of items, and the precise contents of future demands are not known at the time stock levels determined. The interdependence among the demands for items, resulting in a large number of distinct demand sets, makes determining the optimal stock levels challenging. Stocking decisions based on the marginal demand rates for each item can be quite misleading. We formulate the problem, and suggest some bounds on the performance of a stocking policy. The bounds we propose have a very simple form and it is a straightforward task to find policies which optimize the bounds. The repair kit problem provides the context for our analysis. For clarity we will call the items to be stocked “parts” and the demands “repair jobs”. We conclude with two illustrative examples.
A Decomposition Based Pricing Procedure for Large Scale Linear Programs: An Application to the Linear Multicommodity Flow Problem. J.W. Mamer, R.D. McBride. Management Science. 46(5): 693-709. May 2000.
We propose and test a new pricing procedure for solving large-scale structured linear programs. The procedure interactively solves a relaxed sub problem to identify potential entering basic columns. The sub problem is chosen to exploit special structure, rendering it easy to solve. The effect of the procedure is the reduction of the number of pivots needed to solve the problem. Our approach is motivated by the column-generation approach of Dantzig-Wolfe decomposition. We test our procedure on two sets of multicommodity flow problems. One group of test problems arises in routing telecommunications traffic and the second group is a set of logistics problem which have been widely used to test multicommodity flow algorithms.
Routing Heuristics for Automated Pick and Place Machines. R.H. Ahmadi, J.W. Mamer. European Journal of Operational Research. 117(3): 533-552. September 1999.
The problem of sequencing the placements of multiple part types for a computer controlled placement machine is examined. The problem is modeled as a collection of interdependent traveling salesman problems. A heuristic based on a space filling curve is shown to be easy to compute and quite effective. Numerical experiments show that on problems of realistic size the heuristics show very little divergence from optimality. The probabilistic analysis of the proposed heuristic indicates that the proposed heuristics are asymptotically optimal. Finally, the heuristic is used to perform the sequencing operation on real placement machines. The results of this experiment are in accord with the numerical simulations. The main ideas have become part of the control system currently in use in a large electronic card assembly facility that produces approximately 12,000 boards per day. Improvements in throughput of between 4% and 9% have been reported.
Competitive Equilibrium in an Exchange Economy with Indivisibilities. S. Bikhchandani, J.W. Mamer. Journal of Economic Theory. 74(2): 385-413. June 1997.
We analyze an exchange economy in which (i) all commodities except money are indivisible, (ii) agents' preferences can be described by a reservation value for each bundle of indivisible objects, and (iii) all agents are price-takers. We obtain a necessary and sufficient condition under which market clearing prices exist. Implications for market mechanisms are discussed.
Solving Multicommodity Flow Problems with a Primal Embedded Network Simplex Algorithm. J.W. Mamer, R.D. McBride. INFORMS Journal on Computing. 9(2): 154-163. Spring 1997.
This article describes the authors’ experiences solving large multicommodity flow problems with an embedded network simplex algorithm augmented with a fast start heuristic for choosing an initial basis. The heuristic makes successive capacity allocations in an attempt to find a feasible initial basis. Our implementation of the heuristic makes use of piece-wise linear convex costs. The efficacy of our heuristic, and of the embedded network simplex method, is demonstrated on large publicly available multicommodity flow problems. Comparisons with other published computational results are given.