| 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 |
#define COMPILING_FOR_LP |
| 17 |
|
| 18 |
/* system include files */ |
| 19 |
#include <math.h> |
| 20 |
#include <stdio.h> |
| 21 |
|
| 22 |
/* SYMPHONY include files */ |
| 23 |
#include "sym_constants.h" |
| 24 |
#include "sym_macros.h" |
| 25 |
#include "sym_qsort.h" |
| 26 |
#include "sym_lp_u.h" |
| 27 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 28 |
#include "sym_lp.h" |
| 29 |
/*___END_EXPERIMENTAL_SECTION___*/ |
| 30 |
|
| 31 |
/* CNRP include files */ |
| 32 |
#include "cnrp_lp.h" |
| 33 |
#include "cnrp_macros.h" |
| 34 |
#include "cnrp_const.h" |
| 35 |
|
| 36 |
/*===========================================================================*/ |
| 37 |
|
| 38 |
/*===========================================================================*\ |
| 39 |
* This file contains the user-written functions for the LP process related |
| 40 |
* to branching. |
| 41 |
\*===========================================================================*/ |
| 42 |
|
| 43 |
/*===========================================================================*\ |
| 44 |
* This function determines whether to branch. You can eseentially |
| 45 |
* leave this up to SYMPHONY unless there is some compelling reason not to. |
| 46 |
\*===========================================================================*/ |
| 47 |
|
| 48 |
int user_shall_we_branch(void *user, double lpetol, int cutnum, |
| 49 |
int slacks_in_matrix_num, cut_data **slacks_im_matrix, |
| 50 |
int slack_cut_num, cut_data **slack_cuts, int varnum, |
| 51 |
var_desc **vars, double *x, char *status, |
| 52 |
int *cand_num, branch_obj ***candidates, |
| 53 |
int *action) |
| 54 |
{ |
| 55 |
int i; |
| 56 |
double fracx, lpetol1 = 1 - lpetol; |
| 57 |
|
| 58 |
cnrp_spec *cnrp = (cnrp_spec *) user; |
| 59 |
|
| 60 |
|
| 61 |
for (i = varnum - 1; i >= 0; i--){ |
| 62 |
if (vars[i]->is_int){ |
| 63 |
fracx = x[i] - floor(x[i]); |
| 64 |
if (fracx > lpetol && fracx < lpetol1){ |
| 65 |
break; |
| 66 |
} |
| 67 |
} |
| 68 |
} |
| 69 |
|
| 70 |
if(i >= 0 ){ |
| 71 |
*action = USER__BRANCH_IF_TAILOFF; |
| 72 |
} else{ |
| 73 |
*action = USER__BRANCH_IF_MUST; |
| 74 |
} |
| 75 |
|
| 76 |
#if 0 |
| 77 |
if (cnrp->par.detect_tailoff){ |
| 78 |
*action = USER__BRANCH_IF_MUST; |
| 79 |
return(USER_SUCCESS); |
| 80 |
} |
| 81 |
|
| 82 |
*action = USER__BRANCH_IF_TAILOFF; |
| 83 |
#endif |
| 84 |
|
| 85 |
return(USER_SUCCESS); |
| 86 |
} |
| 87 |
|
| 88 |
/*===========================================================================*/ |
| 89 |
|
| 90 |
/*===========================================================================*\ |
| 91 |
* Here, we select the branching candidates. This can essentially be |
| 92 |
* left to SYMPHONY too using one of the built-in functions, but here, I |
| 93 |
* demonstrate how to branch on cuts, which must be done by the user. |
| 94 |
\*===========================================================================*/ |
| 95 |
|
| 96 |
int user_select_candidates(void *user, double lpetol, int cutnum, |
| 97 |
int slacks_in_matrix_num, |
| 98 |
cut_data **slacks_in_matrix, int slack_cut_num, |
| 99 |
cut_data **slack_cuts, int varnum, var_desc **vars, |
| 100 |
double *x, char *status, int *cand_num, |
| 101 |
branch_obj ***candidates, int *action, |
| 102 |
int bc_level) |
| 103 |
|
| 104 |
{ |
| 105 |
cnrp_spec *cnrp = (cnrp_spec *)user; |
| 106 |
cut_data *cut; |
| 107 |
branch_obj **cand_list, *can; |
| 108 |
int i, candnum, found_violated = FALSE; |
| 109 |
p_w_l *pwl; |
| 110 |
double left_hand_side, lpetol1 = 1 - lpetol, lpetol5=.95, slack, fracx; |
| 111 |
waiting_row **new_rows; |
| 112 |
int new_row_num; |
| 113 |
int *userind; |
| 114 |
int sim_cand_num = 0, sc_cand_num = 0; |
| 115 |
int total_edgenum = cnrp->vertnum*(cnrp->vertnum - 1)/2; |
| 116 |
int j, cnt = 0; |
| 117 |
double lim[7] = {.1, .15, .20, .233333, .266667, .3, 1}; |
| 118 |
branch_obj *cand; |
| 119 |
|
| 120 |
int *xind = (int *) malloc(varnum * ISIZE); |
| 121 |
double *xval = (double *) calloc(varnum, DSIZE); |
| 122 |
|
| 123 |
#if 0 |
| 124 |
if (!cnrp->par.branch_on_cuts && cnrp->par.branching_rule == 2) |
| 125 |
/* use the built-in rule */ |
| 126 |
return(USER_DEFAULT); |
| 127 |
#endif |
| 128 |
|
| 129 |
/* first try the fixed-charge variables */ |
| 130 |
for (i = varnum - 1; i >= 0; i--){ |
| 131 |
if (vars[i]->is_int){ |
| 132 |
fracx = x[i] - floor(x[i]); |
| 133 |
if (fracx > lpetol && fracx < lpetol1){ |
| 134 |
xind[cnt] = i; |
| 135 |
xval[cnt++] = fabs(fracx - .5); |
| 136 |
} |
| 137 |
} |
| 138 |
} |
| 139 |
|
| 140 |
#ifdef ADD_FLOW_VARS |
| 141 |
if (cnt == 0){ |
| 142 |
/* Now try the flow variables */ |
| 143 |
for (i = varnum - 1; i >= 0; i--){ |
| 144 |
if (!vars[i]->is_int){ |
| 145 |
fracx = x[i] - floor(x[i]); |
| 146 |
if (fracx > lpetol && fracx < lpetol1){ |
| 147 |
xind[cnt] = i; |
| 148 |
xval[cnt++] = fabs(fracx - .5); |
| 149 |
} |
| 150 |
} |
| 151 |
} |
| 152 |
} |
| 153 |
#endif |
| 154 |
|
| 155 |
qsort_di(xval, xind, cnt); |
| 156 |
|
| 157 |
for (j = 0, i = 0; i < cnt;){ |
| 158 |
if (xval[i] > lim[j]){ |
| 159 |
if (i == 0){ |
| 160 |
j++; continue; |
| 161 |
}else{ |
| 162 |
break; |
| 163 |
} |
| 164 |
}else{ |
| 165 |
i++; |
| 166 |
} |
| 167 |
} |
| 168 |
cnt = i; |
| 169 |
|
| 170 |
*cand_num = cnrp->par.strong_branching_cand_num_max; |
| 171 |
*cand_num = MAX(*cand_num, cnrp->par.strong_branching_cand_num_min); |
| 172 |
*cand_num = MIN(*cand_num, cnt); |
| 173 |
|
| 174 |
if (!*candidates) |
| 175 |
*candidates = (branch_obj **) malloc(*cand_num * sizeof(branch_obj *)); |
| 176 |
for (i=*cand_num-1; i>=0; i--){ |
| 177 |
cand = (*candidates)[i] = (branch_obj *) calloc(1, sizeof(branch_obj) ); |
| 178 |
cand->type = CANDIDATE_VARIABLE; |
| 179 |
cand->child_num = 2; |
| 180 |
cand->position = xind[i]; |
| 181 |
cand->sense[0] = 'L'; |
| 182 |
cand->sense[1] = 'G'; |
| 183 |
cand->rhs[0] = floor(x[xind[i]]); |
| 184 |
cand->rhs[1] = cand->rhs[0] + 1; |
| 185 |
cand->range[0] = cand->range[1] = 0; |
| 186 |
} |
| 187 |
|
| 188 |
FREE(xind); |
| 189 |
FREE(xval); |
| 190 |
|
| 191 |
return(USER_SUCCESS); |
| 192 |
|
| 193 |
#if 0 |
| 194 |
#ifdef DIRECTED_X_VARS |
| 195 |
nz = collect_nonzeros(p, x, xind, xval, status); |
| 196 |
|
| 197 |
for (j = 0; j < nz && xind[j] < total_edgenum; j++); |
| 198 |
for (i = 0; i < nz && xind[i] < total_edgenum; i++){ |
| 199 |
for (; j < nz && xind[j] < xind[i] + total_edgenum; j++){ |
| 200 |
if (xind[i] == xind[j] + total_edgenum){ |
| 201 |
xval[i] += xval[j]; |
| 202 |
break; |
| 203 |
}else{ |
| 204 |
xind[j] -= total_edgenum; |
| 205 |
} |
| 206 |
} |
| 207 |
} |
| 208 |
for (i = 0; i < nz; i++){ |
| 209 |
if (xind[i] < total_edgenum){ |
| 210 |
if ((xval[i] = fabs(xval[i] - floor(xval[i]) - .5)) < .5 - lpetol) |
| 211 |
cnt++; |
| 212 |
} |
| 213 |
} |
| 214 |
qsort_di(xval, xind, nz); |
| 215 |
|
| 216 |
candnum = cnrp->par.strong_branching_cand_num_max; |
| 217 |
candnum = MAX(candnum, cnrp->par.strong_branching_cand_num_min); |
| 218 |
candnum = MIN(candnum, cnt); |
| 219 |
|
| 220 |
FREE(xind); |
| 221 |
FREE(xval); |
| 222 |
#endif |
| 223 |
#endif |
| 224 |
|
| 225 |
*cand_num = 0; |
| 226 |
candnum = 0; |
| 227 |
/* allocate also memory for the basic vars */ |
| 228 |
*candidates = cand_list = (branch_obj **) |
| 229 |
malloc((varnum + (cnrp->par.branch_on_cuts ? |
| 230 |
(slacks_in_matrix_num + slack_cut_num) : 0)) * |
| 231 |
sizeof(branch_obj *)); |
| 232 |
switch (cnrp->par.branch_on_cuts){ |
| 233 |
case TRUE: |
| 234 |
pwl = (p_w_l *) malloc((slacks_in_matrix_num + slack_cut_num)* |
| 235 |
sizeof(p_w_l)); |
| 236 |
userind = (int *) malloc(varnum*ISIZE); |
| 237 |
|
| 238 |
for (i = varnum - 1; i >= 0; i--) |
| 239 |
userind[i] = vars[i]->userind; |
| 240 |
|
| 241 |
/* First go through the slack cuts and enlist the violated ones */ |
| 242 |
for (i = 0; i < slack_cut_num; i++){ |
| 243 |
left_hand_side = compute_lhs(varnum, userind, x, cut = slack_cuts[i], |
| 244 |
cnrp->vertnum); |
| 245 |
switch (cut->type){ |
| 246 |
case SUBTOUR_ELIM_SIDE: |
| 247 |
slack = cut->rhs - left_hand_side; |
| 248 |
if (slack < -lpetol){/*---------------- This cut became violated */ |
| 249 |
found_violated = TRUE; |
| 250 |
can = cand_list[candnum++] = |
| 251 |
(branch_obj *) calloc(1, sizeof(branch_obj)); |
| 252 |
can->type = VIOLATED_SLACK; |
| 253 |
can->position = i; |
| 254 |
}else if ((!found_violated) && (slack>lpetol) && |
| 255 |
!(cut->sense == 'R' || cut->sense == 'E')){ |
| 256 |
pwl[sc_cand_num].lhs = left_hand_side; |
| 257 |
pwl[sc_cand_num++].position = i; |
| 258 |
} |
| 259 |
break; |
| 260 |
|
| 261 |
case SUBTOUR_ELIM_ACROSS: |
| 262 |
slack = left_hand_side - cut->rhs; |
| 263 |
if (slack < -lpetol){/*---------------- This cut became violated */ |
| 264 |
found_violated = TRUE; |
| 265 |
can = cand_list[candnum++] = |
| 266 |
(branch_obj *) calloc(1, sizeof(branch_obj)); |
| 267 |
can->type = VIOLATED_SLACK; |
| 268 |
can->position = i; |
| 269 |
}else if ((!found_violated) && (slack>lpetol) && |
| 270 |
!(cut->sense=='R' || cut->sense=='E')){ |
| 271 |
pwl[sc_cand_num].lhs = left_hand_side; |
| 272 |
pwl[sc_cand_num++].position = i; |
| 273 |
} |
| 274 |
break; |
| 275 |
|
| 276 |
default: |
| 277 |
break; |
| 278 |
} |
| 279 |
} |
| 280 |
if (found_violated){ |
| 281 |
*cand_num = candnum; |
| 282 |
FREE(pwl); |
| 283 |
*action = USER__DO_NOT_BRANCH; |
| 284 |
return(USER_SUCCESS); |
| 285 |
} |
| 286 |
|
| 287 |
/* now go through the slack rows in the matrix and add the potential |
| 288 |
candidates to the end of the pos/weight lists */ |
| 289 |
for (i = 0; i < slacks_in_matrix_num; i++) |
| 290 |
if ((cut = slacks_in_matrix[i]) && |
| 291 |
(cut->type==SUBTOUR_ELIM_SIDE || cut->type== SUBTOUR_ELIM_ACROSS) |
| 292 |
&& !(cut->sense=='R' || cut->sense=='E')){ |
| 293 |
left_hand_side = compute_lhs(varnum, userind, x, cut, |
| 294 |
cnrp->vertnum); |
| 295 |
switch (cut->type){ |
| 296 |
case SUBTOUR_ELIM_SIDE: |
| 297 |
slack = cut->rhs - left_hand_side; |
| 298 |
/* if (slack > lpetol && slack < lpetol1){*/ |
| 299 |
if (slack > lpetol ){ |
| 300 |
pwl[sc_cand_num+sim_cand_num].lhs = left_hand_side; |
| 301 |
pwl[sc_cand_num+sim_cand_num].position = i; |
| 302 |
sim_cand_num++; |
| 303 |
} |
| 304 |
break; |
| 305 |
|
| 306 |
case SUBTOUR_ELIM_ACROSS: |
| 307 |
slack = left_hand_side - cut->rhs; |
| 308 |
/* if (slack > lpetol && slack < 2-lpetol){*/ |
| 309 |
if (slack > lpetol ){ |
| 310 |
pwl[sc_cand_num+sim_cand_num].lhs = left_hand_side; |
| 311 |
pwl[sc_cand_num+sim_cand_num].position = i; |
| 312 |
sim_cand_num++; |
| 313 |
} |
| 314 |
break; |
| 315 |
|
| 316 |
default: |
| 317 |
break; |
| 318 |
} |
| 319 |
} |
| 320 |
|
| 321 |
/* set the children's rhs etc */ |
| 322 |
for (i = 0 ; i < sc_cand_num + sim_cand_num; i++){ |
| 323 |
can = cand_list[candnum++] = |
| 324 |
(branch_obj *) calloc(1, sizeof(branch_obj)); |
| 325 |
if (i < sc_cand_num ){ |
| 326 |
can->type = CANDIDATE_CUT_NOT_IN_MATRIX; |
| 327 |
cut = slack_cuts[can->position = pwl[i].position ]; |
| 328 |
user_unpack_cuts(user, CUT_NOT_IN_MATRIX_SLACK, |
| 329 |
UNPACK_CUTS_SINGLE, varnum, vars, 1, |
| 330 |
slack_cuts+can->position, &new_row_num, |
| 331 |
&new_rows); |
| 332 |
can->row = *new_rows; |
| 333 |
cut = can->row->cut; |
| 334 |
FREE(new_rows); |
| 335 |
}else{ |
| 336 |
can->type = CANDIDATE_CUT_IN_MATRIX; |
| 337 |
cut = slacks_in_matrix[can->position = pwl[i].position ]; |
| 338 |
} |
| 339 |
can->child_num = 2; |
| 340 |
can->lhs = pwl[i].lhs; |
| 341 |
/* no need to allocate these. they are of fixed length |
| 342 |
can->sense = (char *) malloc(2 * CSIZE); |
| 343 |
can->rhs = (double *) malloc(2 * DSIZE); |
| 344 |
can->range = (double *) malloc(2 * DSIZE); |
| 345 |
*/ |
| 346 |
switch (cut->type){ |
| 347 |
case SUBTOUR_ELIM_SIDE: |
| 348 |
if ((slack = cut->rhs - can->lhs) < lpetol1){ |
| 349 |
can->sense[0] = 'E'; |
| 350 |
can->rhs[0] = cut->rhs; |
| 351 |
can->range[0] = 0; |
| 352 |
can->branch[0] = DO_NOT_BRANCH_ON_THIS_ROW; |
| 353 |
can->sense[1] = 'L'; |
| 354 |
can->rhs[1] = cut->rhs - 1; |
| 355 |
can->range[1] = 0; |
| 356 |
can->branch[1] = ALLOWED_TO_BRANCH_ON; |
| 357 |
}else{ |
| 358 |
can->sense[0] = 'R'; |
| 359 |
can->rhs[0] = cut->rhs; |
| 360 |
can->range[0] = -floor(slack) ; |
| 361 |
can->branch[0] = DO_NOT_BRANCH_ON_THIS_ROW; |
| 362 |
can->sense[1] = 'L'; |
| 363 |
can->rhs[1] = cut->rhs - ceil(slack); |
| 364 |
can->range[1] = 0; |
| 365 |
can->branch[1] = ALLOWED_TO_BRANCH_ON; |
| 366 |
} |
| 367 |
break; |
| 368 |
case SUBTOUR_ELIM_ACROSS: |
| 369 |
if ((slack = can->lhs - cut->rhs) < 2-lpetol){ |
| 370 |
can->sense[0] = 'E'; |
| 371 |
can->rhs[0] = cut->rhs; |
| 372 |
can->range[0] = 0; |
| 373 |
can->branch[0] = DO_NOT_BRANCH_ON_THIS_ROW; |
| 374 |
can->sense[1] = 'G'; |
| 375 |
can->rhs[1] = cut->rhs + 2; |
| 376 |
can->range[1] = 0; |
| 377 |
can->branch[1] = ALLOWED_TO_BRANCH_ON; |
| 378 |
}else{ |
| 379 |
can->sense[0] = 'R'; |
| 380 |
can->rhs[0] = cut->rhs; |
| 381 |
can->range[0] = 2*floor(slack/2); |
| 382 |
can->branch[0] = DO_NOT_BRANCH_ON_THIS_ROW; |
| 383 |
can->sense[1] = 'G'; |
| 384 |
can->rhs[1] = cut->rhs + 2*floor(slack/2) +2; |
| 385 |
can->range[1] = 0; |
| 386 |
can->branch[1] = ALLOWED_TO_BRANCH_ON; |
| 387 |
} |
| 388 |
break; |
| 389 |
} |
| 390 |
} |
| 391 |
FREE(pwl); |
| 392 |
FREE(userind); |
| 393 |
*cand_num = candnum; |
| 394 |
cand_list = *candidates + *cand_num; |
| 395 |
|
| 396 |
case FALSE: |
| 397 |
|
| 398 |
switch (((cnrp_spec *)user)->par.branching_rule){ |
| 399 |
case 0: |
| 400 |
{ |
| 401 |
int *xind = (int *) malloc(varnum*ISIZE); |
| 402 |
double *xval = (double *) malloc(varnum*DSIZE); |
| 403 |
int cnt = 0; |
| 404 |
|
| 405 |
for (i = varnum-1; i >= 0; i--){ |
| 406 |
fracx = x[i] - floor(x[i]); |
| 407 |
if (fracx > lpetol && fracx < 1-lpetol){ |
| 408 |
xind[cnt] = i; |
| 409 |
xval[cnt++] = fabs(fracx - .5); |
| 410 |
} |
| 411 |
} |
| 412 |
qsort_di(xval, xind, cnt); |
| 413 |
|
| 414 |
candnum = cnrp->par.strong_branching_cand_num_max - |
| 415 |
cnrp->par.strong_branching_red_ratio * bc_level; |
| 416 |
candnum = MAX(candnum, cnrp->par.strong_branching_cand_num_min); |
| 417 |
candnum = MIN(candnum, cnt); |
| 418 |
|
| 419 |
for (i = candnum-1; i >= 0; i--){ |
| 420 |
can=cand_list[i]=(branch_obj *) calloc(1, sizeof(branch_obj)); |
| 421 |
can->type = CANDIDATE_VARIABLE; |
| 422 |
can->child_num = 2; |
| 423 |
can->position = xind[i]; |
| 424 |
can->sense[0] = 'L'; |
| 425 |
can->sense[1] = 'G'; |
| 426 |
can->rhs[0] = floor(x[xind[i]]); |
| 427 |
can->rhs[1] = can->rhs[0] + 1; |
| 428 |
can->range[0] = can->range[1] = 0; |
| 429 |
} |
| 430 |
FREE(xind); |
| 431 |
FREE(xval); |
| 432 |
} |
| 433 |
break; |
| 434 |
|
| 435 |
case 1: |
| 436 |
candnum = 0; |
| 437 |
for (i = varnum-1; i >= 0; i--){ |
| 438 |
fracx = x[i] - floor(x[i]); |
| 439 |
if (fracx > lpetol && fracx < lpetol5){ |
| 440 |
can = cand_list[candnum++] = |
| 441 |
(branch_obj *) calloc(1, sizeof(branch_obj)); |
| 442 |
can->type = CANDIDATE_VARIABLE; |
| 443 |
can->child_num = 2; |
| 444 |
can->position = i; |
| 445 |
can->sense[0] = 'L'; |
| 446 |
can->sense[1] = 'G'; |
| 447 |
can->rhs[0] = floor(x[i]); |
| 448 |
can->rhs[1] = can->rhs[0] + 1; |
| 449 |
can->range[0] = can->range[1] = 0; |
| 450 |
} |
| 451 |
} |
| 452 |
break; |
| 453 |
|
| 454 |
case 2: |
| 455 |
return(USER__CLOSE_TO_HALF); |
| 456 |
} |
| 457 |
*cand_num += candnum; |
| 458 |
*action = USER__DO_BRANCH; |
| 459 |
} |
| 460 |
return(USER_SUCCESS); |
| 461 |
} |
| 462 |
|
| 463 |
/*===========================================================================*/ |
| 464 |
|
| 465 |
double compute_lhs(int number, int *indices, double *values, cut_data *cut, |
| 466 |
int vertnum) |
| 467 |
{ |
| 468 |
char *coef; |
| 469 |
int v0, v1; |
| 470 |
double lhs = 0; |
| 471 |
int i; |
| 472 |
|
| 473 |
switch (cut->type){ |
| 474 |
|
| 475 |
case SUBTOUR_ELIM_SIDE: |
| 476 |
coef = (char *)(cut->coef); |
| 477 |
for (i = 0, lhs = 0; i<number; i++){ |
| 478 |
BOTH_ENDS(indices[i], &v1, &v0); |
| 479 |
if (coef[v0 >> DELETE_POWER] & (1 << (v0 & DELETE_AND)) && |
| 480 |
(coef[v1 >> DELETE_POWER]) & (1 << (v1 & DELETE_AND))) |
| 481 |
lhs += values[i]; |
| 482 |
|
| 483 |
} |
| 484 |
return(lhs); |
| 485 |
|
| 486 |
case SUBTOUR_ELIM_ACROSS: |
| 487 |
coef = (char *)(cut->coef); |
| 488 |
for (lhs = 0, i = 0; i<number; i++){ |
| 489 |
BOTH_ENDS(indices[i], &v1, &v0); |
| 490 |
if ((coef[v0 >> DELETE_POWER] >> (v0 & DELETE_AND) & 1) ^ |
| 491 |
(coef[v1 >> DELETE_POWER] >> (v1 & DELETE_AND) & 1)) |
| 492 |
lhs += values[i]; |
| 493 |
} |
| 494 |
|
| 495 |
return(lhs); |
| 496 |
|
| 497 |
default: |
| 498 |
printf("Cut type's not recognized! \n\n"); |
| 499 |
return(0); |
| 500 |
} |
| 501 |
} |
| 502 |
|
| 503 |
/*===========================================================================*/ |
| 504 |
|
| 505 |
/*===========================================================================*\ |
| 506 |
* I wrote my own function to compare candidates. Maybe this should go |
| 507 |
* into SYMPHONY. |
| 508 |
\*===========================================================================*/ |
| 509 |
|
| 510 |
int user_compare_candidates(void *user, branch_obj *can1, branch_obj *can2, |
| 511 |
double ub, double granularity, |
| 512 |
int *which_is_better) |
| 513 |
{ |
| 514 |
int i, j; |
| 515 |
double low1, low2; |
| 516 |
|
| 517 |
for (i = 1; i >= 0; i--) |
| 518 |
if (can1->termcode[i] == LP_OPT_FEASIBLE || |
| 519 |
can1->termcode[i] == LP_OPT_FEASIBLE_BUT_CONTINUE || |
| 520 |
can1->termcode[i] == LP_D_OBJLIM || |
| 521 |
can1->termcode[i] == LP_D_UNBOUNDED || |
| 522 |
(can1->termcode[i] == LP_OPTIMAL && can1->objval[i] > ub - granularity)) |
| 523 |
break; |
| 524 |
|
| 525 |
for (j = 1; j >= 0; j--) |
| 526 |
if (can2->termcode[j] == LP_OPT_FEASIBLE || |
| 527 |
can1->termcode[i] == LP_OPT_FEASIBLE_BUT_CONTINUE || |
| 528 |
can2->termcode[j] == LP_D_OBJLIM || |
| 529 |
can2->termcode[j] == LP_D_UNBOUNDED || |
| 530 |
(can2->termcode[j] == LP_OPTIMAL && can2->objval[j] > ub - granularity)) |
| 531 |
break; |
| 532 |
|
| 533 |
if (i < 0 && j < 0) |
| 534 |
return(USER_DEFAULT); |
| 535 |
|
| 536 |
if (i < 0 && j > 0){ |
| 537 |
*which_is_better = SECOND_CANDIDATE_BETTER; |
| 538 |
return(USER_SUCCESS); |
| 539 |
} |
| 540 |
|
| 541 |
if (i > 0 && j < 0){ |
| 542 |
*which_is_better = FIRST_CANDIDATE_BETTER; |
| 543 |
return(USER_SUCCESS); |
| 544 |
} |
| 545 |
|
| 546 |
low1 = i ? can1->objval[0] : can1->objval[1]; |
| 547 |
low2 = j ? can2->objval[0] : can2->objval[1]; |
| 548 |
|
| 549 |
*which_is_better = low1 > low2 ? FIRST_CANDIDATE_BETTER : |
| 550 |
SECOND_CANDIDATE_BETTER; |
| 551 |
|
| 552 |
return(USER_SUCCESS); |
| 553 |
} |
| 554 |
|
| 555 |
/*===========================================================================*/ |
| 556 |
|
| 557 |
/*===========================================================================*\ |
| 558 |
* You can let SYMPHONY choose which child to retain. The default is |
| 559 |
* to keep the one with the lower objective function value. |
| 560 |
\*===========================================================================*/ |
| 561 |
|
| 562 |
int user_select_child(void *user, double ub, branch_obj *can, char *action) |
| 563 |
{ |
| 564 |
return(USER_DEFAULT); |
| 565 |
} |
| 566 |
|
| 567 |
/*===========================================================================*/ |
| 568 |
|
| 569 |
/*===========================================================================*\ |
| 570 |
* Here, you can print out a more identifiable description of the |
| 571 |
* branching object than just "variable 51". I print out the end points |
| 572 |
* of the edge if an edge is branched on. |
| 573 |
\*===========================================================================*/ |
| 574 |
|
| 575 |
int user_print_branch_stat(void *user, branch_obj *can, cut_data *cut, |
| 576 |
int n, var_desc **vars, char *action) |
| 577 |
{ |
| 578 |
cnrp_spec *cnrp = (cnrp_spec *)user; |
| 579 |
int v0, v1, i; |
| 580 |
char *coef; |
| 581 |
int total_edgenum = cnrp->vertnum*(cnrp->vertnum - 1)/2; |
| 582 |
|
| 583 |
if (cut){ |
| 584 |
switch(cut->type){ |
| 585 |
case SUBTOUR_ELIM_SIDE: |
| 586 |
coef = (char *)(cut->coef); |
| 587 |
for (i = 0; i < n; i++){ |
| 588 |
BOTH_ENDS(vars[i]->userind, &v1, &v0); |
| 589 |
if (coef[v0 >> DELETE_POWER] & (1 << (v0 & DELETE_AND)) && |
| 590 |
(coef[v1 >> DELETE_POWER]) & (1 << (v1 & DELETE_AND))) |
| 591 |
printf("Edge (%i, %i)\n", v0, v1); |
| 592 |
} |
| 593 |
|
| 594 |
case SUBTOUR_ELIM_ACROSS: |
| 595 |
coef = (char *)(cut->coef); |
| 596 |
for (i = 0; i < n; i++){ |
| 597 |
BOTH_ENDS(vars[i]->userind, &v1, &v0); |
| 598 |
if ((coef[v0 >> DELETE_POWER] >> (v0 & DELETE_AND) & 1) ^ |
| 599 |
(coef[v1 >> DELETE_POWER] >> (v1 & DELETE_AND) & 1)) |
| 600 |
printf("Edge (%i, %i)\n", v0, v1); |
| 601 |
} |
| 602 |
} |
| 603 |
}else{ |
| 604 |
if (vars[can->position]->userind < total_edgenum){ |
| 605 |
BOTH_ENDS(vars[can->position]->userind, &v1, &v0); |
| 606 |
}else if (vars[can->position]->userind < 2*total_edgenum){ |
| 607 |
BOTH_ENDS(vars[can->position]->userind-total_edgenum, &v1, &v0); |
| 608 |
}else{ |
| 609 |
printf("ERROR in branching.../n/n"); |
| 610 |
} |
| 611 |
printf("Edge (%i, %i)\n", v0, v1); |
| 612 |
} |
| 613 |
|
| 614 |
return(USER_SUCCESS); |
| 615 |
} |