An Implicit Enumeration Scheme for the Batch Selection Problem

An important problem arising in the management of logistic networks is the following: given a set of activities to be performed, each requiring a set of resources, select the optimal set of resources compatible with the system capacity constraints. This problem is called Batch Selection Problem (BSP) from traditional applications to flexible manufacturing. BSP is known to be NP-hard, and is also considered a difficult integer programming problem. In fact, polyhedral approaches to BSP suffer from the poor quality of the bound provided by the linear relaxation, even after strengthening. We devise an implicit enumeration scheme that attempts to overcome this difficulty. It is based on a formulation of BSP, which is equivalent to a stable set problem with one side constraint. This allows to exploit the upper bound, not only for pruning subproblems, but also for controlling the number and the quality of the subproblems generated. We show the effectiveness of the approach by an extensive computational experience on real-sized randomly generated instances. (C) 2004 Wiley Periodicals, Inc.