| 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 |
/* the Vehicle Routing Problem and the Traveling Salesman Problem. */ |
| 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 <memory.h> |
| 21 |
#include <stdio.h> |
| 22 |
|
| 23 |
/* SYMPHONY include files */ |
| 24 |
#include "sym_constants.h" |
| 25 |
#include "sym_macros.h" |
| 26 |
#include "sym_qsort.h" |
| 27 |
#include "sym_lp_u.h" |
| 28 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 29 |
#include "sym_lp.h" |
| 30 |
/*___END_EXPERIMENTAL_SECTION___*/ |
| 31 |
|
| 32 |
/* VRP include files */ |
| 33 |
#include "vrp_lp.h" |
| 34 |
#include "vrp_macros.h" |
| 35 |
#include "vrp_const.h" |
| 36 |
#include "sym_timemeas.h" |
| 37 |
|
| 38 |
/*===========================================================================*/ |
| 39 |
|
| 40 |
/*===========================================================================*\ |
| 41 |
* This file contains the user-written functions for the LP process related |
| 42 |
* to branching. |
| 43 |
\*===========================================================================*/ |
| 44 |
|
| 45 |
/*===========================================================================*\ |
| 46 |
* This function determines whether to branch. You can eseentially |
| 47 |
* leave this up to SYMPHONY unless there is some compelling reason not to. |
| 48 |
\*===========================================================================*/ |
| 49 |
|
| 50 |
int user_shall_we_branch(void *user, double lpetol, int cutnum, |
| 51 |
int slacks_in_matrix_num, cut_data **slacks_im_matrix, |
| 52 |
int slack_cut_num, cut_data **slack_cuts, int varnum, |
| 53 |
var_desc **vars, double *x, char *status, |
| 54 |
int *cand_num, branch_obj ***candidates, |
| 55 |
int *action) |
| 56 |
{ |
| 57 |
|
| 58 |
int i; |
| 59 |
double fracx, lpetol1 = 1 - lpetol; |
| 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 |
vrp_lp_problem *vrp = (vrp_lp_problem *) user; |
| 78 |
|
| 79 |
if (!vrp->par.detect_tailoff){ |
| 80 |
*action = USER__BRANCH_IF_MUST; |
| 81 |
}else{ |
| 82 |
*action = USER__BRANCH_IF_TAILOFF; |
| 83 |
} |
| 84 |
#endif |
| 85 |
|
| 86 |
return(USER_SUCCESS); |
| 87 |
} |
| 88 |
|
| 89 |
/*===========================================================================*/ |
| 90 |
|
| 91 |
/*===========================================================================*\ |
| 92 |
* Here, we select the branching candidates. This can essentially be |
| 93 |
* left to SYMPHONY too using one of the built-in functions, but here, I |
| 94 |
* demonstrate how to branch on cuts, which must be done by the user. |
| 95 |
\*===========================================================================*/ |
| 96 |
|
| 97 |
int user_select_candidates(void *user, double lpetol, int cutnum, |
| 98 |
int slacks_in_matrix_num, |
| 99 |
cut_data **slacks_in_matrix, int slack_cut_num, |
| 100 |
cut_data **slack_cuts, int varnum, var_desc **vars, |
| 101 |
double *x, char *status, int *cand_num, |
| 102 |
branch_obj ***candidates, int *action, |
| 103 |
int bc_level) |
| 104 |
|
| 105 |
{ |
| 106 |
vrp_lp_problem *vrp = (vrp_lp_problem *)user; |
| 107 |
cut_data *cut; |
| 108 |
branch_obj **cand_list, *can; |
| 109 |
int i, candnum, found_violated = FALSE; |
| 110 |
p_w_l *pwl; |
| 111 |
double left_hand_side, lpetol1 = 1 - lpetol, lpetol5=.95, slack, fracx; |
| 112 |
waiting_row **new_rows; |
| 113 |
int new_row_num; |
| 114 |
int *userind; |
| 115 |
int sim_cand_num = 0, sc_cand_num = 0; |
| 116 |
/* numbers of slacks_in_matrix, slack_cuts and variables, that are used |
| 117 |
as branching cands */ |
| 118 |
|
| 119 |
if (!vrp->par.branch_on_cuts && vrp->par.branching_rule == 2) |
| 120 |
/* use the built-in rule */ |
| 121 |
return(USER_DEFAULT); |
| 122 |
|
| 123 |
*cand_num = 0; |
| 124 |
candnum = 0; |
| 125 |
/* allocate also memory for the basic vars */ |
| 126 |
*candidates = cand_list = (branch_obj **) |
| 127 |
malloc((varnum + (vrp->par.branch_on_cuts ? |
| 128 |
(slacks_in_matrix_num + slack_cut_num) : 0)) * |
| 129 |
sizeof(branch_obj *)); |
| 130 |
switch (vrp->par.branch_on_cuts){ |
| 131 |
case TRUE: |
| 132 |
pwl = (p_w_l *) malloc((slacks_in_matrix_num + slack_cut_num)* |
| 133 |
sizeof(p_w_l)); |
| 134 |
userind = (int *) malloc(varnum*ISIZE); |
| 135 |
|
| 136 |
for (i = varnum - 1; i >= 0; i--) |
| 137 |
userind[i] = vars[i]->userind; |
| 138 |
|
| 139 |
/* First go through the slack cuts and enlist the violated ones */ |
| 140 |
for (i = 0; i < slack_cut_num; i++){ |
| 141 |
left_hand_side = compute_lhs(varnum, userind, x, cut = slack_cuts[i], |
| 142 |
vrp->vertnum); |
| 143 |
switch (cut->type){ |
| 144 |
case SUBTOUR_ELIM_SIDE: |
| 145 |
slack = cut->rhs - left_hand_side; |
| 146 |
if (slack < -lpetol){/*---------------- This cut became violated */ |
| 147 |
found_violated = TRUE; |
| 148 |
can = cand_list[candnum++] = |
| 149 |
(branch_obj *) calloc(1, sizeof(branch_obj)); |
| 150 |
can->type = VIOLATED_SLACK; |
| 151 |
can->position = i; |
| 152 |
}else if ((!found_violated) && (slack>lpetol) && |
| 153 |
!(cut->sense == 'R' || cut->sense == 'E')){ |
| 154 |
pwl[sc_cand_num].lhs = left_hand_side; |
| 155 |
pwl[sc_cand_num++].position = i; |
| 156 |
} |
| 157 |
break; |
| 158 |
|
| 159 |
case SUBTOUR_ELIM_ACROSS: |
| 160 |
slack = left_hand_side - cut->rhs; |
| 161 |
if (slack < -lpetol){/*---------------- This cut became violated */ |
| 162 |
found_violated = TRUE; |
| 163 |
can = cand_list[candnum++] = |
| 164 |
(branch_obj *) calloc(1, sizeof(branch_obj)); |
| 165 |
can->type = VIOLATED_SLACK; |
| 166 |
can->position = i; |
| 167 |
}else if ((!found_violated) && (slack>lpetol) && |
| 168 |
!(cut->sense=='R' || cut->sense=='E')){ |
| 169 |
pwl[sc_cand_num].lhs = left_hand_side; |
| 170 |
pwl[sc_cand_num++].position = i; |
| 171 |
} |
| 172 |
break; |
| 173 |
|
| 174 |
default: |
| 175 |
break; |
| 176 |
} |
| 177 |
} |
| 178 |
if (found_violated){ |
| 179 |
*cand_num = candnum; |
| 180 |
FREE(pwl); |
| 181 |
*action = USER__DO_NOT_BRANCH; |
| 182 |
return(USER_SUCCESS); |
| 183 |
} |
| 184 |
|
| 185 |
/* now go through the slack rows in the matrix and add the potential |
| 186 |
candidates to the end of the pos/weight lists */ |
| 187 |
for (i = 0; i < slacks_in_matrix_num; i++) |
| 188 |
if ((cut = slacks_in_matrix[i]) && |
| 189 |
(cut->type==SUBTOUR_ELIM_SIDE || cut->type== SUBTOUR_ELIM_ACROSS) |
| 190 |
&& !(cut->sense=='R' || cut->sense=='E')){ |
| 191 |
left_hand_side = compute_lhs(varnum, userind, x, cut, |
| 192 |
vrp->vertnum); |
| 193 |
switch (cut->type){ |
| 194 |
case SUBTOUR_ELIM_SIDE: |
| 195 |
slack = cut->rhs - left_hand_side; |
| 196 |
/* if (slack > lpetol && slack < lpetol1){*/ |
| 197 |
if (slack > lpetol ){ |
| 198 |
pwl[sc_cand_num+sim_cand_num].lhs = left_hand_side; |
| 199 |
pwl[sc_cand_num+sim_cand_num].position = i; |
| 200 |
sim_cand_num++; |
| 201 |
} |
| 202 |
break; |
| 203 |
|
| 204 |
case SUBTOUR_ELIM_ACROSS: |
| 205 |
slack = left_hand_side - cut->rhs; |
| 206 |
/* if (slack > lpetol && slack < 2-lpetol){*/ |
| 207 |
if (slack > lpetol ){ |
| 208 |
pwl[sc_cand_num+sim_cand_num].lhs = left_hand_side; |
| 209 |
pwl[sc_cand_num+sim_cand_num].position = i; |
| 210 |
sim_cand_num++; |
| 211 |
} |
| 212 |
break; |
| 213 |
|
| 214 |
default: |
| 215 |
break; |
| 216 |
} |
| 217 |
} |
| 218 |
|
| 219 |
/* set the children's rhs etc */ |
| 220 |
for (i = 0 ; i < sc_cand_num + sim_cand_num; i++){ |
| 221 |
can = cand_list[candnum++] = |
| 222 |
(branch_obj *) calloc(1, sizeof(branch_obj)); |
| 223 |
if (i < sc_cand_num ){ |
| 224 |
can->type = CANDIDATE_CUT_NOT_IN_MATRIX; |
| 225 |
cut = slack_cuts[can->position = pwl[i].position ]; |
| 226 |
user_unpack_cuts(user, CUT_NOT_IN_MATRIX_SLACK, |
| 227 |
UNPACK_CUTS_SINGLE, varnum, vars, 1, |
| 228 |
slack_cuts+can->position, &new_row_num, |
| 229 |
&new_rows); |
| 230 |
can->row = *new_rows; |
| 231 |
cut = can->row->cut; |
| 232 |
FREE(new_rows); |
| 233 |
}else{ |
| 234 |
can->type = CANDIDATE_CUT_IN_MATRIX; |
| 235 |
cut = slacks_in_matrix[can->position = pwl[i].position ]; |
| 236 |
} |
| 237 |
can->child_num = 2; |
| 238 |
can->lhs = pwl[i].lhs; |
| 239 |
/* no need to allocate these. they are of fixed length |
| 240 |
can->sense = (char *) malloc(2 * CSIZE); |
| 241 |
can->rhs = (double *) malloc(2 * DSIZE); |
| 242 |
can->range = (double *) malloc(2 * DSIZE); |
| 243 |
*/ |
| 244 |
switch (cut->type){ |
| 245 |
case SUBTOUR_ELIM_SIDE: |
| 246 |
if ((slack = cut->rhs - can->lhs) < lpetol1){ |
| 247 |
can->sense[0] = 'E'; |
| 248 |
can->rhs[0] = cut->rhs; |
| 249 |
can->range[0] = 0; |
| 250 |
can->branch[0] = DO_NOT_BRANCH_ON_THIS_ROW; |
| 251 |
can->sense[1] = 'L'; |
| 252 |
can->rhs[1] = cut->rhs - 1; |
| 253 |
can->range[1] = 0; |
| 254 |
can->branch[1] = ALLOWED_TO_BRANCH_ON; |
| 255 |
}else{ |
| 256 |
can->sense[0] = 'R'; |
| 257 |
can->rhs[0] = cut->rhs; |
| 258 |
can->range[0] = -floor(slack) ; |
| 259 |
can->branch[0] = DO_NOT_BRANCH_ON_THIS_ROW; |
| 260 |
can->sense[1] = 'L'; |
| 261 |
can->rhs[1] = cut->rhs - ceil(slack); |
| 262 |
can->range[1] = 0; |
| 263 |
can->branch[1] = ALLOWED_TO_BRANCH_ON; |
| 264 |
} |
| 265 |
break; |
| 266 |
case SUBTOUR_ELIM_ACROSS: |
| 267 |
if ((slack = can->lhs - cut->rhs) < 2-lpetol){ |
| 268 |
can->sense[0] = 'E'; |
| 269 |
can->rhs[0] = cut->rhs; |
| 270 |
can->range[0] = 0; |
| 271 |
can->branch[0] = DO_NOT_BRANCH_ON_THIS_ROW; |
| 272 |
can->sense[1] = 'G'; |
| 273 |
can->rhs[1] = cut->rhs + 2; |
| 274 |
can->range[1] = 0; |
| 275 |
can->branch[1] = ALLOWED_TO_BRANCH_ON; |
| 276 |
}else{ |
| 277 |
can->sense[0] = 'R'; |
| 278 |
can->rhs[0] = cut->rhs; |
| 279 |
can->range[0] = 2*floor(slack/2); |
| 280 |
can->branch[0] = DO_NOT_BRANCH_ON_THIS_ROW; |
| 281 |
can->sense[1] = 'G'; |
| 282 |
can->rhs[1] = cut->rhs + 2*floor(slack/2) +2; |
| 283 |
can->range[1] = 0; |
| 284 |
can->branch[1] = ALLOWED_TO_BRANCH_ON; |
| 285 |
} |
| 286 |
break; |
| 287 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 288 |
case FARKAS: |
| 289 |
break; |
| 290 |
case NO_COLUMNS: |
| 291 |
break; |
| 292 |
/*___END_EXPERIMENTAL_SECTION___*/ |
| 293 |
} |
| 294 |
} |
| 295 |
FREE(pwl); |
| 296 |
FREE(userind); |
| 297 |
*cand_num = candnum; |
| 298 |
cand_list = *candidates + *cand_num; |
| 299 |
|
| 300 |
case FALSE: |
| 301 |
|
| 302 |
switch (((vrp_lp_problem *)user)->par.branching_rule){ |
| 303 |
case 0: |
| 304 |
{ |
| 305 |
int *xind = (int *) malloc(varnum*ISIZE); |
| 306 |
double *xval = (double *) malloc(varnum*DSIZE); |
| 307 |
int cnt = 0; |
| 308 |
|
| 309 |
for (i = varnum-1; i >= 0; i--){ |
| 310 |
fracx = x[i] - floor(x[i]); |
| 311 |
if (fracx > lpetol && fracx < 1-lpetol){ |
| 312 |
xind[cnt] = i; |
| 313 |
xval[cnt++] = fabs(fracx - .5); |
| 314 |
} |
| 315 |
} |
| 316 |
qsort_di(xval, xind, cnt); |
| 317 |
|
| 318 |
candnum = vrp->par.strong_branching_cand_num_max - |
| 319 |
vrp->par.strong_branching_red_ratio * bc_level; |
| 320 |
candnum = MAX(candnum, vrp->par.strong_branching_cand_num_min); |
| 321 |
candnum = MIN(candnum, cnt); |
| 322 |
|
| 323 |
for (i = candnum-1; i >= 0; i--){ |
| 324 |
can=cand_list[i]=(branch_obj *) calloc(1, sizeof(branch_obj)); |
| 325 |
can->type = CANDIDATE_VARIABLE; |
| 326 |
can->child_num = 2; |
| 327 |
can->position = xind[i]; |
| 328 |
can->sense[0] = 'L'; |
| 329 |
can->sense[1] = 'G'; |
| 330 |
can->rhs[0] = floor(x[xind[i]]); |
| 331 |
can->rhs[1] = can->rhs[0] + 1; |
| 332 |
can->range[0] = can->range[1] = 0; |
| 333 |
} |
| 334 |
FREE(xind); |
| 335 |
FREE(xval); |
| 336 |
} |
| 337 |
break; |
| 338 |
|
| 339 |
case 1: |
| 340 |
candnum = 0; |
| 341 |
for (i = varnum-1; i >= 0; i--){ |
| 342 |
fracx = x[i] - floor(x[i]); |
| 343 |
if (fracx > lpetol && fracx < lpetol5){ |
| 344 |
can = cand_list[candnum++] = |
| 345 |
(branch_obj *) calloc(1, sizeof(branch_obj)); |
| 346 |
can->type = CANDIDATE_VARIABLE; |
| 347 |
can->child_num = 2; |
| 348 |
can->position = i; |
| 349 |
can->sense[0] = 'L'; |
| 350 |
can->sense[1] = 'G'; |
| 351 |
can->rhs[0] = floor(x[i]); |
| 352 |
can->rhs[1] = can->rhs[0] + 1; |
| 353 |
can->range[0] = can->range[1] = 0; |
| 354 |
} |
| 355 |
} |
| 356 |
break; |
| 357 |
|
| 358 |
case 2: |
| 359 |
return(USER__CLOSE_TO_HALF); |
| 360 |
} |
| 361 |
*cand_num += candnum; |
| 362 |
*action = USER__DO_BRANCH; |
| 363 |
} |
| 364 |
return(USER_SUCCESS); |
| 365 |
} |
| 366 |
|
| 367 |
/*===========================================================================*/ |
| 368 |
|
| 369 |
double compute_lhs(int number, int *indices, double *values, cut_data *cut, |
| 370 |
int vertnum) |
| 371 |
{ |
| 372 |
char *coef; |
| 373 |
int v0, v1; |
| 374 |
double lhs = 0; |
| 375 |
int i; |
| 376 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 377 |
int num_arcs, edge_index ; |
| 378 |
char *cpt; |
| 379 |
int *arcs ; |
| 380 |
char *indicators; |
| 381 |
double bigM, *weights ; |
| 382 |
int jj; |
| 383 |
/*___END_EXPERIMENTAL_SECTION___*/ |
| 384 |
|
| 385 |
switch (cut->type){ |
| 386 |
|
| 387 |
case SUBTOUR_ELIM_SIDE: |
| 388 |
coef = (char *)(cut->coef); |
| 389 |
for (i = 0, lhs = 0; i<number; i++){ |
| 390 |
BOTH_ENDS(indices[i], &v1, &v0); |
| 391 |
if (coef[v0 >> DELETE_POWER] & (1 << (v0 & DELETE_AND)) && |
| 392 |
(coef[v1 >> DELETE_POWER]) & (1 << (v1 & DELETE_AND))) |
| 393 |
lhs += values[i]; |
| 394 |
|
| 395 |
} |
| 396 |
return(lhs); |
| 397 |
|
| 398 |
case SUBTOUR_ELIM_ACROSS: |
| 399 |
coef = (char *)(cut->coef); |
| 400 |
for (lhs = 0, i = 0; i<number; i++){ |
| 401 |
BOTH_ENDS(indices[i], &v1, &v0); |
| 402 |
if ((coef[v0 >> DELETE_POWER] >> (v0 & DELETE_AND) & 1) ^ |
| 403 |
(coef[v1 >> DELETE_POWER] >> (v1 & DELETE_AND) & 1)) |
| 404 |
lhs += values[i]; |
| 405 |
} |
| 406 |
|
| 407 |
return(lhs); |
| 408 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 409 |
|
| 410 |
case FARKAS: |
| 411 |
coef = (char *)(cut->coef); |
| 412 |
arcs = (int *) calloc( ((vertnum*vertnum)/2), sizeof(int)); |
| 413 |
weights = (double *) calloc( ((vertnum*vertnum)/2), sizeof(double)) ; |
| 414 |
|
| 415 |
cpt=coef+ ((vertnum >> DELETE_POWER) + 1); |
| 416 |
memcpy((char *)&num_arcs, cpt, ISIZE); |
| 417 |
memcpy((char *)arcs, cpt, ISIZE*(num_arcs +1)); |
| 418 |
arcs++; |
| 419 |
cpt+=(ISIZE*(num_arcs +1))/CSIZE; |
| 420 |
memcpy((char *)weights, cpt, DSIZE*(num_arcs +1)); |
| 421 |
bigM=(*(double *)weights); |
| 422 |
weights++; |
| 423 |
|
| 424 |
for (i = 0, lhs=0 ; i<number; i++){ |
| 425 |
BOTH_ENDS(indices[i], &v1, &v0); |
| 426 |
edge_index=indices[i]; |
| 427 |
|
| 428 |
if (isset(coef, v1) || isset(coef,v0)){ |
| 429 |
for (jj=0; jj<num_arcs; jj++){ |
| 430 |
if ( arcs[jj]==edge_index){ |
| 431 |
lhs+=weights[jj]*values[i]; |
| 432 |
break; |
| 433 |
} |
| 434 |
} |
| 435 |
if (jj==num_arcs) lhs+=bigM*values[i]; |
| 436 |
|
| 437 |
} |
| 438 |
} |
| 439 |
arcs--; |
| 440 |
weights--; |
| 441 |
FREE(arcs); |
| 442 |
FREE(weights); |
| 443 |
return(lhs); |
| 444 |
|
| 445 |
|
| 446 |
case NO_COLUMNS: |
| 447 |
coef = (char *)(cut->coef); |
| 448 |
arcs = (int *) malloc( ((vertnum*vertnum)/2)* sizeof(int)); |
| 449 |
indicators = (char *) malloc( ((vertnum*vertnum)/2)* sizeof(char)); |
| 450 |
|
| 451 |
cpt=coef+ ((vertnum >> DELETE_POWER) + 1); |
| 452 |
memcpy((char *)&num_arcs, cpt, ISIZE); |
| 453 |
cpt+= ISIZE /CSIZE; |
| 454 |
memcpy((char *)arcs, cpt, ISIZE*(num_arcs)); |
| 455 |
cpt+=(ISIZE*(num_arcs ))/CSIZE; |
| 456 |
memcpy((char *)indicators, cpt, CSIZE*(num_arcs)); |
| 457 |
|
| 458 |
for (i = 0, lhs=0 ; i<number; i++){ |
| 459 |
BOTH_ENDS(indices[i], &v1, &v0); |
| 460 |
edge_index=indices[i]; |
| 461 |
|
| 462 |
if (isset(coef, v1) || isset(coef,v0)){ |
| 463 |
for (jj=0; jj<num_arcs; jj++){ |
| 464 |
if ( arcs[jj]==edge_index){ |
| 465 |
lhs+=values[i]* ( indicators[jj] ? 1.0:0.0); |
| 466 |
break; |
| 467 |
} |
| 468 |
} |
| 469 |
if (jj==num_arcs) lhs-=values[i]; |
| 470 |
} |
| 471 |
} |
| 472 |
FREE(arcs); |
| 473 |
FREE(indicators); |
| 474 |
return(lhs); |
| 475 |
/*___END_EXPERIMENTAL_SECTION___*/ |
| 476 |
|
| 477 |
default: |
| 478 |
printf("Cut type's not recognized! \n\n"); |
| 479 |
return(0); |
| 480 |
} |
| 481 |
} |
| 482 |
|
| 483 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 484 |
#if 0 |
| 485 |
/*===========================================================================*/ |
| 486 |
|
| 487 |
int user_select_candidates(lp_prob *p, void *user, double lpetol, int cutnum, |
| 488 |
int slacks_in_matrix_num, |
| 489 |
cut_data **slacks_im_matrix, int slack_cut_num, |
| 490 |
cut_data **slack_cuts, int varnum, var_desc **vars, |
| 491 |
double *x, char *status, int *cand_num, |
| 492 |
branch_obj ***candidates, int *action) |
| 493 |
|
| 494 |
{ |
| 495 |
return(USER__CLOSE_TO_HALF); |
| 496 |
} |
| 497 |
|
| 498 |
/*===========================================================================*/ |
| 499 |
|
| 500 |
int user_select_candidates(lp_prob *p, void *user, double lpetol, int cutnum, |
| 501 |
int slacks_in_matrix_num, |
| 502 |
cut_data **slacks_im_matrix, int slack_cut_num, |
| 503 |
cut_data **slack_cuts, int varnum, var_desc **vars, |
| 504 |
double *x, char *status, int *cand_num, |
| 505 |
branch_obj ***candidates, int *action) |
| 506 |
|
| 507 |
{ |
| 508 |
vrp_lp_problem *vrp = (vrp_lp_problem *)user; |
| 509 |
int i; |
| 510 |
int *sorted_cand_list, j = 0, k = 0; |
| 511 |
double *sorted_diffs; |
| 512 |
int cand_num = vrp->par.max_branch_cand; |
| 513 |
int branch_rule = vrp->par.branching_rule; |
| 514 |
branch_obj **candidates, *cand; |
| 515 |
|
| 516 |
candidates = |
| 517 |
*candidates = (branch_obj **) malloc(cand_num * sizeof(branch_obj *)); |
| 518 |
|
| 519 |
sorted_cand_list = (int *) calloc (varnum, sizeof(int)); |
| 520 |
sorted_diffs = (double *) calloc (varnum, sizeof(double)); |
| 521 |
for (i = 0; i < varnum; i++){ |
| 522 |
sorted_cand_list[i] = i; |
| 523 |
sorted_diffs[i] = fabs(x[i] - .5); |
| 524 |
} |
| 525 |
|
| 526 |
cand_sort(sorted_cand_list, sorted_diffs, varnum); |
| 527 |
|
| 528 |
switch(vrp->par.branching_rule){ /* which branching rule to use */ |
| 529 |
|
| 530 |
case DEPOTS_AT_HALF_BRANCH_RIGHT: |
| 531 |
case DEPOTS_AT_HALF: |
| 532 |
case VARS_AT_HALF_PREFER_DEPOT_BRANCH_RIGHT: |
| 533 |
case VARS_AT_HALF_PREFER_DEPOT: |
| 534 |
|
| 535 |
for (i=0, j=0; sorted_diffs[i]<lpetol && i<varnum && j<cand_num; i++){ |
| 536 |
/* Here we find the depot edges that are at a half*/ |
| 537 |
if (vrp->edges[(vars[sorted_cand_list[i]]->userind) << 1] == 0){ |
| 538 |
/* This userind serves the purpose of checking whether the |
| 539 |
variable corresponds to an edge connected to the depot */ |
| 540 |
cand = candidates[i] = (branch_obj *)calloc(1, sizeof(branch_obj)); |
| 541 |
cand->position = sorted_cand_list[i]; |
| 542 |
cand->type = CANDIDATE_VARIABLE; |
| 543 |
cand->child_num = 2; |
| 544 |
cand->sense[0] = 'L'; |
| 545 |
cand->sense[1] = 'G'; |
| 546 |
cand->rhs[0] = 0; |
| 547 |
cand->rhs[1] = 1; |
| 548 |
cand->range[0] = cand->range[1] = 0; |
| 549 |
} |
| 550 |
} |
| 551 |
if (j && (branch_rule == DEPOTS_AT_HALF_BRANCH_RIGHT || |
| 552 |
branch_rule == DEPOTS_AT_HALF)){ |
| 553 |
*cand_num = j; |
| 554 |
break; |
| 555 |
} |
| 556 |
for (k = 0; k < i && j < cand_num; k++){ |
| 557 |
if (vrp->edges[(vars[sorted_cand_list[k]]->userind) << 1] != 0) |
| 558 |
cand = candidates[j++] = (branch_obj *) |
| 559 |
calloc(1, sizeof(branch_obj)); |
| 560 |
cand->position = sorted_cand_list[i]; |
| 561 |
cand->type = CANDIDATE_VARIABLE; |
| 562 |
cand->child_num = 2; |
| 563 |
cand->sense[0] = 'L'; |
| 564 |
cand->sense[1] = 'G'; |
| 565 |
cand->rhs[0] = 0; |
| 566 |
cand->rhs[1] = 1; |
| 567 |
cand->range[0] = cand->range[1] = 0; |
| 568 |
} |
| 569 |
if (j){ |
| 570 |
*cand_num = j; |
| 571 |
break; |
| 572 |
} |
| 573 |
/*otherwise, fall through*/ |
| 574 |
|
| 575 |
case DEPOTS_CLOSEST_TO_HALF: |
| 576 |
case DEPOTS_CLOSEST_TO_HALF_BRANCH_RIGHT: |
| 577 |
case VARS_CLOSEST_TO_HALF_PREFER_DEPOT: |
| 578 |
case VARS_CLOSEST_TO_HALF_PREFER_DEPOT_BRANCH_RIGHT: |
| 579 |
|
| 580 |
for (i = 0, j = 0; |
| 581 |
i < varnum && sorted_diffs[i]<.5-lpetol && j < cand_num; i++){ |
| 582 |
if (vrp->edges[(vars[sorted_cand_list[i]]->userind) << 1] == 0){ |
| 583 |
cand = candidates[j++] = (branch_obj *) |
| 584 |
calloc(1, sizeof(branch_obj)); |
| 585 |
cand->position = sorted_cand_list[i]; |
| 586 |
cand->type = CANDIDATE_VARIABLE; |
| 587 |
cand->child_num = 2; |
| 588 |
cand->sense[0] = 'L'; |
| 589 |
cand->sense[1] = 'G'; |
| 590 |
cand->rhs[0] = 0; |
| 591 |
cand->rhs[1] = 1; |
| 592 |
cand->range[0] = cand->range[1] = 0; |
| 593 |
} |
| 594 |
} |
| 595 |
if (j && (branch_rule == DEPOTS_CLOSEST_TO_HALF || |
| 596 |
branch_rule == DEPOTS_CLOSEST_TO_HALF_BRANCH_RIGHT)){ |
| 597 |
*cand_num = j; |
| 598 |
break; |
| 599 |
} |
| 600 |
for (k = 0; k < i && j < cand_num; k++){ |
| 601 |
cand = candidates[j++] = (branch_obj *)calloc(1, sizeof(branch_obj)); |
| 602 |
cand->position = sorted_cand_list[i]; |
| 603 |
cand->type = CANDIDATE_VARIABLE; |
| 604 |
cand->child_num = 2; |
| 605 |
cand->sense[0] = 'L'; |
| 606 |
cand->sense[1] = 'G'; |
| 607 |
cand->rhs[0] = 0; |
| 608 |
cand->rhs[1] = 1; |
| 609 |
cand->range[0] = cand->range[1] = 0; |
| 610 |
} |
| 611 |
|
| 612 |
if (j){ |
| 613 |
*cand_num = j; |
| 614 |
break; |
| 615 |
} |
| 616 |
/*otherwise, fall through*/ |
| 617 |
|
| 618 |
case VARS_CLOSEST_TO_HALF: |
| 619 |
|
| 620 |
for (i = 0, j = 0; |
| 621 |
sorted_diffs[i]<.5-lpetol && i < varnum && j < cand_num; i++){ |
| 622 |
cand = candidates[j++] = (branch_obj *)calloc(1, sizeof(branch_obj)); |
| 623 |
cand->position = sorted_cand_list[i]; |
| 624 |
cand->type = CANDIDATE_VARIABLE; |
| 625 |
cand->child_num = 2; |
| 626 |
cand->sense[0] = 'L'; |
| 627 |
cand->sense[1] = 'G'; |
| 628 |
cand->rhs[0] = 0; |
| 629 |
cand->rhs[1] = 1; |
| 630 |
cand->range[0] = cand->range[1] = 0; |
| 631 |
} |
| 632 |
if (j){ |
| 633 |
*cand_num = j; |
| 634 |
break; |
| 635 |
} |
| 636 |
/*otherwise, fall through*/ |
| 637 |
|
| 638 |
case BEST_K: |
| 639 |
#if 0 |
| 640 |
for (i = 0, j = 0; i < varnum && j < cand_num; i++){ |
| 641 |
if (p->lp_data->fixed[sorted_cand_list[i]] == NOT_FIXED){ |
| 642 |
cand = candidates[j++] = (branch_obj *) |
| 643 |
calloc(1, sizeof(branch_obj)); |
| 644 |
cand->position = sorted_cand_list[i]; |
| 645 |
cand->type = CANDIDATE_VARIABLE; |
| 646 |
cand->child_num = 2; |
| 647 |
cand->sense[0] = 'L'; |
| 648 |
cand->sense[1] = 'G'; |
| 649 |
cand->rhs[0] = 0; |
| 650 |
cand->rhs[1] = 1; |
| 651 |
cand->range[0] = cand->range[1] = 0; |
| 652 |
} |
| 653 |
} |
| 654 |
|
| 655 |
*cand_num = j; |
| 656 |
break; |
| 657 |
#endif |
| 658 |
*cand_num = 0; |
| 659 |
break; |
| 660 |
|
| 661 |
case VARS_AT_HALF: |
| 662 |
|
| 663 |
for (j = 0; sorted_diffs[j] < lpetol && j < cand_num; j++){ |
| 664 |
cand = candidates[j++] = (branch_obj *)calloc(1, sizeof(branch_obj)); |
| 665 |
cand->position = sorted_cand_list[i]; |
| 666 |
cand->type = CANDIDATE_VARIABLE; |
| 667 |
cand->child_num = 2; |
| 668 |
cand->sense[0] = 'L'; |
| 669 |
cand->sense[1] = 'G'; |
| 670 |
cand->rhs[0] = 0; |
| 671 |
cand->rhs[1] = 1; |
| 672 |
cand->range[0] = cand->range[1] = 0; |
| 673 |
} |
| 674 |
|
| 675 |
*cand_num = j; |
| 676 |
break; |
| 677 |
|
| 678 |
default: |
| 679 |
FREE(sorted_cand_list); |
| 680 |
FREE(sorted_diffs); |
| 681 |
return(DEFAULT); |
| 682 |
} |
| 683 |
FREE(sorted_cand_list); |
| 684 |
FREE(sorted_diffs); |
| 685 |
|
| 686 |
return(USER_SUCCESS); |
| 687 |
} |
| 688 |
#endif |
| 689 |
|
| 690 |
/*___END_EXPERIMENTAL_SECTION___*/ |
| 691 |
/*===========================================================================*/ |
| 692 |
|
| 693 |
/*===========================================================================*\ |
| 694 |
* I wrote my own function to compare candidates. Maybe this should go |
| 695 |
* into SYMPHONY. |
| 696 |
\*===========================================================================*/ |
| 697 |
|
| 698 |
int user_compare_candidates(void *user, branch_obj *can1, branch_obj *can2, |
| 699 |
double ub, double granularity, |
| 700 |
int *which_is_better) |
| 701 |
{ |
| 702 |
int i, j; |
| 703 |
double low1, low2; |
| 704 |
|
| 705 |
for (i = 1; i >= 0; i--) |
| 706 |
if (can1->termcode[i]==LP_OPT_FEASIBLE || can1->termcode[i]==LP_D_OBJLIM || |
| 707 |
can1->termcode[i]==LP_D_UNBOUNDED || can1->objval[i] > ub - |
| 708 |
granularity) |
| 709 |
break; |
| 710 |
|
| 711 |
for (j = 1; j >= 0; j--) |
| 712 |
if (can2->termcode[j]==LP_OPT_FEASIBLE || can2->termcode[j]==LP_D_OBJLIM || |
| 713 |
can2->termcode[j] == LP_D_UNBOUNDED || can2->objval[j] > ub - |
| 714 |
granularity) |
| 715 |
break; |
| 716 |
|
| 717 |
if (i < 0 && j < 0) |
| 718 |
return(USER_DEFAULT); |
| 719 |
|
| 720 |
if (i < 0 && j > 0){ |
| 721 |
*which_is_better = SECOND_CANDIDATE_BETTER; |
| 722 |
return(USER_SUCCESS); |
| 723 |
} |
| 724 |
|
| 725 |
if (i > 0 && j < 0){ |
| 726 |
*which_is_better = FIRST_CANDIDATE_BETTER; |
| 727 |
return(USER_SUCCESS); |
| 728 |
} |
| 729 |
|
| 730 |
low1 = i ? can1->objval[0] : can1->objval[1]; |
| 731 |
low2 = j ? can2->objval[0] : can2->objval[1]; |
| 732 |
|
| 733 |
*which_is_better = low1 > low2 ? FIRST_CANDIDATE_BETTER : |
| 734 |
SECOND_CANDIDATE_BETTER; |
| 735 |
|
| 736 |
return(USER_SUCCESS); |
| 737 |
} |
| 738 |
|
| 739 |
/*===========================================================================*/ |
| 740 |
|
| 741 |
/*===========================================================================*\ |
| 742 |
* You can let SYMPHONY choose which child to retain. The default is |
| 743 |
* to keep the one with the lower objective function value. |
| 744 |
\*===========================================================================*/ |
| 745 |
|
| 746 |
int user_select_child(void *user, double ub, branch_obj *can, char *action) |
| 747 |
{ |
| 748 |
return(USER_DEFAULT); |
| 749 |
} |
| 750 |
|
| 751 |
/*===========================================================================*/ |
| 752 |
|
| 753 |
/*===========================================================================*\ |
| 754 |
* Here, you can print out a more identifiable description of the |
| 755 |
* branching object than just "variable 51". I print out the end points |
| 756 |
* of the edge if an edge is branched on. |
| 757 |
\*===========================================================================*/ |
| 758 |
|
| 759 |
int user_print_branch_stat(void *user, branch_obj *can, cut_data *cut, |
| 760 |
int n, var_desc **vars, char *action) |
| 761 |
{ |
| 762 |
int v0, v1, i; |
| 763 |
char *coef; |
| 764 |
|
| 765 |
if (cut){ |
| 766 |
switch(cut->type){ |
| 767 |
case SUBTOUR_ELIM_SIDE: |
| 768 |
coef = (char *)(cut->coef); |
| 769 |
for (i = 0; i < n; i++){ |
| 770 |
BOTH_ENDS(vars[i]->userind, &v1, &v0); |
| 771 |
if (coef[v0 >> DELETE_POWER] & (1 << (v0 & DELETE_AND)) && |
| 772 |
(coef[v1 >> DELETE_POWER]) & (1 << (v1 & DELETE_AND))) |
| 773 |
printf("Edge (%i, %i)\n", v0, v1); |
| 774 |
} |
| 775 |
|
| 776 |
case SUBTOUR_ELIM_ACROSS: |
| 777 |
coef = (char *)(cut->coef); |
| 778 |
for (i = 0; i < n; i++){ |
| 779 |
BOTH_ENDS(vars[i]->userind, &v1, &v0); |
| 780 |
if ((coef[v0 >> DELETE_POWER] >> (v0 & DELETE_AND) & 1) ^ |
| 781 |
(coef[v1 >> DELETE_POWER] >> (v1 & DELETE_AND) & 1)) |
| 782 |
printf("Edge (%i, %i)\n", v0, v1); |
| 783 |
} |
| 784 |
} |
| 785 |
}else{ |
| 786 |
BOTH_ENDS(vars[can->position]->userind, &v1, &v0); |
| 787 |
printf("Edge (%i, %i)\n", v0, v1); |
| 788 |
} |
| 789 |
|
| 790 |
return(USER_SUCCESS); |
| 791 |
} |