| 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 ([email protected]) */ |
| 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 |
|
| 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 |
|
| 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 |
|