Exact solution method to solve large scale integer quadratic multidimensional knapsack problems

DOI10.1007/s10878-007-9105-1zbMath1180.90201MaRDI QIDQ841599

Eric Soutif, Dominique Quadri, Pierre Tolla

Publication date: 18 September 2009

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://basepub.dauphine.fr/handle/123456789/3950

zbMATH Keywords

integer programming; linearization; branch-and-bound; surrogate relaxation; separable quadratic function

Mathematics Subject Classification ID

90C10: Integer programming

90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut

Related Items

Two-stage quadratic integer programs with stochastic right-hand sides, Improving an exact approach for solving separable integer quadratic knapsack problems, Separable relaxation for nonconvex quadratic integer programming: Integer diagonalization approach, Simple solution methods for separable mixed linear and quadratic knapsack problem, Computational experience with a core-based reduction procedure for the 2-knapsack problem, A roof linearization algorithm to obtain a tight upper bound for integer nonseparable quadratic programming

Cites Work

• A branch and search algorithm for a class of nonlinear knapsack problems
• An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem
• On the numerical realization of the exact penalty method for quadratic programming algorithms
• Integer quadratic optimization
• The multidimensional 0-1 knapsack problem -- bounds and computational aspects
• Computing exact solution to nonlinear integer programming: convergent Lagrangian and objective level cut method
• A surrogate relaxation based algorithm for a general quadratic multi- dimensional knapsack problem
• The nonlinear knapsack problem - algorithms and applications
• Solution of Large Quadratic Knapsack Problems Through Aggressive Reduction
• A Survey of Methods for Pure Nonlinear Integer Programming
• Constraint Pairing In Integer Programming
• An Integer Programming Algorithm for Portfolio Selection
• Surrogate Constraint Duality in Mathematical Programming
• Improved Linear Integer Programming Formulations of Nonlinear Integer Problems
• Unnamed Item
• Unnamed Item