An implicit enumeration scheme for the batch selection problem

An implicit enumeration scheme for the batch selection problem

0.00 Avg rating0 Votes
Article ID: iaor20051090
Country: Netherlands
Volume: 44
Issue: 2
Start Page Number: 151
End Page Number: 159
Publication Date: Jul 2004
Journal: Networks
Authors: , ,
Keywords: programming: integer
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.