Binary knapsack problems with random budgets |
| |
Authors: | S Das D Ghosh |
| |
Institution: | 1.QM&IS Area, Indian Institute of Management,Bangalore,India;2.P&QM Area, Indian Institute of Management,Ahmedabad,India |
| |
Abstract: | The binary knapsack problem is a combinatorial optimization problem in which a subset of a given set of elements needs to be chosen in order to maximize profit, given a budget constraint. In this paper, we study a stochastic version of the problem in which the budget is random. We propose two different formulations of this problem, based on different ways of handling infeasibility, and propose an exact algorithm and a local search-based heuristic to solve the problems represented by these formulations. We also present the results from some computational experiments. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|