| 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 |
/* system include files */ |
| 17 |
#include <stdio.h> |
| 18 |
#include <stdlib.h> |
| 19 |
/*#include <sys/param.h>*/ |
| 20 |
#include <memory.h> |
| 21 |
#include <math.h> |
| 22 |
|
| 23 |
/* SYMPHONY include files */ |
| 24 |
#include "sym_constants.h" |
| 25 |
#include "sym_macros.h" |
| 26 |
#include "sym_proccomm.h" |
| 27 |
#include "sym_messages.h" |
| 28 |
#include "sym_timemeas.h" |
| 29 |
#include "sym_lp_u.h" |
| 30 |
#include "sym_dg_params.h" |
| 31 |
|
| 32 |
/* VRP include files */ |
| 33 |
#include "vrp_lp.h" |
| 34 |
#include "vrp_dg_functions.h" |
| 35 |
#include "vrp_macros.h" |
| 36 |
#include "vrp_const.h" |
| 37 |
|
| 38 |
/*===========================================================================*/ |
| 39 |
|
| 40 |
/*===========================================================================*\ |
| 41 |
* This file contains the user-written functions for the LP process. |
| 42 |
\*===========================================================================*/ |
| 43 |
|
| 44 |
/*===========================================================================*\ |
| 45 |
* Here is where the user must receive all of the data sent from |
| 46 |
* user_send_lp_data() and set up data structures. Note that this function is |
| 47 |
* only called if one of COMPILE_IN_LP or COMPILE_IN_TM is FALSE. |
| 48 |
\*===========================================================================*/ |
| 49 |
|
| 50 |
int user_receive_lp_data(void **user) |
| 51 |
{ |
| 52 |
vrp_lp_problem *vrp; |
| 53 |
int vertnum; |
| 54 |
int i, j, k, l; |
| 55 |
int total_edgenum; |
| 56 |
int zero_varnum, *zero_vars = NULL; |
| 57 |
|
| 58 |
vrp = (vrp_lp_problem *) calloc (1, sizeof(vrp_lp_problem)); |
| 59 |
|
| 60 |
*user = (void *)vrp; |
| 61 |
|
| 62 |
receive_char_array((char *)(&vrp->par), sizeof(vrp_lp_params)); |
| 63 |
receive_int_array(&vrp->window, 1); |
| 64 |
receive_int_array(&vrp->numroutes, 1); |
| 65 |
receive_int_array(&vrp->vertnum, 1); |
| 66 |
vertnum = vrp->vertnum; |
| 67 |
vrp->demand = (int *) calloc (vertnum, sizeof(int)); |
| 68 |
receive_int_array(vrp->demand, (int)vertnum); |
| 69 |
receive_int_array(&vrp->capacity, 1); |
| 70 |
total_edgenum = vertnum*(vertnum-1)/2; |
| 71 |
vrp->costs = (int *) calloc (total_edgenum, sizeof(int)); |
| 72 |
receive_int_array(vrp->costs, total_edgenum); |
| 73 |
receive_int_array(&zero_varnum, 1); |
| 74 |
if (zero_varnum){ |
| 75 |
zero_vars = (int *) malloc (zero_varnum*sizeof(int)); |
| 76 |
receive_int_array(zero_vars, zero_varnum); |
| 77 |
} |
| 78 |
|
| 79 |
vrp->edges = (int *) calloc (2*total_edgenum, sizeof(int)); |
| 80 |
|
| 81 |
/*create the edge list (we assume a complete graph) The edge is set to |
| 82 |
(0,0) in the edge list if it was eliminated in preprocessing*/ |
| 83 |
for (i = 1, k = 0, l = 0; i < vertnum; i++){ |
| 84 |
for (j = 0; j < i; j++){ |
| 85 |
if (l < zero_varnum && k == zero_vars[l]){ |
| 86 |
/*This is one of the zero edges*/ |
| 87 |
vrp->edges[2*k] = vrp->edges[2*k+1] = 0; |
| 88 |
l++; |
| 89 |
k++; |
| 90 |
continue; |
| 91 |
} |
| 92 |
vrp->edges[2*k] = j; |
| 93 |
vrp->edges[2*k+1] = i; |
| 94 |
k++; |
| 95 |
} |
| 96 |
} |
| 97 |
FREE(zero_vars); |
| 98 |
|
| 99 |
vrp->cur_sol = (_node *) calloc (vrp->vertnum, sizeof(_node)); |
| 100 |
if (vrp->window){ |
| 101 |
copy_node_set(vrp->window, TRUE, (char *)"Original solution"); |
| 102 |
#if 0 |
| 103 |
copy_node_set(vrp->window, TRUE, (char *)"Compressed solution"); |
| 104 |
#endif |
| 105 |
} |
| 106 |
return(USER_SUCCESS); |
| 107 |
} |
| 108 |
|
| 109 |
/*===========================================================================*/ |
| 110 |
|
| 111 |
/*===========================================================================*\ |
| 112 |
* Here is where the user must create the initial LP relaxation for |
| 113 |
* each search node. See the comments below. |
| 114 |
\*===========================================================================*/ |
| 115 |
|
| 116 |
int user_create_subproblem(void *user, int *indices, MIPdesc *mip, |
| 117 |
int *maxn, int *maxm, int *maxnz) |
| 118 |
{ |
| 119 |
vrp_lp_problem *vrp = (vrp_lp_problem *)user; |
| 120 |
int *costs = vrp->costs; |
| 121 |
int *edges = vrp->edges; |
| 122 |
int i; |
| 123 |
int total_edgenum = vrp->vertnum*(vrp->vertnum-1)/2; |
| 124 |
int cap_check = vrp->capacity*(vrp->numroutes-1); |
| 125 |
int total_demand = vrp->demand[0]; |
| 126 |
|
| 127 |
/* set up the inital LP data */ |
| 128 |
|
| 129 |
/* Our base constraints are that the sum of the weights of the |
| 130 |
edges adjacent to each node (except the depot) is 2. This means |
| 131 |
that each column will have exactly two nonzeros, one in each of |
| 132 |
the rows corresponding to its end points. Hence the total |
| 133 |
nonzeros is 2*n (n is the number of active variables). */ |
| 134 |
mip->nz = 2 * mip->n; |
| 135 |
|
| 136 |
/* Estimate the maximum number of nonzeros (not needed, but helpful for |
| 137 |
efficiency*/ |
| 138 |
*maxm = 2 * mip->m; |
| 139 |
*maxn = total_edgenum; |
| 140 |
*maxnz = mip->nz + ((*maxm) * (*maxn) / 10); |
| 141 |
|
| 142 |
/* Allocate the arrays. These are owned by SYMPHONY after returning. */ |
| 143 |
mip->matbeg = (int *) malloc((mip->n + 1) * ISIZE); |
| 144 |
mip->matind = (int *) malloc((mip->nz) * ISIZE); |
| 145 |
mip->matval = (double *) malloc((mip->nz) * DSIZE); |
| 146 |
mip->obj = (double *) malloc(mip->n * DSIZE); |
| 147 |
mip->ub = (double *) malloc(mip->n * DSIZE); |
| 148 |
mip->lb = (double *) calloc(mip->n, DSIZE); /* zero lower bounds */ |
| 149 |
mip->rhs = (double *) malloc(mip->m * DSIZE); |
| 150 |
mip->sense = (char *) malloc(mip->m * CSIZE); |
| 151 |
mip->rngval = (double *) calloc(mip->m, DSIZE); |
| 152 |
mip->is_int = (char *) calloc(mip->n, CSIZE); |
| 153 |
|
| 154 |
/* Fill out the appropriate data structures -- each column has |
| 155 |
exactly two entries */ |
| 156 |
for (i = 0; i < mip->n; i++){ |
| 157 |
mip->obj[i] = (double) costs[indices[i]]; |
| 158 |
mip->matbeg[i] = 2*i; |
| 159 |
mip->matval[2*i] = 1.0; |
| 160 |
mip->matval[2*i+1] = 1.0; |
| 161 |
mip->matind[2*i] = edges[2*indices[i]]; |
| 162 |
mip->matind[2*i+1] = edges[2*indices[i] + 1]; |
| 163 |
mip->is_int[i] = TRUE; |
| 164 |
|
| 165 |
/* Set the upper and lower bounds */ |
| 166 |
if (edges[indices[i] << 1] == 0){ |
| 167 |
/*This is a depot edge and we have to check what its ub should be*/ |
| 168 |
/*Recall vrp->demand[0] == total_demand*/ |
| 169 |
if (total_demand - vrp->demand[edges[(indices[i] << 1) + 1]] > |
| 170 |
cap_check) |
| 171 |
/*in this case, the node cannot be on its own route*/ |
| 172 |
mip->ub[i] = 1; |
| 173 |
else |
| 174 |
mip->ub[i] = 2; |
| 175 |
}else{ |
| 176 |
mip->ub[i] = 1; |
| 177 |
} |
| 178 |
} |
| 179 |
mip->matbeg[mip->n] = 2*mip->n; |
| 180 |
|
| 181 |
/* set the initial right hand side */ |
| 182 |
mip->rhs[0] = 2*vrp->numroutes; |
| 183 |
mip->sense[0] = 'E'; |
| 184 |
for (i = vrp->vertnum - 1; i > 0; i--){ |
| 185 |
mip->rhs[i] = (double) 2; |
| 186 |
mip->sense[i] = 'E'; |
| 187 |
} |
| 188 |
|
| 189 |
return(USER_SUCCESS); |
| 190 |
} |
| 191 |
|
| 192 |
|
| 193 |
/*===========================================================================*/ |
| 194 |
|
| 195 |
/*===========================================================================*\ |
| 196 |
* This function takes an LP solution and checks it for feasibility. |
| 197 |
* In our case, that means (1) it is integral (2) it is connected, and |
| 198 |
* (3) the routes obey the capacity constraints. |
| 199 |
\*===========================================================================*/ |
| 200 |
|
| 201 |
int user_is_feasible(void *user, double lpetol, int varnum, int *indices, |
| 202 |
double *values, int *feasible, double *true_objval, |
| 203 |
char branching, double *heur_solution) |
| 204 |
{ |
| 205 |
vrp_lp_problem *vrp = (vrp_lp_problem *)user; |
| 206 |
vertex *verts; |
| 207 |
int *demand = vrp->demand, capacity = vrp->capacity; |
| 208 |
int rcnt, *compnodes, *compdemands; |
| 209 |
int vertnum = vrp->vertnum, i; |
| 210 |
network *n; |
| 211 |
double *compcuts; |
| 212 |
|
| 213 |
n = createnet(indices, values, varnum, lpetol, vrp->edges, demand, vertnum); |
| 214 |
|
| 215 |
if (!n->is_integral){ |
| 216 |
*feasible = IP_INFEASIBLE; |
| 217 |
free_net(n); |
| 218 |
return(USER_SUCCESS); |
| 219 |
} |
| 220 |
|
| 221 |
verts = n->verts; |
| 222 |
compnodes = (int *) calloc (vertnum + 1, sizeof(int)); |
| 223 |
compdemands = (int *) calloc (vertnum + 1, sizeof(int)); |
| 224 |
compcuts = (double *) calloc (vertnum + 1, sizeof(double)); |
| 225 |
/*get the components of the solution graph without the depot to check if the |
| 226 |
graph is connected or not*/ |
| 227 |
rcnt = connected(n, compnodes, compdemands, NULL, compcuts, NULL); |
| 228 |
|
| 229 |
/*------------------------------------------------------------------------*\ |
| 230 |
* For each component check to see if the cut it induces is nonzero -- each |
| 231 |
* component's cut value must be either 0 or 2 since we have integrality |
| 232 |
\*------------------------------------------------------------------------*/ |
| 233 |
|
| 234 |
for (i = 0; i<rcnt; i++){ |
| 235 |
if (compcuts[i+1] < lpetol || compdemands[i+1] > capacity){ |
| 236 |
*feasible = IP_INFEASIBLE; |
| 237 |
FREE(compnodes); |
| 238 |
FREE(compdemands); |
| 239 |
FREE(compcuts); |
| 240 |
free_net(n); |
| 241 |
return(USER_SUCCESS); |
| 242 |
} |
| 243 |
} |
| 244 |
|
| 245 |
FREE(compnodes); |
| 246 |
FREE(compdemands); |
| 247 |
FREE(compcuts); |
| 248 |
|
| 249 |
*feasible = IP_FEASIBLE; |
| 250 |
|
| 251 |
construct_feasible_solution(vrp, n, true_objval); |
| 252 |
|
| 253 |
free_net(n); |
| 254 |
|
| 255 |
return(USER_SUCCESS); |
| 256 |
} |
| 257 |
|
| 258 |
/*===========================================================================*/ |
| 259 |
|
| 260 |
/*===========================================================================*\ |
| 261 |
* In my case, a feasible solution is specified most compactly by |
| 262 |
* essentially a permutation of the customers along with routes numbers, |
| 263 |
* specifying the order of the customers on their routes. This is just |
| 264 |
* sent as a character array which then gets cast to an array of |
| 265 |
* structures, one for each customers specifying the route number and |
| 266 |
* the next customer on the route. |
| 267 |
\*===========================================================================*/ |
| 268 |
|
| 269 |
int user_send_feasible_solution(void *user, double lpetol, int varnum, |
| 270 |
int *indices, double *values) |
| 271 |
{ |
| 272 |
vrp_lp_problem *vrp = (vrp_lp_problem *)user; |
| 273 |
|
| 274 |
send_char_array((char *)vrp->cur_sol, vrp->vertnum*sizeof(_node)); |
| 275 |
|
| 276 |
return(USER_SUCCESS); |
| 277 |
} |
| 278 |
|
| 279 |
|
| 280 |
/*===========================================================================*/ |
| 281 |
|
| 282 |
/*===========================================================================*\ |
| 283 |
* This function graphically displays the current fractional solution |
| 284 |
* This is done using the Interactie Graph Drawing program. |
| 285 |
\*===========================================================================*/ |
| 286 |
|
| 287 |
int user_display_lp_solution(void *user, int which_sol, int varnum, |
| 288 |
int *indices, double *values) |
| 289 |
{ |
| 290 |
vrp_lp_problem *vrp = (vrp_lp_problem *)user; |
| 291 |
|
| 292 |
if (vrp->par.verbosity > 10 || |
| 293 |
(vrp->par.verbosity > 8 && (which_sol == DISP_FINAL_RELAXED_SOLUTION)) || |
| 294 |
(vrp->par.verbosity > 6 && (which_sol == DISP_FEAS_SOLUTION))){ |
| 295 |
display_support_graph(vrp->window, FALSE, (char *)"Original solution", |
| 296 |
varnum, indices, values, .000001, |
| 297 |
CTOI_WAIT_FOR_CLICK_AND_REPORT); |
| 298 |
#if 0 |
| 299 |
display_compressed_support_graph(vrp->window, FALSE, |
| 300 |
(char *)"Compressed solution", |
| 301 |
varnum, indices, values, |
| 302 |
CTOI_WAIT_FOR_CLICK_AND_REPORT); |
| 303 |
#endif |
| 304 |
} |
| 305 |
|
| 306 |
if (which_sol == DISP_FINAL_RELAXED_SOLUTION){ |
| 307 |
return(DISP_NZ_INT); |
| 308 |
}else{ |
| 309 |
return(USER_SUCCESS); |
| 310 |
} |
| 311 |
} |
| 312 |
|
| 313 |
/*===========================================================================*/ |
| 314 |
|
| 315 |
/*===========================================================================*\ |
| 316 |
* You can add whatever information you want about a node to help you |
| 317 |
* recreate it. I don't have a use for it, but maybe you will. |
| 318 |
\*===========================================================================*/ |
| 319 |
|
| 320 |
int user_add_to_desc(void *user, int *desc_size, char **desc) |
| 321 |
{ |
| 322 |
return(USER_DEFAULT); |
| 323 |
} |
| 324 |
|
| 325 |
/*===========================================================================*/ |
| 326 |
|
| 327 |
/*===========================================================================*\ |
| 328 |
* Compare cuts to see if they are the same. We use the default, which |
| 329 |
* is just comparing byte by byte. |
| 330 |
\*===========================================================================*/ |
| 331 |
|
| 332 |
int user_same_cuts(void *user, cut_data *cut1, cut_data *cut2, int *same_cuts) |
| 333 |
{ |
| 334 |
/*for now, we just compare byte by byte, as in the previous version of the |
| 335 |
code. Later, we might want to change this to be more efficient*/ |
| 336 |
return(USER_DEFAULT); |
| 337 |
} |
| 338 |
|
| 339 |
/*===========================================================================*/ |
| 340 |
|
| 341 |
/*===========================================================================*\ |
| 342 |
* This function receives a cut, unpacks it, and adds it to the set of |
| 343 |
* rows to be added to the LP. |
| 344 |
\*===========================================================================*/ |
| 345 |
|
| 346 |
int user_unpack_cuts(void *user, int from, int type, int varnum, |
| 347 |
var_desc **vars, int cutnum, cut_data **cuts, |
| 348 |
int *new_row_num, waiting_row ***new_rows) |
| 349 |
{ |
| 350 |
int i, j, nzcnt = 0, nzcnt_side = 0, nzcnt_across = 0; |
| 351 |
int v0, v1, *edges = ((vrp_lp_problem *)user)->edges; |
| 352 |
waiting_row **row_list = NULL; |
| 353 |
int *matind = NULL, *matind_across, *matind_side; |
| 354 |
cut_data *cut; |
| 355 |
char *coef; |
| 356 |
double *matval = NULL; |
| 357 |
int jj, size, vertnum = ((vrp_lp_problem *)user)->vertnum; |
| 358 |
int cliquecount = 0, val; |
| 359 |
char *clique_array; |
| 360 |
|
| 361 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 362 |
int num_fracs, fracs; |
| 363 |
int num_arcs, edge_index; |
| 364 |
char *cpt; |
| 365 |
int *arcs; |
| 366 |
char *indicators; |
| 367 |
|
| 368 |
double bigM, *weights; |
| 369 |
|
| 370 |
/*___END_EXPERIMENTAL_SECTION___*/ |
| 371 |
*new_row_num = cutnum; |
| 372 |
if (cutnum > 0) |
| 373 |
*new_rows = row_list = (waiting_row **) calloc (cutnum, |
| 374 |
sizeof(waiting_row *)); |
| 375 |
|
| 376 |
for (j = 0; j < cutnum; j++){ |
| 377 |
coef = (cut = cuts[j])->coef; |
| 378 |
cuts[j] = NULL; |
| 379 |
(row_list[j] = (waiting_row *) malloc(sizeof(waiting_row)))->cut = cut; |
| 380 |
switch (cut->type){ |
| 381 |
/*-------------------------------------------------------------------*\ |
| 382 |
* The subtour elimination constraints are stored as a vector of |
| 383 |
* bits indicating which side of the cut each customer is on |
| 384 |
\*-------------------------------------------------------------------*/ |
| 385 |
|
| 386 |
case SUBTOUR_ELIM: |
| 387 |
matind_side = (int *) malloc(varnum * ISIZE); |
| 388 |
matind_across = (int *) malloc(varnum * ISIZE); |
| 389 |
for (i = 0, nzcnt = 0; i < varnum; i++){ |
| 390 |
v0 = edges[(vars[i]->userind) << 1]; |
| 391 |
v1 = edges[((vars[i]->userind) << 1) + 1]; |
| 392 |
if (coef[v0 >> DELETE_POWER] & |
| 393 |
(1 << (v0 & DELETE_AND)) && |
| 394 |
(coef[v1 >> DELETE_POWER]) & |
| 395 |
(1 << (v1 & DELETE_AND))){ |
| 396 |
matind_side[nzcnt_side++] = i; |
| 397 |
}else if ((coef[v0 >> DELETE_POWER] >> |
| 398 |
(v0 & DELETE_AND) & 1) ^ |
| 399 |
(coef[v1 >> DELETE_POWER] >> |
| 400 |
(v1 & DELETE_AND) & 1)){ |
| 401 |
matind_across[nzcnt_across++] = i; |
| 402 |
} |
| 403 |
} |
| 404 |
cut->type = nzcnt_side < nzcnt_across ? SUBTOUR_ELIM_SIDE : |
| 405 |
SUBTOUR_ELIM_ACROSS; |
| 406 |
cut->deletable = TRUE; |
| 407 |
switch (cut->type){ |
| 408 |
case SUBTOUR_ELIM_SIDE: |
| 409 |
row_list[j]->nzcnt = nzcnt_side; |
| 410 |
row_list[j]->matind = matind_side; |
| 411 |
cut->rhs = 0; /*RHS(compnodes[i+1],compdemands[i+1], capacity)*/ |
| 412 |
cut->sense = 'L'; |
| 413 |
FREE(matind_across); |
| 414 |
break; |
| 415 |
|
| 416 |
case SUBTOUR_ELIM_ACROSS: |
| 417 |
row_list[j]->nzcnt = nzcnt_across; |
| 418 |
row_list[j]->matind = matind_across; |
| 419 |
cut->rhs = 0; /*2*BINS(compdemands[i+1], capacity)*/ |
| 420 |
cut->sense = 'G'; |
| 421 |
FREE(matind_side); |
| 422 |
break; |
| 423 |
} |
| 424 |
|
| 425 |
break; |
| 426 |
|
| 427 |
|
| 428 |
case SUBTOUR_ELIM_SIDE: |
| 429 |
matind = (int *) malloc(varnum * ISIZE); |
| 430 |
for (i = 0, nzcnt = 0; i < varnum; i++){ |
| 431 |
v0 = edges[(vars[i]->userind) << 1]; |
| 432 |
v1 = edges[((vars[i]->userind) << 1) + 1]; |
| 433 |
if (coef[v0 >> DELETE_POWER] & |
| 434 |
(1 << (v0 & DELETE_AND)) && |
| 435 |
(coef[v1 >> DELETE_POWER]) & |
| 436 |
(1 << (v1 & DELETE_AND))){ |
| 437 |
matind[nzcnt++] = i; |
| 438 |
} |
| 439 |
} |
| 440 |
cut->deletable = TRUE; |
| 441 |
cut->sense = 'L'; |
| 442 |
break; |
| 443 |
|
| 444 |
case SUBTOUR_ELIM_ACROSS: |
| 445 |
matind = (int *) malloc(varnum * ISIZE); |
| 446 |
for (i = 0, nzcnt = 0; i < varnum; i++){ |
| 447 |
v0 = edges[(vars[i]->userind) << 1]; |
| 448 |
v1 = edges[((vars[i]->userind) << 1) + 1]; |
| 449 |
if ((coef[v0 >> DELETE_POWER] >> |
| 450 |
(v0 & DELETE_AND) & 1) ^ |
| 451 |
(coef[v1 >> DELETE_POWER] >> |
| 452 |
(v1 & DELETE_AND) & 1)){ |
| 453 |
matind[nzcnt++] = i; |
| 454 |
} |
| 455 |
} |
| 456 |
cut->deletable = TRUE; |
| 457 |
cut->sense = 'G'; |
| 458 |
break; |
| 459 |
|
| 460 |
case CLIQUE: |
| 461 |
size = (vertnum >> DELETE_POWER) + 1; |
| 462 |
memcpy(&cliquecount, coef, ISIZE); |
| 463 |
matind = (int *) malloc(cliquecount*varnum*ISIZE); |
| 464 |
matval = (double *) malloc(cliquecount*varnum*DSIZE); |
| 465 |
coef += ISIZE; |
| 466 |
for (nzcnt = 0, i = 0; i < varnum; i++){ |
| 467 |
v0 = edges[(vars[i]->userind) << 1]; |
| 468 |
v1 = edges[((vars[i]->userind) << 1) + 1]; |
| 469 |
val = 0; |
| 470 |
for (jj = 0; jj < cliquecount; jj++){ |
| 471 |
clique_array = coef + size * jj; |
| 472 |
if (clique_array[v0 >> DELETE_POWER] & |
| 473 |
(1 << (v0 & DELETE_AND)) && |
| 474 |
(clique_array[v1 >> DELETE_POWER]) & |
| 475 |
(1 << (v1 & DELETE_AND))){ |
| 476 |
val += 1; |
| 477 |
} |
| 478 |
} |
| 479 |
if (val){ |
| 480 |
matind[nzcnt] = i; |
| 481 |
matval[nzcnt++] = val; |
| 482 |
} |
| 483 |
} |
| 484 |
cut->deletable = TRUE; |
| 485 |
break; |
| 486 |
|
| 487 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 488 |
case FARKAS: |
| 489 |
matind = (int *) malloc(varnum * ISIZE); |
| 490 |
matval = (double *) malloc(varnum * DSIZE); |
| 491 |
|
| 492 |
cpt = coef + ((vertnum >> DELETE_POWER) + 1); |
| 493 |
memcpy((char *)&num_arcs, cpt, ISIZE); |
| 494 |
cpt += ISIZE; |
| 495 |
arcs = (int *) malloc(num_arcs * ISIZE); |
| 496 |
indicators = (char *) malloc(num_arcs); |
| 497 |
memcpy((char *)arcs, cpt, num_arcs * ISIZE); |
| 498 |
cpt += num_arcs * ISIZE; |
| 499 |
memcpy(indicators, cpt, num_arcs); |
| 500 |
cpt += num_arcs; |
| 501 |
memcpy((char *)&num_fracs, cpt, ISIZE); |
| 502 |
cpt += ISIZE; |
| 503 |
weights = (double *) malloc((num_fracs + 1) * DSIZE); |
| 504 |
memcpy((char *)weights, cpt, (num_fracs + 1) * DSIZE); |
| 505 |
bigM = (*(double *)weights); |
| 506 |
weights++; |
| 507 |
|
| 508 |
for (fracs = 0, i = 0, nzcnt = 0; i < varnum; i++){ |
| 509 |
edge_index = vars[i]->userind; |
| 510 |
v0 = edges[edge_index << 1]; |
| 511 |
v1 = edges[(edge_index << 1) + 1]; |
| 512 |
|
| 513 |
if (isset(coef, v1) || isset(coef,v0)){ |
| 514 |
for (jj = 0; jj < num_arcs; jj++){ |
| 515 |
if (arcs[jj] == edge_index){ |
| 516 |
matval[nzcnt] = indicators[jj] ? -bigM : weights[fracs++]; |
| 517 |
break; |
| 518 |
} |
| 519 |
} |
| 520 |
if (jj == num_arcs) matval[nzcnt] = bigM; |
| 521 |
matind[nzcnt++] = i; |
| 522 |
} |
| 523 |
} |
| 524 |
cut->sense = 'G'; |
| 525 |
cut->branch = DO_NOT_BRANCH_ON_THIS_ROW; |
| 526 |
--weights; |
| 527 |
FREE(indicators); |
| 528 |
FREE(arcs); |
| 529 |
FREE(weights); |
| 530 |
break; |
| 531 |
|
| 532 |
case NO_COLUMNS: |
| 533 |
matind = (int *) malloc(varnum * ISIZE); |
| 534 |
matval = (double *) malloc(varnum * DSIZE); |
| 535 |
cpt = coef + ((vertnum >> DELETE_POWER) + 1); |
| 536 |
memcpy((char *)&num_arcs, cpt, ISIZE); |
| 537 |
cpt += ISIZE; |
| 538 |
arcs = (int *) calloc(num_arcs, ISIZE); |
| 539 |
indicators = (char *) malloc(num_arcs); |
| 540 |
memcpy((char *)arcs, cpt, num_arcs * ISIZE); |
| 541 |
cpt += num_arcs * ISIZE; |
| 542 |
memcpy(indicators, cpt, num_arcs); |
| 543 |
|
| 544 |
for (i = 0, nzcnt = 0; i < varnum; i++){ |
| 545 |
edge_index = vars[i]->userind; |
| 546 |
v0 = edges[edge_index << 1]; |
| 547 |
v1 = edges[(edge_index << 1) + 1]; |
| 548 |
|
| 549 |
if (isset(coef, v1) || isset(coef, v0)){ |
| 550 |
for (jj = 0; jj < num_arcs; jj++){ |
| 551 |
if (arcs[jj] == edge_index){ |
| 552 |
matval[nzcnt] = (indicators[jj]) ? 1.0 : 0.0; |
| 553 |
break; |
| 554 |
} |
| 555 |
} |
| 556 |
if (jj == num_arcs) matval[nzcnt]= -1.0; |
| 557 |
if (fabs(matval[nzcnt]) >.5) matind[nzcnt++] = i; |
| 558 |
} |
| 559 |
} |
| 560 |
cut->branch = DO_NOT_BRANCH_ON_THIS_ROW; |
| 561 |
cut->deletable = TRUE; |
| 562 |
cut->sense = 'L'; |
| 563 |
FREE(indicators); |
| 564 |
FREE(arcs); |
| 565 |
break; |
| 566 |
|
| 567 |
case GENERAL_NONZEROS: |
| 568 |
cpt = coef; |
| 569 |
memcpy((char *)&num_arcs, cpt, ISIZE); |
| 570 |
cpt += ISIZE; |
| 571 |
matind = (int *) malloc(num_arcs * ISIZE); |
| 572 |
arcs = (int *) calloc(num_arcs, ISIZE); |
| 573 |
matval = (double *) malloc(num_arcs * DSIZE); |
| 574 |
weights = (double *) malloc(num_arcs * DSIZE); |
| 575 |
memcpy((char *)arcs, cpt, num_arcs * ISIZE); |
| 576 |
cpt += num_arcs * ISIZE; |
| 577 |
memcpy((char *)weights, cpt, num_arcs * DSIZE); |
| 578 |
|
| 579 |
for (i = 0, nzcnt = 0; i < varnum; i++){ |
| 580 |
for (jj = 0; jj < num_arcs; jj++){ |
| 581 |
if (arcs[jj] == (edge_index = vars[i]->userind)){ |
| 582 |
matind[nzcnt] = i; |
| 583 |
matval[nzcnt++] = weights[jj]; |
| 584 |
break; |
| 585 |
} |
| 586 |
} |
| 587 |
} |
| 588 |
cut->branch = DO_NOT_BRANCH_ON_THIS_ROW; |
| 589 |
cut->deletable = TRUE; |
| 590 |
FREE(weights); |
| 591 |
FREE(arcs); |
| 592 |
break; |
| 593 |
/*___END_EXPERIMENTAL_SECTION___*/ |
| 594 |
|
| 595 |
default: |
| 596 |
break; |
| 597 |
|
| 598 |
} |
| 599 |
|
| 600 |
row_list[j]->matind = matind = |
| 601 |
(int *) realloc((char *)matind, nzcnt*ISIZE); |
| 602 |
row_list[j]->nzcnt = nzcnt; |
| 603 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 604 |
if (cut->type != CLIQUE && cut->type != FARKAS && |
| 605 |
cut->type != NO_COLUMNS && cut->type != GENERAL_NONZEROS){ |
| 606 |
/*___END_EXPERIMENTAL_SECTION___*/ |
| 607 |
/*UNCOMMENT FOR PRODUCTION CODE*/ |
| 608 |
#if 0 |
| 609 |
if (cut->type != CLIQUE){ |
| 610 |
#endif |
| 611 |
row_list[j]->matval = matval = (double *) malloc(nzcnt * DSIZE); |
| 612 |
for (i = nzcnt-1; i >= 0; i--) |
| 613 |
matval[i] = 1; |
| 614 |
cut->branch = ALLOWED_TO_BRANCH_ON; |
| 615 |
}else{ |
| 616 |
row_list[j]->matval=(double *) realloc((char *)matval, nzcnt * DSIZE); |
| 617 |
} |
| 618 |
} |
| 619 |
|
| 620 |
return(USER_SUCCESS); |
| 621 |
} |
| 622 |
|
| 623 |
/*===========================================================================*/ |
| 624 |
|
| 625 |
int user_send_lp_solution(void *user, int varnum, var_desc **vars, double *x, |
| 626 |
int where) |
| 627 |
{ |
| 628 |
return(SEND_NONZEROS); |
| 629 |
} |
| 630 |
|
| 631 |
/*===========================================================================*/ |
| 632 |
|
| 633 |
/*===========================================================================*\ |
| 634 |
* This routine does logical fixing of variables |
| 635 |
\*===========================================================================*/ |
| 636 |
|
| 637 |
int user_logical_fixing(void *user, int varnum, var_desc **vars, double *x, |
| 638 |
char *status, int *num_fixed) |
| 639 |
{ |
| 640 |
vrp_lp_problem *vrp = (vrp_lp_problem *)user; |
| 641 |
lp_net *lp_net; |
| 642 |
int *compdemands, capacity = vrp->capacity; |
| 643 |
int numchains = 0, v0, v1; |
| 644 |
lp_net_node *verts; |
| 645 |
int i; |
| 646 |
int *edges = vrp->edges; |
| 647 |
int fixed_num = 0; |
| 648 |
|
| 649 |
/*This routine could possibly be sped up by using pointers directly |
| 650 |
as in the min_cut routine */ |
| 651 |
|
| 652 |
/*set up the graph induced by the edges fixed to one*/ |
| 653 |
lp_net = create_lp_net(vrp, status, varnum, vars); |
| 654 |
|
| 655 |
verts = lp_net->verts; |
| 656 |
|
| 657 |
compdemands = (int *) calloc (varnum + 1, sizeof(int)); |
| 658 |
|
| 659 |
/*get the connected components of the 1-edge graph*/ |
| 660 |
numchains = vrp_lp_connected(lp_net, compdemands); |
| 661 |
|
| 662 |
for (i = 0; i < varnum; i++){ |
| 663 |
if (!(status[i] & NOT_FIXED) || (status[i] & VARIABLE_BRANCHED_ON)) |
| 664 |
continue; |
| 665 |
v0 = edges[(vars[i]->userind) << 1]; |
| 666 |
v1 = edges[((vars[i]->userind) << 1) + 1]; |
| 667 |
if (!v0){ |
| 668 |
if (verts[0].degree == 2*(vrp->numroutes)){ |
| 669 |
/* if the depot has 2*numroutes edges adjacent to it fixed to one, |
| 670 |
then we can eliminate all other edges adjacent to the depot |
| 671 |
from the problem*/ |
| 672 |
status[i] = PERM_FIXED_TO_LB; |
| 673 |
fixed_num++; |
| 674 |
} |
| 675 |
}else if ((verts[v0].degree == 2) || (verts[v1].degree == 2)){ |
| 676 |
/* if a particular node has to fixed-to-one edges adjacent to it, |
| 677 |
then we can eliminate all other edges adjacent to that node from |
| 678 |
the problem*/ |
| 679 |
fixed_num++; |
| 680 |
status[i] = PERM_FIXED_TO_LB; |
| 681 |
}else if (verts[v0].comp == verts[v1].comp){ |
| 682 |
/*if two vertices are in the same component in the 1-edge graph, then |
| 683 |
the edge between them can be eliminated from the problem*/ |
| 684 |
fixed_num++; |
| 685 |
status[i] = PERM_FIXED_TO_LB; |
| 686 |
}else if (compdemands[verts[v0].comp] + compdemands[verts[v1].comp] |
| 687 |
> capacity){ |
| 688 |
/*if the sum of the demands in two components of the 1-edge graph is |
| 689 |
greater than the capacity of a truck, then these two components |
| 690 |
cannot be linked and so any edge that goes bewtween them can be |
| 691 |
eliminated from the problem*/ |
| 692 |
fixed_num++; |
| 693 |
status[i] = PERM_FIXED_TO_LB; |
| 694 |
} |
| 695 |
} |
| 696 |
|
| 697 |
*num_fixed = fixed_num; |
| 698 |
|
| 699 |
free_lp_net(lp_net); |
| 700 |
|
| 701 |
free((char *)compdemands); |
| 702 |
|
| 703 |
return(USER_SUCCESS); |
| 704 |
} |
| 705 |
|
| 706 |
/*===========================================================================*/ |
| 707 |
|
| 708 |
/*===========================================================================*\ |
| 709 |
* This function generates the 'next' column |
| 710 |
\*===========================================================================*/ |
| 711 |
|
| 712 |
int user_generate_column(void *user, int generate_what, int cutnum, |
| 713 |
cut_data **cuts, int prevind, int nextind, |
| 714 |
int *real_nextind, double *colval, int *colind, |
| 715 |
int *collen, double *obj, double *lb, double *ub) |
| 716 |
{ |
| 717 |
vrp_lp_problem *vrp = (vrp_lp_problem *)user; |
| 718 |
int vh, vl, i; |
| 719 |
int total_edgenum = vrp->vertnum*(vrp->vertnum-1)/2; |
| 720 |
|
| 721 |
switch (generate_what){ |
| 722 |
case GENERATE_NEXTIND: |
| 723 |
/* Here we just have to generate the specified column. First, we |
| 724 |
determine the endpoints */ |
| 725 |
BOTH_ENDS(nextind, &vh, &vl); |
| 726 |
*real_nextind = nextind; |
| 727 |
break; |
| 728 |
case GENERATE_REAL_NEXTIND: |
| 729 |
/* In this case, we have to determine what the "real" next edge is*/ |
| 730 |
*real_nextind = nextind; |
| 731 |
if (prevind >= total_edgenum-1){ |
| 732 |
*real_nextind = -1; |
| 733 |
return(USER_SUCCESS); |
| 734 |
}else{ |
| 735 |
if (nextind == -1) nextind = total_edgenum; |
| 736 |
/*first, cycle through the edges that were eliminated in the root*/ |
| 737 |
for (i = prevind + 1; i < nextind && !vrp->edges[(i<<1)+1]; i++); |
| 738 |
/*now we should have the next nonzero edge*/ |
| 739 |
vl = vrp->edges[i << 1]; |
| 740 |
vh = vrp->edges[(i << 1) + 1]; |
| 741 |
} |
| 742 |
if (i == nextind) |
| 743 |
return(USER_SUCCESS); |
| 744 |
|
| 745 |
*real_nextind = i; |
| 746 |
break; |
| 747 |
} |
| 748 |
|
| 749 |
/* Now we just have to generate the column corresponding to (vh, vl) */ |
| 750 |
|
| 751 |
{ |
| 752 |
int nzcnt = 0, vertnum = vrp->vertnum; |
| 753 |
char *coef; |
| 754 |
cut_data *cut; |
| 755 |
int j, size; |
| 756 |
int cliquecount = 0, val; |
| 757 |
char *clique_array; |
| 758 |
|
| 759 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 760 |
int num_arcs, edge_index; |
| 761 |
char *cpt; |
| 762 |
int *arcs = (int *) calloc(total_edgenum, sizeof(int)); |
| 763 |
double bigM, *weights = (double *) calloc(total_edgenum, sizeof(double)); |
| 764 |
char *indicators = (char *) malloc(((vertnum*vertnum)/2)* sizeof(char)); |
| 765 |
|
| 766 |
/*___END_EXPERIMENTAL_SECTION___*/ |
| 767 |
colval[0] = 1; |
| 768 |
colind[0] = vl; /* supposes vl < vh !!!!!!**********/ |
| 769 |
colval[1] = 1; |
| 770 |
colind[1] = vh; |
| 771 |
nzcnt = 2; |
| 772 |
|
| 773 |
/* The coefficient for each row depends on what kind of cut it |
| 774 |
is */ |
| 775 |
for (i = 0; i < cutnum; i++){ |
| 776 |
coef = (cut = cuts[i])->coef; |
| 777 |
switch(cut->type){ |
| 778 |
|
| 779 |
case SUBTOUR_ELIM_SIDE: |
| 780 |
if (isset(coef, vh) && isset(coef, vl)){ |
| 781 |
colval[nzcnt] = 1; |
| 782 |
colind[nzcnt++] = vertnum + i; |
| 783 |
} |
| 784 |
break; |
| 785 |
|
| 786 |
case SUBTOUR_ELIM_ACROSS: |
| 787 |
/* It's important to have isclr here!!!!! see the macros */ |
| 788 |
if (isclr(coef, vh) ^ isclr(coef, vl)){ |
| 789 |
colval[nzcnt] = 1; |
| 790 |
colind[nzcnt++] = vertnum + i; |
| 791 |
} |
| 792 |
break; |
| 793 |
|
| 794 |
case CLIQUE: |
| 795 |
size = (vertnum >> DELETE_POWER) + 1; |
| 796 |
memcpy(&cliquecount, coef, ISIZE); |
| 797 |
coef += ISIZE; |
| 798 |
val = 0; |
| 799 |
for (j = 0; j < cliquecount; j++){ |
| 800 |
clique_array = coef + size * j; |
| 801 |
if (isset(clique_array, vh) && isset(clique_array, vl)) |
| 802 |
val += 1; |
| 803 |
} |
| 804 |
if (val){ |
| 805 |
colval[nzcnt] = val; |
| 806 |
colind[nzcnt++] = vertnum + i; |
| 807 |
} |
| 808 |
break; |
| 809 |
|
| 810 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 811 |
case FARKAS: |
| 812 |
if (isset(coef, vh) || isset(coef,vl)){ |
| 813 |
cpt = coef + ((vertnum >> DELETE_POWER) + 1); |
| 814 |
memcpy((char *)&num_arcs, cpt, ISIZE); |
| 815 |
memcpy((char *)arcs, cpt, ISIZE*(num_arcs + 1)); |
| 816 |
arcs++; |
| 817 |
cpt += (ISIZE * (num_arcs + 1))/CSIZE; |
| 818 |
memcpy((char *)weights, cpt, DSIZE*(num_arcs + 1)); |
| 819 |
bigM = (*(double *)weights); |
| 820 |
weights++; |
| 821 |
weights = (double *) calloc( total_edgenum, sizeof(double)) ; |
| 822 |
edge_index = INDEX(vh, vl); |
| 823 |
|
| 824 |
for (j = 0; j < num_arcs; j++){ |
| 825 |
if ( arcs[j] == edge_index){ |
| 826 |
colval[nzcnt] = weights[j]; |
| 827 |
break; |
| 828 |
} |
| 829 |
} |
| 830 |
if (j == num_arcs) colval[nzcnt] = bigM; |
| 831 |
colind[nzcnt++] = vertnum + i; |
| 832 |
arcs--; |
| 833 |
weights--; |
| 834 |
} |
| 835 |
break; |
| 836 |
|
| 837 |
case NO_COLUMNS: |
| 838 |
if (isset(coef, vh) || isset(coef,vl)){ |
| 839 |
cpt=coef+ ((vertnum >> DELETE_POWER) + 1); |
| 840 |
memcpy((char *)&num_arcs, cpt, ISIZE); |
| 841 |
cpt+= ISIZE /CSIZE; |
| 842 |
memcpy((char *)arcs, cpt, ISIZE*(num_arcs)); |
| 843 |
cpt+=(ISIZE*(num_arcs ))/CSIZE; |
| 844 |
memcpy((char *)indicators, cpt, CSIZE*(num_arcs)); |
| 845 |
edge_index=INDEX(vh, vl); |
| 846 |
|
| 847 |
for (j = 0; j < num_arcs; j++){ |
| 848 |
if ( arcs[j]==edge_index){ |
| 849 |
colval[nzcnt]=(indicators[j]) ? 1.0 : 0.0; |
| 850 |
break; |
| 851 |
} |
| 852 |
} |
| 853 |
if (j == num_arcs) colval[nzcnt] = -1.0; |
| 854 |
if (fabs(colval[nzcnt]) >.5) colind[nzcnt++] = i; |
| 855 |
|
| 856 |
} |
| 857 |
break; |
| 858 |
|
| 859 |
/*___END_EXPERIMENTAL_SECTION___*/ |
| 860 |
default: |
| 861 |
printf("Unrecognized cut type %i!\n", cut->type); |
| 862 |
} |
| 863 |
|
| 864 |
/* Set the upper and lower bounds */ |
| 865 |
if (vrp->edges[i << 1] == 0){ |
| 866 |
/*This is a depot edge and we have to check what its ub should be*/ |
| 867 |
/*Recall vrp->demand[0] == total_demand*/ |
| 868 |
if (vrp->demand[0] - vrp->demand[vrp->edges[(i << 1) + 1]] > |
| 869 |
vrp->capacity*(vrp->numroutes-1)) |
| 870 |
/*in this case, the node cannot be on its own route*/ |
| 871 |
*ub = 1; |
| 872 |
else |
| 873 |
*ub = 2; |
| 874 |
}else{ |
| 875 |
*ub = 1; |
| 876 |
} |
| 877 |
*lb = 0; |
| 878 |
} |
| 879 |
*collen = nzcnt; |
| 880 |
*obj = vrp->costs[*real_nextind]; |
| 881 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 882 |
FREE(indicators); |
| 883 |
FREE(arcs); |
| 884 |
FREE(weights); |
| 885 |
/*___END_EXPERIMENTAL_SECTION___*/ |
| 886 |
} |
| 887 |
|
| 888 |
return(USER_SUCCESS); |
| 889 |
} |
| 890 |
|
| 891 |
/*===========================================================================*/ |
| 892 |
|
| 893 |
/*===========================================================================*\ |
| 894 |
* You might want to print some statistics on the types and quantities |
| 895 |
* of cuts or something like that. |
| 896 |
\*===========================================================================*/ |
| 897 |
|
| 898 |
int user_print_stat_on_cuts_added(void *user, int rownum, waiting_row **rows) |
| 899 |
{ |
| 900 |
return(USER_DEFAULT); |
| 901 |
} |
| 902 |
|
| 903 |
/*===========================================================================*/ |
| 904 |
|
| 905 |
/*===========================================================================*\ |
| 906 |
* You might want to eliminate rows from the local pool based on |
| 907 |
* knowledge of problem structure. |
| 908 |
\*===========================================================================*/ |
| 909 |
|
| 910 |
int user_purge_waiting_rows(void *user, int rownum, waiting_row **rows, |
| 911 |
char *delete_rows) |
| 912 |
{ |
| 913 |
return(USER_DEFAULT); |
| 914 |
} |
| 915 |
|
| 916 |
/*===========================================================================*/ |
| 917 |
|
| 918 |
/*===========================================================================*\ |
| 919 |
* The user has to generate the ubber bounds for the specified (non-base) |
| 920 |
* variables. Lower bounds are always assumed (w.l.o.g.) to be zero. |
| 921 |
\*===========================================================================*/ |
| 922 |
|
| 923 |
/* Deprecated function */ |
| 924 |
|
| 925 |
#if 0 |
| 926 |
int user_get_upper_bounds(void *user, int varnum, int *indices, double *ub) |
| 927 |
{ |
| 928 |
vrp_lp_problem *vrp = (vrp_lp_problem *)user; |
| 929 |
int *edges = vrp->edges, i; |
| 930 |
int cap_check = vrp->capacity*(vrp->numroutes-1); |
| 931 |
int total_demand = vrp->demand[0]; |
| 932 |
|
| 933 |
for (i = 0; i < varnum; i++){ |
| 934 |
if (edges[indices[i] << 1] == 0){ |
| 935 |
/*This is a depot edge and we have to check what its ub should be*/ |
| 936 |
/*Recall vrp->demand[0] == total_demand*/ |
| 937 |
if (total_demand - vrp->demand[edges[(indices[i] << 1) + 1]] > |
| 938 |
cap_check) |
| 939 |
/*on this case, the node cannot be on its own route*/ |
| 940 |
ub[i] = 1; |
| 941 |
else |
| 942 |
ub[i] = 2; |
| 943 |
}else{ |
| 944 |
ub[i] = 1; |
| 945 |
} |
| 946 |
} |
| 947 |
|
| 948 |
return(USER_SUCCESS); |
| 949 |
} |
| 950 |
#endif |
| 951 |
|
| 952 |
/*===========================================================================*/ |
| 953 |
|
| 954 |
/*===========================================================================*\ |
| 955 |
* The user might want to generate cuts in the LP using information |
| 956 |
* about the current tableau, etc. This is for advanced users only. |
| 957 |
\*===========================================================================*/ |
| 958 |
|
| 959 |
int user_generate_cuts_in_lp(void *user, LPdata *lp_data, int varnum, |
| 960 |
var_desc **vars, double *x, |
| 961 |
int *new_row_num, cut_data ***cuts) |
| 962 |
{ |
| 963 |
return(DO_NOT_GENERATE_CGL_CUTS); |
| 964 |
} |
| 965 |
|
| 966 |
/*===========================================================================*/ |
| 967 |
|
| 968 |
/*===========================================================================*\ |
| 969 |
* Free all the user data structures |
| 970 |
\*===========================================================================*/ |
| 971 |
|
| 972 |
int user_free_lp(void **user) |
| 973 |
{ |
| 974 |
vrp_lp_problem *vrp = (vrp_lp_problem *)(*user); |
| 975 |
|
| 976 |
#ifndef COMPILE_IN_CG |
| 977 |
FREE(vrp->demand); |
| 978 |
#endif |
| 979 |
#if 0 |
| 980 |
FREE(vrp->costs); |
| 981 |
FREE(vrp->edges); |
| 982 |
FREE(vrp->cur_sol); |
| 983 |
FREE(vrp); |
| 984 |
#endif |
| 985 |
return(USER_SUCCESS); |
| 986 |
} |
| 987 |
|
| 988 |
/*===========================================================================*/ |
| 989 |
|
| 990 |
/*===========================================================================*\ |
| 991 |
* This function creates a the network of fixed edges that is used in the |
| 992 |
* logical fixing routine |
| 993 |
\*===========================================================================*/ |
| 994 |
|
| 995 |
lp_net *create_lp_net(vrp_lp_problem *vrp, char *status, int edgenum, |
| 996 |
var_desc **vars) |
| 997 |
{ |
| 998 |
lp_net *n; |
| 999 |
lp_net_node *verts; |
| 1000 |
int nv0 = 0, nv1 = 0; |
| 1001 |
lp_net_edge *adjlist; |
| 1002 |
int vertnum = vrp->vertnum, i; |
| 1003 |
int *demand = vrp->demand; |
| 1004 |
int *edges = vrp->edges; |
| 1005 |
|
| 1006 |
n = (lp_net *) calloc (1, sizeof(lp_net)); |
| 1007 |
n->vertnum = vertnum; |
| 1008 |
n->edgenum = vertnum*(vertnum-1)/2; |
| 1009 |
n->verts = (lp_net_node *) calloc (n->vertnum, sizeof(lp_net_node)); |
| 1010 |
n->adjlist = (lp_net_edge *) calloc (2*(n->edgenum), sizeof(lp_net_edge)); |
| 1011 |
verts = n->verts; |
| 1012 |
adjlist = n->adjlist; |
| 1013 |
|
| 1014 |
for (i = 0; i < edgenum; i++, status++){ |
| 1015 |
if (*status != PERM_FIXED_TO_UB) |
| 1016 |
continue; |
| 1017 |
nv0 = edges[vars[i]->userind << 1]; |
| 1018 |
nv1 = edges[(vars[i]->userind << 1) +1]; |
| 1019 |
if (!verts[nv0].first){ |
| 1020 |
verts[nv0].first = adjlist; |
| 1021 |
verts[nv0].degree += (int) vars[i]->ub; |
| 1022 |
} |
| 1023 |
else{ |
| 1024 |
adjlist->next = verts[nv0].first; |
| 1025 |
verts[nv0].first = adjlist; |
| 1026 |
verts[nv0].degree += (int) vars[i]->ub; |
| 1027 |
} |
| 1028 |
adjlist->other_end = nv1; |
| 1029 |
adjlist++; |
| 1030 |
if (!verts[nv1].first){ |
| 1031 |
verts[nv1].first = adjlist; |
| 1032 |
verts[nv1].degree += (int) vars[i]->ub; |
| 1033 |
} |
| 1034 |
else{ |
| 1035 |
adjlist->next = verts[nv1].first; |
| 1036 |
verts[nv1].first = adjlist; |
| 1037 |
verts[nv1].degree += (int) vars[i]->ub; |
| 1038 |
} |
| 1039 |
adjlist->other_end = nv0; |
| 1040 |
adjlist++; |
| 1041 |
} |
| 1042 |
|
| 1043 |
for (i=0; i< vertnum; i++) |
| 1044 |
verts[i].demand = demand[i]; |
| 1045 |
|
| 1046 |
return(n); |
| 1047 |
} |
| 1048 |
|
| 1049 |
/*===========================================================================*/ |
| 1050 |
|
| 1051 |
/*===========================================================================*\ |
| 1052 |
* This function constructs the connected components of the 1-edges graph |
| 1053 |
* used in the logical fixing routine |
| 1054 |
\*===========================================================================*/ |
| 1055 |
|
| 1056 |
int vrp_lp_connected(lp_net *n, int *compdemands) |
| 1057 |
{ |
| 1058 |
int cur_node = 0, cur_comp = 0; |
| 1059 |
lp_net_node *verts = n->verts; |
| 1060 |
int vertnum = n->vertnum; |
| 1061 |
lp_net_edge *cur_edge; |
| 1062 |
int *nodes_to_scan, num_nodes_to_scan = 0; |
| 1063 |
|
| 1064 |
nodes_to_scan = (int *) calloc (vertnum, sizeof(int)); |
| 1065 |
|
| 1066 |
while (TRUE){ |
| 1067 |
for (cur_node = 1; cur_node < vertnum; cur_node++) |
| 1068 |
if (!verts[cur_node].comp){ /* Look for the first node not already |
| 1069 |
in a component */ |
| 1070 |
break; |
| 1071 |
} |
| 1072 |
|
| 1073 |
if (cur_node == n->vertnum) break; /* we are done */ |
| 1074 |
|
| 1075 |
nodes_to_scan[num_nodes_to_scan++] = cur_node; |
| 1076 |
/* add the cur_node to the list of nodes to be scanned */ |
| 1077 |
verts[cur_node].comp = ++cur_comp; |
| 1078 |
/* add the current node to the current component */ |
| 1079 |
compdemands[cur_comp] = verts[cur_node].demand; |
| 1080 |
while(TRUE){ |
| 1081 |
/* In each iteration of this loop, we take the next node off the |
| 1082 |
list of nodes to be scanned, add it to the current component, and |
| 1083 |
then add all its neighbors to the list of nodes to be scanned */ |
| 1084 |
for (cur_node = nodes_to_scan[--num_nodes_to_scan], |
| 1085 |
verts[cur_node].scanned = TRUE, |
| 1086 |
cur_edge = verts[cur_node].first, |
| 1087 |
cur_comp = verts[cur_node].comp; |
| 1088 |
cur_edge; cur_edge = cur_edge->next){ |
| 1089 |
if (cur_edge->other_end){ |
| 1090 |
if (!verts[cur_edge->other_end].comp){ |
| 1091 |
verts[cur_edge->other_end].comp = cur_comp; |
| 1092 |
compdemands[cur_comp] += verts[cur_edge->other_end].demand; |
| 1093 |
nodes_to_scan[num_nodes_to_scan++] = cur_edge->other_end; |
| 1094 |
} |
| 1095 |
} |
| 1096 |
} |
| 1097 |
if (!num_nodes_to_scan) break; |
| 1098 |
/* when there are no more nodes to scan, we start a new component */ |
| 1099 |
} |
| 1100 |
} |
| 1101 |
|
| 1102 |
free((char *) nodes_to_scan); |
| 1103 |
return(cur_comp); |
| 1104 |
} |
| 1105 |
|
| 1106 |
/*===========================================================================*/ |
| 1107 |
|
| 1108 |
/*===========================================================================*\ |
| 1109 |
* Free the data structures associated with the 1-edges graph |
| 1110 |
\*===========================================================================*/ |
| 1111 |
|
| 1112 |
void free_lp_net(lp_net *n) |
| 1113 |
{ |
| 1114 |
if (n){ |
| 1115 |
FREE(n->adjlist); |
| 1116 |
FREE(n->verts); |
| 1117 |
FREE(n); |
| 1118 |
} |
| 1119 |
} |
| 1120 |
|
| 1121 |
/*===========================================================================*/ |
| 1122 |
|
| 1123 |
void construct_feasible_solution(vrp_lp_problem *vrp, network *n, |
| 1124 |
double *true_objval) |
| 1125 |
{ |
| 1126 |
_node *tour = vrp->cur_sol; |
| 1127 |
int cur_vert = 0, prev_vert = 0, cur_route, count; |
| 1128 |
elist *cur_route_start = NULL; |
| 1129 |
edge *edge_data; |
| 1130 |
vertex *verts = n->verts; |
| 1131 |
double cost = 0; |
| 1132 |
|
| 1133 |
/*construct the tour corresponding to this solution vector*/ |
| 1134 |
for (cur_route_start = verts[0].first, cur_route = 1, cost = 0, |
| 1135 |
edge_data = cur_route_start->data; cur_route <= vrp->numroutes; |
| 1136 |
cur_route++){ |
| 1137 |
edge_data = cur_route_start->data; |
| 1138 |
edge_data->scanned = TRUE; |
| 1139 |
cur_vert = edge_data->v1; |
| 1140 |
tour[prev_vert].next = cur_vert; |
| 1141 |
tour[cur_vert].route = cur_route; |
| 1142 |
prev_vert = 0; |
| 1143 |
cost += vrp->costs[INDEX(prev_vert, cur_vert)]; |
| 1144 |
while (cur_vert){ |
| 1145 |
if (verts[cur_vert].first->other_end != prev_vert){ |
| 1146 |
prev_vert = cur_vert; |
| 1147 |
edge_data = verts[cur_vert].first->data; |
| 1148 |
cur_vert = verts[cur_vert].first->other_end; |
| 1149 |
} |
| 1150 |
else{ |
| 1151 |
prev_vert = cur_vert; |
| 1152 |
edge_data = verts[cur_vert].last->data; /*This statement could |
| 1153 |
possibly be taken out to |
| 1154 |
speed things up a bit*/ |
| 1155 |
cur_vert = verts[cur_vert].last->other_end; |
| 1156 |
} |
| 1157 |
tour[prev_vert].next = cur_vert; |
| 1158 |
tour[cur_vert].route = cur_route; |
| 1159 |
cost += vrp->costs[INDEX(prev_vert, cur_vert)]; |
| 1160 |
} |
| 1161 |
edge_data->scanned = TRUE; |
| 1162 |
|
| 1163 |
while (cur_route_start->data->scanned){ |
| 1164 |
if (!(cur_route_start = cur_route_start->next_edge)) break; |
| 1165 |
} |
| 1166 |
} |
| 1167 |
*true_objval = cost; |
| 1168 |
|
| 1169 |
/* Display the solution */ |
| 1170 |
|
| 1171 |
printf("\nSolution Found:\n"); |
| 1172 |
printf("Solution Cost: %.0f\n", cost); |
| 1173 |
|
| 1174 |
cur_vert = tour[0].next; |
| 1175 |
|
| 1176 |
if (tour[0].route == 1) |
| 1177 |
printf("\n0 "); |
| 1178 |
while (cur_vert != 0){ |
| 1179 |
if (tour[prev_vert].route != tour[cur_vert].route){ |
| 1180 |
printf("\nRoute #%i: ", tour[cur_vert].route); |
| 1181 |
count = 0; |
| 1182 |
} |
| 1183 |
printf("%i ", cur_vert); |
| 1184 |
count++; |
| 1185 |
if (count > 15){ |
| 1186 |
printf("\n"); |
| 1187 |
count = 0; |
| 1188 |
} |
| 1189 |
prev_vert = cur_vert; |
| 1190 |
cur_vert = tour[cur_vert].next; |
| 1191 |
} |
| 1192 |
printf("\n\n"); |
| 1193 |
} |
| 1194 |
|
| 1195 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 1196 |
#ifdef TRACE_PATH |
| 1197 |
|
| 1198 |
#include "sym_lp.h" |
| 1199 |
|
| 1200 |
void check_lp(lp_prob *p) |
| 1201 |
{ |
| 1202 |
LPdata *lp_data = p->lp_data; |
| 1203 |
int i, j, l; |
| 1204 |
tm_prob *tm = p->tm; |
| 1205 |
double *x = (double *) malloc(tm->feas_sol_size * DSIZE), lhs, cost = 0; |
| 1206 |
double *lhs_totals = (double *) calloc(lp_data->m, DSIZE); |
| 1207 |
MakeMPS(lp_data, 0, 0); |
| 1208 |
|
| 1209 |
get_x(lp_data); |
| 1210 |
|
| 1211 |
printf("Optimal Fractional Solution: %.10f\n", lp_data->lpetol); |
| 1212 |
for (i = 0; i < lp_data->n; i++){ |
| 1213 |
if (lp_data->x[i] > lp_data->lpetol){ |
| 1214 |
printf("uind: %i colind: %i value: %.10f cost: %f\n", |
| 1215 |
lp_data->vars[i]->userind, i, lp_data->x[i], lp_data->obj[i]); |
| 1216 |
} |
| 1217 |
cost += lp_data->obj[i]*lp_data->x[i]; |
| 1218 |
} |
| 1219 |
printf("Cost: %f\n", cost); |
| 1220 |
|
| 1221 |
printf("\nFeasible Integer Solution:\n"); |
| 1222 |
for (cost = 0, i = 0; i < tm->feas_sol_size; i++){ |
| 1223 |
printf("uind: %i ", tm->feas_sol[i]); |
| 1224 |
for (j = 0; j < lp_data->n; j++){ |
| 1225 |
if (lp_data->vars[j]->userind == tm->feas_sol[i]){ |
| 1226 |
cost += lp_data->obj[j]; |
| 1227 |
printf("colind: %i lb: %f ub: %f obj: %f\n", j, lp_data->lb[j], |
| 1228 |
lp_data->ub[j], lp_data->obj[j]); |
| 1229 |
break; |
| 1230 |
} |
| 1231 |
} |
| 1232 |
if (j == lp_data->n) |
| 1233 |
printf("\n\nERROR!!!!!!!!!!!!!!!!\n\n"); |
| 1234 |
x[i] = 1.0; |
| 1235 |
} |
| 1236 |
printf("Cost: %f\n", cost); |
| 1237 |
|
| 1238 |
printf("\nChecking LP....\n\n"); |
| 1239 |
printf("Number of cuts: %i\n", lp_data->m); |
| 1240 |
for (i = 0; i < tm->feas_sol_size; i++){ |
| 1241 |
for (j = 0; j < lp_data->n; j++){ |
| 1242 |
if (tm->feas_sol[i] == lp_data->vars[j]->userind) |
| 1243 |
break; |
| 1244 |
} |
| 1245 |
for (l = lp_data->matbeg[j]; l < lp_data->matbeg[j] + lp_data->matcnt[j]; |
| 1246 |
l++){ |
| 1247 |
lhs_totals[lp_data->matind[l]] += 1; |
| 1248 |
} |
| 1249 |
} |
| 1250 |
for (i = 0; i < p->base.cutnum; i++){ |
| 1251 |
printf("Cut %i: %f %c %f\n", i, lhs_totals[i], lp_data->sense[i], |
| 1252 |
lp_data->rhs[i]); |
| 1253 |
} |
| 1254 |
for (; i < lp_data->m; i++){ |
| 1255 |
lhs = compute_lhs(tm->feas_sol_size, tm->feas_sol, x, |
| 1256 |
lp_data->rows[i].cut, p->base.cutnum); |
| 1257 |
printf("Cut %i: %f %f %c %f\n", i, lhs_totals[i], lhs, lp_data->sense[i], |
| 1258 |
lp_data->rhs[i]); |
| 1259 |
if (lp_data->rows[i].cut->sense == 'G' ? |
| 1260 |
lhs < lp_data->rows[i].cut->rhs : lhs > lp_data->rows[i].cut->rhs){ |
| 1261 |
printf("LP: ERROR -- row is violated by feasible solution!!!\n"); |
| 1262 |
sleep(600); |
| 1263 |
exit(1); |
| 1264 |
} |
| 1265 |
} |
| 1266 |
} |
| 1267 |
#endif |
| 1268 |
/*___END_EXPERIMENTAL_SECTION___*/ |