Tight bounds on indefinite separable singly-constrained quadratic programs in linear-time

DOI10.1007/S10107-016-1082-7MaRDI QIDQ2364490zbMATH OpenOpenAlexFDO

Authors Jaehwan Jeong, N. Chanaka P. Edirisinghe

Publication date 21 July 2017

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10107-016-1082-7

zbMATH Keywords

lower and upper boundsindefinite knapsack problemslinear-time complexityseparable quadratic optimization

Mathematics Subject Classification ID

Quadratic programming (90C20) Nonconvex programming, global optimization (90C26) Mixed integer programming (90C11)

Recommendations

• An efficient global algorithm for a class of indefinite separable quadratic programs
• Indefinite multi-constrained separable quadratic optimization: large-scale efficient solution
• Fast algorithm for the quadratic knapsack problem
• Simple solution methods for separable mixed linear and quadratic knapsack problem
• Effective algorithms for separable nonconvex quadratic programming with one quadratic and box constraints

Cites work

• scientific article; zbMATH DE number 5641435 (Why is no real title available?)
• A Newton's method for the continuous quadratic knapsack problem
• Algorithms for the continuous nonlinear resource allocation problem -- new implementations and numerical studies
• An efficient global algorithm for a class of indefinite separable quadratic programs
• Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
• Globally solving nonconvex quadratic programming problems via completely positive programming
• Local minima for indefinite quadratic knapsack problems
• New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds
• Nonlinear Programming
• On the continuous quadratic knapsack problem
• On the solution of concave knapsack problems
• Where are the hard knapsack problems?

Cited in

(7)

• Optimal portfolio deleveraging under market impact and margin restrictions
• An efficient global algorithm for indefinite separable quadratic knapsack problems with box constraints
• Indefinite multi-constrained separable quadratic optimization: large-scale efficient solution
• Fast computation of global solutions to the single-period unit commitment problem
• An efficient global algorithm for a class of indefinite separable quadratic programs
• Variable fixing method by weighted average for the continuous quadratic knapsack problem
• A fast global algorithm for singly linearly constrained separable binary quadratic program with partially identical parameters

Describes a project that uses

Uses Software

• Matlab
• CPLEX
• Knapsack
• QuadProgBB
• Algorithm 489

This page was built for publication: Tight bounds on indefinite separable singly-constrained quadratic programs in linear-time

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