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

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

Dominique Quadri, Eric Soutif, 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 programminglinearizationbranch-and-boundsurrogate relaxationseparable quadratic function

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items (13)

A roof linearization algorithm to obtain a tight upper bound for integer nonseparable quadratic programming ⋮ Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems ⋮ Separable relaxation for nonconvex quadratic integer programming: Integer diagonalization approach ⋮ A decision space algorithm for multiobjective convex quadratic integer optimization ⋮ Pilot pattern design scheme with branch and bound in PSA-OFDM system ⋮ Two-stage quadratic integer programs with stochastic right-hand sides ⋮ Improving an exact approach for solving separable integer quadratic knapsack problems ⋮ Completely positive and copositive program modelling for quadratic optimization problems ⋮ Simple solution methods for separable mixed linear and quadratic knapsack problem ⋮ Computational experience with a core-based reduction procedure for the 2-knapsack problem ⋮ Reformulation of the Quadratic Multidimensional Knapsack Problem as Copositive/Completely Positive Prorams ⋮ Two-Agent Advertisement Scheduling on Physical Books to Maximize the Total Profit ⋮ A nonlinear multidimensional knapsack problem in the optimal design of mixture experiments

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

This page was built for publication: Exact solution method to solve large scale integer quadratic multidimensional knapsack problems