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

Revue française d informatique et de recherche opérationnelle Série verte

Un algorithme de programmation quadratique en variables binaires

Victor A Ginsburgh, Alain Van Peeterssen

Published Jan 1, 1969• 5 citations
Publisher

Abstract

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>

DOI
10.1051/ro/196903v200571

Related papers

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

Jean-Claude Hennet

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>

RAIRO - Operations Research•Jan 1, 1983•3 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

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

Linéarisation et relaxation lagrangienne pour problèmes quadratiques en variables binaires

Serigne Guèye

Un probleme quadratique en variables binaires est un probleme d'optimisation en variables binaires consistant a minimiser une fonction objectif quadratique sous des contraintes lineaires. Dans cas general, c'est un probleme dificile a resoudre de maniere exacte (NP- difficile), trouvant de nombreuses applications pratiques. La resolution exacte du probleme passe par determination de bornes inferieures qu'il convient d'integrer dans des schemas de separation et evaluation progressive (ou Branch-and-Bound). Plusieurs techniques, allant de programmation semi-definie positive a l'optimisation globale, sont utilisees pour determiner ces bornes. Nous nous sommes particulierement interesses aux methodes lagrangiennes et aux techniques de linearisation. Nous avons traite dans cette these deux instances particulieres du probleme : la bipolarisation de graphes avec contrainte de cardinalite et le probleme quadratique en variables binaires sans contrainte. Pour bipartition de graphes, nous avons propose une demarche hybride melant relaxation lagrangienne et linearisation de probleme. Les tests numeriques, issus de l'algorithme resultant, ont montre des ameliorations significatives par rapport a certaines techniques existantes. Pour probleme quadratique en variables binaires sans contrainte, des etudes sur les techniques de linearisation ont ete effectuees. Elles consistent a remplacer fonction objectif quadratique par une forme lineaire, grâce a l'ajout de variables permettant de remplacer les parties quadratiques de fonction. L'ajout de ces variables entrainent [sic] aussi l'ajout de contraintes visant a s'assurer de validite du remplacement. Apres etude et tests des linearisations existantes, nous unifions ces techniques dans un schema general de linearisation. De nouveaux modeles ont, grâce a ce schema , vu jour et ameliorent significativement les resultats numeriques des formulations lineaires precedentes

•Jan 1, 2002•4 citations

Programmation quadratique en variables binaires

Brossard, Nicolas

•Jan 1, 1995•0 citations

Utilisation de la programmation semidéfinie pour la résolution exacte de programmes quadratiques en variables 0-1

Marie-Christine Plateau

Utilisation de la programmation semidéfinie pour la résolution exacte de programmes quadratiques en variables 0-1

•Jan 1, 2007•0 citations
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
Un probleme quadratique en variables binaires est un probleme d'optimisation en variables binaires consistant a minimiser une fonction objectif quadratique sous des contraintes lineaires. Dans cas general, c'est un probleme dificile a resoudre de maniere exacte (NP- difficile), trouvant de nombreuses applications pratiques. La resolution exacte du probleme passe par determination de bornes inferieures qu'il convient d'integrer dans des schemas de separation et evaluation progressive (ou Branch-and-Bound). Plusieurs techniques, allant de programmation semi-definie positive a l'optimisation globale, sont utilisees pour determiner ces bornes. Nous nous sommes particulierement interesses aux methodes lagrangiennes et aux techniques de linearisation. Nous avons traite dans cette these deux instances particulieres du probleme : la bipolarisation de graphes avec contrainte de cardinalite et le probleme quadratique en variables binaires sans contrainte. Pour bipartition de graphes, nous avons propose une demarche hybride melant relaxation lagrangienne et linearisation de probleme. Les tests numeriques, issus de l'algorithme resultant, ont montre des ameliorations significatives par rapport a certaines techniques existantes. Pour probleme quadratique en variables binaires sans contrainte, des etudes sur les techniques de linearisation ont ete effectuees. Elles consistent a remplacer fonction objectif quadratique par une forme lineaire, grâce a l'ajout de variables permettant de remplacer les parties quadratiques de fonction. L'ajout de ces variables entrainent [sic] aussi l'ajout de contraintes visant a s'assurer de validite du remplacement. Apres etude et tests des linearisations existantes, nous unifions ces techniques dans un schema general de linearisation. De nouveaux modeles ont, grâce a ce schema , vu jour et ameliorent significativement les resultats numeriques des formulations lineaires precedentes