Capacitated selection problem

Optimizing the selection of resources to accomplish a set of tasks involves evaluating the tradeoffs between the cost of maintaining the resources nec essary to accomplish the tasks and the penalty cost associated with unfinis hed 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 s elected. The objective is to minimize the sum of penalty costs and resource costs. This problem has several practical applications including productio n planning, new product design, menu selection and inventory management. We develop a branch-and-bound algorithm to find exact solutions to the proble m. To generate bounds, we utilize a dual ascent procedure which exploits th e special structure of the problem. Information from the dual and recovered primal solutions are used to select branching variables. We generate stron g valid inequalities and use them to fix other variables at each branching step. Results of tests performed on reasonably sized problems are presented . (C) 1999 John Wiley & Sons, Inc.