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 
11 char help[]="\n\
12 Compute the stable set for a graph. \n\n\
13 DSDP Usage: stable <graph filename> \n";
14 
15 typedef struct {
16  double v[3];
17  int indd[3];
18 } EdgeMat;
19 
20 static int ReadGraphFromFile(char*,int*, int*, EdgeMat*[]);
21 int SetStableSetData(DSDP, SDPCone, int, int, EdgeMat[]);
22 int StableSet(int argc,char *argv[]);
23 int StableRandomized(SDPCone,int, int, EdgeMat[]);
24 #define CHKERR(a) { if (a){printf("DSDP Numerical Error or Memory Problem"); return 2;} }
25 
26 int main(int argc,char *argv[]){
27  int info;
28  info=StableSet(argc,argv);
29  return 0;
30 }
31 
40 int 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 
107 int 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 
164 int 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"
202 static 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"
222 static 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 
int DSDPCreate(int m, DSDP *dsdpnew)
Create a DSDP solver. FIRST DSDP routine!
Definition: dsdpsetup.c:30
int DSDPDestroy(DSDP dsdp)
Free the internal data structures of the solver and the cones associated with it. ...
Definition: dsdpsetup.c:496
int DSDPReadOptions(DSDP dsdp, char filename[])
Read DSDP parameters from a file.
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 DSDPSetOptions(DSDP dsdp, char *runargs[], int nargs)
Read command line arguments to set options in DSDP.
int DSDPSetZBar(DSDP dsdp, double ppobj)
Set an upper bound on the objective value at the solution.
Definition: dsdpsetdata.c:283
int DSDPSetDualObjective(DSDP dsdp, int i, double bi)
Set the objective vector b in (D).
Definition: dsdpsetdata.c:25
int SDPConeCheckData(SDPCone sdpcone)
Check the matrix operations on a data matrix;.
Definition: dsdpadddata.c:692
Internal structures for the DSDP solver.
Definition: dsdp.h:65
int DSDPSetGapTolerance(DSDP dsdp, double gaptol)
Terminate the solver when the relative duality gap is less than this tolerance.
Definition: dsdpconverge.c:110
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...
Definition: dsdpadddata.c:328
The API to DSDP for those applications using DSDP as a subroutine library.
int SDPConeAddXVAV(SDPCone sdpcone, int blockj, double vin[], int n, double sum[], int mm)
Compute for i = 0 through m.
Definition: sdpcone.c:292
int SDPConeViewDataMatrix(SDPCone sdpcone, int blockj, int vari)
Print a data matrix to the screen.
Definition: dsdpadddata.c:205
int DSDPSetup(DSDP dsdp)
Set up data structures in the solver and the cones associated with it.
Definition: dsdpsetup.c:193
int DSDPReuseMatrix(DSDP dsdp, int rm)
Reuse the Hessian of the barrier function multiple times at each DSDP iteration.
Definition: dsdpsetdata.c:905
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 StableRandomized(SDPCone, int, int, EdgeMat[])
Apply a randomized procedure to find feasible stable sets.
Definition: stable.c:164
int SDPConeComputeXV(SDPCone sdpcone, int blockj, int *derror)
Compute a factor V such that .
Definition: sdpcone.c:325
int DSDPSetY0(DSDP dsdp, int i, double yi0)
Set the initial values of variables y in (D).
Definition: dsdpsetdata.c:77
int SDPConeUsePackedFormat(SDPCone sdpcone, int blockj)
Use packed symmetric format for the dense array.
Definition: dsdpadddata.c:452
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 DSDPSolve(DSDP dsdp)
Apply DSDP to the problem.
Definition: dsdpsetup.c:343
int SDPConeSetBlockSize(SDPCone sdpcone, int blockj, int n)
Set the dimension of one block in the semidefinite cone.
Definition: dsdpadddata.c:535
Internal structure for semidefinite cone.
Definition: dsdpsdp.h:80
int SDPConeSetSparsity(SDPCone sdpcone, int blockj, int nnz)
Set the number of nonzero matrices in a block of the semidefinite cone.
Definition: dsdpadddata.c:596
int DSDPComputeX(DSDP dsdp)
Compute the X variables.
Definition: dsdpx.c:55
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 StableSet(int argc, char *argv[])
Formulate and solve the maximum Stable Set problem.
Definition: stable.c:40
int DSDPSetStandardMonitor(DSDP dsdp, int k)
Print at every kth iteration.
Definition: dsdpprintout.c:153