english version
SDP_S.1.1.tgz
: la
corrige des erreurs de compilation survenant avec certaines versions
récentes de gcc
En cas de problèmes de compilation avec certaines distributions, vous pouvez essayer ce Makefile (merci à Maurice Diamantini de l'ENSTA)
SDP_S est un outil permettant de formuler automatiquement des relaxations semidéfinies pour les problèmes quadratiques ou linéaires en variables bivalentes. SDP_S permet également de résoudre numériquement les relaxations obtenues en utilisant l'algorithme SB (``Spectral Bundle method '') écrit par C. Helmberg.
SDP_S est une implémentation de l'algorithme de formulation de relaxations semidéfinies proposé par Frédéric Roupin dans " From Linear to Semidefinite Programming: an Algorithm to obtain Semidefinite Relaxations for Bivalent Quadratic Problems".
SDP_S a été initialement développé lors de deux stages de trois mois effectués à l'Institut d'Informatique d'Entreprise (devenue ENSIIE) par deux élèves de deuxième année: Géraud Delaporte et Sébastien Jouteau . SDP_S est distribué sous GNU General Public License .
Ce programme est particulièrement utile pour tester très
rapidement l'intérêt d'une approche par programmation
semidéfinie pour la résolution approchée (ou
exacte) d'un problème combinatoire pouvant se formuler comme
un programme quadratique ou linéaire en 0-1. Un des avantages
principaux de SDP_S est qu'il ne requiert aucune connaissance
concernant la programmation semidefinie. En effet, le problème
à traiter doit simplement être formulé sous sa
forme habituelle:
où 
et 
est une constante. Certaines matrices 
peuvent être nulles, et si c'est le cas pour
tout 
dans 
alors 
est un simple programme linéaire en 0-1. De plus, certains 
ou 
peuvent être omis.
Pour télécharger SDP_S: SDP_S.1.1.tgz
(version SDP_S.1.0.tgz)
: la version 1.1 corrige des erreurs de compilation survenant avec
des versions récentes de gcc
Cette archive contient toutes
les sources (écrites en C et C++) ainsi que la documentation
(en anglais) en pdf. De plus, trois exemples complets d'application
sont donnés: l'affectation quadratique (QAP), k-cluster, et un
problème de placement de tâches dans un système
distribué avec contraintes de ressources. SDP_S doit
fonctionner sans problème sous tout système unix, mais
n'a été testé pour l'instant que sous Linux.
Les commentaires, suggestions ou rapports de bugs peuvent être envoyés à F. Roupin