13 DSDP Usage: maxcut <graph filename> \n\ 14 -gaptol <relative duality gap: default is 0.001> \n\ 15 -maxit <maximum iterates: default is 200> \n";
17 static int ReadGraph(
char*,
int *,
int *,
int**,
int **,
double **);
18 static int TCheckArgs(
DSDP,
int,
char **);
19 static int ParseGraphline(
char*,
int*,
int*,
double*,
int*);
21 int MaxCut(
int,
int,
int[],
int[],
double[]);
24 int main(
int argc,
char *argv[]){
26 int *node1,*node2,nedges,nnodes;
29 if (argc<2){ printf(
"%s",help);
return(1); }
31 info = ReadGraph(argv[1],&nnodes,&nedges,&node1,&node2,&weight);
32 if (info){ printf(
"Problem reading file\n");
return 1; }
34 MaxCut(nnodes,nedges,node1,node2,weight);
36 free(node1);free(node2);free(weight);
51 int MaxCut(
int nnodes,
int nedges,
int node1[],
int node2[],
double weight[]){
55 double *yy,*val,*diag,tval=0;
61 info = DSDPCreateSDPCone(dsdp,1,&sdpcone);
63 if (info){ printf(
"Out of memory\n");
return 1; }
74 diag=(
double*)malloc(nnodes*
sizeof(
double));
75 iptr=(
int*)malloc(nnodes*
sizeof(
int));
76 for (i=0;i<nnodes;i++){
81 for (i=0;i<nnodes;i++){
85 printf(
"Matrix: %d\n",i+1);
92 yy=(
double*)malloc(nnodes*
sizeof(
double));
93 for (i=0;i<nnodes;i++){yy[i]=0.0;}
94 indd=(
int*)malloc((nnodes+nedges)*
sizeof(int));
95 val=(
double*)malloc((nnodes+nedges)*
sizeof(double));
96 for (i=0;i<nnodes+nedges;i++){indd[i]=0;}
97 for (i=0;i<nnodes;i++){indd[nedges+i]=i*(i+1)/2+i;}
98 for (i=0;i<nnodes+nedges;i++){val[i]=0;}
99 for (i=0;i<nedges;i++){
100 indd[i]=(node1[i])*(node1[i]+1)/2 + node2[i];
101 tval+=fabs(weight[i]);
103 val[nedges+node1[i]]-=weight[i]/4;
104 val[nedges+node2[i]]-=weight[i]/4;
105 yy[node1[i]]-= fabs(weight[i]/2);
106 yy[node2[i]]-= fabs(weight[i]/2);
120 for (i=0;i<nnodes; i++){
123 if (info)
return info;
134 if (info){ printf(
"Out of memory\n");
return 1; }
138 if (info){ printf(
"Out of memory\n");
return 1; }
141 if (info){ printf(
"Numerical error\n");
return 1; }
147 int n;
double *xx,*y=diag;
177 double dd,scal=RAND_MAX,*vv,*tt,*cc,ymin=0;
179 vv=(
double*)malloc(nnodes*
sizeof(
double));
180 tt=(
double*)malloc(nnodes*
sizeof(
double));
181 cc=(
double*)malloc((nnodes+2)*
sizeof(double));
183 for (i=0;i<nnodes;i++){
184 for (j=0;j<nnodes;j++){dd = (( rand())/scal - .5); vv[j] = tan(3.1415926*dd);}
186 for (j=0;j<nnodes;j++){
if (tt[j]<0) tt[j]=-1;
else tt[j]=1;}
187 for (j=0;j<nnodes+2;j++){cc[j]=0;}
189 if (cc[0]<ymin) ymin=cc[0];
191 printf(
"Best integer solution: %4.2f\n",ymin);
192 free(vv); free(tt); free(cc);
197 static int TCheckArgs(
DSDP dsdp,
int nargs,
char *runargs[]){
202 for (kk=1; kk<nargs-1; kk++){
203 if (strncmp(runargs[kk],
"-dloginfo",8)==0){
205 }
else if (strncmp(runargs[kk],
"-params",7)==0){
207 }
else if (strncmp(runargs[kk],
"-help",7)==0){
216 #define BUFFERSIZ 100 219 #define __FUNCT__ "ParseGraphline" 220 static int ParseGraphline(
char * thisline,
int *row,
int *col,
double *value,
226 rtmp=-1, coltmp=-1, *value=0.0;
227 temp=sscanf(thisline,
"%d %d %lf",&rtmp,&coltmp,value);
228 if (temp==3 && rtmp>0 && coltmp>0) *gotem=3;
229 else if (temp==2 && rtmp>0 && coltmp>0){ *value = 1.0; *gotem=3;}
231 *row=rtmp-1; *col=coltmp-1;
238 #define __FUNCT__ "ReadGraph" 239 int ReadGraph(
char* filename,
int *nnodes,
int *nedges,
240 int**n1,
int ** n2,
double **wght){
243 char thisline[BUFFERSIZ]=
"*";
244 int i,k=0,line=0,nodes,edges,gotone=3;
250 fp=fopen(filename,
"r");
251 if (!fp){printf(
"Cannot open file %s !",filename);
return(1);}
253 while(!feof(fp) && (thisline[0] ==
'*' || thisline[0] ==
'"') ){
254 fgets(thisline,BUFFERSIZ,fp); line++;
257 if (sscanf(thisline,
"%d %d",&nodes, &edges)!=2){
258 printf(
"First line must contain the number of nodes and number of edges\n");
262 node1=(
int*)malloc(edges*
sizeof(
int));
263 node2=(
int*)malloc(edges*
sizeof(
int));
264 weight=(
double*)malloc(edges*
sizeof(
double));
266 for (i=0; i<edges; i++){ node1[i]=0;node2[i]=0;weight[i]=0.0;}
268 while(!feof(fp) && gotone){
270 fgets(thisline,BUFFERSIZ,fp); line++;
271 info = ParseGraphline(thisline,&row,&col,&value,&gotone);
272 if (gotone && value!=0.0 && k<edges &&
273 col < nodes && row < nodes && col >= 0 && row >= 0){
274 if (row<col){info=row;row=col;col=info;}
277 node1[k]=row; node2[k]=col;
278 weight[k]=value; k++;
280 }
else if (gotone && k>=edges) {
281 printf(
"To many edges in file.\nLine %d, %s\n",line,thisline);
283 }
else if (gotone&&(col >= nodes || row >= nodes || col < 0 || row < 0)){
284 printf(
"Invalid node number.\nLine %d, %s\n",line,thisline);
288 *nnodes=nodes; *nedges=edges;
289 *n1=node1; *n2=node2; *wght=weight;
int DSDPCreate(int m, DSDP *dsdpnew)
Create a DSDP solver. FIRST DSDP routine!
int DSDPDestroy(DSDP dsdp)
Free the internal data structures of the solver and the cones associated with it.
int DSDPReadOptions(DSDP dsdp, char filename[])
Read DSDP parameters from a file.
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.
int DSDPSetDualObjective(DSDP dsdp, int i, double bi)
Set the objective vector b in (D).
Internal structures for the DSDP solver.
DSDPTerminationReason
There are many reasons to terminate the solver.
int DSDPSetGapTolerance(DSDP dsdp, double gaptol)
Terminate the solver when the relative duality gap is less than this tolerance.
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.
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.
int SDPConeViewDataMatrix(SDPCone sdpcone, int blockj, int vari)
Print a data matrix to the screen.
int DSDPSetup(DSDP dsdp)
Set up data structures in the solver and the cones associated with it.
int DSDPReuseMatrix(DSDP dsdp, int rm)
Reuse the Hessian of the barrier function multiple times at each DSDP iteration.
int MaxCut(int, int, int[], int[], double[])
Formulate and solve the SDP relaxation of the Maximum Cut problem.
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 DSDPSetPotentialParameter(DSDP dsdp, double rho)
Set the potential parameter.
int DSDPStopReason(DSDP dsdp, DSDPTerminationReason *reason)
Copy the reason why the solver terminated.
int SDPConeComputeXV(SDPCone sdpcone, int blockj, int *derror)
Compute a factor V such that .
int DSDPSetY0(DSDP dsdp, int i, double yi0)
Set the initial values of variables y in (D).
int DSDPSetPNormTolerance(DSDP dsdp, double ptol)
Terminate the solver when the relative duality gap is suffiently small and the PNorm is less than thi...
int SDPConeXVMultiply(SDPCone sdpcone, int blockj, double vin[], double vout[], int n)
Multiply an array by a factor V such that .
int DSDPSolve(DSDP dsdp)
Apply DSDP to the problem.
int SDPConeSetBlockSize(SDPCone sdpcone, int blockj, int n)
Set the dimension of one block in the semidefinite cone.
Internal structure for semidefinite cone.
int DSDPGetY(DSDP dsdp, double y[], int m)
Copies the variables y into an array.
int DSDPComputeX(DSDP dsdp)
Compute the X variables.
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 DSDPSetR0(DSDP dsdp, double res)
Set an initial value for the variable r in (DD)
int DSDPSetStandardMonitor(DSDP dsdp, int k)
Print at every kth iteration.
int MaxCutRandomized(SDPCone, int)
Apply the Goemens and Williamson randomized cut algorithm to the SDP relaxation of the max-cut proble...