An expanding-core algorithm for the exact 0-1 knapsack problem

Article Abstract:

A novel branch-and-bound procedure for solving the 0-1 knapsack problem is introduced. The problem, which concerns the placement of n items into a knapsack of given capacity c, requires the maximization of the profit sum under the constraint that the total weight of the items is less than the c. The new algorithm, which has been dubbed EXPKNAP, eliminates sorting and reduction steps to yield an exact solution in less time than other methods.

Case studies

---

Avoiding anomalies in the MT2 algorithm by Martello and Toth

Article Abstract:

The MT2 algorithm of Martello and Toth for the solution of the Knapsack Problem enables the solution of some profit maximization problems in fractions of a second. However, it also takes many hours to solve other problems. This anomalous behavior is due to the a-priori identification of the core problem and the expenditure of too much computation time trying to solve it. The anomalous behavior may be avoided by evading the core problem.

Evaluation, Mathematical optimization, Optimization theory

---

Budgeting with bounded multiple-choice constraints

Article Abstract:

Research is presented describing the development of a dynamic programming model for costing projects where several constraints limit expansion and budgets are required.

Usage, Production (Economics), Dynamic programming

Similar abstracts:

• Abstracts: An exact algorithm for the knapsack sharing problem with common items. Heuristic and exact algorithms for the simultaneous assignment problem
• Abstracts: Evaluation of leading heuristics for the single machine tardiness problem. A comparison of stochastic scheduling rules for maximizing project net present value
• Abstracts: A new penalty function algorithm for convex quadratic programming. Effect of maintenance on the economic design of x-control chart
• Abstracts: The use of genetic algorithms to solve the economic lot size scheduling problem. Basket problems in margin calculation: Modelling and algorithms
• Abstracts: A multiattribute decision-theoretic approach for the layout design problem. Modeling and algorithmic development of a staff scheduling problem

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