/*===========================================================================*/ /* */ /* This file is part of a demonstration application for use with the */ /* SYMPHONY Branch, Cut, and Price Library. This application is a solver for */ /* the Vehicle Routing Problem and the Traveling Salesman Problem. */ /* */ /* (c) Copyright 2000-2007 Ted Ralphs. All Rights Reserved. */ /* */ /* This application was developed by Ted Ralphs (ted@lehigh.edu) */ /* */ /* This software is licensed under the Eclipse Public License. Please see */ /* accompanying file for terms. */ /* */ /*===========================================================================*/ #define COMPILING_FOR_LP /* system include files */ #include #include #include /* SYMPHONY include files */ #include "sym_constants.h" #include "sym_macros.h" #include "sym_qsort.h" #include "sym_lp_u.h" /*__BEGIN_EXPERIMENTAL_SECTION__*/ #include "sym_lp.h" /*___END_EXPERIMENTAL_SECTION___*/ /* VRP include files */ #include "vrp_lp.h" #include "vrp_macros.h" #include "vrp_const.h" #include "sym_timemeas.h" /*===========================================================================*/ /*===========================================================================*\ * This file contains the user-written functions for the LP process related * to branching. \*===========================================================================*/ /*===========================================================================*\ * This function determines whether to branch. You can eseentially * leave this up to SYMPHONY unless there is some compelling reason not to. \*===========================================================================*/ int user_shall_we_branch(void *user, double lpetol, int cutnum, int slacks_in_matrix_num, cut_data **slacks_im_matrix, int slack_cut_num, cut_data **slack_cuts, int varnum, var_desc **vars, double *x, char *status, int *cand_num, branch_obj ***candidates, int *action) { int i; double fracx, lpetol1 = 1 - lpetol; for (i = varnum - 1; i >= 0; i--){ if (vars[i]->is_int){ fracx = x[i] - floor(x[i]); if (fracx > lpetol && fracx < lpetol1){ break; } } } if(i >= 0 ){ *action = USER__BRANCH_IF_TAILOFF; } else{ *action = USER__BRANCH_IF_MUST; } #if 0 vrp_lp_problem *vrp = (vrp_lp_problem *) user; if (!vrp->par.detect_tailoff){ *action = USER__BRANCH_IF_MUST; }else{ *action = USER__BRANCH_IF_TAILOFF; } #endif return(USER_SUCCESS); } /*===========================================================================*/ /*===========================================================================*\ * Here, we select the branching candidates. This can essentially be * left to SYMPHONY too using one of the built-in functions, but here, I * demonstrate how to branch on cuts, which must be done by the user. \*===========================================================================*/ int user_select_candidates(void *user, double lpetol, int cutnum, int slacks_in_matrix_num, cut_data **slacks_in_matrix, int slack_cut_num, cut_data **slack_cuts, int varnum, var_desc **vars, double *x, char *status, int *cand_num, branch_obj ***candidates, int *action, int bc_level) { vrp_lp_problem *vrp = (vrp_lp_problem *)user; cut_data *cut; branch_obj **cand_list, *can; int i, candnum, found_violated = FALSE; p_w_l *pwl; double left_hand_side, lpetol1 = 1 - lpetol, lpetol5=.95, slack, fracx; waiting_row **new_rows; int new_row_num; int *userind; int sim_cand_num = 0, sc_cand_num = 0; /* numbers of slacks_in_matrix, slack_cuts and variables, that are used as branching cands */ if (!vrp->par.branch_on_cuts && vrp->par.branching_rule == 2) /* use the built-in rule */ return(USER_DEFAULT); *cand_num = 0; candnum = 0; /* allocate also memory for the basic vars */ *candidates = cand_list = (branch_obj **) malloc((varnum + (vrp->par.branch_on_cuts ? (slacks_in_matrix_num + slack_cut_num) : 0)) * sizeof(branch_obj *)); switch (vrp->par.branch_on_cuts){ case TRUE: pwl = (p_w_l *) malloc((slacks_in_matrix_num + slack_cut_num)* sizeof(p_w_l)); userind = (int *) malloc(varnum*ISIZE); for (i = varnum - 1; i >= 0; i--) userind[i] = vars[i]->userind; /* First go through the slack cuts and enlist the violated ones */ for (i = 0; i < slack_cut_num; i++){ left_hand_side = compute_lhs(varnum, userind, x, cut = slack_cuts[i], vrp->vertnum); switch (cut->type){ case SUBTOUR_ELIM_SIDE: slack = cut->rhs - left_hand_side; if (slack < -lpetol){/*---------------- This cut became violated */ found_violated = TRUE; can = cand_list[candnum++] = (branch_obj *) calloc(1, sizeof(branch_obj)); can->type = VIOLATED_SLACK; can->position = i; }else if ((!found_violated) && (slack>lpetol) && !(cut->sense == 'R' || cut->sense == 'E')){ pwl[sc_cand_num].lhs = left_hand_side; pwl[sc_cand_num++].position = i; } break; case SUBTOUR_ELIM_ACROSS: slack = left_hand_side - cut->rhs; if (slack < -lpetol){/*---------------- This cut became violated */ found_violated = TRUE; can = cand_list[candnum++] = (branch_obj *) calloc(1, sizeof(branch_obj)); can->type = VIOLATED_SLACK; can->position = i; }else if ((!found_violated) && (slack>lpetol) && !(cut->sense=='R' || cut->sense=='E')){ pwl[sc_cand_num].lhs = left_hand_side; pwl[sc_cand_num++].position = i; } break; default: break; } } if (found_violated){ *cand_num = candnum; FREE(pwl); *action = USER__DO_NOT_BRANCH; return(USER_SUCCESS); } /* now go through the slack rows in the matrix and add the potential candidates to the end of the pos/weight lists */ for (i = 0; i < slacks_in_matrix_num; i++) if ((cut = slacks_in_matrix[i]) && (cut->type==SUBTOUR_ELIM_SIDE || cut->type== SUBTOUR_ELIM_ACROSS) && !(cut->sense=='R' || cut->sense=='E')){ left_hand_side = compute_lhs(varnum, userind, x, cut, vrp->vertnum); switch (cut->type){ case SUBTOUR_ELIM_SIDE: slack = cut->rhs - left_hand_side; /* if (slack > lpetol && slack < lpetol1){*/ if (slack > lpetol ){ pwl[sc_cand_num+sim_cand_num].lhs = left_hand_side; pwl[sc_cand_num+sim_cand_num].position = i; sim_cand_num++; } break; case SUBTOUR_ELIM_ACROSS: slack = left_hand_side - cut->rhs; /* if (slack > lpetol && slack < 2-lpetol){*/ if (slack > lpetol ){ pwl[sc_cand_num+sim_cand_num].lhs = left_hand_side; pwl[sc_cand_num+sim_cand_num].position = i; sim_cand_num++; } break; default: break; } } /* set the children's rhs etc */ for (i = 0 ; i < sc_cand_num + sim_cand_num; i++){ can = cand_list[candnum++] = (branch_obj *) calloc(1, sizeof(branch_obj)); if (i < sc_cand_num ){ can->type = CANDIDATE_CUT_NOT_IN_MATRIX; cut = slack_cuts[can->position = pwl[i].position ]; user_unpack_cuts(user, CUT_NOT_IN_MATRIX_SLACK, UNPACK_CUTS_SINGLE, varnum, vars, 1, slack_cuts+can->position, &new_row_num, &new_rows); can->row = *new_rows; cut = can->row->cut; FREE(new_rows); }else{ can->type = CANDIDATE_CUT_IN_MATRIX; cut = slacks_in_matrix[can->position = pwl[i].position ]; } can->child_num = 2; can->lhs = pwl[i].lhs; /* no need to allocate these. they are of fixed length can->sense = (char *) malloc(2 * CSIZE); can->rhs = (double *) malloc(2 * DSIZE); can->range = (double *) malloc(2 * DSIZE); */ switch (cut->type){ case SUBTOUR_ELIM_SIDE: if ((slack = cut->rhs - can->lhs) < lpetol1){ can->sense[0] = 'E'; can->rhs[0] = cut->rhs; can->range[0] = 0; can->branch[0] = DO_NOT_BRANCH_ON_THIS_ROW; can->sense[1] = 'L'; can->rhs[1] = cut->rhs - 1; can->range[1] = 0; can->branch[1] = ALLOWED_TO_BRANCH_ON; }else{ can->sense[0] = 'R'; can->rhs[0] = cut->rhs; can->range[0] = -floor(slack) ; can->branch[0] = DO_NOT_BRANCH_ON_THIS_ROW; can->sense[1] = 'L'; can->rhs[1] = cut->rhs - ceil(slack); can->range[1] = 0; can->branch[1] = ALLOWED_TO_BRANCH_ON; } break; case SUBTOUR_ELIM_ACROSS: if ((slack = can->lhs - cut->rhs) < 2-lpetol){ can->sense[0] = 'E'; can->rhs[0] = cut->rhs; can->range[0] = 0; can->branch[0] = DO_NOT_BRANCH_ON_THIS_ROW; can->sense[1] = 'G'; can->rhs[1] = cut->rhs + 2; can->range[1] = 0; can->branch[1] = ALLOWED_TO_BRANCH_ON; }else{ can->sense[0] = 'R'; can->rhs[0] = cut->rhs; can->range[0] = 2*floor(slack/2); can->branch[0] = DO_NOT_BRANCH_ON_THIS_ROW; can->sense[1] = 'G'; can->rhs[1] = cut->rhs + 2*floor(slack/2) +2; can->range[1] = 0; can->branch[1] = ALLOWED_TO_BRANCH_ON; } break; /*__BEGIN_EXPERIMENTAL_SECTION__*/ case FARKAS: break; case NO_COLUMNS: break; /*___END_EXPERIMENTAL_SECTION___*/ } } FREE(pwl); FREE(userind); *cand_num = candnum; cand_list = *candidates + *cand_num; case FALSE: switch (((vrp_lp_problem *)user)->par.branching_rule){ case 0: { int *xind = (int *) malloc(varnum*ISIZE); double *xval = (double *) malloc(varnum*DSIZE); int cnt = 0; for (i = varnum-1; i >= 0; i--){ fracx = x[i] - floor(x[i]); if (fracx > lpetol && fracx < 1-lpetol){ xind[cnt] = i; xval[cnt++] = fabs(fracx - .5); } } qsort_di(xval, xind, cnt); candnum = vrp->par.strong_branching_cand_num_max - vrp->par.strong_branching_red_ratio * bc_level; candnum = MAX(candnum, vrp->par.strong_branching_cand_num_min); candnum = MIN(candnum, cnt); for (i = candnum-1; i >= 0; i--){ can=cand_list[i]=(branch_obj *) calloc(1, sizeof(branch_obj)); can->type = CANDIDATE_VARIABLE; can->child_num = 2; can->position = xind[i]; can->sense[0] = 'L'; can->sense[1] = 'G'; can->rhs[0] = floor(x[xind[i]]); can->rhs[1] = can->rhs[0] + 1; can->range[0] = can->range[1] = 0; } FREE(xind); FREE(xval); } break; case 1: candnum = 0; for (i = varnum-1; i >= 0; i--){ fracx = x[i] - floor(x[i]); if (fracx > lpetol && fracx < lpetol5){ can = cand_list[candnum++] = (branch_obj *) calloc(1, sizeof(branch_obj)); can->type = CANDIDATE_VARIABLE; can->child_num = 2; can->position = i; can->sense[0] = 'L'; can->sense[1] = 'G'; can->rhs[0] = floor(x[i]); can->rhs[1] = can->rhs[0] + 1; can->range[0] = can->range[1] = 0; } } break; case 2: return(USER__CLOSE_TO_HALF); } *cand_num += candnum; *action = USER__DO_BRANCH; } return(USER_SUCCESS); } /*===========================================================================*/ double compute_lhs(int number, int *indices, double *values, cut_data *cut, int vertnum) { char *coef; int v0, v1; double lhs = 0; int i; /*__BEGIN_EXPERIMENTAL_SECTION__*/ int num_arcs, edge_index ; char *cpt; int *arcs ; char *indicators; double bigM, *weights ; int jj; /*___END_EXPERIMENTAL_SECTION___*/ switch (cut->type){ case SUBTOUR_ELIM_SIDE: coef = (char *)(cut->coef); for (i = 0, lhs = 0; i> DELETE_POWER] & (1 << (v0 & DELETE_AND)) && (coef[v1 >> DELETE_POWER]) & (1 << (v1 & DELETE_AND))) lhs += values[i]; } return(lhs); case SUBTOUR_ELIM_ACROSS: coef = (char *)(cut->coef); for (lhs = 0, i = 0; i> DELETE_POWER] >> (v0 & DELETE_AND) & 1) ^ (coef[v1 >> DELETE_POWER] >> (v1 & DELETE_AND) & 1)) lhs += values[i]; } return(lhs); /*__BEGIN_EXPERIMENTAL_SECTION__*/ case FARKAS: coef = (char *)(cut->coef); arcs = (int *) calloc( ((vertnum*vertnum)/2), sizeof(int)); weights = (double *) calloc( ((vertnum*vertnum)/2), sizeof(double)) ; cpt=coef+ ((vertnum >> DELETE_POWER) + 1); memcpy((char *)&num_arcs, cpt, ISIZE); memcpy((char *)arcs, cpt, ISIZE*(num_arcs +1)); arcs++; cpt+=(ISIZE*(num_arcs +1))/CSIZE; memcpy((char *)weights, cpt, DSIZE*(num_arcs +1)); bigM=(*(double *)weights); weights++; for (i = 0, lhs=0 ; icoef); arcs = (int *) malloc( ((vertnum*vertnum)/2)* sizeof(int)); indicators = (char *) malloc( ((vertnum*vertnum)/2)* sizeof(char)); cpt=coef+ ((vertnum >> DELETE_POWER) + 1); memcpy((char *)&num_arcs, cpt, ISIZE); cpt+= ISIZE /CSIZE; memcpy((char *)arcs, cpt, ISIZE*(num_arcs)); cpt+=(ISIZE*(num_arcs ))/CSIZE; memcpy((char *)indicators, cpt, CSIZE*(num_arcs)); for (i = 0, lhs=0 ; ipar.max_branch_cand; int branch_rule = vrp->par.branching_rule; branch_obj **candidates, *cand; candidates = *candidates = (branch_obj **) malloc(cand_num * sizeof(branch_obj *)); sorted_cand_list = (int *) calloc (varnum, sizeof(int)); sorted_diffs = (double *) calloc (varnum, sizeof(double)); for (i = 0; i < varnum; i++){ sorted_cand_list[i] = i; sorted_diffs[i] = fabs(x[i] - .5); } cand_sort(sorted_cand_list, sorted_diffs, varnum); switch(vrp->par.branching_rule){ /* which branching rule to use */ case DEPOTS_AT_HALF_BRANCH_RIGHT: case DEPOTS_AT_HALF: case VARS_AT_HALF_PREFER_DEPOT_BRANCH_RIGHT: case VARS_AT_HALF_PREFER_DEPOT: for (i=0, j=0; sorted_diffs[i]edges[(vars[sorted_cand_list[i]]->userind) << 1] == 0){ /* This userind serves the purpose of checking whether the variable corresponds to an edge connected to the depot */ cand = candidates[i] = (branch_obj *)calloc(1, sizeof(branch_obj)); cand->position = sorted_cand_list[i]; cand->type = CANDIDATE_VARIABLE; cand->child_num = 2; cand->sense[0] = 'L'; cand->sense[1] = 'G'; cand->rhs[0] = 0; cand->rhs[1] = 1; cand->range[0] = cand->range[1] = 0; } } if (j && (branch_rule == DEPOTS_AT_HALF_BRANCH_RIGHT || branch_rule == DEPOTS_AT_HALF)){ *cand_num = j; break; } for (k = 0; k < i && j < cand_num; k++){ if (vrp->edges[(vars[sorted_cand_list[k]]->userind) << 1] != 0) cand = candidates[j++] = (branch_obj *) calloc(1, sizeof(branch_obj)); cand->position = sorted_cand_list[i]; cand->type = CANDIDATE_VARIABLE; cand->child_num = 2; cand->sense[0] = 'L'; cand->sense[1] = 'G'; cand->rhs[0] = 0; cand->rhs[1] = 1; cand->range[0] = cand->range[1] = 0; } if (j){ *cand_num = j; break; } /*otherwise, fall through*/ case DEPOTS_CLOSEST_TO_HALF: case DEPOTS_CLOSEST_TO_HALF_BRANCH_RIGHT: case VARS_CLOSEST_TO_HALF_PREFER_DEPOT: case VARS_CLOSEST_TO_HALF_PREFER_DEPOT_BRANCH_RIGHT: for (i = 0, j = 0; i < varnum && sorted_diffs[i]<.5-lpetol && j < cand_num; i++){ if (vrp->edges[(vars[sorted_cand_list[i]]->userind) << 1] == 0){ cand = candidates[j++] = (branch_obj *) calloc(1, sizeof(branch_obj)); cand->position = sorted_cand_list[i]; cand->type = CANDIDATE_VARIABLE; cand->child_num = 2; cand->sense[0] = 'L'; cand->sense[1] = 'G'; cand->rhs[0] = 0; cand->rhs[1] = 1; cand->range[0] = cand->range[1] = 0; } } if (j && (branch_rule == DEPOTS_CLOSEST_TO_HALF || branch_rule == DEPOTS_CLOSEST_TO_HALF_BRANCH_RIGHT)){ *cand_num = j; break; } for (k = 0; k < i && j < cand_num; k++){ cand = candidates[j++] = (branch_obj *)calloc(1, sizeof(branch_obj)); cand->position = sorted_cand_list[i]; cand->type = CANDIDATE_VARIABLE; cand->child_num = 2; cand->sense[0] = 'L'; cand->sense[1] = 'G'; cand->rhs[0] = 0; cand->rhs[1] = 1; cand->range[0] = cand->range[1] = 0; } if (j){ *cand_num = j; break; } /*otherwise, fall through*/ case VARS_CLOSEST_TO_HALF: for (i = 0, j = 0; sorted_diffs[i]<.5-lpetol && i < varnum && j < cand_num; i++){ cand = candidates[j++] = (branch_obj *)calloc(1, sizeof(branch_obj)); cand->position = sorted_cand_list[i]; cand->type = CANDIDATE_VARIABLE; cand->child_num = 2; cand->sense[0] = 'L'; cand->sense[1] = 'G'; cand->rhs[0] = 0; cand->rhs[1] = 1; cand->range[0] = cand->range[1] = 0; } if (j){ *cand_num = j; break; } /*otherwise, fall through*/ case BEST_K: #if 0 for (i = 0, j = 0; i < varnum && j < cand_num; i++){ if (p->lp_data->fixed[sorted_cand_list[i]] == NOT_FIXED){ cand = candidates[j++] = (branch_obj *) calloc(1, sizeof(branch_obj)); cand->position = sorted_cand_list[i]; cand->type = CANDIDATE_VARIABLE; cand->child_num = 2; cand->sense[0] = 'L'; cand->sense[1] = 'G'; cand->rhs[0] = 0; cand->rhs[1] = 1; cand->range[0] = cand->range[1] = 0; } } *cand_num = j; break; #endif *cand_num = 0; break; case VARS_AT_HALF: for (j = 0; sorted_diffs[j] < lpetol && j < cand_num; j++){ cand = candidates[j++] = (branch_obj *)calloc(1, sizeof(branch_obj)); cand->position = sorted_cand_list[i]; cand->type = CANDIDATE_VARIABLE; cand->child_num = 2; cand->sense[0] = 'L'; cand->sense[1] = 'G'; cand->rhs[0] = 0; cand->rhs[1] = 1; cand->range[0] = cand->range[1] = 0; } *cand_num = j; break; default: FREE(sorted_cand_list); FREE(sorted_diffs); return(DEFAULT); } FREE(sorted_cand_list); FREE(sorted_diffs); return(USER_SUCCESS); } #endif /*___END_EXPERIMENTAL_SECTION___*/ /*===========================================================================*/ /*===========================================================================*\ * I wrote my own function to compare candidates. Maybe this should go * into SYMPHONY. \*===========================================================================*/ int user_compare_candidates(void *user, branch_obj *can1, branch_obj *can2, double ub, double granularity, int *which_is_better) { int i, j; double low1, low2; for (i = 1; i >= 0; i--) if (can1->termcode[i]==LP_OPT_FEASIBLE || can1->termcode[i]==LP_D_OBJLIM || can1->termcode[i]==LP_D_UNBOUNDED || can1->objval[i] > ub - granularity) break; for (j = 1; j >= 0; j--) if (can2->termcode[j]==LP_OPT_FEASIBLE || can2->termcode[j]==LP_D_OBJLIM || can2->termcode[j] == LP_D_UNBOUNDED || can2->objval[j] > ub - granularity) break; if (i < 0 && j < 0) return(USER_DEFAULT); if (i < 0 && j > 0){ *which_is_better = SECOND_CANDIDATE_BETTER; return(USER_SUCCESS); } if (i > 0 && j < 0){ *which_is_better = FIRST_CANDIDATE_BETTER; return(USER_SUCCESS); } low1 = i ? can1->objval[0] : can1->objval[1]; low2 = j ? can2->objval[0] : can2->objval[1]; *which_is_better = low1 > low2 ? FIRST_CANDIDATE_BETTER : SECOND_CANDIDATE_BETTER; return(USER_SUCCESS); } /*===========================================================================*/ /*===========================================================================*\ * You can let SYMPHONY choose which child to retain. The default is * to keep the one with the lower objective function value. \*===========================================================================*/ int user_select_child(void *user, double ub, branch_obj *can, char *action) { return(USER_DEFAULT); } /*===========================================================================*/ /*===========================================================================*\ * Here, you can print out a more identifiable description of the * branching object than just "variable 51". I print out the end points * of the edge if an edge is branched on. \*===========================================================================*/ int user_print_branch_stat(void *user, branch_obj *can, cut_data *cut, int n, var_desc **vars, char *action) { int v0, v1, i; char *coef; if (cut){ switch(cut->type){ case SUBTOUR_ELIM_SIDE: coef = (char *)(cut->coef); for (i = 0; i < n; i++){ BOTH_ENDS(vars[i]->userind, &v1, &v0); if (coef[v0 >> DELETE_POWER] & (1 << (v0 & DELETE_AND)) && (coef[v1 >> DELETE_POWER]) & (1 << (v1 & DELETE_AND))) printf("Edge (%i, %i)\n", v0, v1); } case SUBTOUR_ELIM_ACROSS: coef = (char *)(cut->coef); for (i = 0; i < n; i++){ BOTH_ENDS(vars[i]->userind, &v1, &v0); if ((coef[v0 >> DELETE_POWER] >> (v0 & DELETE_AND) & 1) ^ (coef[v1 >> DELETE_POWER] >> (v1 & DELETE_AND) & 1)) printf("Edge (%i, %i)\n", v0, v1); } } }else{ BOTH_ENDS(vars[can->position]->userind, &v1, &v0); printf("Edge (%i, %i)\n", v0, v1); } return(USER_SUCCESS); }