2019 journal article

Allocation under a general substitution structure

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 277(2), 492–506.

By: Y. Tseytlin* & H. Heese n 

co-author countries: Germany πŸ‡©πŸ‡ͺ United States of America πŸ‡ΊπŸ‡Έ
author keywords: Inventory; Substitution; Allocation; Transportation problem; Monge sequences
Source: Web Of Science
Added: May 20, 2019

Abstract We develop a novel solution approach for the single-period multi-product inventory allocation problem with general substitution structure. First, we construct an initial allocation sequence and present conditions for existence of a Monge sequence, implying optimality of a greedy solution. We prove that the greedy allocation along the initial sequence is optimal even if no Monge sequence exists, when in the solution all demand is satisfied and all inventory is used. For all other cases, we develop a correction algorithm and prove optimality of the resulting allocation. The worst-case computational complexity of our solution is superior to existing algorithms for the structurally related transportation problem.