Linear programming for the 0-1 quadratic knapsack problem
From MaRDI portal
Publication:1268263
DOI10.1016/0377-2217(94)00229-0zbMATH Open0912.90221OpenAlexW2026973340WikidataQ127012240 ScholiaQ127012240MaRDI QIDQ1268263FDOQ1268263
Authors: 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
Recommendations
branch-and-boundquadratic knapsack problemlinear capacity constraintpositive quadratic pseudo-Boolean function
Quadratic programming (90C20) Linear programming (90C05) Integer programming (90C10) Boolean programming (90C09)
Cites Work
- A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
- Quadratic knapsack problems
- 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
- Assignment of Tasks in a Distributed Processor System with Limited Memory
- Roof duality, complementation and persistency in quadratic 0–1 optimization
- Computational aspects of a branch and bound algorithm for quadratic zero- one programming
- Title not available (Why is that?)
- Methods of Nonlinear 0-1 Programming
- Experiments in quadratic 0-1 programming
- Minimization of a quadratic pseudo-Boolean function
- The indefinite zero-one quadratic problem
- On the supermodular knapsack problem
- A new bound for the quadratic knapsack problem and its use in a branch and bound algorithm
- Lagrangean methods for 0-1 quadratic problems
Cited In (57)
- Inductive linearization for binary quadratic programs with linear constraints: a computational study
- Upper bounds and exact algorithms for \(p\)-dispersion problems
- Cutting planes for RLT relaxations of mixed 0-1 polynomial programs
- A note on representations of linear inequalities in non-convex mixed-integer quadratic programs
- A Lagrangian decomposition approach to computing feasible solutions for quadratic binary programs
- The polynomial robust knapsack problem
- Construction de facettes pour le polytope du sac-à-dos quadratique en 0-1
- Solution of large quadratic knapsack problems through aggressive reduction
- Simple solution methods for separable mixed linear and quadratic knapsack problem
- A matheuristic for the 0--1 generalized quadratic multiple knapsack problem
- Constrained 0-1 quadratic programming: basic approaches and extensions
- Coefficient reduction for knapsack-like constraints in 0-1 programs with variable upper bounds
- Block linear majorants in quadratic 0--1 optimization
- An iterated ``hyperplane exploration approach for the quadratic knapsack problem
- Title not available (Why is that?)
- A multi-start iterated local search algorithm for the generalized quadratic multiple knapsack problem
- 0-1 quadratic knapsack problems: an exact approach based on a \(t\)-linearization
- The newsvendor problem with capacitated suppliers and quantity discounts
- A branch-and-bound algorithm for multi-dimensional quadratic 0–1 knapsack problems
- Exact Solution of the Quadratic Knapsack Problem
- A branch-and-bound algorithm for the quadratic multiple knapsack problem
- Polyhedral combinatorics of the cardinality constrained quadratic knapsack problem and the quadratic selective travelling salesman problem
- Lagrangian heuristics for the quadratic knapsack problem
- On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem
- Quadratic bottleneck knapsack problems
- Strong RLT1 bounds from decomposable Lagrangean relaxation for some quadratic \(0-1\) optimization problems with linear constraints
- Parametric convex quadratic relaxation of the quadratic knapsack problem
- Global optimality conditions and optimization methods for quadratic knapsack problems
- A new bound for the quadratic knapsack problem and its use in a branch and bound algorithm
- Using a mixed integer programming tool for solving the 0-1 quadratic knapsack problem
- An effective GRASP and tabu search for the 0-1 quadratic knapsack problem
- An O(n) algorithm for quadratic knapsack problems
- 0-1 quadratic knapsack problem solved with VNS algorithm
- Generalized quadratic multiple knapsack problem and two solution approaches
- A cut-and-branch algorithm for the quadratic knapsack problem
- An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem
- A Branch-and-Bound Algorithm for Team Formation on Social Networks
- Strengthening a linear reformulation of the 0-1 cubic knapsack problem via variable reordering
- Comparisons and enhancement strategies for linearizing mixed 0-1 quadratic programs
- Title not available (Why is that?)
- The nonlinear knapsack problem - algorithms and applications
- A new upper bound for the 0-1 quadratic knapsack problem
- A simple procedure for solving a continuous quadratic mathematical model.
- The quadratic knapsack problem -- a survey
- Lagrangean decompositions for the unconstrained binary quadratic programming problem
- The submodular knapsack polytope
- A computational study on the quadratic knapsack problem with multiple constraints
- Reoptimization in Lagrangian methods for the \(0\)-\(1\) quadratic knapsack problem
- The quadratic 0-1 knapsack problem with series-parallel support
- A dynamic programming heuristic for the quadratic knapsack problem
- Inductive linearization for binary quadratic programs with linear constraints
- Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement
- Exact solution methods for the \(k\)-item quadratic knapsack problem
- On a nonseparable convex maximization problem with continuous Knapsack constraints
- A lifted-space dynamic programming algorithm for the quadratic knapsack problem
- A nonlinear multidimensional knapsack problem in the optimal design of mixture experiments
- An Exact Algorithm for the Quadratic Multiknapsack Problem with an Application to Event Seating
This page was built for publication: Linear programming for the \(0-1\) quadratic knapsack problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1268263)
