Linear programming for the \(0-1\) quadratic knapsack problem

DOI10.1016/0377-2217(94)00229-0zbMath0912.90221OpenAlexW2026973340WikidataQ127012240 ScholiaQ127012240MaRDI QIDQ1268263

Alain Billionnet, Frédéric Calmels

Publication date: 1996

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(94)00229-0

zbMATH Keywords

branch-and-boundquadratic knapsack problemlinear capacity constraintpositive quadratic pseudo-Boolean function

Mathematics Subject Classification ID

Integer programming (90C10) Quadratic programming (90C20) Linear programming (90C05) Boolean programming (90C09)

Related Items

Quadratic bottleneck knapsack problems, Comparisons and enhancement strategies for linearizing mixed 0-1 quadratic programs, On a nonseparable convex maximization problem with continuous Knapsack constraints, Generalized quadratic multiple knapsack problem and two solution approaches, An iterated ``hyperplane exploration approach for the quadratic knapsack problem, A multi-start iterated local search algorithm for the generalized quadratic multiple knapsack problem, Strengthening a linear reformulation of the 0-1 cubic knapsack problem via variable reordering, A Branch-and-Bound Algorithm for Team Formation on Social Networks, The quadratic knapsack problem -- a survey, Strong RLT1 bounds from decomposable Lagrangean relaxation for some quadratic \(0-1\) optimization problems with linear constraints, A cut-and-branch algorithm for the quadratic knapsack problem, A lifted-space dynamic programming algorithm for the quadratic knapsack problem, Inductive linearization for binary quadratic programs with linear constraints, A Dynamic Programming Heuristic for the Quadratic Knapsack Problem, On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem, Global optimality conditions and optimization methods for quadratic knapsack problems, An Exact Algorithm for the Quadratic Multiknapsack Problem with an Application to Event Seating, Constrained 0-1 quadratic programming: basic approaches and extensions, Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement, A Lagrangian decomposition approach to computing feasible solutions for quadratic binary programs, Polyhedral combinatorics of the cardinality constrained quadratic knapsack problem and the quadratic selective travelling salesman problem, Simple solution methods for separable mixed linear and quadratic knapsack problem, A computational study on the quadratic knapsack problem with multiple constraints, An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem, Upper bounds and exact algorithms for \(p\)-dispersion problems, The newsvendor problem with capacitated suppliers and quantity discounts, Lagrangian heuristics for the quadratic knapsack problem, A new upper bound for the 0-1 quadratic knapsack problem, Lagrangean decompositions for the unconstrained binary quadratic programming problem, Construction de facettes pour le polytope du sac-à-dos quadratique en 0-1, A matheuristic for the 0--1 generalized quadratic multiple knapsack problem, Exact Solution Methods for the k-Item Quadratic Knapsack Problem, The submodular knapsack polytope, Parametric convex quadratic relaxation of the quadratic knapsack problem, A nonlinear multidimensional knapsack problem in the optimal design of mixture experiments, The polynomial robust knapsack problem, The nonlinear knapsack problem - algorithms and applications, Cutting planes for RLT relaxations of mixed 0-1 polynomial programs, The quadratic 0-1 knapsack problem with series-parallel support

Cites Work

• Unnamed Item
• The indefinite zero-one quadratic problem
• Experiments in quadratic 0-1 programming
• Minimization of a quadratic pseudo-Boolean function
• Lagrangean methods for 0-1 quadratic problems
• On the supermodular knapsack problem
• Computational aspects of a branch and bound algorithm for quadratic zero- one programming
• Roof duality, complementation and persistency in quadratic 0–1 optimization
• A new bound for the quadratic knapsack problem and its use in a branch and bound algorithm
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• Methods of Nonlinear 0-1 Programming
• Quadratic knapsack problems
• Assignment of Tasks in a Distributed Processor System with Limited Memory
• A Fast Parametric Maximum Flow Algorithm and Applications
• A Decomposition Method for Quadratic Zero-One Programming
• Quadratic Binary Programming with Application to Capital-Budgeting Problems