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

DOI10.1007/s10107-016-1082-7zbMath1387.90156OpenAlexW2547781575MaRDI QIDQ2364490

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

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

Related Items (5)

Indefinite multi-constrained separable quadratic optimization: large-scale efficient solution ⋮ An efficient global algorithm for indefinite separable quadratic knapsack problems with box constraints ⋮ Optimal portfolio deleveraging under market impact and margin restrictions ⋮ Variable fixing method by weighted average for the continuous quadratic knapsack problem ⋮ Fast computation of global solutions to the single-period unit commitment problem

Uses Software

• Matlab
• CPLEX
• Knapsack
• QuadProgBB
• Algorithm 489

Cites Work

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

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