• 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 - Request a copy

Two useful computational tricks for Quadratic Programming: hybrid SDP bounding procedures and a new linearisation technique

Furini, Fabio; Traversi, Emiliano (2014), Two useful computational tricks for Quadratic Programming: hybrid SDP bounding procedures and a new linearisation technique, 15ème congrès annuel de la Société française de recherche opérationnelle et d'aide à la décision (ROADEF 2014), 2014-02, Bordeaux, France

Type
Communication / Conférence
Date
2014
Conference title
15ème congrès annuel de la Société française de recherche opérationnelle et d'aide à la décision (ROADEF 2014)
Conference date
2014-02
Conference city
Bordeaux
Conference country
France
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
Abstract (EN)
Quadratic programming problems have received an increasing amount of attention in the recent years, both from the theoretical and practical point of views. For this class of problems, we studied two different useful computational tricks.The first one is the exploitation of Semidefinite Programming (SDP) relaxation within the framework provided by Mixed Integer Nonlinear Programming (MINLP) solvers. We included the SDP relaxation in a state-of-the-art MINLP solver as an additional bounding technique and demonstrated that this idea could be computationally useful. The Quadratic Stable Set Problem is adopted as the case study. The tests indicate that the Hybrid SDP Bounding Procedure allows an average 50% cut of the overall computing time and a cut of more than one order of magnitude for the branching nodes.The second one is a new linearisation technique. We computationally prove that the new formulation, called Extended Linear Formulation, can be effective for different classes of problems in practice. Our tests are based on two sets of classical BQPs from the literature, i.e., the Unconstrained BQP and the Maximum Cut of edge-weighted graphs. Finally we discuss the relations between the Linear Programming relaxations of the different linearisation techniques presented and we discuss the elimination of constraint redundancy which is effective at speeding up the computational convergence.
Subjects / Keywords
Binary Quadratic Programming; Max Cut; Quadratic Stable Set Problem; Semidefinite Programming; Bounding Procedure

Related items

Showing items related by title and author.

  • Thumbnail
    Theoretical and computational study of several linearisation techniques for binary quadratic problems 
    Furini, Fabio; Traversi, Emiliano (2018) Article accepté pour publication ou publié
  • 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
    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
    Lower Bounding Techniques for DSATUR-based Branch and Bound 
    Furini, Fabio; Gabrel, Virginie; Ternier, Ian-Christopher (2016) 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é
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