DSDP
stable.c
Go to the documentation of this file.
1#include "dsdp5.h"
2#include <stdio.h>
3#include <string.h>
4#include <math.h>
5#include <stdlib.h>
6
10
11char help[]="\n\
12Compute the stable set for a graph. \n\n\
13DSDP Usage: stable <graph filename> \n";
14
15typedef struct {
16 double v[3];
17 int indd[3];
18} EdgeMat;
19
20static int ReadGraphFromFile(char*,int*, int*, EdgeMat*[]);
21int SetStableSetData(DSDP, SDPCone, int, int, EdgeMat[]);
22int StableSet(int argc,char *argv[]);
23int StableRandomized(SDPCone,int, int, EdgeMat[]);
24#define CHKERR(a) { if (a){printf("DSDP Numerical Error or Memory Problem"); return 2;} }
25
26int main(int argc,char *argv[]){
27 int info;
28 info=StableSet(argc,argv);
29 return 0;
30}
31
40int StableSet(int argc,char *argv[]){
41
42 int info,kk,nedges,nnodes;
43 EdgeMat *Edges;
44 DSDP dsdp;
45 SDPCone sdpcone;
46
47 if (argc<2){ printf("%s",help); return(1); }
48
49 info = ReadGraphFromFile(argv[1],&nnodes,&nedges,&Edges);
50 if (info){ printf("Problem reading file\n"); return 1; }
51
52 info = DSDPCreate(nedges+nnodes+1,&dsdp);CHKERR(info);
53 info = DSDPCreateSDPCone(dsdp,1,&sdpcone);CHKERR(info);
54 info = SDPConeSetBlockSize(sdpcone,0,nnodes+1);CHKERR(info);
55 info = SDPConeUsePackedFormat(sdpcone,0);CHKERR(info);
56 info = SDPConeSetSparsity(sdpcone,0,nedges+nnodes+1);CHKERR(info);
57 info = SetStableSetData(dsdp, sdpcone, nnodes, nedges, Edges);
58 if (info){ printf("Problem setting data\n"); return 1; }
59
60 info = DSDPSetGapTolerance(dsdp,0.0001);CHKERR(info);
61 info = DSDPSetZBar(dsdp,1e10*nnodes+1);CHKERR(info);
62 info = DSDPReuseMatrix(dsdp,10);CHKERR(info);
63
64 for (kk=1; kk<argc-1; kk++){
65 if (strncmp(argv[kk],"-dloginfo",8)==0){
66 info=DSDPLogInfoAllow(DSDP_TRUE,0);CHKERR(info);
67 } else if (strncmp(argv[kk],"-params",7)==0){
68 info=DSDPReadOptions(dsdp,argv[kk+1]);CHKERR(info);
69 } else if (strncmp(argv[kk],"-help",5)==0){
70 printf("%s\n",help);
71 }
72 }
73 info=DSDPSetOptions(dsdp,argv,argc);CHKERR(info);
74
75 info = DSDPSetStandardMonitor(dsdp,1);CHKERR(info);
76
77 info = DSDPSetup(dsdp);CHKERR(info);
78 if (0==1){info=SDPConeCheckData(sdpcone);}
79
80 info=DSDPSolve(dsdp); CHKERR(info);
81 info=StableRandomized(sdpcone,nnodes,nedges,Edges);
82
83 info=DSDPComputeX(dsdp);CHKERR(info);
84
85 if (0==1){ /* Look at the solution */
86 int n; double *xx;
87 info=SDPConeGetXArray(sdpcone,0,&xx,&n);CHKERR(info);
88 }
89
90 info = DSDPDestroy(dsdp);CHKERR(info);
91 free(Edges);
92
93 return 0;
94} /* main */
95
107int SetStableSetData(DSDP dsdp, SDPCone sdpcone, int nodes, int edges, EdgeMat Edge[]){
108
109 int i,ii,info,nnodes=nodes+1;
110 int *iptr,*iptr2;
111 double *diag;
112
113 /* The c matrix has all elements equal to 1.0 */
114 diag=(double*)malloc(nnodes*sizeof(double));
115 iptr=(int*)malloc(nnodes*sizeof(int));
116 iptr2=(int*)malloc(nnodes*sizeof(int));
117
118 ii=nodes*(nodes+1)/2;
119 for (i=0;i<nnodes;i++){
120 diag[i]=1.0;
121 iptr[i]=i*(i+1)/2+i;
122 iptr2[i]=i;
123 }
124 info = SDPConeSetASparseVecMat(sdpcone,0,0,nnodes,-0.50,0,iptr,diag,nodes);CHKERR(info);
125 info = SDPConeAddASparseVecMat(sdpcone,0,0,nnodes,-0.25,-ii,iptr2,diag,nodes);CHKERR(info);
126 if (0){info=SDPConeViewDataMatrix(sdpcone,0,0);}
127 /* Diagonal elements must equal 1 */
128 for (i=0;i<nnodes;i++){
129 info = DSDPSetDualObjective(dsdp,i+1,1.0);CHKERR(info);
130 info = DSDPSetY0(dsdp,i+1,0.0);CHKERR(info);
131 info = SDPConeSetASparseVecMat(sdpcone,0,i+1,nnodes,1.0,0,iptr+i,diag+i,1);CHKERR(info);
132 }
133
134 /*
135 For each edge connecting nodes i and j,
136 X(i,i)+X(j,j)+X(i,j)+X(j,i)+X(i,n)+X(n,i)+X(j,n)+X(n,j)+X(n,n) = 1
137 where nodes i,j numbered 0 ... n-1.
138 */
139 for (i=0; i<edges; i++){
140 info = SDPConeAddARankOneMat(sdpcone,0,i+nnodes+1,nnodes,1.0,0,Edge[i].indd,Edge[i].v,3);
141 if (0==1){info = SDPConeViewDataMatrix(sdpcone,0,i+nnodes+1);CHKERR(info);}
142 info = DSDPSetDualObjective(dsdp,i+nnodes+1,1.0);CHKERR(info);
143 info = DSDPSetY0(dsdp,i+nnodes+1,0.0);CHKERR(info);
144 }
145
146 /* The initial point y is feasible and near the central path */
147 /*
148 info = DSDPSetR0(dsdp,0);
149 */
150 return(0);
151}
152
164int StableRandomized(SDPCone sdpcone,int nodes, int edges, EdgeMat Edge[]){
165 int i,j,derror,info,nnodes=nodes+1;
166 double dd,scal=RAND_MAX,*vv,*tt,*cc,ymin=0;
167 int e0,e1,e2;
168
169 vv=(double*)malloc(nnodes*sizeof(double));
170 tt=(double*)malloc(nnodes*sizeof(double));
171 cc=(double*)malloc((edges+nnodes+2)*sizeof(double));
172 info=SDPConeComputeXV(sdpcone,0,&derror);
173 for (i=0;i<nnodes;i++){
174 for (j=0;j<nnodes;j++){dd = (( rand())/scal - .5); vv[j] = tan(3.1415926*dd);}
175 info=SDPConeXVMultiply(sdpcone,0,vv,tt,nnodes);
176 for (j=0; j<edges; j++){
177 e0=Edge[j].indd[0];e1=Edge[j].indd[1];e2=Edge[j].indd[2];
178 if (tt[e0] * tt[e2] > 0 && tt[e1]*tt[e2] >0){
179 if ( fabs(tt[e0]-tt[e2]) > fabs(tt[e1]-tt[e2]) ){
180 tt[e0]*=-1;
181 } else {
182 tt[e1]*=-1;
183 }
184 }
185 }
186 for (j=0;j<nnodes;j++){if (tt[j]<0) tt[j]=-1; else tt[j]=1;}
187 for (j=0;j<edges+nodes+1;j++){cc[j]=0;}
188 info=SDPConeAddXVAV(sdpcone,0,tt,nnodes,cc,edges+nnodes+2);
189 if (cc[0]<ymin) ymin=cc[0];
190 }
191 printf("Stable Set Size: %4.0f\n",-ymin);
192 free(vv); free(tt); free(cc);
193
194 return(0);
195}
196
197
198#define BUFFERSIZ 100
199
200#undef __FUNCT__
201#define __FUNCT__ "ParseGraphline"
202static int ParseGraphline(char * thisline,int *row,int *col,double *value,
203 int *gotem){
204
205 int temp;
206 int rtmp,coltmp;
207
208 rtmp=-1, coltmp=-1, *value=0.0;
209 temp=sscanf(thisline,"%d %d %lf",&rtmp,&coltmp,value);
210 if (temp==3 && rtmp>0 && coltmp>0) *gotem=3;
211 else if (temp==2 && rtmp>0 && coltmp>0){ *value = 1.0; *gotem=3;}
212 else *gotem=0;
213 *row=rtmp-1; *col=coltmp-1;
214 if (*gotem && (*col < 0 || *row < 0)){
215 printf("Node Number must be positive.\n, %s\n",thisline);
216 }
217 return(0);
218}
219
220#undef __FUNCT__
221#define __FUNCT__ "ReadGraphFromFile"
222static int ReadGraphFromFile(char* filename,int *nnodes, int *nedges, EdgeMat**EE){
223
224 FILE*fp;
225 char thisline[BUFFERSIZ]="*";
226 int i,k=0,line=0,nodes,edges,gotone=3;
227 int info,row,col;
228 double value;
229 EdgeMat *E;
230
231 fp=fopen(filename,"r");
232 if (!fp){ printf("Cannot open file %s !",filename); return(1); }
233
234 while(!feof(fp) && (thisline[0] == '*' || thisline[0] == '"') ){
235 fgets(thisline,BUFFERSIZ,fp); line++; }
236
237 if (sscanf(thisline,"%d %d",&nodes, &edges)!=2){
238 printf("First line must contain the number of nodes and number of edges\n");
239 return 1;
240 }
241
242 E=(EdgeMat*)malloc(edges*sizeof(EdgeMat)); *EE=E;
243 for (i=0; i<edges; i++){
244 E[i].v[0]=0; E[i].v[1]=0; E[i].v[2]=0;
245 E[i].indd[0]=0; E[i].indd[1]=0; E[i].indd[2]=0;
246 }
247
248 while(!feof(fp) && gotone){
249 thisline[0]='\0';
250 fgets(thisline,BUFFERSIZ,fp); line++;
251 info = ParseGraphline(thisline,&row,&col,&value,&gotone);
252 if (gotone && k<edges &&
253 col < nodes && row < nodes && col >= 0 && row >= 0){
254 if (row > col){i=row;row=col;col=i;}
255 if (row == col){}
256 else {
257 E[k].indd[0]=row; E[k].indd[1]=col; E[k].indd[2]=nodes;
258 E[k].v[0]=1.0; E[k].v[1]=1.0; E[k].v[2]=1.0;
259 k++;
260 }
261 } else if (gotone && k>=edges) {
262 printf("To many edges in file.\nLine %d, %s\n",line,thisline);
263 return 1;
264 } else if (gotone&&(col >= nodes || row >= nodes || col < 0 || row < 0)){
265 printf("Invalid node number.\nLine %d, %s\n",line,thisline);
266 return 1;
267 }
268 }
269
270 *nnodes=nodes; *nedges=k;
271
272 return 0;
273}
274
The API to DSDP for those applications using DSDP as a subroutine library.
struct SDPCone_C * SDPCone
The SDPCone object points to blocks of data that specify semidefinite matrix inequalities.
Definition dsdp5.h:26
@ DSDP_TRUE
struct DSDP_C * DSDP
An implementation of the dual-scaling algorithm for semidefinite programming.
int DSDPSetup(DSDP dsdp)
Set up data structures in the solver and the cones associated with it.
Definition dsdpsetup.c:193
int DSDPDestroy(DSDP dsdp)
Free the internal data structures of the solver and the cones associated with it.
Definition dsdpsetup.c:496
int DSDPSetOptions(DSDP dsdp, char *runargs[], int nargs)
Read command line arguments to set options in DSDP.
int DSDPSetDualObjective(DSDP dsdp, int i, double bi)
Set the objective vector b in (D).
Definition dsdpsetdata.c:25
int DSDPSetStandardMonitor(DSDP dsdp, int k)
Print at every kth iteration.
int DSDPCreate(int m, DSDP *dsdpnew)
Create a DSDP solver. FIRST DSDP routine!
Definition dsdpsetup.c:30
int DSDPSolve(DSDP dsdp)
Apply DSDP to the problem.
Definition dsdpsetup.c:343
int DSDPComputeX(DSDP dsdp)
Compute the X variables.
Definition dsdpx.c:55
int DSDPSetGapTolerance(DSDP dsdp, double gaptol)
Terminate the solver when the relative duality gap is less than this tolerance.
int DSDPSetY0(DSDP dsdp, int i, double yi0)
Set the initial values of variables y in (D).
Definition dsdpsetdata.c:77
int DSDPSetZBar(DSDP dsdp, double ppobj)
Set an upper bound on the objective value at the solution.
int DSDPReuseMatrix(DSDP dsdp, int rm)
Reuse the Hessian of the barrier function multiple times at each DSDP iteration.
int DSDPReadOptions(DSDP dsdp, char filename[])
Read DSDP parameters from a file.
int StableRandomized(SDPCone, int, int, EdgeMat[])
Apply a randomized procedure to find feasible stable sets.
Definition stable.c:164
int SetStableSetData(DSDP, SDPCone, int, int, EdgeMat[])
Given a graph, formulate maximum Stable Set problem and place data into solver.
Definition stable.c:107
int StableSet(int argc, char *argv[])
Formulate and solve the maximum Stable Set problem.
Definition stable.c:40
int SDPConeViewDataMatrix(SDPCone sdpcone, int blockj, int vari)
Print a data matrix to the screen.
int SDPConeGetXArray(SDPCone sdpcone, int blockj, double *xx[], int *nn)
After applying the solver, set a pointer to the array in the object with the solution X.
int SDPConeSetASparseVecMat(SDPCone sdpcone, int blockj, int vari, int n, double alpha, int ishift, const int ind[], const double val[], int nnz)
Set data matrix in a sparse format.
int SDPConeAddARankOneMat(SDPCone sdpcone, int blockj, int vari, int n, double alpha, int ishift, const int ind[], const double val[], int nnz)
Add data matrix where v is a sparse vector.
int SDPConeAddASparseVecMat(SDPCone sdpcone, int blockj, int vari, int n, double alpha, int ishift, const int ind[], const double val[], int nnz)
Add data matrix in a sparse format.
int SDPConeCheckData(SDPCone sdpcone)
Check the matrix operations on a data matrix;.
int SDPConeUsePackedFormat(SDPCone sdpcone, int blockj)
Use packed symmetric format for the dense array.
int SDPConeSetBlockSize(SDPCone sdpcone, int blockj, int n)
Set the dimension of one block in the semidefinite cone.
int SDPConeComputeXV(SDPCone sdpcone, int blockj, int *derror)
Compute a factor V such that .
Definition sdpcone.c:325
int SDPConeXVMultiply(SDPCone sdpcone, int blockj, double vin[], double vout[], int n)
Multiply an array by a factor V such that .
Definition sdpcone.c:251
int SDPConeSetSparsity(SDPCone sdpcone, int blockj, int nnz)
Set the number of nonzero matrices in a block of the semidefinite cone.
int SDPConeAddXVAV(SDPCone sdpcone, int blockj, double vin[], int n, double sum[], int mm)
Compute for i = 0 through m.
Definition sdpcone.c:292