A new upper bound for the 0-1 quadratic knapsack problem

Article Abstract:

A study was conducted to present a solution to the 0-1 quadratic knapsack problem using a novel method based on Lagrangian decomposition. A quadratic pseudo-Boolean function was defined using real coefficients. Computational experiments were carried out to determine the effectiveness of the bound for large size instances. An algorithm was then implemented in C language using an HP 9000 workstation. Findings showed that the method generated approximate solutions to the problem that supported a relative error less than 1%.

Operations Research, Usage, Decomposition method, Algebra, Boolean, Boolean algebra

---

Linear programming for the 0-1 quadratic knapsack problem

Article Abstract:

A method for computing an upper bound for the 0-1 quadratic knapsack problem is proposed. The problem concerns the maximization of a pseudo-Boolean quadratic function subject to a linear capacity constraint. The proposed method is based on the solution of a continuous linear program which is formed by adding constraints redundant in 0-1 variables but nonredundant in continuous variables to a classical linearization of the problem. The resulting upper bound is better than those derived through existing methods.

Linear programming, Branch and bound algorithms

---

An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem

Article Abstract:

An exact method, derived from Lagrangian decomposition, is presented to solve the 0-1 quadratic knapsack problem (QKP) that consists in maximizing a quadratic pseudo-Boolean function with positive coefficients subject to a linear capacity constraint. The method can be used to solve 150-variable problems regardless of density, going up to 300 variables for medium and low density.

Density functionals, Density functional theory, Lagrangian functions

Similar abstracts:

• Abstracts: Exact solution methods for uncapacitated location problems with convex transportation costs. Bicriteria network location (BNL) problems with criteria dependant lengths and minisum objectives
• Abstracts: Netter slips under the tonnage limit. Pelagic skippers renew their ships. Is that my ship? u asks owner after conversion
• Abstracts: A decision support system for a real vehicle routing problem. Solving the flowshop scheduling problem with sequence dependent setup times using advanced metaheuristics
• Abstracts: A tabu search algorithm for the multi-trip vehicle routing and scheduling problem. A tabu search algorithm for the open vehicle routing problem

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