1 #include <stdio.h>
2 #include "machdefs.h"
3 #include "util.h"
4 #include "tsp.h"
5
6
7 static int process_subproblem (char *probname, int id, int ncount,
8 CCdatagroup *dat, int *ptour, double *lbound, CCrandstate *rstate);
9 static int build_edges (CCdatagroup *dat, int ncount, int *ecount, int **elist,
10 int **elen, int silent, CCrandstate *rstate);
11
12 static FILE *jokeout = (FILE *) NULL;
13 static int jokecount = 0;
14 static int jokeneg = 0;
15 static double *jokepi = (double *) NULL;
16
main(int ac,char ** av)17 int main (int ac, char **av)
18 {
19 char *bosshost = (char *) NULL;
20 double lbound = -1.0, rtime = 0.0;
21 char probname[CCutil_FILE_NAME_LEN];
22 int id = -1;
23 int rval = 0;
24 CC_SFILE *s = (CC_SFILE *) NULL;
25 double szeit;
26 CCrandstate rstate;
27 int seed = 99;
28 int ncount;
29 int *perm = (int *) NULL;
30 CCdatagroup dat;
31
32 if (ac != 2) {
33 fprintf (stderr, "Usage: %s boss\n", av[0]);
34 rval = 1; goto CLEANUP;
35 }
36
37 CCutil_printlabel ();
38
39 CCutil_sprand (seed, &rstate);
40
41
42 /* Hacky for subtours */
43 jokeout = fopen ("all.cuts", "w");
44 if (!jokeout) {
45 fprintf (stderr, "unable to open all.cuts for writing\n");
46 rval = 1; goto CLEANUP;
47 }
48 jokepi = CC_SAFE_MALLOC (100000, double);
49 CCcheck_NULL (jokepi, "out of memory for jokepi");
50 {
51 int i;
52 for (i = 0; i < 100000; i++) jokepi[i] = -1000.0;
53 }
54
55 /* end Hacky for subtours */
56
57 bosshost = av[1];
58
59 while (1) {
60 s = CCutil_snet_open (bosshost, CC_SUBDIV_PORT);
61 if (!s) {
62 fprintf (stderr, "CCutil_snet_open failed\n");
63 rval = 1; goto CLEANUP;
64 }
65
66 rval = CCutil_swrite_int (s, id);
67 CCcheck_rval (rval, "CCutil_swrite_int failed (id)");
68 rval = CCutil_swrite_double (s, rtime);
69 CCcheck_rval (rval, "CCutil_swrite_double failed (rtime)");
70 rval = CCutil_swrite_double (s, lbound);
71 CCcheck_rval (rval, "CCutil_swrite_double failed (rtime)");
72
73 rval = CCutil_sread_int (s, &id);
74 CCcheck_rval (rval, "CCutil_sread_int failed (id)");
75
76 if (id == -1) {
77 CCutil_sclose (s);
78 s = (CC_SFILE *) NULL;
79 goto DONE;
80 }
81
82 rval = CCutil_sread_string (s, probname, CCutil_FILE_NAME_LEN);
83 CCcheck_rval (rval, "CCutil_sread_string failed (probname)");
84
85 CCutil_init_datagroup (&dat);
86 perm = (int *) NULL;
87
88 rval = CCutil_readmaster (s, &ncount, &dat, &perm);
89 CCcheck_rval (rval, "CCutil_readmaster failed");
90
91 CCutil_sclose (s);
92 s = (CC_SFILE *) NULL;
93
94 printf ("PROCESSING %s subproblem %d\n", probname, id);
95 fflush (stdout);
96
97 szeit = CCutil_zeit ();
98
99 rval = process_subproblem (probname, id, ncount, &dat, perm, &lbound,
100 &rstate);
101 CCcheck_rval (rval, "process_subproblem failed");
102
103 rtime = CCutil_zeit () - szeit;
104
105 CC_IFFREE (perm, int);
106 CCutil_freedatagroup (&dat);
107 }
108
109 DONE:
110
111 printf ("No work available. Shutting down.\n"); fflush (stdout);
112 printf ("Found %d cuts in total\n", jokecount);
113 printf ("Found %d negative pi values\n", jokeneg);
114 {
115 FILE *jokepiout = fopen ("all.pi", "w");
116 int i = 0;
117
118 if (!jokepiout) {
119 fprintf (stderr, "could not open all.pi for writing\n");
120 rval = 1; goto CLEANUP;
121 }
122
123 while (jokepi[i] != -1000.0) {
124 fprintf (jokepiout, "%f\n", jokepi[i]);
125 i++;
126 }
127 printf ("Found %d pi values\n", i);
128 fclose (jokepiout);
129 }
130
131 CLEANUP:
132
133 if (s != (CC_SFILE *) NULL) {
134 CCutil_sclose (s);
135 }
136
137 if (jokeout) fclose (jokeout);
138 CC_IFFREE (jokepi, double);
139
140 return rval;
141 }
142
process_subproblem(char * probname,int id,int ncount,CCdatagroup * dat,int * ptour,double * lbound,CCrandstate * rstate)143 static int process_subproblem (char *probname, int id, int ncount,
144 CCdatagroup *dat, int *ptour, double *lbound, CCrandstate *rstate)
145 {
146 char name[CCutil_FILE_NAME_LEN];
147 int i, ecount, yesno, rval = 0, silent = 1;
148 int *elist = (int *) NULL;
149 int *elen = (int *) NULL;
150 int *besttour = (int *) NULL;
151 CCtsp_lp *lp = (CCtsp_lp *) NULL;
152 CCtsp_lpcuts *pool = (CCtsp_lpcuts *) NULL;
153 double ptour_len, lb;
154 CCtsp_cutselect sel;
155 CCbigguy exbound;
156
157
158 printf ("ncount = %d, Depots = %d\n", ncount, dat->ndepot);
159 fflush (stdout);
160
161 CCutil_cycle_len (ncount, dat, ptour, &ptour_len);
162 printf ("initial tour: %.2f\n", ptour_len); fflush (stdout);
163
164 rval = build_edges (dat, ncount, &ecount, &elist, &elen, silent, rstate);
165 CCcheck_rval (rval, "build_edges failed");
166
167 rval = CCtsp_init_cutpool (&ncount, (char *) NULL, &pool);
168 CCcheck_rval (rval, "CCtsp_init_cutpool failed");
169
170 besttour = CC_SAFE_MALLOC (ncount, int);
171 CCcheck_NULL (besttour, "out or memory in process_subproblem");
172 for (i = 0; i < ncount; i++) besttour[i] = i;
173
174 sprintf (name, "%s_%d", probname, id);
175
176 rval = CCtsp_init_lp (&lp, name, -1, (char *) NULL, ncount, dat,
177 ecount, elist, elen, 0, (int *) NULL, (int *) NULL,
178 0, ptour, ptour_len, pool, 0, rstate);
179 CCcheck_rval (rval, "CCtsp_init_lp failed");
180
181 CCtsp_init_cutselect (&sel);
182 rval = CCtsp_get_lp_result (lp, &lb, (double *) NULL, (int *) NULL,
183 (int **) NULL, (double **) NULL, (double **) NULL,
184 (double **) NULL, (double **) NULL);
185 CCcheck_rval (rval, "CCtsp_get_lp_result failed");
186 sel.roundtol = 0.0001 * lb;
187 sel.nexttol = 0.001 * lb;
188 printf ("Setting tolerances: next cuts %.4f next round %.4f\n",
189 sel.nexttol, sel.roundtol);
190 fflush (stdout);
191 /*
192 rval = CCtsp_cutselect_set_tols (&sel, lp, 1, silent);
193 CCcheck_rval (rval, "CCtsp_cutselect_set_tols failed");
194 */
195
196 /*
197 rval = CCtsp_cutting_loop (lp, &sel, 1, silent, rstate);
198 CCcheck_rval (rval, "CCtsp_cutting_loop failed");
199 */
200
201 /*
202 rval = CCtsp_cutting_multiple_loop (lp, &sel, 1, 24, 0, silent, rstate);
203 CCcheck_rval (rval, "CCtsp_cutting_multiple_loop failed");
204 */
205
206 /* Hacky code for subtour picture */
207
208 rval = CCtsp_subtour_loop (lp, silent, rstate);
209 CCcheck_rval (rval, "CCtsp_subtour_loop failed");
210
211 {
212 int j, k, acount, ocount;
213 CCtsp_lpcut_in c;
214 int *ar = (int *) NULL;
215 int orig = lp->dat->orig_ncount;
216 int ncuts = lp->cuts.cutcount;
217 int nrows = ncount + ncuts;
218 double *pi = (double *) NULL;
219 double *cut_pi;
220 double cx;
221
222 /*
223 for (i = 0; i < ncount; i++) {
224 rval = CClp_change_sense (lp->lp, i, 'G');
225 CCcheck_rval (rval, "CClp_change_sense failed");
226 }
227
228 rval = CClp_opt (lp->lp, CClp_METHOD_DUAL);
229 CCcheck_rval (rval, "CClp_opt failed");
230 */
231
232 pi = CC_SAFE_MALLOC (nrows, double);
233 CCcheck_NULL (pi, "out of memory in print_the_subs");
234
235 rval = CClp_pi (lp->lp, pi);
236 CCcheck_rval (rval, "CClp_pi failed");
237 cut_pi = pi + ncount;
238
239 for (i = 0; i < ncuts; i++) {
240 cx = cut_pi[i];
241 for (k = 0; k < lp->cuts.cuts[i].modcount; k++) {
242 pi[lp->cuts.cuts[i].mods[k].node] += cx *
243 (((int) lp->cuts.cuts[i].mods[k].mult) - 128);
244 }
245 }
246
247 for (i = 0; i < ncount; i++) {
248 if (lp->perm[i] < orig) {
249 if (pi[i] < -0.001) {
250 fprintf (stderr, "Oh no, negative %f\n", pi[i]);
251 jokeneg++;
252 }
253 }
254 }
255
256 for (i = 0; i < ncount; i++) {
257 if (lp->perm[i] < orig) {
258 jokepi[lp->dat->orig_names[lp->perm[i]]] = pi[i];
259 }
260 }
261
262 for (i = 0; i < ncuts; i++) {
263 if (cut_pi[i] < 0.001) continue;
264 rval = CCtsp_lpcut_to_lpcut_in (&lp->cuts, &lp->cuts.cuts[i], &c);
265 CCcheck_rval (rval, "CCtsp_lpcut_to_lpcut_in failed");
266
267 if (c.cliquecount != 1) {
268 fprintf (stderr, "HEY! This is not a subtour\n");
269 exit (1);
270 }
271
272 rval = CCtsp_clique_to_array (&c.cliques[0], &ar, &acount);
273 if (rval) {
274 fprintf (stderr, "CCtsp_clique_to_array failed");
275 rval = 1; goto CLEANUP;
276 }
277
278 ocount = 0;
279 for (j = 0; j < acount; j++) {
280 if (lp->perm[ar[j]] >= orig) {
281 ocount++;
282 ar[j] = ar[acount-1];
283 acount--;
284 j--;
285 }
286 }
287
288 if (ocount == 0 && acount >= 3) {
289 for (j = 0; j < acount; j++) {
290 ar[j] = lp->dat->orig_names[lp->perm[ar[j]]];
291 }
292 CCutil_int_array_quicksort (ar, acount);
293
294 fprintf (jokeout, "%f %d ", cut_pi[i], acount);
295 for (j = 0; j < acount; j++) {
296 fprintf (jokeout, "%d ", ar[j]);
297 }
298 fprintf (jokeout, "\n");
299 jokecount++;
300 }
301
302 CCtsp_free_lpcut_in (&c);
303 CC_IFFREE (ar, int);
304 }
305 CC_IFFREE (pi, double);
306 }
307
308 /* end subtour picture hack */
309
310 /*
311 {
312 double tourval;
313 CCutil_start_timer (&lp->stats.linkern);
314 rval = CCtsp_call_x_heuristic (lp, &tourval, besttour, silent,
315 rstate);
316 if (rval) {
317 fprintf (stderr, "CCtsp_call_x_heuristic failed\n");
318 goto CLEANUP;
319 }
320 CCutil_stop_timer (&lp->stats.linkern, 0);
321 if (tourval < lp->upperbound) {
322 printf ("New upperbound from x-heuristic: %.2f\n", tourval);
323 lp->upperbound = tourval;
324 }
325 }
326 */
327
328
329 printf ("Final LP has %d rows, %d columns, %d nonzeros\n",
330 CClp_nrows (lp->lp), CClp_ncols (lp->lp),
331 CClp_nnonzeros (lp->lp));
332 printf ("Final lower bound %f, upper bound %f\n", lp->lowerbound,
333 lp->upperbound);
334 fflush (stdout);
335
336 rval = CCtsp_exact_price (lp, &exbound, 1, 0, silent);
337 CCcheck_rval (rval, "CCtsp_exact_price failed");
338
339 lp->exact_lowerbound = exbound;
340 printf ("Exact lower bound: %.6f\n", CCbigguy_bigguytod (exbound));
341 printf ("DIFF: %f\n", lp->lowerbound - CCbigguy_bigguytod (exbound));
342 fflush (stdout);
343
344 rval = CCtsp_depot_valid (lp, dat->ndepot, &yesno);
345 CCcheck_rval (rval, "CCtsp_depot_valid failed");
346
347 if (yesno == 0) *lbound = -1.0;
348 else *lbound = CCbigguy_bigguytod (exbound);
349
350 CLEANUP:
351
352 CC_IFFREE (elist, int);
353 CC_IFFREE (elen, int);
354 if (pool) CCtsp_free_cutpool (&pool);
355 CCtsp_free_tsp_lp_struct (&lp);
356 return rval;
357 }
358
build_edges(CCdatagroup * dat,int ncount,int * ecount,int ** elist,int ** elen,int silent,CCrandstate * rstate)359 static int build_edges (CCdatagroup *dat, int ncount, int *ecount, int **elist,
360 int **elen, int silent, CCrandstate *rstate)
361 {
362 int i, rval = 0;
363 CCedgegengroup plan;
364
365 CCedgegen_init_edgegengroup (&plan);
366 plan.linkern.count = 10;
367 plan.linkern.quadnearest = 2;
368 plan.linkern.greedy_start = 0;
369 plan.linkern.nkicks = (ncount / 100) + 1;
370
371 rval = CCedgegen_edges (&plan, ncount, dat, (double *) NULL, ecount,
372 elist, silent, rstate);
373 CCcheck_rval (rval, "CCedgegen_edges failed");
374
375 *elen = CC_SAFE_MALLOC (*ecount, int);
376 CCcheck_NULL (*elen, "out of memory in build_edges");
377
378 for (i = 0; i < *ecount; i++) {
379 (*elen)[i] = CCutil_dat_edgelen ((*elist)[2*i], (*elist)[(2*i) + 1],
380 dat);
381 }
382
383 CLEANUP:
384
385 return rval;
386 }
387