• 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

Theoretical and computational study of several linearisation techniques for binary quadratic problems

Furini, Fabio; Traversi, Emiliano (2018), Theoretical and computational study of several linearisation techniques for binary quadratic problems, Annals of Operations Research, p. 1-25. 10.1007/s10479-018-3118-2

View/Open
elf_rev.pdf (272.6Kb)
Type
Article accepté pour publication ou publié
Date
2018
Journal name
Annals of Operations Research
Publisher
Springer
Pages
1-25
Publication identifier
10.1007/s10479-018-3118-2
Metadata
Show full item record
Author(s)
Furini, Fabio
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Traversi, Emiliano
Laboratoire d'Informatique de Paris-Nord [LIPN]
Abstract (EN)
We perform a theoretical and computational study of the classical linearisation techniques (LT) and we propose a new LT for binary quadratic problems (BQPs). We discuss the relations between the linear programming (LP) relaxations of the considered LT for generic BQPs. We prove that for a specific class of BQP all the LTs have the same LP relaxation value. We also compare the LT computational performance for four different BQPs from the literature. We consider the Unconstrained BQP and the maximum cut of edge-weighted graphs and, in order to measure the effects of constraints on the computational performance, we also consider the quadratic extension of two classical combinatorial optimization problems, i.e., the knapsack and stable set problems.
Subjects / Keywords
Linearisation techniques; Binary quadratic problems; Max cut problem; Quadratic knapsack problem; Quadratic stable set problem

Related items

Showing items related by title and author.

  • Thumbnail
    Two useful computational tricks for Quadratic Programming: hybrid SDP bounding procedures and a new linearisation technique 
    Furini, Fabio; Traversi, Emiliano (2014) Communication / Conférence
  • Thumbnail
    QPLIB: a library of quadratic programming instances 
    Furini, Fabio; Traversi, Emiliano; Belotti, Pietro; Frangioni, Antonio; Gleixner, Ambros; Gould, Nick; Liberti, Leo; Lodi, Andrea; Misener, Ruth; Mittelmann, Hans; Sahinidis, Nikolaos V.; Vigerske, Stefan; Wiegele, Angelika (2019) Article accepté pour publication ou publié
  • Thumbnail
    Exact approaches for the knapsack problem with setups 
    Furini, Fabio; Monaci, Michele; Traversi, Emiliano (2018) Article accepté pour publication ou publié
  • Thumbnail
    A hybrid heuristic for the multi-activity tour scheduling problem 
    Létocart, Lucas; Furini, Fabio; Liberti, Leo; Traversi, Emiliano; Bettiol, Enrico; Rinaldi, Francesco (2018) Article accepté pour publication ou publié
  • Thumbnail
    On the Product Knapsack Problem 
    D’Ambrosio, Claudia; Furini, Fabio; Monaci, Michele; Traversi, Emiliano (2018) Article accepté pour publication ou publié
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