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 NPhard, 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.

An implicit enumeration scheme for the batch selection problem

ROSSI, FABRIZIO;SMRIGLIO, STEFANO
2004-01-01

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 NPhard, 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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11697/1608
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact