Capacitated selection problem

✍ Scribed by Renato de Matta; Vernon Ning Hsu; Timothy J. Lowe

• Publisher: John Wiley and Sons
• Year: 1999
• Tongue: English
• Weight: 105 KB
• Volume: 46
• Category: Article
• ISSN: 0894-069X
• DOI: 10.1002/(sici)1520-6750(199902)46:1<19::aid-nav2>3.0.co;2-l

✦ Synopsis

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.