Journal article
Capacitated selection problem
Naval research logistics, Vol.46(1), pp.19-37
02/1999
DOI: 10.1002/(SICI)1520-6750(199902)46:1<19::AID-NAV2>3.0.CO;2-L
Abstract
Optimizing the selection of resources to accomplish a set of tasks involves evaluating the tradeoffs between the cost of maintaining the resources necessary to accomplish the tasks and the penalty cost associated with unfinished tasks. We consider the case where resources are categorized into types, and limits (capacity) are imposed on the number of each type that can be selected. The objective is to minimize the sum of penalty costs and resource costs. This problem has several practical applications including production planning, new product design, menu selection and inventory management. We develop a branch-and-bound algorithm to find exact solutions to the problem. To generate bounds, we utilize a dual ascent procedure which exploits the special structure of the problem. Information from the dual and recovered primal solutions are used to select branching variables. We generate strong valid inequalities and use them to fix other variables at each branching step. Results of tests performed on reasonably sized problems are presented. © 1999 John Wiley & Sons, Inc.
Details
- Title: Subtitle
- Capacitated selection problem
- Creators
- Renato de Matta - University of IowaVernon Ning Hsu - George Mason UniversityTimothy J. Lowe - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Naval research logistics, Vol.46(1), pp.19-37
- Publisher
- John Wiley & Sons, Inc
- DOI
- 10.1002/(SICI)1520-6750(199902)46:1<19::AID-NAV2>3.0.CO;2-L
- ISSN
- 0894-069X
- eISSN
- 1520-6750
- Number of pages
- 19
- Language
- English
- Date published
- 02/1999
- Academic Unit
- Business Analytics
- Record Identifier
- 9984380391102771
Metrics
1 Record Views