Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

RAIRO - Operations Research

Comparaison de deux méthodes de résolution d'un problème combinatoire quadratique

Jean-Claude Hennet

Published Jan 1, 1983• 3 citations
Publisher

Abstract

Comparaison de deux méthodes de résolution d'un problème combinatoire quadratiqueRevue française d'automatique, d'informatique et de recherche opérationnelle.Recherche opérationnelle, tome 17, n o 3 (1983), p. 285-295.<http://www.numdam.org/item?id=RO_1983__17_3_285_0>

DOI
10.1051/ro/1983170302851

Related papers

Un algorithme de programmation quadratique en variables binaires

Victor A Ginsburgh, Alain Van Peeterssen

Un algorithme de programmation quadratique en variables binairesRevue française d'automatique, d'informatique et de recherche opérationnelle.Recherche opérationnelle, tome 3, n o V2 (1969), p. 57-73.<http://www.numdam.org/item?id=RO_1969__3_2_57_0>

Revue française d informatique et de recherche opérationnelle Série verte•Jan 1, 1969•5 citations

Optimisation quadratique en variables binaires : heuristiques et cas polynomiaux

Kim Allemand

These Ecole polytechnique federale de Lausanne EPFL, n° 2496 (2001)Faculte des sciences de baseInstitut de mathematiquesChaire de recherche operationnelle SOJury: Anthony C. Davison, Dominique de Werra, Komei Fukuda, Michel Mittaz, Marino Widmer Public defense: 2001-12-13 Reference doi:10.5075/epfl-thesis-2496Print copy in library catalog Record created on 2005-03-16, modified on 2016-08-08

•Jan 1, 2002•0 citations

Optimisation non lineaire en variables bivalentes et applications

Rouquia Djabali

Le probleme de la minimisation d'une fonction pseudo-booleenne quadratique sous une contrainte lineaire est np-difficile. Par consequent, l'obtention de bornes inferieures est importante. Nous avons etudie differentes methodes pour calculer des bornes inferieures de la solution optimale et nous montrons que le calcul de ces bornes revient a la resolution de programmes lineaires continus. La principale originalite de nos travaux, est qu'ils generalisent les bornes proposees pour le probleme de la minimisation d'une fonction pseudo-booleenne quadratique sans contraintes. Nous avons ensuite applique le calcul des bornes proposees a des problemes particuliers ; la bipartition minimale d'un graphe, l'ensemble stable de cardinal maximal d'un graphe et le sac a dos quadratique. Pour chaque probleme nous avons mis en evidence des proprietes interessantes qui permettent de simplifier le calcul des bornes et des coupes qui permettent d'ameliorer la qualite des bornes proposees. En outre, pour reduire le temps de resolution des programmes lineaires continus consideres, nous avons elabore une methode de coupes qui permet de resoudre des programmes lineaires continus de maniere approchee. Enfin, pour chaque probleme particulier, nous avons integre notre methode de coupes dans un algorithme de resolution exacte (branch and cut). Nous nous sommes egalement interesse a un probleme d'optimisation lie a l'architecture des futurs reseaux numeriques urbains. Le probleme est de determiner une topologie en anneau de cout minimal qui respecte un certain nombre de contraintes. Nous avons modelise ce probleme a l'aide de la programmation mathematique et montre qu'une methode de resolution fondee sur la programmation lineaire en nombres entiers et les methodes de coupes permet de traiter des problemes reels avec un temps de calcul raisonnable.

•Jan 1, 1998•2 citations

Machine learning for quantum bandits and quantum entanglement detection

Balthazar Casalé

Apprentissage automatique pour le bandit quantique et la détection d'intrication Le quantum machine learning est un nouveau sujet de recherche étudiant les interactions entre informatique quantique et apprentissage automatique. Cette thèse apporte deux contributions au domaine: en premier lieu, nous proposons une adaptation du problème des bandits au contexte quantique, et démontrons que les ordinateurs quantiques sont capable d'identifier le meilleur bras quadratiquement plus rapidement que leurs équivalent classique. En second lieu, nous proposons une méthode pour générer des données permettant de traiter le problème de la détection de l'intrication comme un problème de classification binaire traitable par machine learning

•Dec 5, 2023•0 citations

Un schéma de linéarisation pour les problèmes quadratiques en variables binaires

Serigne Guèye, Philippe Yves Paul Michelon

•Jan 1, 2002•0 citations

Formulations linéaires miniaturisées pour problèmes quadratiques en variables binaires

Serigne Guèye, Philippe Yves Paul Michelon

•Jan 1, 2002•0 citations
Comparaison de deux méthodes de résolution d'un problème combinatoire quadratiqueRevue française d'automatique, d'informatique et de recherche opérationnelle.Recherche opérationnelle, tome 17, n o 3 (1983), p. 285-295.http://www.numdam.org/item?id=RO_1983__17_3_285_0
Le probleme de la minimisation d'une fonction pseudo-booleenne quadratique sous une contrainte lineaire est np-difficile. Par consequent, l'obtention de bornes inferieures est importante. Nous avons etudie differentes methodes pour calculer des bornes inferieures de la solution optimale et nous montrons que le calcul de ces bornes revient a la resolution de programmes lineaires continus. La principale originalite de nos travaux, est qu'ils generalisent les bornes proposees pour le probleme de la minimisation d'une fonction pseudo-booleenne quadratique sans contraintes. Nous avons ensuite applique le calcul des bornes proposees a des problemes particuliers ; la bipartition minimale d'un graphe, l'ensemble stable de cardinal maximal d'un graphe et le sac a dos quadratique. Pour chaque probleme nous avons mis en evidence des proprietes interessantes qui permettent de simplifier le calcul des bornes et des coupes qui permettent d'ameliorer la qualite des bornes proposees. En outre, pour reduire le temps de resolution des programmes lineaires continus consideres, nous avons elabore une methode de coupes qui permet de resoudre des programmes lineaires continus de maniere approchee. Enfin, pour chaque probleme particulier, nous avons integre notre methode de coupes dans un algorithme de resolution exacte (branch and cut). Nous nous sommes egalement interesse a un probleme d'optimisation lie a l'architecture des futurs reseaux numeriques urbains. Le probleme est de determiner une topologie en anneau de cout minimal qui respecte un certain nombre de contraintes. Nous avons modelise ce probleme a l'aide de la programmation mathematique et montre qu'une methode de resolution fondee sur la programmation lineaire en nombres entiers et les methodes de coupes permet de traiter des problemes reels avec un temps de calcul raisonnable.
Apprentissage automatique pour le bandit quantique et la détection d'intrication Le quantum machine learning est un nouveau sujet de recherche étudiant les interactions entre informatique quantique et apprentissage automatique. Cette thèse apporte deux contributions au domaine: en premier lieu, nous proposons une adaptation du problème des bandits au contexte quantique, et démontrons que les ordinateurs quantiques sont capable d'identifier le meilleur bras quadratiquement plus rapidement que leurs équivalent classique. En second lieu, nous proposons une méthode pour générer des données permettant de traiter le problème de la détection de l'intrication comme un problème de classification binaire traitable par machine learning