Approximate and exact algorithms for the fixed-charge knapsack problem

Approximate and exact algorithms for the fixed-charge knapsack problem

0.00 Avg rating0 Votes
Article ID: iaor2007405
Country: Netherlands
Volume: 170
Issue: 2
Start Page Number: 363
End Page Number: 375
Publication Date: Apr 2006
Journal: European Journal of Operational Research
Authors:
Keywords: programming: branch and bound
Abstract:

The subject of this paper is the formulation and solution of a variation of the classical binary knapsack problem. The variation that is addressed is termed the ‘fixed-charge knapsack problem’, in which sub-sets of variables (activities) are associated with fixed costs. These costs may represent certain set-ups and/or preparations required for the associated sub-set of activities to be scheduled. Several potential real-world applications as well as problem extensions/generalizations are discussed. The efficient solution of the problem is facilitated by a standard branch-and-bound algorithm based on (1) a non-iterative, polynomial algorithm to solve the LP relaxation, (2) various heuristic procedures to obtain good candidate solutions by adjusting the LP solution, and (3) powerful rules to peg the variables. Computational experience shows that the suggested branch-and-bound algorithm shows excellent potential in the solution of a wide variety of large fixed-charge knapsack problems.

Reviews

Required fields are marked *. Your email address will not be published.