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

indefinite knapsack problemslinear-time complexitylower and upper boundsseparable quadratic optimization

Mathematics Subject Classification ID

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

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

• 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
• scientific article; zbMATH DE number 5641435 (Why is no real title available?)
• 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

(9)

• Variable fixing method by weighted average for the continuous quadratic knapsack problem
• Fast computation of global solutions to the single-period unit commitment problem
• Optimal portfolio deleveraging under market impact and margin restrictions
• Indefinite multi-constrained separable quadratic optimization: large-scale efficient solution
• A fast global algorithm for singly linearly constrained separable binary quadratic program with partially identical parameters
• An efficient global algorithm for a class of indefinite separable quadratic programs
• An efficient global algorithm for indefinite separable quadratic knapsack problems with box constraints
• Reformulations of separable quadratic optimization problems with symmetric structures via variable aggregation
• All-integer global optimization for high-dimensional sparse regression, with applications in financial and genomic data

Describes a project that uses

Uses Software

• Knapsack
• QuadProgBB
• Matlab
• CPLEX
• 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)