French version
SDP_S.1.1.tgz
: ,
updated on Dec 13, 2007 : some header files were causing compilation
errors with recent versions of gcc
If a compilation error occurs, please try this Makefile (many thanks to Maurice Diamantini from the ENSTA)
SDP_S is a stand-alone program which formulates and solves
semidefinite relaxations for any 0-1 quadratic problem. It runs on
Linux and other unix like systems. It uses the Spectral
Bundle method written by C. Helmberg to solve the semidefinite
programs.
SDP_S is an implementation of the algorithm proposed by
Frédéric
Roupin in "
From Linear to Semidefinite Programming: an Algorithm to obtain
Semidefinite Relaxations for Bivalent Quadratic Problems".
SDP_S has been written by two students of the "Institut d'Informatique d'Entreprise": Géraud Delaporte and Sébastien Jouteau. SDP_S is made available under the GNU General Public License version 2.
This program is useful to test quickly if a semidefinite approach
is fruitful to solve a combinatorial problem which can be stated as a
0-1 quadratic (or linear) program. One of the major advantages of
SDP_S is that it requires no particular knowledge in semidefinite
programming. Indeed, the considered problem has only to be stated
as:
where 
and 
is a real number. Some matrices 
can
be equal to zero, and if it is true for all 
in 
then 
is a 0-1 linear program. Moreover, some 
or 
can be missing.
To download SDP_S: SDP_S.1.1.tgz
(old version : SDP_S.1.0.tgz).
Version 1.1, updated on Dec 13, 2007 : some header files were causing
compilation errors with recent versions of gcc.
This file contains
all the source codes (C and C++) and the documentation files in pdf
format. Three complete examples are given: the Quadratic Assignment
Problem (QAP), the k-cluster problem, and the Memory-Constrained
Allocation Problem.
Comments, suggestions or bugs should be sent to F. Roupin