• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

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

Quadri, Dominique; Soutif, Eric; Tolla, Pierre (2009), Exact solution method to solve large scale integer quadratic multidimensional knapsack problems, Journal of Combinatorial Optimization, 17, 2, p. 157-167. http://dx.doi.org/10.1007/s10878-007-9105-1

View/Open
cahierLamsade260.pdf (279.6Kb)
Type
Article accepté pour publication ou publié
Date
2009
Journal name
Journal of Combinatorial Optimization
Volume
17
Number
2
Publisher
Springer
Pages
157-167
Publication identifier
http://dx.doi.org/10.1007/s10878-007-9105-1
Metadata
Show full item record
Author(s)
Quadri, Dominique
Soutif, Eric
Tolla, Pierre
Abstract (EN)
In this paper we develop a branch-and-bound algorithm for solving a particular integer quadratic multi-knapsack problem. The problem we study is defined as the maximization of a concave separable quadratic objective function over a convex set of linear constraints and bounded integer variables. Our exact solution method is based on the computation of an upper bound and also includes pre-procedure techniques in order to reduce the problem size before starting the branch-and-bound process. We lead a numerical comparison between our method and three other existing algorithms. The approach we propose outperforms other procedures for large-scaled instances (up to 2000 variables and constraints).
Subjects / Keywords
Branch-and-bound; Surrogate relaxation; Linearization; Separable quadratic function; Integer programming

Related items

Showing items related by title and author.

  • Thumbnail
    A Branch-and-Bound Algorithm to Solve Large Scale Integer Quadratic Multi-Knapsack Problems 
    Tolla, Pierre; Soutif, Eric; Quadri, Dominique (2007) Communication / Conférence
  • Thumbnail
    Upper Bounds for Large Scale Integer Quadratic Mulitdimensional Knapsack Problems 
    Quadri, Dominique; Soutif, Eric; Tolla, Pierre (2007) Article accepté pour publication ou publié
  • Thumbnail
    Rewriting integer variables into zero-one variables: some guidelines for the integer quadratic multi-knapsack problem 
    Soutif, Eric; Quadri, Dominique (2007) Article accepté pour publication ou publié
  • Thumbnail
    Les problèmes de sac-à-dos quadratiques en variables entières 
    Quadri, Dominique; Soutif, Eric; Tolla, Pierre (2007) Chapitre d'ouvrage
  • Thumbnail
    Non séparabilité en programmation quadratique en nombres entiers: reformulations du multi-sac-à-dos quadratique entier 
    Quadri, Dominique; Soutif, Eric; Tolla, Pierre (2007) Document de travail / Working paper
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo