1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <math.h>
4
write_acyclic_problem(long n_nodes,long n_add_edges)5 void write_acyclic_problem(long n_nodes, long n_add_edges) {
6
7 long i,j, i2,j2, k, n,N,
8 n_forw = n_nodes * (n_nodes-1) / 2;
9
10 if (n_add_edges) N = n_forw / n_add_edges;
11 else N = n_forw + 1;
12
13 printf ("%li\t%li\t%li\t%li\n",
14 n_nodes,
15 n_forw + n_add_edges,
16 (n_forw+n_add_edges) * 2,
17 n_forw);
18
19 //
20 // variables
21 //
22
23 for (i=0;i<n_nodes;i++) printf("0\t%li\n",n_nodes);
24
25 //
26 // constraints
27 //
28
29 for (n=k=i=0; i<n_nodes; i++) {
30
31 for (j=i+1; j<n_nodes; j++) {
32
33 if (!(n++ % N) && (k++ < n_add_edges)) {
34
35 //
36 // add additional backward arcs
37 //
38
39 do {
40
41 i2 = floor (drand48 () * n_nodes);
42 j2 = floor (drand48 () * n_nodes);
43
44 } while (i2==j2);
45
46 if (i2 < j2) printf("2\t1\t1e30\t%li\t1\t%li\t-1\n", j2, i2);
47 else printf("2\t1\t1e30\t%li\t1\t%li\t-1\n", i2, j2);
48 }
49
50 printf("2\t1\t1e30\t%li\t1\t%li\t-1\n",i,j);
51 // forw-backw geq 1, i.e.,i-j
52 }
53 }
54 }
55
main(int argc,char * argv[])56 int main(int argc, char* argv[]){
57
58 if (argc >= 2) {
59
60 const int n_nodes = atoi (argv [1]);
61 const int n_add_edges = (argc >= 3) ? (atoi (argv [2])):0;
62
63 write_acyclic_problem (n_nodes, n_add_edges);
64 }
65 else printf ("usage: %s <num_nodes> [<num_backward_arcs>]\n", *argv);
66
67 return 0;
68 }
69