1 /*===========================================================================*/
2 /*                                                                           */
3 /* This file is part of a demonstration application for use with the         */
4 /* SYMPHONY Branch, Cut, and Price Library. This application is a solver for */
5 /* Capacitated Network Routing Problems.                                     */
6 /*                                                                           */
7 /* (c) Copyright 2000-2007 Ted Ralphs. All Rights Reserved.                  */
8 /*                                                                           */
9 /* This application was developed by Ted Ralphs (ted@lehigh.edu)             */
10 /*                                                                           */
11 /* This software is licensed under the Eclipse Public License. Please see    */
12 /* accompanying file for terms.                                              */
13 /*                                                                           */
14 /*===========================================================================*/
15 
16 /* system include files */
17 #include <string.h>
18 
19 /* SYMPHONY include files */
20 #include "sym_macros.h"
21 #include "sym_constants.h"
22 #include "sym_proto.h"
23 #include "sym_cg.h"
24 
25 /* CNRP include files */
26 #include "cnrp_cg.h"
27 #include "network.h"
28 extern "C"{
29 #include "concorde.h"
30 }
31 
32 int add_tsp_cuts PROTO((CCtsp_lpcut_in **tsp_cuts, int *cutnum, int vertnum,
33 			char tsp_prob, cut_data ***cuts, int *num_cuts,
34 			int *alloc_cuts));
35 
36 /*===========================================================================*/
37 
38 /*===========================================================================*\
39  * This file contains the interface to the CONCORDE cutting plane routines
40 \*===========================================================================*/
41 
42 /*===========================================================================*/
43 
tsp_cuts(network * n,int verbosity,char tsp_prob,int which_cuts,cut_data *** cuts,int * num_cuts,int * alloc_cuts)44 int tsp_cuts(network *n, int verbosity, char tsp_prob, int which_cuts,
45 	     cut_data ***cuts, int *num_cuts, int *alloc_cuts)
46 {
47    edge *edges = n->edges;
48    CCtsp_lpcut_in *tsp_cuts = NULL;
49    int *tsp_edgelist = (int *) malloc(2*n->edgenum*ISIZE);
50    double *tsp_x = (double *) malloc(n->edgenum*DSIZE);
51    int i, cutnum = 0, cuts_added = 0, rval, seed;
52    CCrandstate rstate;
53    CCtsp_cutselect *sel;
54    CCtsp_tighten_info *stats;
55 
56    stats = (CCtsp_tighten_info *) calloc(1, sizeof(CCtsp_tighten_info));
57    sel = (CCtsp_cutselect *) calloc(1, sizeof(CCtsp_cutselect));
58 
59    if (tsp_prob){
60       sel->connect          = 1;
61       if (which_cuts & SUBTOUR){
62 	 sel->segments         = 1;
63 	 sel->exactsubtour     = 1;
64       }
65       if (which_cuts & BLOSSOM){
66 	 sel->fastblossom      = 1;
67 	 sel->ghfastblossom    = 1;
68 	 sel->exactblossom     = 0;
69       }
70       if (which_cuts & COMB){
71 	 sel->blockcombs       = 1;
72 	 sel->growcombs        = 0;
73 	 sel->prclique         = 0;
74       }
75    }else{
76       if (which_cuts & BLOSSOM){
77 	 sel->fastblossom      = 1;
78 	 sel->ghfastblossom    = 1;
79 	 sel->exactblossom     = 1;
80       }
81    }
82 
83    for (i = 0; i < n->edgenum; i++, edges++){
84       tsp_edgelist[i << 1] = edges->v0;
85       tsp_edgelist[(i << 1) + 1] = edges->v1;
86       tsp_x[i] = edges->weight;
87    }
88 
89    if (sel->connect){
90       rval = CCtsp_connect_cuts(&tsp_cuts, &cutnum, n->vertnum, n->edgenum,
91 				tsp_edgelist, tsp_x);
92       if (rval) {
93 	 fprintf(stderr, "CCtsp_connect_cuts failed\n");
94 	 printf("CCtsp_connect_cuts failed\n");
95 	 rval = 1;
96       }
97       if (verbosity > 3)
98 	 printf("Found %2d connect cuts\n", cutnum);
99       if (!rval && cutnum > 0){
100 	 cuts_added += add_tsp_cuts(&tsp_cuts, &cutnum, n->vertnum, tsp_prob,
101 				    cuts, num_cuts, alloc_cuts);
102 	 if (cuts_added){
103 	    if (verbosity > 3)
104 	       printf("%i connect cuts added\n", cuts_added);
105 	    goto CLEANUP;
106 	 }
107       }
108    }
109 
110    if (sel->segments){
111       rval = CCtsp_segment_cuts(&tsp_cuts, &cutnum, n->vertnum, n->edgenum,
112 				tsp_edgelist, tsp_x);
113       if (rval) {
114 	 fprintf(stderr, "CCtsp_segment_cuts failed\n");
115 	 printf("CCtsp_segment_cuts failed\n");
116 	 rval = 1;
117       }
118       if (verbosity > 3)
119 	 printf("Found %2d segment cuts\n", cutnum);
120       if (!rval && cutnum > 0){
121 	 cuts_added += add_tsp_cuts(&tsp_cuts, &cutnum, n->vertnum, tsp_prob,
122 				    cuts, num_cuts, alloc_cuts);
123 	 if (cuts_added){
124 	    if (verbosity > 3)
125 	       printf("%i segment cuts added\n", cuts_added);
126 	    goto CLEANUP;
127 	 }
128       }
129     }
130 
131    if (sel->fastblossom){
132       rval = CCtsp_fastblossom(&tsp_cuts, &cutnum, n->vertnum, n->edgenum,
133 			       tsp_edgelist, tsp_x);
134       if (rval) {
135 	 fprintf(stderr, "CCtsp_fastblossom failed\n");
136 	 printf("CCtsp_fastblossom failed\n");
137 	 rval = 1;
138       }
139       if (verbosity > 3)
140 	 printf("Found %2d fastblossom cuts\n", cutnum);
141       if (!rval && cutnum > 0){
142 	 cuts_added += add_tsp_cuts(&tsp_cuts, &cutnum, n->vertnum, tsp_prob,
143 				    cuts, num_cuts, alloc_cuts);
144 	 if (cuts_added){
145 	    if (verbosity > 3)
146 	       printf("%i fastblossom cuts added\n", cuts_added);
147 	    goto CLEANUP;
148 	 }
149       }
150    }
151 
152    if (sel->ghfastblossom){
153       rval = CCtsp_ghfastblossom(&tsp_cuts, &cutnum, n->vertnum, n->edgenum,
154 				 tsp_edgelist, tsp_x);
155       if (rval) {
156 	 fprintf(stderr, "CCtsp_ghfastblossom failed\n");
157 	 printf("CCtsp_ghfastblossom failed\n");
158 	 rval = 1;
159       }
160       if (verbosity > 3)
161 	 printf("Found %2d ghfastblossom cuts\n", cutnum);
162       if (!rval && cutnum > 0){
163 	 cuts_added += add_tsp_cuts(&tsp_cuts, &cutnum, n->vertnum, tsp_prob,
164 				    cuts, num_cuts, alloc_cuts);
165 	 if (cuts_added){
166 	    if (verbosity > 3)
167 	       printf("%i ghfastblossom cuts added\n", cuts_added);
168 	    goto CLEANUP;
169 	 }
170       }
171    }
172 
173    if (sel->blockcombs){
174       rval = CCtsp_block_combs(&tsp_cuts, &cutnum, n->vertnum, n->edgenum,
175 			       tsp_edgelist, tsp_x, TRUE);
176       if (rval) {
177 	 fprintf(stderr, "CCtsp_block_combs failed\n");
178 	 printf("CCtsp_block_combs failed\n");
179 	 rval = 1;
180       }
181       if (verbosity > 3)
182 	 printf("Found %2d block combs\n", cutnum);
183       if (!rval && cutnum > 0){
184 	 cuts_added += add_tsp_cuts(&tsp_cuts, &cutnum, n->vertnum, tsp_prob,
185 				    cuts, num_cuts, alloc_cuts);
186 	 if (cuts_added){
187 	    if (verbosity > 3)
188 	       printf("%i block combs added\n", cuts_added);
189 	    goto CLEANUP;
190 	 }
191       }
192    }
193 
194    if (sel->growcombs){
195       rval = CCtsp_edge_comb_grower(&tsp_cuts, &cutnum, n->vertnum,
196 				    n->edgenum, tsp_edgelist, tsp_x, stats);
197       if (rval) {
198 	 fprintf(stderr, "CCtsp_edge_comb_grower failed\n");
199 	 printf("CCtsp_edge_comb_grower failed\n");
200 	 rval = 1;
201       }
202       if (verbosity > 3)
203 	 printf("Found %2d grown combs\n", cutnum);
204       if (!rval && cutnum > 0){
205 	 cuts_added += add_tsp_cuts(&tsp_cuts, &cutnum, n->vertnum, tsp_prob,
206 				    cuts, num_cuts, alloc_cuts);
207 	 if (cuts_added){
208 	    if (verbosity > 3)
209 	       printf("%i grown combs added\n", cuts_added);
210 	    goto CLEANUP;
211 	 }
212       }
213    }
214 
215    if (sel->prclique){
216       rval = CCtsp_pr_cliquetree(&tsp_cuts, &cutnum, n->vertnum,
217 				 n->edgenum, tsp_edgelist, tsp_x, stats);
218       if (rval) {
219 	 fprintf(stderr, "CCtsp_pr_cliquetree failed\n");
220 	 printf("CCtsp_pr_cliquetree failed\n");
221 	 rval = 1;
222       }
223       if (verbosity > 3)
224 	 printf("Found %2d PR cliquetrees\n", cutnum);
225       if (!rval && cutnum > 0){
226 	 cuts_added += add_tsp_cuts(&tsp_cuts, &cutnum, n->vertnum, tsp_prob,
227 				    cuts, num_cuts, alloc_cuts);
228 	 if (cuts_added){
229 	    if (verbosity > 3)
230 	       printf("%i PR cliquetrees added\n", cuts_added);
231 	    goto CLEANUP;
232 	 }
233       }
234    }
235 
236    if (sel->exactsubtour){
237       rval = CCtsp_exact_subtours(&tsp_cuts, &cutnum, n->vertnum,
238 				  n->edgenum, tsp_edgelist, tsp_x);
239       if (rval) {
240 	 fprintf(stderr, "CCtsp_exact_subtours failed\n");
241 	 printf("CCtsp_exact_subtours failed\n");
242 	 rval = 1;
243       }
244       if (verbosity > 3)
245 	 printf("Found %2d exact subtours\n", cutnum);
246       if (!rval && cutnum > 0){
247 	 cuts_added += add_tsp_cuts(&tsp_cuts, &cutnum, n->vertnum, tsp_prob,
248 				    cuts, num_cuts, alloc_cuts);
249 	 if (cuts_added){
250 	    if (verbosity > 3)
251 	       printf("%i exactsubtours added\n", cuts_added);
252 	    goto CLEANUP;
253 	 }
254       }
255    }
256 
257    if (sel->exactblossom){
258       seed = (int) CCutil_real_zeit ();
259       CCutil_sprand(seed, &rstate);
260       rval = CCtsp_exactblossom(&tsp_cuts, &cutnum, n->vertnum, n->edgenum,
261 				tsp_edgelist, tsp_x, &rstate);
262       if (rval) {
263 	 fprintf(stderr, "CCtsp_exactblossom failed\n");
264 	 printf("CCtsp_exactblossom failed\n");
265 	 rval = 1;
266       }
267       if (verbosity > 3)
268 	 printf("Found %2d exactblossoms\n", cutnum);
269       if (!rval && cutnum > 0){
270 	 cuts_added += add_tsp_cuts(&tsp_cuts, &cutnum, n->vertnum, tsp_prob,
271 				    cuts, num_cuts, alloc_cuts);
272 	 if (cuts_added){
273 	    if (verbosity > 3)
274 	       printf("%i exact blossoms added\n", cuts_added);
275 	    goto CLEANUP;
276 	 }
277       }
278    }
279 
280 CLEANUP:
281 
282    FREE(stats);
283    FREE(tsp_edgelist);
284    FREE(tsp_x);
285 
286    return(cuts_added);
287 }
288 
289 /*===========================================================================*/
290 
add_tsp_cuts(CCtsp_lpcut_in ** tsp_cuts,int * cutnum,int vertnum,char tsp_prob,cut_data *** cuts,int * num_cuts,int * alloc_cuts)291 int add_tsp_cuts(CCtsp_lpcut_in **tsp_cuts, int *cutnum, int vertnum,
292 		 char tsp_prob, cut_data ***cuts, int *num_cuts,
293 		 int *alloc_cuts)
294 {
295    cut_data cut;
296    int i, j, k, cliquecount, cuts_added = 0;
297    char *coef, *clique_array;
298    char valid = TRUE;
299    int size = (vertnum >> DELETE_POWER) + 1;
300    CCtsp_lpcut_in *tsp_cut, *tsp_cut_next;
301 
302    if (*cutnum <= 0) return(0);
303 
304    cut.type = CLIQUE;
305    cut.name = CUT__SEND_TO_CP;
306    cut.range = 0;
307    cut.branch = ALLOWED_TO_BRANCH_ON;
308    for (tsp_cut = *tsp_cuts; tsp_cut; tsp_cut = tsp_cut->next){
309       cliquecount = tsp_cut->cliquecount;
310       cut.sense = 'L';
311       cut.rhs = (cliquecount == 1 ? 0.0 : -((double)cliquecount)/2.0 + 1.0);
312       cut.size = ISIZE + cliquecount * size;
313       cut.coef = coef = (char *) calloc(cut.size, sizeof(char));
314       memcpy(cut.coef, (char *) (&cliquecount), ISIZE);
315       clique_array = cut.coef + ISIZE;
316       for (i = 0; i < cliquecount; i++, clique_array += size){
317 	 valid = TRUE;
318 	 for(j = 0; j < tsp_cut->cliques[i].segcount; j++){
319 	    for(k = tsp_cut->cliques[i].nodes[j].lo;
320 		k <= tsp_cut->cliques[i].nodes[j].hi; k++){
321 	       cut.rhs++;
322 	       if (!k && !tsp_prob){
323 		  valid = FALSE;
324 		  break;
325 	       }
326 	       clique_array[k >> DELETE_POWER] |= (1 << (k & DELETE_AND));
327 	    }
328 	    /*For each tooth, we want to add |T|-1 to the rhs so we have to
329 	      subtract off the one here. It subtracts one for the handle too
330 	      but that is compensated for above*/
331 	    if (!valid) break;
332 	 }
333 	 cut.rhs--;
334 	 if (!valid) break;
335       }
336       if (!valid){
337 	 FREE(cut.coef);
338 	 continue;
339       }
340 
341       cg_send_cut(&cut, num_cuts, alloc_cuts, cuts);
342       cuts_added++;
343 
344       FREE(cut.coef);
345    }
346 
347    for (tsp_cut = *tsp_cuts; tsp_cut; tsp_cut = tsp_cut_next){
348       tsp_cut_next = tsp_cut->next;
349       CCtsp_free_lpcut_in(tsp_cut);
350       FREE(tsp_cut);
351    }
352    *tsp_cuts = NULL;
353    *cutnum = 0;
354 
355    return(cuts_added);
356 }
357 
358