An exact algorithm for large multiple knapsack problems

Article Abstract:

The MULKNAP algorithm, which is based on the MTM framework of Martello and Toth, is the first algorithm capable of solving large sized cases up to n=100,000 with data range of as much as R=10,000. MULKNAP uses specialized algorithms to derive both lower bounds and upper bounds as well as solve the Subset-sum Problem. It has been demonstrated that despite the unsuitability of Multiple Knapsack Problem in dynamic programming, dynamic programming algorithms can be used to provide the needed solutions.

Research, Dynamic programming, Branch and bound algorithms

---

The inverse-parametric knapsack problem

Article Abstract:

The inverse-parametric knapsack problem is analyzed wherein the costs of a knapsack problem are replaced by linear functions in a parameter t. A value for t is then needed to make the optimal solution of the knapsack problem equal to a given solution value. Pseudopolynomial algorithms were derived for the inverse-parametric problem. Sample applications show that straight-forward methods perform better than pseudopolynomial algorithms.

Models, Combinatorial optimization

---

Approximation algorithms for knapsack problems with cardinality constraints

Article Abstract:

A variant of the classical knapsack problem is considered.

Operations research, Management science, Analysis, Usage

Similar abstracts:

• Abstracts: A note on exact algorithms for the bottleneck generalized assignment problem. New trends in exact algorithms for the 0-1 knapsack problem

This website is not affiliated with document authors or copyright owners. This page is provided for informational purposes only. Unintentional errors are possible.