13DSDP Usage: maxcut <graph filename> \n\
14 -gaptol <relative duality gap: default is 0.001> \n\
15 -maxit <maximum iterates: default is 200> \n";
17static int ReadGraph(
char*,
int *,
int *,
int**,
int **,
double **);
18static int TCheckArgs(
DSDP,
int,
char **);
19static int ParseGraphline(
char*,
int*,
int*,
double*,
int*);
21int MaxCut(
int,
int,
int[],
int[],
double[]);
24int 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);
51int 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);
197static 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){
219#define __FUNCT__ "ParseGraphline"
220static 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"
239int 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;
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.
struct DSDP_C * DSDP
An implementation of the dual-scaling algorithm for semidefinite programming.
DSDPTerminationReason
There are many reasons to terminate the solver.
int DSDPSetup(DSDP dsdp)
Set up data structures in the solver and the cones associated with it.
int DSDPDestroy(DSDP dsdp)
Free the internal data structures of the solver and the cones associated with it.
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).
int DSDPGetY(DSDP dsdp, double y[], int m)
Copies the variables y into an array.
int DSDPSetStandardMonitor(DSDP dsdp, int k)
Print at every kth iteration.
int DSDPCreate(int m, DSDP *dsdpnew)
Create a DSDP solver. FIRST DSDP routine!
int DSDPSolve(DSDP dsdp)
Apply DSDP to the problem.
int DSDPComputeX(DSDP dsdp)
Compute the X variables.
int DSDPSetGapTolerance(DSDP dsdp, double gaptol)
Terminate the solver when the relative duality gap is less than this tolerance.
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 DSDPStopReason(DSDP dsdp, DSDPTerminationReason *reason)
Copy the reason why the solver terminated.
int DSDPSetR0(DSDP dsdp, double res)
Set an initial value for the variable r in (DD)
int DSDPSetY0(DSDP dsdp, int i, double yi0)
Set the initial values of variables y in (D).
int DSDPSetZBar(DSDP dsdp, double ppobj)
Set an upper bound on the objective value at the solution.
int DSDPSetPotentialParameter(DSDP dsdp, double rho)
Set the potential parameter.
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 MaxCut(int, int, int[], int[], double[])
Formulate and solve the SDP relaxation of the Maximum Cut problem.
int MaxCutRandomized(SDPCone, int)
Apply the Goemens and Williamson randomized cut algorithm to the SDP relaxation of the max-cut proble...
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 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 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 .
int SDPConeXVMultiply(SDPCone sdpcone, int blockj, double vin[], double vout[], int n)
Multiply an array by a factor V such that .
int SDPConeAddXVAV(SDPCone sdpcone, int blockj, double vin[], int n, double sum[], int mm)
Compute for i = 0 through m.