Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

A Multilevel Algorithm for Large Unconstrained Binary Quadratic Optimization

Abstract :

The unconstrained binary quadratic programming (UBQP) problem is a general NP-hard problem with various applications. In this paper, we present a multilevel algorithm designed to approximate large UBQP instances. The proposed multilevel algorithm is composed of a backbone-based coarsening phase, an asymmetric uncoarsening phase and a memetic refinement phase, where the backbone-based procedure and the memetic refinement procedure make use of tabu search to obtain improved solutions. Evaluated on a set of 11 largest instances from the literature (with 5000 to 7000 variables), the proposed algorithm proves to be able to attain all the best known values with a computing effort less than any existing approach.

Type de document :
Communication dans un congrès
Liste complète des métadonnées

https://hal.univ-angers.fr/hal-03255581
Contributeur : Okina Université d'Angers <>
Soumis le : mercredi 9 juin 2021 - 16:08:42
Dernière modification le : jeudi 10 juin 2021 - 03:39:57

Identifiants

  • HAL Id : hal-03255581, version 1
  • OKINA : ua4510

Collections

Citation

Yang Wang, Zhipeng Lü, Fred Glover, Jin-Kao Hao. A Multilevel Algorithm for Large Unconstrained Binary Quadratic Optimization. 9th International Conference, CPAIOR 2012, 2012, Nantes, France. pp.395 - 408. ⟨hal-03255581⟩

Partager

Métriques

Consultations de la notice

12