A Sequential Algorithm for an Inventory Selection Problem

Assume that we have m finished products in an inventory. Eachfinished product is characterized by two measurements P andQ. A customer specifies a purchase order by the requirementsof characteristics P and Q. A product is qualified to satisfya purchase order if and only if it possesses better measurementsof both P and Q than the customer requires. For a given batchof n purchase orders, the inventory selection problem is tochoose n finished products from the inventory to satisfy allpurchase orders with a minimum cost. This problem can be formulatedas a large-scale transportation problem. When the cost functionof selecting a product to satisfy an order exhibits certainstructure, we develop a fast sequential algorithm to solve thisproblem. Possible extensions and related problems are also discussedin this paper.