1 /* Builds a "sparse" acyclic subgraph instance: Parameters k,t,c
2 Creates a k-inary tree with t+1 levels and replaces each node by a cycle with c nodes */
3
4 #include <stdio.h>
5 #include <stdlib.h>
6 #include <math.h>
7
write_sparse_problem(long k,long t,long c)8 void write_sparse_problem (long k, long t, long c) {
9
10 long i,j,l,parent,T,Tc,node,cyclevar;
11 long Ei_minus, Ei,anz;
12
13 if (c <= 1) {fprintf (stderr, "Error: c has to be larger than 1!"); exit(255);}
14
15 T = (long) (pow (k, t+1) - 1) / (k-1);
16
17 Tc = T * c;
18
19 cyclevar = T - 1;
20
21 // fprintf ("Producing data set with:\n %li variables\n %li constraints\n %li optimum\n",
22 // Tc,Tc+T-1,Tc-1);
23
24 // Write header and variables
25
26 printf ("%li\t%li\t%li\t%li\n", Tc, Tc+T-1, (Tc+T-1) * 2, Tc-1);
27
28 for (i=0; i<Tc; i++) printf ("0\t%li\n",Tc);
29
30 anz = 1;
31 node = 0;
32 Ei_minus = -1;
33 Ei = 0;
34
35 // insert cycle for node -1
36
37 printf ("2\t1\t1e30\t%li\t1\t%i\t-1\n",cyclevar+1,0);
38
39 for (l=0;l<c-2;l++) {
40 cyclevar++;
41 printf ("2\t1\t1e30\t%li\t1\t%li\t-1\n", cyclevar+1, cyclevar);
42 }
43
44 printf ("2\t1\t1e30\t%i\t1\t%li\t-1\n",0,cyclevar+1); cyclevar++;
45
46 for (j=0; j<t; j++) {
47
48 // One level of the tree
49
50 for (i = anz*k; i>0; i--) {
51
52 parent = Ei_minus + ((node - Ei) / k);
53
54 printf ("2\t1\t1e30\t%li\t1\t%li\t-1\n", node+1, parent+1); // write "forw-backw geq 1"
55
56 // insert cycle:
57
58 printf ("2\t1\t1e30\t%li\t1\t%li\t-1\n", cyclevar+1, node+1);
59
60 for (l=0;l<c-2;l++) {
61 cyclevar++;
62 printf("2\t1\t1e30\t%li\t1\t%li\t-1\n",cyclevar+1,cyclevar);
63 }
64
65 printf ("2\t1\t1e30\t%li\t1\t%li\t-1\n",node+1,cyclevar+1);cyclevar++;
66
67 ++node;
68 }
69
70 Ei_minus = Ei;
71 Ei = node;
72 anz *= k;
73 }
74 }
75
main(int argc,char * argv[])76 int main(int argc, char* argv[]){
77
78 if (argc > 3) {
79
80 const long k = atoi (argv [1]);
81 const long t = atoi (argv [2]);
82 const long c = atoi (argv [3]);
83
84 write_sparse_problem (k, t, c);
85 }
86 else printf ("Builds a sparse acyclic subgraph instance\n\
87 Usage: %s k t c\n\
88 Creates a k-inary tree with t+1 levels and replaces each node by a cycle with c nodes\n", *argv);
89
90 return 0;
91 }
92