Premium
An implicit enumeration scheme for the batch selection problem
Author(s) -
Agnetis A.,
Rossi F.,
Smriglio S.
Publication year - 2004
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20025
Subject(s) - pruning , mathematical optimization , enumeration , set (abstract data type) , computer science , scheme (mathematics) , integer programming , relaxation (psychology) , selection (genetic algorithm) , integer (computer science) , constraint (computer aided design) , upper and lower bounds , branch and bound , linear programming , mathematics , artificial intelligence , discrete mathematics , psychology , mathematical analysis , social psychology , geometry , agronomy , biology , programming language
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. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(2), 151–159 2004