A two-phase method for solving continuous rank-one quadratic knapsack problems

DOI10.22067/IJNAO.2022.70644.1096MaRDI QIDQ5054022zbMATH OpenOpenAlexFDO

Authors Sayyed Ehsan Monabbati

Publication date 29 November 2022

Full work available at URL https://arxiv.org/abs/2001.03766

zbMATH Keywords

line-sweep algorithmquadratic knapsack problem

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Quadratic programming (90C20) Convex programming (90C25)

Abstract: In this paper, we propose a two-phase algorithm for solving continuous rank-one quadratic knapsack problems (R1QKP). In particular, we study the solution structure of the problem without the knapsack constraint. We propose an $O(nlogn)$ algorithm in this case. We then use the solution structure to propose an $O(n^{2}logn)$ algorithm that finds an interval containing the optimal value of the Lagrangian dual of R1QKP. In the second phase, we solve the restricted Lagrangian dual problem using a traditional single-variable optimization method. We perform a computational test on random instances and compare our algorithm with the general solver CPLEX.

Recommendations

• Rank two relaxation to the quadratic knapsack problem
• On the continuous quadratic knapsack problem
• A Newton's method for the continuous quadratic knapsack problem
• On linear-time algorithms for the continuous quadratic Knapsack problem
• An Efficient Method for a Class of Continuous Nonlinear Knapsack Problems
• scientific article; zbMATH DE number 6836465
• Efficient Methods For Solving Quadratic 0–1 Knapsack Problems
• Lagrangean methods for the 0-1 quadratic knapsack problem
• A semidefinite programming approach to the quadratic knapsack problem
• Exact solution methods for the k-item quadratic knapsack problem

Cites work

• A class of nonlinear nonseparable continuous Knapsack and multiple-choice knapsack problems
• A Newton's method for the continuous quadratic knapsack problem
• A polynomially bounded algorithm for a singly constrained quadratic program
• A survey on the continuous nonlinear resource allocation problem
• A two-phase gradient method for quadratic programming problems with a single linear constraint and bounds on the variables
• A two-phase method for solving continuous rank-one quadratic knapsack problems
• Algorithms for the continuous nonlinear resource allocation problem -- new implementations and numerical studies
• Algorithms for the solution of quadratic knapsack problems
• An O(n) algorithm for quadratic knapsack problems
• Augmented Lagrangians, box constrained QP and extensions
• Computational geometry. Algorithms and applications.
• Convex quadratic programming with one constraint and bounded variables
• Disaggregation and Resource Allocation Using Convex Knapsack Problems with Bounded Variables
• Fast algorithm for singly linearly constrained quadratic programs with box-like constraints
• New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds
• On the continuous quadratic knapsack problem

Cited in

(4)

• Variable fixing method by weighted average for the continuous quadratic knapsack problem
• scientific article; zbMATH DE number 6836465 (Why is no real title available?)
• A two-phase method for solving continuous rank-one quadratic knapsack problems
• A Newton's method for the continuous quadratic knapsack problem

Describes a project that uses

Uses Software

• CPLEX

This page was built for publication: A two-phase method for solving continuous rank-one quadratic knapsack problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5054022)