The quadratic knapsack problem -- a survey

From MaRDI portal
Publication:875597

DOI10.1016/j.dam.2006.08.007zbMath1143.90028OpenAlexW2082782506WikidataQ58826435 ScholiaQ58826435MaRDI QIDQ875597

David Pisinger

Publication date: 13 April 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2006.08.007




Related Items (83)

Stochastic Quadratic Knapsack with RecourseA branch-and-cut technique to solve multiobjective integer quadratic programming problemsA new family of facet defining inequalities for the maximum edge-weighted clique problemBiqBin: A Parallel Branch-and-bound Solver for Binary Quadratic Problems with Linear ConstraintsDantzig-Wolfe reformulations for binary quadratic problemsDual mean field search for large scale linear and quadratic knapsack problemsOn exact solution approaches for bilevel quadratic 0-1 knapsack problemOptimizing the half-product and related quadratic Boolean functions: approximation and scheduling applicationsKnapsack problems with dependencies through non-additive measures and Choquet integralA tight upper bound for quadratic knapsack problems in grid-based wind farm layout optimizationGreedy robust wind farm layout optimization with feasibility guaranteeKnapsack problems -- an overview of recent advances. I: Single knapsack problemsKnapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problemsAsymptotic behavior of the quadratic knapsack problemApproximation of the Quadratic Knapsack ProblemGeneralized quadratic multiple knapsack problem and two solution approachesAn iterated ``hyperplane exploration approach for the quadratic knapsack problemA multi-start iterated local search algorithm for the generalized quadratic multiple knapsack problemOn the product knapsack problemLower bounds and exact algorithms for the quadratic minimum spanning tree problemA hybrid three-phase approach for the Max-Mean dispersion problemA Hybrid Heuristic Approach Based on a Quadratic Knapsack Formulation for the Max-Mean Dispersion ProblemA mathematical programming approach to overlapping community detectionOn the solution of nonconvex cardinality Boolean quadratic programming problems: a computational studyApproximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositionsOn the rectangular knapsack problemStructured linear reformulation of binary quadratically constrained quadratic programsSeparable relaxation for nonconvex quadratic integer programming: Integer diagonalization approachAn exact semidefinite programming approach for the max-mean dispersion problemProduct allocation to different types of distribution center in retail logistics networksDual mean field annealing scheme for binary optimization under linear constraintsA cut-and-branch algorithm for the quadratic knapsack problemAn effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problemSDP-based branch-and-bound for non-convex quadratic integer optimizationA lifted-space dynamic programming algorithm for the quadratic knapsack problemAggregation with dependencies: capacities and fuzzy integralsThe symmetric quadratic knapsack problem: approximation and scheduling applicationsA general purpose exact solution method for mixed integer concave minimization problemsApproximation of the quadratic knapsack problemKnapsack problem with probability constraintsA Dynamic Programming Heuristic for the Quadratic Knapsack ProblemOn the rectangular knapsack problem: approximation of a specific quadratic knapsack problemLocating a discrete subtree of minimum variance on trees: new strategies to tackle a very hard problemQuadratic Combinatorial Optimization Using Separable UnderestimatorsGlobal optimality conditions and optimization methods for quadratic knapsack problemsAn Exact Algorithm for the Quadratic Multiknapsack Problem with an Application to Event SeatingEnhancing semidefinite relaxation for quadratically constrained quadratic programming via penalty methodsCompletely positive and copositive program modelling for quadratic optimization problemsAn Iterative Scheme for Valid Polynomial Inequality Generation in Binary Polynomial ProgrammingHEURISTIC AND EXACT SOLUTION METHOD FOR CONVEX NONLINEAR KNAPSACK PROBLEMOptimal allocation of buffer times to increase train schedule robustnessMINIMIZING TOTAL WEIGHTED EARLINESS-TARDINESS ON A SINGLE MACHINE AROUND A SMALL COMMON DUE DATE: AN FPTAS USING QUADRATIC KNAPSACKOn reduction of duality gap in quadratic knapsack problemsSimple solution methods for separable mixed linear and quadratic knapsack problemA computational study on the quadratic knapsack problem with multiple constraintsReoptimization in Lagrangian methods for the \(0\)-\(1\) quadratic knapsack problemFully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applicationsBranch-and-price for \(p\)-cluster editingOptimizing a polyhedral-semidefinite relaxation of completely positive programsExact solution approach for a class of nonlinear bilevel knapsack problemsPolynomial-size formulations and relaxations for the quadratic multiple knapsack problemExact and approximate algorithms for discounted \(\{0\text{-}1\}\) knapsack problemLagrangian heuristics for the quadratic knapsack problemTheoretical and computational study of several linearisation techniques for binary quadratic problemsReformulation of the Quadratic Multidimensional Knapsack Problem as Copositive/Completely Positive ProramsKnapsackOn linear conic relaxation of discrete quadratic programsA Genetic Algorithm for Optimization of a Relational Knapsack Problem with Respect to a Description Logic Knowledge BaseA matheuristic for the 0--1 generalized quadratic multiple knapsack problemExact Solution Methods for the k-Item Quadratic Knapsack ProblemConcise RLT forms of binary programs: A computational study of the quadratic knapsack problemComputational comparison of exact solution methods for 0-1 quadratic programs: recommendations for practitionersAN IMPROVED CONVEX 0-1 QUADRATIC PROGRAM REFORMULATION FOR CHANCE-CONSTRAINED QUADRATIC KNAPSACK PROBLEMSParametric convex quadratic relaxation of the quadratic knapsack problemA nonlinear multidimensional knapsack problem in the optimal design of mixture experimentsRepresentations of quadratic combinatorial optimization problems: a case study using quadratic set covering and quadratic knapsack problemsIterated responsive threshold search for the quadratic multiple knapsack problemThe polynomial robust knapsack problemSolving the 0-1 quadratic knapsack problem with a competitive quantum inspired evolutionary algorithmA note on semidefinite relaxation for 0-1 quadratic knapsack problemsCutting planes for RLT relaxations of mixed 0-1 polynomial programsA simplified binary artificial fish swarm algorithm for 0-1 quadratic knapsack problemsA dynamic inequality generation scheme for polynomial programming


Uses Software


Cites Work


This page was built for publication: The quadratic knapsack problem -- a survey