An Algorithm for the Assignment Problem with Stochastic Side Constraints

Abstract

In this paper, we consider the assignment problem with stochastic side constraints, and propose a practical algorithm for solving it. Such a problem may arise, for example, when the assignment requires some scarce resources and the total amounts of those resources are subject to a random variation. Therefore, the problem seems quite general and significant in practice. This algorithm takes a special structure of the problem into account, and may be regarded as a heuristic modification of the method for two-stage linear programming under uncertainty. Although we cannot guarantee that the solution obtained by the proposed algorithm will coincide with the true optimal solution of the problem, our limited computational experience on small test problems indicates that good approximate solutions can be obtained in a fairly small computation time.