| 1 |
#include <math.h> |
| 2 |
#include <memory.h> |
| 3 |
#include <string.h> |
| 4 |
|
| 5 |
#include "BB_macros.h" |
| 6 |
#include "decomp.h" |
| 7 |
#include "decomp_lower_bound.h" |
| 8 |
#include "vrp_macros.h" |
| 9 |
#include "my_decomp.h" |
| 10 |
#include "sym_timemeas.h" |
| 11 |
#include "sym_messages.h" |
| 12 |
#include "network.h" |
| 13 |
#include "vrp_sym_dg.h" |
| 14 |
|
| 15 |
int vrp_decomp(int comp_num, double *compdensity) |
| 16 |
{ |
| 17 |
cg_prob *p = get_cg_ptr(NULL); |
| 18 |
LPdata *lp_data = p->dcmp_data.lp_data; |
| 19 |
cg_vrp_spec *vrp = (cg_vrp_spec *)(p->user); |
| 20 |
/* cut_gen_times *comp_times; */ |
| 21 |
/* decomp_data *dcmp_data = &p->dcmp_data; */ |
| 22 |
/*double *x = dcmp_data->x;*/ |
| 23 |
int cuts_found = 0, init_cols, new_cols, termcode /*,*unbd_row*/ ; |
| 24 |
int cur_comp; |
| 25 |
network *n = vrp->n; |
| 26 |
edge **row_edges = (edge **) malloc((n->edgenum) * sizeof(edge *)); |
| 27 |
int generated_all_columns = FALSE, generated_max_columns = FALSE; |
| 28 |
int columns_deleted, *delstat = NULL; |
| 29 |
int stat, new_cuts; |
| 30 |
|
| 31 |
int i, prev_neighbor, v1, v2, count, vertnum = n->vertnum; |
| 32 |
elist *e,*e1, *neighbor_elist; |
| 33 |
vertex *verts = n->verts, *nv, *neighbor; |
| 34 |
double *new_demand = n->new_demand = (double *) calloc(vertnum, DSIZE); |
| 35 |
int total_demand = vrp->demand[0]; |
| 36 |
int cap_check = vrp->capacity*(vrp->numroutes-1); |
| 37 |
int total_edge_cost; |
| 38 |
int verts_deleted = 0, edges_deleted = 0; |
| 39 |
double density_threshold = vrp->par.graph_density_threshold; |
| 40 |
|
| 41 |
int *compnodes = (int *) calloc(comp_num+1, ISIZE); |
| 42 |
int *compdemands = (int *) calloc(comp_num+1, ISIZE); |
| 43 |
|
| 44 |
if (vrp->par.decomp_decompose){ |
| 45 |
connected(n, compnodes, compdemands, NULL, NULL, NULL); |
| 46 |
}else{ |
| 47 |
for (i = 1; i < vertnum; i ++) |
| 48 |
verts[i].comp = 1; |
| 49 |
compnodes[1] = vertnum - 1; |
| 50 |
} |
| 51 |
|
| 52 |
n->compnodes = compnodes; |
| 53 |
|
| 54 |
/* find the edges that can be used to make 1-customer routes */ |
| 55 |
if (vrp->par.allow_one_routes_in_bfm){ |
| 56 |
for (e = verts[0].first; e; e = e->next_edge){ |
| 57 |
if (vrp->par.feasible_tours_only){ |
| 58 |
e->data->can_be_doubled = (total_demand - vrp->demand[e->other_end] |
| 59 |
> cap_check) ? FALSE : TRUE; |
| 60 |
}else{ |
| 61 |
e->data->can_be_doubled = TRUE; |
| 62 |
} |
| 63 |
} |
| 64 |
} |
| 65 |
|
| 66 |
/*+ ((p->ub - p->cur_sol.objval > 5.5)? 170:0);*/ |
| 67 |
|
| 68 |
/*Here, we are doing some preprocessing, but it is not needed for |
| 69 |
correctness and was causing problems for some reason, so I commented it |
| 70 |
out. Boy, I wish I had written some of this stuff down...*/ |
| 71 |
|
| 72 |
/*FIRST, CONTRACT THE GRAPH */ |
| 73 |
/* here we are contracting 1-chains into single edges: deleting intermediary |
| 74 |
nodes, adjusting elist objects for the endnodes of the chain, and keeping |
| 75 |
the pointers to the deleted edges in the corresponding elist->edges of |
| 76 |
the endnodes. However, if one endnode of 1-chain is depot, and the other |
| 77 |
is incident to it, we do not contract the intermediary node that is next |
| 78 |
to depot on the chain; failure to do this will result in multi-edge |
| 79 |
between the endnodes */ |
| 80 |
|
| 81 |
#if 0 |
| 82 |
for(i = vertnum - 1, nv = verts + vertnum - 1; i; i--, nv--){ |
| 83 |
|
| 84 |
if (nv->degree <= 2 || compdensity[nv->comp] > density_threshold) |
| 85 |
continue; |
| 86 |
|
| 87 |
#if 0 |
| 88 |
not_incident_to_depot = TRUE; |
| 89 |
for (e = nv->first; e; e = e->next_edge){ |
| 90 |
if (!(e->other_end)){ |
| 91 |
not_incident_to_depot = FALSE; |
| 92 |
break; |
| 93 |
} |
| 94 |
} |
| 95 |
#endif |
| 96 |
for (e = nv->first; e; e = e->next_edge){ |
| 97 |
if ((neighbor = e->other)->degree > 2 || neighbor->deleted || |
| 98 |
!neighbor->first->other_end || !neighbor->last->other_end) |
| 99 |
continue; |
| 100 |
|
| 101 |
prev_neighbor = i; |
| 102 |
neighbor_elist = e; |
| 103 |
e->superlink = TRUE; |
| 104 |
e->edgenum = 0; |
| 105 |
total_edge_cost = 0; |
| 106 |
e->edges = (edge **) calloc(vertnum, sizeof(edge *)); |
| 107 |
while(neighbor->degree == 2 && neighbor->first->other_end && |
| 108 |
neighbor->last->other_end){ |
| 109 |
/* trace the 1-chain */ |
| 110 |
e->edges[e->edgenum++] = neighbor_elist->data; |
| 111 |
edges_deleted++; |
| 112 |
total_edge_cost += neighbor_elist->data->cost; |
| 113 |
new_demand[i] += neighbor->demand; |
| 114 |
neighbor->deleted = TRUE; |
| 115 |
verts_deleted++; |
| 116 |
v1 = neighbor->first->other_end; |
| 117 |
v2 = neighbor->last->other_end; |
| 118 |
|
| 119 |
if (v1 == prev_neighbor){ |
| 120 |
prev_neighbor = neighbor->orignodenum; |
| 121 |
neighbor_elist = neighbor->last; |
| 122 |
neighbor = neighbor->last->other; |
| 123 |
}else{ |
| 124 |
prev_neighbor = neighbor->orignodenum; |
| 125 |
neighbor_elist = neighbor->first; |
| 126 |
neighbor = neighbor->first->other; |
| 127 |
} |
| 128 |
} |
| 129 |
e->edges[e->edgenum++] = neighbor_elist->data; |
| 130 |
edges_deleted++; |
| 131 |
total_edge_cost += neighbor_elist->data->cost; |
| 132 |
e->data->cost = total_edge_cost; |
| 133 |
e->other = neighbor; |
| 134 |
e->other_end = neighbor->orignodenum; |
| 135 |
for (e1=neighbor->first; e1; e1=e1->next_edge){ |
| 136 |
if (e1->other_end == prev_neighbor){ |
| 137 |
e1->data->other_data = e->data; |
| 138 |
e1->data->cost = total_edge_cost; |
| 139 |
e1->other = nv; |
| 140 |
e1->other_end = nv->orignodenum; |
| 141 |
e1->superlink = TRUE; |
| 142 |
e1->edgenum = 0; |
| 143 |
e1->edges = (edge **) calloc(vertnum, sizeof(edge *)); |
| 144 |
for (count = e->edgenum; count; count--) |
| 145 |
e1->edges[e1->edgenum++] = e->edges[count-1]; |
| 146 |
} |
| 147 |
} |
| 148 |
} |
| 149 |
} |
| 150 |
|
| 151 |
#if 0 |
| 152 |
printf("Contracted graph: nodes %d, edges %d\n", |
| 153 |
n->vertnum - verts_deleted, n->edgenum - edges_deleted); |
| 154 |
#endif |
| 155 |
(void) used_time(&p->tt); |
| 156 |
/* for each component do */ |
| 157 |
#endif |
| 158 |
|
| 159 |
/*Here is where the real decomposition algorithm starts. each component of |
| 160 |
the support graph after removing the depot is decomposed separately since |
| 161 |
if there is a violated capacity constraint, then there is one using the |
| 162 |
nodes in just one of the components, i.e., we can consider each component |
| 163 |
separately. Now, it seems to me that at one time, I found a problem with |
| 164 |
this, too, and I added a parameter for whether to do decomposition |
| 165 |
component-wise or do the whole graph at once. the parameter is |
| 166 |
vrp->par.decomp_decompose. If set to FALSE, then it reats the whole graph |
| 167 |
as one component. I would stick with this for now. In that case, you can |
| 168 |
ignore the outer loop here. */ |
| 169 |
|
| 170 |
for (cur_comp = 1; cur_comp <= comp_num; cur_comp++) |
| 171 |
if (compnodes[cur_comp]>3 && compdensity[cur_comp]<density_threshold){ |
| 172 |
printf("Calling decomp: density %.2f, obj %.2f, ub %.2f, level %d \n", |
| 173 |
compdensity[cur_comp], p->cur_sol.objval, p->ub, |
| 174 |
p->cur_sol.xlevel); |
| 175 |
|
| 176 |
/*Here we seed the matrix by generating a set of initial columns the |
| 177 |
"conform" to the current LP solution by "brute force", i.e., through |
| 178 |
depth first search of the fractional graph. There is a maximum time |
| 179 |
to be spent in this routine, as well as a maximum number of columns |
| 180 |
allowed to be generated in this way. If we get lucky and the |
| 181 |
fractional graph is sparse, this may produce all possible columns |
| 182 |
conforming to the current solution (indicated by setting |
| 183 |
"generate_all_columns" to TRUE). Otherwise, we move on to the column |
| 184 |
generation phase. */ |
| 185 |
|
| 186 |
init_cols = vrp_create_initial_lp(p, n, cur_comp, comp_num, |
| 187 |
compdemands, row_edges, |
| 188 |
&generated_all_columns); |
| 189 |
if (init_cols){ |
| 190 |
/* If we managed to find any columns, then check to see whether |
| 191 |
we've already reached the maximum allowable. */ |
| 192 |
if (init_cols == lp_data->maxn){ |
| 193 |
generated_max_columns = TRUE; |
| 194 |
} |
| 195 |
}else if (generated_all_columns && vrp->par.generate_no_cols_cuts){ |
| 196 |
/*If no columns were found and the fractional graph was searched |
| 197 |
completey, then we can generate a "no columns cut" */ |
| 198 |
cuts_found += generate_no_cols_cut(p, lp_data, n, row_edges, |
| 199 |
cur_comp); |
| 200 |
printf("No columns cut generated\n"); |
| 201 |
continue; |
| 202 |
}else{ |
| 203 |
/* Otherwise, try to generate columns */ |
| 204 |
new_cols = vrp_generate_new_cols(p, lp_data, n, row_edges, |
| 205 |
cur_comp); |
| 206 |
if (!new_cols){ |
| 207 |
/* If we still didn't find anything, then generate a no columns |
| 208 |
cut*/ |
| 209 |
if (vrp->par.generate_no_cols_cuts){ |
| 210 |
cuts_found += generate_no_cols_cut(p, lp_data, n, row_edges, |
| 211 |
cur_comp); |
| 212 |
printf("No columns cut generated\n"); |
| 213 |
} |
| 214 |
continue; |
| 215 |
} |
| 216 |
} |
| 217 |
p->dcmp_data.timeout = time(NULL); |
| 218 |
while(TRUE){ |
| 219 |
/* This is the main loop |
| 220 |
1. Solve the current LP |
| 221 |
2. If feasible, STOP. |
| 222 |
3. Otherwise, try to generate columns. |
| 223 |
4. Repeat |
| 224 |
*/ |
| 225 |
p->dcmp_data.iter_num++; |
| 226 |
#if 0 |
| 227 |
/*Ignore this*/ |
| 228 |
comp_times = &p->comp_times; |
| 229 |
comp_times->over_head += used_time(&p->tt); |
| 230 |
|
| 231 |
/*solve the current lp*/ |
| 232 |
if (stat = CPXchecklp(lp_data->cpxenv, |
| 233 |
(char *) "Decomp_prob", lp_data->n, |
| 234 |
lp_data->m, 1, lp_data->obj, |
| 235 |
lp_data->rhs, lp_data->sense, |
| 236 |
lp_data->matbeg, lp_data->matcnt, |
| 237 |
lp_data->matind, lp_data->matval, |
| 238 |
lp_data->lb, lp_data->ub, |
| 239 |
lp_data->rngval, lp_data->maxn + |
| 240 |
lp_data->maxm, lp_data->maxm, |
| 241 |
lp_data->maxnz+lp_data->maxm) ){ |
| 242 |
printf("#### AHHA ###"); |
| 243 |
} |
| 244 |
#endif |
| 245 |
/*Solve the decomposition LP. Note that this all depends on CPLEX. |
| 246 |
I planned to remove that dependency, but never did. Shouldn't be |
| 247 |
too hard to do now that there is an interface to OSL. */ |
| 248 |
termcode = CPXdualopt(lp_data->cpxenv, lp_data->lp); |
| 249 |
|
| 250 |
switch (stat = CPXgetstat(lp_data->cpxenv,lp_data->lp)){ |
| 251 |
case CPX_OPTIMAL: termcode = OPTIMAL; break; |
| 252 |
case CPX_INFEASIBLE: termcode = D_INFEASIBLE; break; |
| 253 |
case CPX_UNBOUNDED: termcode = D_UNBOUNDED; break; |
| 254 |
case CPX_OBJ_LIM: termcode = D_OBJLIM; break; |
| 255 |
case CPX_IT_LIM_FEAS: |
| 256 |
case CPX_IT_LIM_INFEAS: termcode = D_ITLIM; break; |
| 257 |
default: termcode = ABANDONED; break; |
| 258 |
} |
| 259 |
|
| 260 |
/*comp_times->lp += used_time(&p->tt);*/ |
| 261 |
|
| 262 |
switch (termcode){ |
| 263 |
case D_UNBOUNDED: |
| 264 |
/*LP is infeasible. try to generate columns */ |
| 265 |
break; |
| 266 |
case OPTIMAL: |
| 267 |
/*Found a decomposition. Try to generate cuts*/ |
| 268 |
cuts_found += |
| 269 |
(new_cuts = vrp_generate_cuts(p, n, cur_comp, |
| 270 |
row_edges, vrp->par.generate_capacity_cuts)); |
| 271 |
printf("Decomp imposed %i new capacity constraints\n", |
| 272 |
new_cuts); |
| 273 |
break; |
| 274 |
default: |
| 275 |
printf("####CutGen: Unexpected lp termcode %i in decomp###\n\n", |
| 276 |
termcode); |
| 277 |
break; |
| 278 |
} |
| 279 |
if (termcode != D_UNBOUNDED || generated_all_columns |
| 280 |
|| generated_max_columns){ |
| 281 |
printf("Generated %i columns\n", lp_data->n); |
| 282 |
break; |
| 283 |
}else if (time(NULL) - p->dcmp_data.timeout < |
| 284 |
p->par.decomp_dynamic_timeout){ |
| 285 |
new_cols = vrp_generate_new_cols(p, lp_data, n, row_edges, |
| 286 |
cur_comp); |
| 287 |
}else{ |
| 288 |
break; |
| 289 |
} |
| 290 |
switch (new_cols){ |
| 291 |
case 0: |
| 292 |
/*This assumes an exact column generator*/ |
| 293 |
|
| 294 |
/*If we're here, then the LP was infeasible and we couldn't |
| 295 |
generate any new columns*/ |
| 296 |
|
| 297 |
/*I think this line was for debugging (see below)*/ |
| 298 |
get_proof_of_infeas(lp_data, &i); |
| 299 |
|
| 300 |
#if 0 |
| 301 |
/* This was some debugging I was trying to do. I figured out |
| 302 |
the problem eventually (I think), but I left the code here. |
| 303 |
Just ignore it. What was that bug...? It was really a nasty |
| 304 |
one and not obvious at first. I'm not sure I fixed it |
| 305 |
completely. I hope I remember ... */ |
| 306 |
termcode = CPXunloadprob(lp_data->cpxenv, lp_data->lp); |
| 307 |
|
| 308 |
lp_data->lp = |
| 309 |
CPXloadlp(lp_data->cpxenv, |
| 310 |
(char *) "Decomp_prob", lp_data->n, lp_data->m, 1, |
| 311 |
lp_data->obj, |
| 312 |
lp_data->rhs, lp_data->sense, lp_data->matbeg, |
| 313 |
lp_data->matcnt, lp_data->matind, lp_data->matval, |
| 314 |
lp_data->lb, lp_data->ub, lp_data->rngval, |
| 315 |
lp_data->maxn+lp_data->maxm, lp_data->maxm, |
| 316 |
lp_data->maxnz+lp_data->maxm); |
| 317 |
|
| 318 |
termcode = CPXdualopt(lp_data->cpxenv, lp_data->lp); |
| 319 |
|
| 320 |
get_proof_of_infeas(lp_data, &i); |
| 321 |
|
| 322 |
new_cols = vrp_generate_new_cols(p, lp_data, n, row_edges, |
| 323 |
cur_comp); |
| 324 |
|
| 325 |
if (new_cols > 0) break; |
| 326 |
|
| 327 |
switch (stat = CPXgetstat(lp_data->cpxenv,lp_data->lp)){ |
| 328 |
case CPX_OPTIMAL: termcode = OPTIMAL; break; |
| 329 |
case CPX_INFEASIBLE: termcode = D_INFEASIBLE; break; |
| 330 |
case CPX_UNBOUNDED: termcode = D_UNBOUNDED; break; |
| 331 |
case CPX_OBJ_LIM: termcode = D_OBJLIM; break; |
| 332 |
case CPX_IT_LIM_FEAS: |
| 333 |
case CPX_IT_LIM_INFEAS: termcode = D_ITLIM; break; |
| 334 |
default: termcode = ABANDONED; break; |
| 335 |
} |
| 336 |
|
| 337 |
MakeMPS(lp_data, 0, 0); |
| 338 |
termcode = CPXwriteprob(lp_data->cpxenv, lp_data->lp, |
| 339 |
"/home/tkr/tmp/matrices/bug.mps", "MPS"); |
| 340 |
#endif |
| 341 |
/*Generate Farkas inequalities*/ |
| 342 |
if (vrp->par.generate_farkas_cuts){ |
| 343 |
cuts_found += |
| 344 |
(new_cuts = generate_farkas_cuts(p, lp_data, n, |
| 345 |
row_edges, cur_comp)); |
| 346 |
printf("Generated %i FARKAS cuts\n", new_cuts); |
| 347 |
} |
| 348 |
if (!new_cols){ |
| 349 |
generated_all_columns = TRUE; |
| 350 |
break; |
| 351 |
} |
| 352 |
case -1: |
| 353 |
generated_max_columns = TRUE; |
| 354 |
break; |
| 355 |
default: |
| 356 |
/*Generated some columns. Go back to the top and try to solve |
| 357 |
the LP */ |
| 358 |
break; |
| 359 |
} |
| 360 |
} |
| 361 |
/*For now, ignore all this. We can get into what all this is at a |
| 362 |
later point. Maybe you can figure it out, but it's difficult to |
| 363 |
explain.*/ |
| 364 |
if (generated_all_columns && !vrp->par.feasible_tours_only && |
| 365 |
p->par.decomp_dynamic_timeout == 0){ |
| 366 |
delstat = (int *) calloc(lp_data->n, ISIZE); |
| 367 |
columns_deleted = purge_infeasible_cols(p, lp_data, row_edges, |
| 368 |
delstat); |
| 369 |
if (columns_deleted == lp_data->n){ |
| 370 |
if (vrp->par.generate_no_cols_cuts){ |
| 371 |
cuts_found += generate_no_cols_cut(p, lp_data, n, row_edges, |
| 372 |
cur_comp); |
| 373 |
printf("No columns cut generated\n"); |
| 374 |
} |
| 375 |
}else{ |
| 376 |
lp_data->n -= columns_deleted; |
| 377 |
CPXdelsetcols(lp_data->cpxenv, lp_data->lp, delstat); |
| 378 |
termcode = CPXdualopt(lp_data->cpxenv, lp_data->lp); |
| 379 |
|
| 380 |
switch (stat = CPXgetstat(lp_data->cpxenv,lp_data->lp)){ |
| 381 |
case CPX_OPTIMAL: termcode = OPTIMAL; break; |
| 382 |
case CPX_INFEASIBLE: termcode = D_INFEASIBLE; break; |
| 383 |
case CPX_UNBOUNDED: termcode = D_UNBOUNDED; break; |
| 384 |
case CPX_OBJ_LIM: termcode = D_OBJLIM; break; |
| 385 |
case CPX_IT_LIM_FEAS: |
| 386 |
case CPX_IT_LIM_INFEAS: termcode = D_ITLIM; break; |
| 387 |
default: termcode = ABANDONED; break; |
| 388 |
} |
| 389 |
|
| 390 |
if (termcode==D_UNBOUNDED){ |
| 391 |
if (vrp->par.generate_farkas_cuts){ |
| 392 |
cuts_found += |
| 393 |
(new_cuts = generate_farkas_cuts(p, lp_data, n, |
| 394 |
row_edges, cur_comp)); |
| 395 |
printf("Generated %i FARKAS cuts\n", new_cuts); |
| 396 |
} |
| 397 |
}else{ |
| 398 |
if (lp_data->n != 1) |
| 399 |
printf("###Unexpected lp termcode %i in decomp###\n\n", |
| 400 |
termcode); |
| 401 |
} |
| 402 |
} |
| 403 |
} |
| 404 |
/*CPXfreeprob(lp_data->cpxenv, &(lp_data->lp));*/ |
| 405 |
} |
| 406 |
|
| 407 |
|
| 408 |
FREE(compnodes); |
| 409 |
FREE(compdemands); |
| 410 |
free(row_edges); |
| 411 |
free(new_demand); |
| 412 |
FREE(delstat); |
| 413 |
for (e=n->adjlist, i=0;i< 2*(n->edgenum) ;i++, e++) |
| 414 |
if (e->superlink) FREE(e->edges); |
| 415 |
printf("Decomp imposed a total of %i new constraints\n", cuts_found); |
| 416 |
return(cuts_found); |
| 417 |
|
| 418 |
} |
| 419 |
|
| 420 |
/*===========================================================================*/ |
| 421 |
|
| 422 |
int vrp_create_initial_lp(cg_prob *p, network *n, int cur_comp, int num_comps, |
| 423 |
int *compdemands, edge **row_edges, |
| 424 |
int *generated_all_columns) |
| 425 |
{ |
| 426 |
|
| 427 |
LPdata *lp_data = p->dcmp_data.lp_data; |
| 428 |
int cpx_status, i; |
| 429 |
int *compnodes = n->compnodes; |
| 430 |
edge *edges = n->edges, *temp_edge; |
| 431 |
vertex *verts = n->verts; |
| 432 |
int v1, v0; |
| 433 |
int edgenum = n->edgenum, node_num, row_num, low_tour_num, high_tour_num; |
| 434 |
cg_vrp_spec *vrp = (cg_vrp_spec *)(p->user); |
| 435 |
int size = vrp->vertnum + vrp->numroutes - 1; |
| 436 |
int *intour, *tour; |
| 437 |
edge **stack; |
| 438 |
elist *cur_edge; |
| 439 |
int numroutes = vrp->numroutes; |
| 440 |
int degree; /*partial degree of depot in the component */ |
| 441 |
int position = 0; |
| 442 |
int minroutes_other_comps; |
| 443 |
double weight, weight_uncovered; |
| 444 |
int cost = MAXINT, num_edges_can_double = 0, total_demand = vrp->demand[0]; |
| 445 |
#ifdef NO_LIFTING |
| 446 |
int varnum = vrp->vertnum*(vrp->vertnum-1)/2; |
| 447 |
|
| 448 |
memset(lp_data->rhs, 0, varnum * DSIZE); |
| 449 |
#endif |
| 450 |
|
| 451 |
/* find out how many nodes in the component; how many edges */ |
| 452 |
node_num = compnodes[cur_comp]+1; |
| 453 |
row_num = 0; |
| 454 |
degree = 0; |
| 455 |
|
| 456 |
for (temp_edge = edges, i = 0; i < edgenum; i++, temp_edge++){ |
| 457 |
v0 = temp_edge->v0; |
| 458 |
v1 = temp_edge->v1; |
| 459 |
if (verts[v0].comp == cur_comp || verts[v1].comp == cur_comp){ |
| 460 |
/* edge is in the component */ |
| 461 |
if (!(v0 && v1)) degree++; /* edge is incident to depot */ |
| 462 |
if (temp_edge->can_be_doubled && !(verts[MAX(v0, v1)].deleted)) |
| 463 |
num_edges_can_double++; |
| 464 |
#ifdef NO_LIFTING |
| 465 |
temp_edge->row = INDEX(v0,v1); |
| 466 |
row_edges[row_num++] = temp_edge; |
| 467 |
lp_data->rhs[temp_edge->row] = temp_edge->weight; |
| 468 |
} |
| 469 |
} |
| 470 |
|
| 471 |
lp_data->rhs[varnum] = 1; |
| 472 |
#else |
| 473 |
temp_edge->row = row_num; |
| 474 |
row_edges[row_num] = temp_edge; |
| 475 |
lp_data->rhs[row_num++] = temp_edge->weight; |
| 476 |
} |
| 477 |
} |
| 478 |
|
| 479 |
lp_data->rhs[row_num++] = 1; |
| 480 |
lp_data->m = row_num; |
| 481 |
#endif |
| 482 |
lp_data->nz = 0; |
| 483 |
lp_data->n = 0; |
| 484 |
|
| 485 |
if (p->par.decomp_initial_timeout <= 0){ |
| 486 |
return(0); |
| 487 |
} |
| 488 |
|
| 489 |
low_tour_num = 1; |
| 490 |
high_tour_num = (vrp->par.allow_one_routes_in_bfm) ? |
| 491 |
(degree - num_edges_can_double)/2 + num_edges_can_double : degree/2; |
| 492 |
high_tour_num = MIN(high_tour_num, numroutes); |
| 493 |
if (vrp->par.feasible_tours_only){ |
| 494 |
minroutes_other_comps = |
| 495 |
BINS(total_demand - compdemands[cur_comp], vrp->capacity); |
| 496 |
high_tour_num = MIN(high_tour_num, numroutes - minroutes_other_comps); |
| 497 |
low_tour_num = BINS(compdemands[cur_comp], vrp->capacity); |
| 498 |
} |
| 499 |
if (num_comps == 1) low_tour_num = high_tour_num = numroutes; |
| 500 |
|
| 501 |
#if 0 |
| 502 |
cost = vrp->par.feasible_tours_only ? |
| 503 |
p->ub - ceil(other_comps_cost) -.9999 : MAXINT; |
| 504 |
#endif |
| 505 |
|
| 506 |
intour = (int *) calloc(vrp->vertnum, sizeof(int)); |
| 507 |
tour = (int *) calloc(size+1, sizeof(int)); |
| 508 |
cur_edge = verts[0].first; |
| 509 |
stack = (edge **) malloc(verts[0].degree*sizeof(edge *)); |
| 510 |
|
| 511 |
#if 0 |
| 512 |
while(cur_edge &&cur_edge->data->weight == 2 && |
| 513 |
verts[cur_edge->other_end].comp == cur_comp){ |
| 514 |
intour[0]++; |
| 515 |
intour[cur_edge->other_end+numroutes]++; |
| 516 |
tour[count] = cur_edge->other_end+numroutes; |
| 517 |
tour[cur_edge->other_end+numroutes]=++count; |
| 518 |
cur_edge->data->deleted = 1; |
| 519 |
stack[position++] = cur_edge->data; |
| 520 |
cur_edge = cur_edge->next_edge; |
| 521 |
cost -= cur_edge->data->cost; |
| 522 |
} |
| 523 |
#endif |
| 524 |
weight = 0; |
| 525 |
weight_uncovered = compdemands[cur_comp]; |
| 526 |
|
| 527 |
if (p->par.decomp_dynamic_timeout > 0){ |
| 528 |
lp_data->maxn = 10; |
| 529 |
} |
| 530 |
|
| 531 |
p->dcmp_data.timeout = time(NULL); |
| 532 |
|
| 533 |
*generated_all_columns = bfm(p, 0, intour, tour, stack, position, |
| 534 |
low_tour_num, high_tour_num, cur_comp, |
| 535 |
&weight, &weight_uncovered, &cost); |
| 536 |
|
| 537 |
lp_data->maxn = vrp->par.max_num_columns; |
| 538 |
#if 0 |
| 539 |
if (BINS(compdemands[cur_comp], vrp->capacity) + |
| 540 |
BINS(other_comps_demand, vrp->capacity) == vrp->numroutes){ |
| 541 |
*generated_all_columns = bfm(p, 0, intour, tour, stack, position, |
| 542 |
low_tour_num, high_tour_num, cur_comp, |
| 543 |
&weight, &weight_uncovered, &cost); |
| 544 |
}else{ |
| 545 |
*generated_all_columns = 0; |
| 546 |
} |
| 547 |
#endif |
| 548 |
|
| 549 |
if (*generated_all_columns){ |
| 550 |
printf(" Time used : %ld \n", ( time(NULL) - p->dcmp_data.timeout)); |
| 551 |
#if 0 |
| 552 |
fprintf(vrp->decomp_res," Time used : %d \n", |
| 553 |
(time(NULL) - p->dcmp_data.timeout)); |
| 554 |
#endif |
| 555 |
} |
| 556 |
FREE(tour); |
| 557 |
FREE(intour); |
| 558 |
FREE(stack); |
| 559 |
|
| 560 |
if (!lp_data->n) |
| 561 |
return(0); |
| 562 |
lp_data->matbeg[lp_data->n]=lp_data->nz; |
| 563 |
|
| 564 |
/*load_decomp_lp*/ |
| 565 |
cpx_status = CPXsetintparam(lp_data->cpxenv, CPX_PARAM_SCAIND, -1); |
| 566 |
cpx_status = |
| 567 |
CPXsetintparam(lp_data->cpxenv, CPX_PARAM_BASINTERVAL, 2100000000); |
| 568 |
cpx_status = CPXsetintparam(lp_data->cpxenv, CPX_PARAM_AGGIND, 0); |
| 569 |
cpx_status = CPXsetintparam(lp_data->cpxenv, CPX_PARAM_DEPIND, 0); |
| 570 |
cpx_status = CPXsetintparam(lp_data->cpxenv, CPX_PARAM_PREIND, 0); |
| 571 |
#if 0 |
| 572 |
cpx_status = CPXsetintparam(lp_data->cpxenv, CPX_PARAM_REINV, 1); |
| 573 |
#endif |
| 574 |
|
| 575 |
CPX_check_error("load_lp - CPXsetintparam"); |
| 576 |
|
| 577 |
p->dcmp_data.iter_num = 0; |
| 578 |
|
| 579 |
#if 0 |
| 580 |
|
| 581 |
lp_data->lp = CPXcreateprob(lp_data->cpxenv, &cpx_status, "Decomp prob"); |
| 582 |
|
| 583 |
cpx_status = CPXcopylp(lp_data->cpxenv, lp_data->lp, lp_data->n, |
| 584 |
lp_data->m, 1, lp_data->obj, lp_data->rhs, |
| 585 |
lp_data->sense, lp_data->matbeg, lp_data->matcnt, |
| 586 |
lp_data->matind, lp_data->matval, lp_data->lb, |
| 587 |
lp_data->ub, lp_data->rngval); |
| 588 |
#endif |
| 589 |
|
| 590 |
lp_data->lp = |
| 591 |
CPXloadlp(lp_data->cpxenv, |
| 592 |
(char *) "Decomp_prob", lp_data->n, lp_data->m, 1, |
| 593 |
lp_data->obj, |
| 594 |
lp_data->rhs, lp_data->sense, lp_data->matbeg, lp_data->matcnt, |
| 595 |
lp_data->matind, lp_data->matval, lp_data->lb, lp_data->ub, |
| 596 |
lp_data->rngval, lp_data->maxn+lp_data->maxm, lp_data->maxm, |
| 597 |
lp_data->maxnz+lp_data->maxm); |
| 598 |
|
| 599 |
#if 0 |
| 600 |
cpx_status = CPXchecklp(lp_data->cpxenv, |
| 601 |
(char *) "Decomp_prob", lp_data->n, lp_data->m, 1, |
| 602 |
lp_data->obj, |
| 603 |
lp_data->rhs, lp_data->sense, lp_data->matbeg, lp_data->matcnt, |
| 604 |
lp_data->matind, lp_data->matval, lp_data->lb, lp_data->ub, |
| 605 |
lp_data->rngval, lp_data->maxn+lp_data->maxm, lp_data->maxm, |
| 606 |
lp_data->maxnz+lp_data->maxm); |
| 607 |
#endif |
| 608 |
|
| 609 |
return(lp_data->n); |
| 610 |
} |
| 611 |
|
| 612 |
/*===========================================================================*/ |
| 613 |
|
| 614 |
int origind_compar(const void *origind1, const void *origind2) |
| 615 |
{ |
| 616 |
return((*((int *)origind1)) - (*((int *)origind2))); |
| 617 |
} |
| 618 |
|
| 619 |
/*===========================================================================*/ |
| 620 |
/*This is the brute force enumerator. Does depth-first search of the support |
| 621 |
graph. */ |
| 622 |
|
| 623 |
char bfm(cg_prob *p, int cur_node, int *intour, int *tour, edge **stack, |
| 624 |
int position,int low_tour_num, int high_tour_num, int cur_comp, |
| 625 |
double *weight, double *weight_uncovered, int *cost) |
| 626 |
{ |
| 627 |
cg_vrp_spec *vrp = (cg_vrp_spec *)(p->user); |
| 628 |
int numroutes = vrp->numroutes, vertnum = vrp->vertnum; |
| 629 |
vertex *verts = vrp->n->verts; |
| 630 |
int capacity = vrp->capacity; |
| 631 |
int i, count=0; |
| 632 |
elist *cur_edge; |
| 633 |
edge *edge_data; |
| 634 |
int other_end; |
| 635 |
int *pt; |
| 636 |
double wt; |
| 637 |
double wt_un = 0; |
| 638 |
int cost_copy; |
| 639 |
int aux; |
| 640 |
double *new_demand =vrp->n->new_demand; |
| 641 |
|
| 642 |
if (time(NULL) - p->dcmp_data.timeout > p->par.decomp_initial_timeout) |
| 643 |
return(FALSE); |
| 644 |
|
| 645 |
if (cur_node==0 && intour[0] >= low_tour_num && intour[0] <= high_tour_num){ |
| 646 |
for (i = 0, pt = intour ; i < vertnum; i++){ |
| 647 |
if (*pt++==FALSE && (verts[i].comp==cur_comp) && !(verts[i].deleted)) |
| 648 |
break; |
| 649 |
} |
| 650 |
|
| 651 |
if (i == vertnum ){ |
| 652 |
#if 0 |
| 653 |
printf("found a column\n"); |
| 654 |
j=0; |
| 655 |
while( tour[j] ){ |
| 656 |
printf("%d ", (tour[j] > numroutes? tour[j]-numroutes:0)); |
| 657 |
j=tour[j]; |
| 658 |
} |
| 659 |
|
| 660 |
printf("\n"); |
| 661 |
#endif |
| 662 |
|
| 663 |
if (add_tour_to_col_set(p, tour, vrp, vrp->n->compnodes[cur_comp] + 1, |
| 664 |
vrp->n)){ |
| 665 |
return(TRUE); |
| 666 |
}else{ |
| 667 |
return(FALSE); |
| 668 |
} |
| 669 |
} |
| 670 |
if (intour[0]==high_tour_num ) |
| 671 |
return(TRUE); |
| 672 |
|
| 673 |
if (time(NULL) - p->dcmp_data.timeout > p->par.decomp_initial_timeout |
| 674 |
/* || cols->num_cols == p->par.max_col_num_per_iter */) |
| 675 |
return(FALSE); |
| 676 |
|
| 677 |
} |
| 678 |
|
| 679 |
|
| 680 |
wt = *weight; |
| 681 |
if (vrp->par.feasible_tours_only){ |
| 682 |
if (!cur_node){ |
| 683 |
wt_un = *weight_uncovered; |
| 684 |
*weight_uncovered -=wt; |
| 685 |
*weight = 0; |
| 686 |
}else{ |
| 687 |
*weight=wt+verts[cur_node].demand+ new_demand[cur_node]; |
| 688 |
} |
| 689 |
if ((cur_node) ? (*weight > capacity): |
| 690 |
(BINS(*weight_uncovered, capacity) > high_tour_num - intour[0])){ |
| 691 |
*weight = wt; |
| 692 |
if (!cur_node) *weight_uncovered = wt_un; |
| 693 |
return(TRUE); |
| 694 |
} |
| 695 |
} |
| 696 |
cost_copy = *cost; |
| 697 |
intour[cur_node]++; |
| 698 |
|
| 699 |
if (cur_node){ |
| 700 |
for (cur_edge = verts[cur_node].first; cur_edge; |
| 701 |
cur_edge = cur_edge->next_edge) |
| 702 |
if (vrp->par.follow_one_edges && cur_edge->data->weight == 1){ |
| 703 |
other_end = cur_edge->other_end; |
| 704 |
if ((!other_end) |
| 705 |
&& (!vrp->par.allow_one_routes_in_bfm || cur_edge->superlink |
| 706 |
|| !cur_edge->data->can_be_doubled) |
| 707 |
&& !(cur_node+numroutes == tour[intour[0]-1])){ |
| 708 |
/*we haven't arrived from the depot */ |
| 709 |
/* we got to go to depot now */ |
| 710 |
if (cur_edge->data->deleted){ |
| 711 |
intour[cur_node]--; |
| 712 |
*weight = wt; |
| 713 |
return(TRUE); |
| 714 |
} |
| 715 |
|
| 716 |
if ((aux = cost_copy - cur_edge->data->cost) < 0) { |
| 717 |
intour[cur_node]--; |
| 718 |
*weight = wt; |
| 719 |
return(TRUE); |
| 720 |
}else{ |
| 721 |
*cost = aux; |
| 722 |
} |
| 723 |
|
| 724 |
tour[cur_node+numroutes] = intour[0]; |
| 725 |
if (!bfm(p, other_end, intour, tour, stack, position, |
| 726 |
low_tour_num, high_tour_num, cur_comp, weight, |
| 727 |
weight_uncovered, cost)){ |
| 728 |
return(FALSE); |
| 729 |
}else{ |
| 730 |
intour[cur_node]--; |
| 731 |
*weight = wt; |
| 732 |
*cost = cost_copy; |
| 733 |
return(TRUE); |
| 734 |
} |
| 735 |
|
| 736 |
} |
| 737 |
if (!(intour[other_end])){ |
| 738 |
if ((aux = cost_copy - cur_edge->data->cost) < 0) { |
| 739 |
intour[cur_node]--; |
| 740 |
*weight = wt; |
| 741 |
return(TRUE); |
| 742 |
}else{ |
| 743 |
*cost = aux; |
| 744 |
} |
| 745 |
tour[cur_node+numroutes] = other_end + numroutes; |
| 746 |
if (!bfm(p, other_end, intour, tour, stack, position, |
| 747 |
low_tour_num, high_tour_num, cur_comp, weight, |
| 748 |
weight_uncovered, cost)){ |
| 749 |
return(FALSE); |
| 750 |
}else{ |
| 751 |
intour[cur_node]--; |
| 752 |
*cost = cost_copy; |
| 753 |
*weight = wt; |
| 754 |
return(TRUE); |
| 755 |
} |
| 756 |
} |
| 757 |
}else{ |
| 758 |
break; |
| 759 |
} |
| 760 |
|
| 761 |
for (cur_edge = verts[cur_node].first; cur_edge; |
| 762 |
cur_edge = cur_edge->next_edge){ |
| 763 |
other_end = cur_edge->other_end; |
| 764 |
if (!(other_end ? intour[other_end] : cur_edge->data->deleted)){ |
| 765 |
if ((aux = cost_copy - cur_edge->data->cost) < 0) { |
| 766 |
continue; |
| 767 |
}else{ |
| 768 |
*cost = aux; |
| 769 |
} |
| 770 |
tour[cur_node+numroutes] = other_end ? |
| 771 |
other_end + numroutes: intour[0]; |
| 772 |
if (!bfm(p, other_end, intour, tour, stack, position, |
| 773 |
low_tour_num, high_tour_num, cur_comp, weight, |
| 774 |
weight_uncovered, cost)) |
| 775 |
return(FALSE); |
| 776 |
} |
| 777 |
} |
| 778 |
|
| 779 |
}else{ |
| 780 |
for (cur_edge = verts[cur_node].first; cur_edge; |
| 781 |
cur_edge = cur_edge->next_edge){ |
| 782 |
other_end = cur_edge->other_end; |
| 783 |
edge_data = cur_edge->data; |
| 784 |
if (verts[other_end].comp == cur_comp && !(intour[other_end]) |
| 785 |
&& !(edge_data->deleted)){ |
| 786 |
if ((aux = cost_copy - edge_data->cost) < 0) { |
| 787 |
continue; |
| 788 |
}else{ |
| 789 |
*cost = aux; |
| 790 |
} |
| 791 |
|
| 792 |
tour[intour[0]-1] = other_end + numroutes; |
| 793 |
if (!vrp->par.allow_one_routes_in_bfm || cur_edge->superlink |
| 794 |
|| !cur_edge->data->can_be_doubled){ |
| 795 |
edge_data->deleted = 1; |
| 796 |
if (cur_edge->superlink) edge_data->other_data->deleted = 1; |
| 797 |
} |
| 798 |
if (!bfm(p, other_end, intour, tour, stack, position, |
| 799 |
low_tour_num, high_tour_num, cur_comp, weight, |
| 800 |
weight_uncovered, cost)) |
| 801 |
return(FALSE); |
| 802 |
edge_data->deleted= 1; |
| 803 |
if (cur_edge->superlink) edge_data->other_data->deleted = 1; |
| 804 |
stack[position++] = edge_data; |
| 805 |
count++; |
| 806 |
} |
| 807 |
} |
| 808 |
for (i = 0;i < count; i++){ |
| 809 |
(stack[--position])->deleted = 0; |
| 810 |
if ((stack[position])->other_data) |
| 811 |
(stack[position])->other_data->deleted = 0; |
| 812 |
} |
| 813 |
*weight_uncovered = wt_un; |
| 814 |
} |
| 815 |
intour[cur_node]--; |
| 816 |
*weight=wt; |
| 817 |
*cost=cost_copy; |
| 818 |
return(TRUE); |
| 819 |
|
| 820 |
} |
| 821 |
|
| 822 |
/*===========================================================================*/ |
| 823 |
/*This is called after fnding a feasible tour, i.e., a potential column, to |
| 824 |
chenge the tour into the column and add it to the column set. */ |
| 825 |
|
| 826 |
char add_tour_to_col_set(cg_prob *p, int *tour, cg_vrp_spec *vrp, int node_num, |
| 827 |
network *net ) |
| 828 |
{ LPdata *lp_data = p->dcmp_data.lp_data; |
| 829 |
double *matval = lp_data->matval; |
| 830 |
int *matind = lp_data->matind; |
| 831 |
int num_routes = vrp->numroutes; |
| 832 |
int cur_node, next_node = 0, next_true_node, cur_true_node; |
| 833 |
int m, n, nz, node_count, count; |
| 834 |
vertex *verts = net->verts; |
| 835 |
elist *e; |
| 836 |
int j; |
| 837 |
|
| 838 |
m = lp_data->m; |
| 839 |
n = lp_data->n; |
| 840 |
nz = lp_data->nz; |
| 841 |
count = 0; |
| 842 |
node_count = 0; |
| 843 |
cur_node=0; |
| 844 |
|
| 845 |
lp_data->lb[n] = 0; |
| 846 |
lp_data->ub[n] = CPX_INFBOUND; |
| 847 |
lp_data->obj[n] = 0; |
| 848 |
lp_data->matbeg[n] = nz; |
| 849 |
|
| 850 |
|
| 851 |
/* node_num is the number of nodes in the component +1, i.e, the depot */ |
| 852 |
|
| 853 |
while (node_count < node_num - 1){ |
| 854 |
cur_true_node = (cur_node > num_routes ) ? cur_node - num_routes : 0; |
| 855 |
if (cur_true_node) node_count++; |
| 856 |
if (node_count == node_num-1){ |
| 857 |
next_true_node = 0; |
| 858 |
}else{ |
| 859 |
next_node = tour[cur_node]; |
| 860 |
next_true_node = (next_node > num_routes) ? next_node - num_routes: 0; |
| 861 |
} |
| 862 |
|
| 863 |
for ( e = verts[cur_true_node].first; e; e = e->next_edge){ |
| 864 |
if (e->other_end == next_true_node){ |
| 865 |
if (!(e->superlink)){ |
| 866 |
if (nz && e->data->row == matind[nz-1]){ |
| 867 |
/* returning to depot immediately */ |
| 868 |
matval[nz-1] = 2; |
| 869 |
break; |
| 870 |
}else{ |
| 871 |
matval[nz] = 1; |
| 872 |
matind[nz++] = e->data->row; |
| 873 |
count++; |
| 874 |
break; |
| 875 |
} |
| 876 |
}else{ /* we are following a 1-path */ |
| 877 |
for (j = 0; j < e->edgenum; j++){ |
| 878 |
matval[nz] = 1; |
| 879 |
matind[nz++] = ((e->edges)[j])->row; |
| 880 |
count++; |
| 881 |
} |
| 882 |
node_count += e->edgenum - 1; |
| 883 |
break; |
| 884 |
} |
| 885 |
} |
| 886 |
} |
| 887 |
cur_node = next_node; |
| 888 |
} |
| 889 |
/* take care of the last row */ |
| 890 |
matval[nz] = 1; |
| 891 |
matind[nz++] = m - 1; |
| 892 |
count++; |
| 893 |
|
| 894 |
lp_data->nz = nz; |
| 895 |
lp_data->matcnt[n] = count; |
| 896 |
lp_data->n++; |
| 897 |
|
| 898 |
/* if (p->par.verbosity > 4 && vrp->dg_id) |
| 899 |
display_part_tour(vrp->dg_id, TRUE, (char *)"Partial Decomp Tour", |
| 900 |
tour, numroutes, CTOI_WAIT_FOR_CLICK_AND_REPORT);*/ |
| 901 |
|
| 902 |
if (n == lp_data->maxn-1) |
| 903 |
return(FALSE); |
| 904 |
else |
| 905 |
return(TRUE); |
| 906 |
} |
| 907 |
|
| 908 |
/*===========================================================================*/ |
| 909 |
|
| 910 |
void usr_open_decomp_lp(cg_prob *p, int varnum) |
| 911 |
{ |
| 912 |
cg_vrp_spec *vrp = (cg_vrp_spec *)(p->user); |
| 913 |
LPdata *lp_data; |
| 914 |
int maxn, maxm, maxnz, i; |
| 915 |
|
| 916 |
lp_data = p->dcmp_data.lp_data = (LPdata *) calloc (1, sizeof(LPdata)); |
| 917 |
|
| 918 |
#ifndef COMPILE_IN_CG |
| 919 |
open_lp_solver(lp_data); |
| 920 |
#endif |
| 921 |
|
| 922 |
maxm = lp_data->maxm = lp_data->m = varnum + 1; |
| 923 |
maxn = lp_data->maxn = vrp->par.max_num_columns; |
| 924 |
maxnz = lp_data->maxnz = lp_data->maxn*lp_data->maxm; |
| 925 |
|
| 926 |
lp_data->rhs = (double *) calloc(maxm, sizeof(double)); |
| 927 |
lp_data->sense = (char *) calloc(maxm, sizeof(char)); |
| 928 |
lp_data->lb = (double *) calloc(maxn + maxm, sizeof(double)); |
| 929 |
lp_data->ub = (double *) calloc(maxn + maxm, sizeof(double)); |
| 930 |
lp_data->obj = (double *) calloc(maxn + maxm, sizeof(double)); |
| 931 |
lp_data->x = (double *) calloc(maxn, sizeof(double)); |
| 932 |
lp_data->matbeg = (int *) calloc(maxn + maxm + 1, sizeof(int)); |
| 933 |
lp_data->matval = (double *) calloc(maxnz + maxm, sizeof(double)); |
| 934 |
lp_data->matind = (int *) calloc(maxnz + maxm, sizeof(int)); |
| 935 |
lp_data->matcnt = (int *) calloc(maxn + maxm + 1, sizeof(int)); |
| 936 |
lp_data->dj = (double *) calloc(maxn, sizeof(int)); |
| 937 |
|
| 938 |
/*p->dcmp_data.unbdd_row = (double *) calloc (maxm, sizeof(double)); */ |
| 939 |
|
| 940 |
for (i = 0; i < maxm; i++) |
| 941 |
lp_data->sense[i] = 'E'; |
| 942 |
|
| 943 |
lp_data->lp_is_modified = LP_HAS_NOT_BEEN_MODIFIED; |
| 944 |
} |
| 945 |
|
| 946 |
/*===========================================================================*/ |
| 947 |
/*Try to generate cuts based on a decomposition */ |
| 948 |
|
| 949 |
int vrp_generate_cuts(cg_prob *p, network *n, int cur_comp, edge **row_edges, |
| 950 |
int generate_cuts) |
| 951 |
{ |
| 952 |
LPdata *lp_data = p->dcmp_data.lp_data; |
| 953 |
double *x = lp_data->x; |
| 954 |
int i, num_cols = 0, pos_cols = 0; |
| 955 |
|
| 956 |
get_x(lp_data); |
| 957 |
|
| 958 |
for (i = 0; i < lp_data->n; i++){ |
| 959 |
if (x[i] > 0){ |
| 960 |
pos_cols++; |
| 961 |
if (generate_cuts) |
| 962 |
num_cols += vrp_check_col(p, lp_data->matind + lp_data->matbeg[i], |
| 963 |
lp_data->matval + lp_data->matbeg[i], |
| 964 |
lp_data->matbeg[i+1] - |
| 965 |
lp_data->matbeg[i] - 1, n, |
| 966 |
cur_comp,row_edges ); |
| 967 |
/* the last entry is the last row |
| 968 |
is not an edge */ |
| 969 |
|
| 970 |
} |
| 971 |
} |
| 972 |
printf("There are %i columns at nonzero level\n", pos_cols); |
| 973 |
return(num_cols); |
| 974 |
} |
| 975 |
|
| 976 |
/*===========================================================================*/ |
| 977 |
/* Check a column to see if it violates any inequalities */ |
| 978 |
|
| 979 |
int vrp_check_col(cg_prob *p, int *colind, double *colval, int collen, |
| 980 |
network *n, int cur_comp, edge **row_edges) |
| 981 |
{ |
| 982 |
cg_vrp_spec *vrp = (cg_vrp_spec *)p->user; |
| 983 |
int capacity = vrp->capacity, *demand = vrp->demand, vertnum = vrp->vertnum; |
| 984 |
int j, weight = 0, reduced_weight, num_cuts = 0; |
| 985 |
double set_fract_weight = 0, reduced_fract_weight; |
| 986 |
double *new_demand = n->new_demand, *fract_weight; |
| 987 |
int cut_size = (vrp->vertnum >> DELETE_POWER) +1; |
| 988 |
elist *e, *e1; |
| 989 |
vertex *verts = n->verts, *col_verts; |
| 990 |
int cur_vert = 0, next_vert, prev_vert, max_vert, vert1, vert2, *route; |
| 991 |
int cust_num = 0, reduced_cust_num; |
| 992 |
edge *cur_edge, *true_edge; |
| 993 |
cut_data *new_cut; |
| 994 |
char *in_set; |
| 995 |
network *col_net; |
| 996 |
double lpetol = p->cur_sol.lpetol, max_val; |
| 997 |
|
| 998 |
#ifndef NO_LIFTING |
| 999 |
int *new_ind = (int *) malloc(collen * ISIZE), i; |
| 1000 |
|
| 1001 |
for (i = 0; i < collen; i++) |
| 1002 |
new_ind[i] = INDEX(row_edges[colind[i]]->v0, row_edges[colind[i]]->v1); |
| 1003 |
col_net = createnet(new_ind, colval, collen, lpetol, vrp->edges, demand, |
| 1004 |
vertnum); |
| 1005 |
#else |
| 1006 |
col_net = createnet(colind, colval, collen, lpetol, vrp->edges, demand, |
| 1007 |
vertnum); |
| 1008 |
#endif |
| 1009 |
col_verts = col_net->verts; |
| 1010 |
|
| 1011 |
new_cut = (cut_data *) calloc(1, sizeof(cut_data)); |
| 1012 |
new_cut->size = cut_size; |
| 1013 |
route = (int *) malloc(vertnum*ISIZE); |
| 1014 |
in_set = (char *) calloc(vertnum, sizeof(char)); |
| 1015 |
fract_weight = (double *) malloc(vertnum * sizeof(double)); |
| 1016 |
new_cut->coef = malloc(cut_size); |
| 1017 |
|
| 1018 |
for (cur_vert = 0, e = col_verts[0].first; e; e = e->next_edge){ |
| 1019 |
if (e->data->scanned) continue; |
| 1020 |
(cur_edge = e->data)->scanned = TRUE; |
| 1021 |
cur_vert = prev_vert = 0; |
| 1022 |
next_vert = cur_edge->v1; |
| 1023 |
weight = cust_num = 0; |
| 1024 |
set_fract_weight = 0; |
| 1025 |
memset(new_cut->coef, 0, cut_size); |
| 1026 |
memset(in_set, 0, vertnum); |
| 1027 |
route[0] = next_vert; |
| 1028 |
while(next_vert){ |
| 1029 |
in_set[next_vert] = TRUE; |
| 1030 |
cust_num++; |
| 1031 |
weight += demand[next_vert] + new_demand[next_vert]; |
| 1032 |
for (e1 = verts[next_vert].first; e1; e1 = e1->next_edge){ |
| 1033 |
if (!(e1->superlink)){ |
| 1034 |
if (in_set[e1->other_end]) set_fract_weight+= e1->data->weight; |
| 1035 |
}else{ |
| 1036 |
true_edge = e1->edges[0]; |
| 1037 |
if (in_set[(true_edge->v0 == next_vert) ? |
| 1038 |
true_edge->v1 : true_edge->v0]) |
| 1039 |
set_fract_weight += e1->data->weight; |
| 1040 |
} |
| 1041 |
|
| 1042 |
} |
| 1043 |
new_cut->coef[next_vert >> DELETE_POWER] |= |
| 1044 |
(1 << (next_vert & DELETE_AND)); |
| 1045 |
|
| 1046 |
if ((cust_num - set_fract_weight) < BINS(weight, capacity) - lpetol){ |
| 1047 |
new_cut->type = (cust_num < vertnum/2 ? |
| 1048 |
SUBTOUR_ELIM_SIDE: SUBTOUR_ELIM_ACROSS); |
| 1049 |
new_cut->rhs = (new_cut->type ==SUBTOUR_ELIM_SIDE ? |
| 1050 |
RHS(cust_num, weight, capacity): |
| 1051 |
2*BINS(weight, capacity)); |
| 1052 |
|
| 1053 |
num_cuts += cg_send_cut(new_cut); |
| 1054 |
vert1 = route[0]; |
| 1055 |
reduced_fract_weight = set_fract_weight; |
| 1056 |
reduced_cust_num = cust_num; |
| 1057 |
reduced_weight = weight; |
| 1058 |
while(TRUE){ |
| 1059 |
reduced_cust_num--; |
| 1060 |
reduced_weight -= demand[vert1] + new_demand[vert1]; |
| 1061 |
for (e1 = verts[vert1].first; e1; e1 = e1->next_edge){ |
| 1062 |
if (!(e1->superlink)){ |
| 1063 |
if (in_set[e1->other_end]) |
| 1064 |
reduced_fract_weight -= e1->data->weight; |
| 1065 |
}else{ |
| 1066 |
true_edge = e1->edges[0]; |
| 1067 |
if (in_set[(true_edge->v0 == next_vert) ? |
| 1068 |
true_edge->v1 : true_edge->v0]) |
| 1069 |
reduced_fract_weight -= e1->data->weight; |
| 1070 |
} |
| 1071 |
|
| 1072 |
} |
| 1073 |
|
| 1074 |
if ((reduced_cust_num - reduced_fract_weight) < |
| 1075 |
BINS(reduced_weight, capacity) -lpetol){ |
| 1076 |
in_set[vert1] = FALSE; |
| 1077 |
new_cut->coef[vert1 >> DELETE_POWER] &= |
| 1078 |
~(1 << (vert1 & DELETE_AND)); |
| 1079 |
new_cut->type = (reduced_cust_num < vertnum/2 ? |
| 1080 |
SUBTOUR_ELIM_SIDE: SUBTOUR_ELIM_ACROSS); |
| 1081 |
new_cut->rhs = (new_cut->type ==SUBTOUR_ELIM_SIDE ? |
| 1082 |
RHS(reduced_cust_num, reduced_weight, |
| 1083 |
capacity): |
| 1084 |
2*BINS(reduced_weight, capacity)); |
| 1085 |
|
| 1086 |
num_cuts += cg_send_cut(new_cut); |
| 1087 |
vert1 = route[vert1]; |
| 1088 |
}else{ |
| 1089 |
break; |
| 1090 |
} |
| 1091 |
} |
| 1092 |
vert2 = route[0]; |
| 1093 |
while (vert2 != vert1){ |
| 1094 |
in_set[vert2] = TRUE; |
| 1095 |
new_cut->coef[vert2 >> DELETE_POWER] |= |
| 1096 |
(1 << (vert2 & DELETE_AND)); |
| 1097 |
vert2 = route[vert2]; |
| 1098 |
} |
| 1099 |
} |
| 1100 |
prev_vert = cur_vert; |
| 1101 |
cur_vert = next_vert; |
| 1102 |
if (col_verts[cur_vert].first->other_end != prev_vert){ |
| 1103 |
cur_edge = col_verts[cur_vert].first->data; |
| 1104 |
next_vert = col_verts[cur_vert].first->other_end; |
| 1105 |
}else{ |
| 1106 |
cur_edge = col_verts[cur_vert].last->data; /*This statement could |
| 1107 |
possibly be taken out to |
| 1108 |
speed things up a bit*/ |
| 1109 |
next_vert = col_verts[cur_vert].last->other_end; |
| 1110 |
} |
| 1111 |
route[cur_vert] = next_vert; |
| 1112 |
} |
| 1113 |
if (weight > capacity && !num_cuts){ |
| 1114 |
cust_num = set_fract_weight = 0; |
| 1115 |
for (vert1 = route[0]; vert1; vert1 = route[vert1], cust_num = 0, |
| 1116 |
set_fract_weight = 0){ |
| 1117 |
memset(new_cut->coef, 0, cut_size); |
| 1118 |
memset(fract_weight, 0, vertnum * DSIZE); |
| 1119 |
fract_weight[vert1] = -1.0; |
| 1120 |
new_cut->coef[vert1 >> DELETE_POWER] |= |
| 1121 |
(1 << (vert1 & DELETE_AND)); |
| 1122 |
cust_num++; |
| 1123 |
for (e1 = verts[vert1].first; e1; e1 = e1->next_edge){ |
| 1124 |
if (!(e1->superlink)){ |
| 1125 |
if (in_set[e1->other_end]){ |
| 1126 |
fract_weight[e1->other_end] = e1->data->weight; |
| 1127 |
} |
| 1128 |
}else{ |
| 1129 |
true_edge = e1->edges[0]; |
| 1130 |
if (in_set[(true_edge->v0 == next_vert) ? |
| 1131 |
true_edge->v1 : true_edge->v0]){ |
| 1132 |
fract_weight[(true_edge->v0 == next_vert) ? |
| 1133 |
true_edge->v1 : true_edge->v0] = e1->data->weight; |
| 1134 |
} |
| 1135 |
} |
| 1136 |
} |
| 1137 |
weight = demand[vert1] + new_demand[vert1]; |
| 1138 |
while(TRUE){ |
| 1139 |
if ((cust_num - set_fract_weight) < |
| 1140 |
BINS(weight, capacity) - lpetol){ |
| 1141 |
new_cut->type = (cust_num < vertnum/2 ? |
| 1142 |
SUBTOUR_ELIM_SIDE:SUBTOUR_ELIM_ACROSS); |
| 1143 |
new_cut->rhs = (new_cut->type == SUBTOUR_ELIM_SIDE ? |
| 1144 |
RHS(cust_num, weight, capacity): |
| 1145 |
2*BINS(weight, capacity)); |
| 1146 |
num_cuts += cg_send_cut(new_cut); |
| 1147 |
} |
| 1148 |
for (max_val = 0, j = 1; j < vertnum; j++){ |
| 1149 |
if (fract_weight[j] > max_val){ |
| 1150 |
max_val = fract_weight[j]; |
| 1151 |
max_vert = j; |
| 1152 |
} |
| 1153 |
} |
| 1154 |
if (max_val > 0){ /* add the vertex to the set */ |
| 1155 |
new_cut->coef[max_vert >> DELETE_POWER] |= |
| 1156 |
(1 << (max_vert & DELETE_AND)); |
| 1157 |
cust_num++; |
| 1158 |
weight += demand[max_vert] + new_demand[max_vert]; |
| 1159 |
set_fract_weight += fract_weight[max_vert]; |
| 1160 |
fract_weight[max_vert] = -1.0; |
| 1161 |
for (e1 = verts[max_vert].first; e1; e1 = e1->next_edge){ |
| 1162 |
if (!(e1->superlink)){ |
| 1163 |
if (in_set[e1->other_end] && |
| 1164 |
fract_weight[e1->other_end] >= 0){ |
| 1165 |
fract_weight[e1->other_end] += e1->data->weight; |
| 1166 |
} |
| 1167 |
}else{ |
| 1168 |
true_edge = e1->edges[0]; |
| 1169 |
if (in_set[(true_edge->v0 == next_vert) ? |
| 1170 |
true_edge->v1 : true_edge->v0] && |
| 1171 |
fract_weight[(true_edge->v0 == next_vert) ? |
| 1172 |
true_edge->v1 : true_edge->v0] >= 0){ |
| 1173 |
fract_weight[(true_edge->v0 == next_vert) ? |
| 1174 |
true_edge->v1 : true_edge->v0] += |
| 1175 |
e1->data->weight; |
| 1176 |
} |
| 1177 |
} |
| 1178 |
} |
| 1179 |
}else{ /* can't add anything to the set */ |
| 1180 |
break; |
| 1181 |
} |
| 1182 |
} |
| 1183 |
} |
| 1184 |
} |
| 1185 |
cur_edge->scanned = TRUE; |
| 1186 |
} |
| 1187 |
FREE(in_set); |
| 1188 |
FREE(new_cut->coef); |
| 1189 |
FREE(new_cut); |
| 1190 |
return(num_cuts); |
| 1191 |
} |
| 1192 |
|
| 1193 |
/*===========================================================================*/ |
| 1194 |
|
| 1195 |
#if 0 |
| 1196 |
int vrp_check_col(cg_prob *p, int *colind, double *colval, int collen, |
| 1197 |
network *n, int cur_comp, edge **row_edges) |
| 1198 |
{ |
| 1199 |
cg_vrp_spec *vrp = (cg_vrp_spec *)p->user; |
| 1200 |
int capacity = vrp->capacity, *demand = vrp->demand, vertnum = vrp->vertnum; |
| 1201 |
int i, j, weight = 0, reduced_weight, num_cuts = 0; |
| 1202 |
double set_fract_weight = 0, reduced_fract_weight; |
| 1203 |
double *new_demand = n->new_demand, *fract_weight; |
| 1204 |
int cut_size = (vrp->vertnum >> DELETE_POWER) +1; |
| 1205 |
elist *e, *e1; |
| 1206 |
vertex *verts = n->verts, *col_verts; |
| 1207 |
int cur_vert = 0, next_vert, prev_vert, max_vert, vert1, vert2, *route; |
| 1208 |
int cust_num = 0, reduced_cust_num, *new_ind; |
| 1209 |
edge *cur_edge, *true_edge; |
| 1210 |
cut_data *new_cut; |
| 1211 |
char *in_set; |
| 1212 |
network *col_net; |
| 1213 |
double lpetol = p->cur_sol.lpetol, max_val; |
| 1214 |
|
| 1215 |
new_ind = (int *) malloc(collen * ISIZE); |
| 1216 |
for (i = 0; i < collen; i++) |
| 1217 |
new_ind[i] = INDEX(row_edges[colind[i]]->v0, row_edges[colind[i]]->v1); |
| 1218 |
col_net = createnet(new_ind, colval, collen, lpetol, vrp->edges, demand, |
| 1219 |
vertnum); |
| 1220 |
col_verts = col_net->verts; |
| 1221 |
|
| 1222 |
new_cut = (cut_data *) calloc(1, sizeof(cut_data)); |
| 1223 |
new_cut->size = cut_size; |
| 1224 |
route = (int *) malloc(vertnum*ISIZE); |
| 1225 |
in_set = (char *) calloc(vertnum, sizeof(char)); |
| 1226 |
fract_weight = (double *) malloc(vertnum * sizeof(double)); |
| 1227 |
new_cut->coef = malloc(cut_size); |
| 1228 |
|
| 1229 |
for (cur_vert = 0, e = col_verts[0].first; e; e = e->next_edge){ |
| 1230 |
if (e->data->scanned) continue; |
| 1231 |
(cur_edge = e->data)->scanned = TRUE; |
| 1232 |
cur_vert = prev_vert = 0; |
| 1233 |
next_vert = cur_edge->v1; |
| 1234 |
weight = cust_num = 0; |
| 1235 |
memset(in_set, 0, vertnum); |
| 1236 |
route[0] = next_vert; |
| 1237 |
while(next_vert){ |
| 1238 |
in_set[next_vert] = TRUE; |
| 1239 |
cust_num++; |
| 1240 |
weight += demand[next_vert] + new_demand[next_vert]; |
| 1241 |
prev_vert = cur_vert; |
| 1242 |
cur_vert = next_vert; |
| 1243 |
if (col_verts[cur_vert].first->other_end != prev_vert){ |
| 1244 |
cur_edge = col_verts[cur_vert].first->data; |
| 1245 |
next_vert = col_verts[cur_vert].first->other_end; |
| 1246 |
}else{ |
| 1247 |
cur_edge = col_verts[cur_vert].last->data; /*This statement could |
| 1248 |
possibly be taken out to |
| 1249 |
speed things up a bit*/ |
| 1250 |
next_vert = col_verts[cur_vert].last->other_end; |
| 1251 |
} |
| 1252 |
route[cur_vert] = next_vert; |
| 1253 |
} |
| 1254 |
if (weight > capacity){ |
| 1255 |
cust_num = set_fract_weight = 0; |
| 1256 |
for (vert1 = route[0]; vert1; vert1 = route[vert1], cust_num = 0, |
| 1257 |
set_fract_weight = 0){ |
| 1258 |
memset(new_cut->coef, 0, cut_size); |
| 1259 |
memset(fract_weight, 0, vertnum * DSIZE); |
| 1260 |
fract_weight[vert1] = -1.0; |
| 1261 |
new_cut->coef[vert1 >> DELETE_POWER] |= |
| 1262 |
(1 << (vert1 & DELETE_AND)); |
| 1263 |
cust_num++; |
| 1264 |
for (e1 = verts[vert1].first; e1; e1 = e1->next_edge){ |
| 1265 |
if (!(e1->superlink)){ |
| 1266 |
if (in_set[e1->other_end]){ |
| 1267 |
fract_weight[e1->other_end] = e1->data->weight; |
| 1268 |
} |
| 1269 |
}else{ |
| 1270 |
true_edge = e1->edges[0]; |
| 1271 |
if (in_set[(true_edge->v0 == next_vert) ? |
| 1272 |
true_edge->v1 : true_edge->v0]){ |
| 1273 |
fract_weight[(true_edge->v0 == next_vert) ? |
| 1274 |
true_edge->v1 : true_edge->v0] = e1->data->weight; |
| 1275 |
} |
| 1276 |
} |
| 1277 |
} |
| 1278 |
weight = demand[vert1] + new_demand[vert1]; |
| 1279 |
while(TRUE){ |
| 1280 |
if ((cust_num - set_fract_weight) < |
| 1281 |
BINS(weight, capacity) - lpetol){ |
| 1282 |
new_cut->type = (cust_num < vertnum/2 ? |
| 1283 |
SUBTOUR_ELIM_SIDE:SUBTOUR_ELIM_ACROSS); |
| 1284 |
new_cut->rhs = (new_cut->type == SUBTOUR_ELIM_SIDE ? |
| 1285 |
RHS(cust_num, weight, capacity): |
| 1286 |
2*BINS(weight, capacity)); |
| 1287 |
num_cuts += cg_send_cut(new_cut); |
| 1288 |
} |
| 1289 |
for (max_val = 0, j = 1; j < vertnum; j++){ |
| 1290 |
if (fract_weight[j] > max_val){ |
| 1291 |
max_val = fract_weight[j]; |
| 1292 |
max_vert = j; |
| 1293 |
} |
| 1294 |
} |
| 1295 |
if (max_val > 0){ /* add the vertex to the set */ |
| 1296 |
new_cut->coef[max_vert >> DELETE_POWER] |= |
| 1297 |
(1 << (max_vert & DELETE_AND)); |
| 1298 |
cust_num++; |
| 1299 |
weight += demand[max_vert] + new_demand[max_vert]; |
| 1300 |
set_fract_weight += fract_weight[max_vert]; |
| 1301 |
fract_weight[max_vert] = -1.0; |
| 1302 |
for (e1 = verts[max_vert].first; e1; e1 = e1->next_edge){ |
| 1303 |
if (!(e1->superlink)){ |
| 1304 |
if (in_set[e1->other_end] && |
| 1305 |
fract_weight[e1->other_end] >= 0){ |
| 1306 |
fract_weight[e1->other_end] += e1->data->weight; |
| 1307 |
} |
| 1308 |
}else{ |
| 1309 |
true_edge = e1->edges[0]; |
| 1310 |
if (in_set[(true_edge->v0 == next_vert) ? |
| 1311 |
true_edge->v1 : true_edge->v0] && |
| 1312 |
fract_weight[(true_edge->v0 == next_vert) ? |
| 1313 |
true_edge->v1 : true_edge->v0] >= 0){ |
| 1314 |
fract_weight[(true_edge->v0 == next_vert) ? |
| 1315 |
true_edge->v1 : true_edge->v0] += |
| 1316 |
e1->data->weight; |
| 1317 |
} |
| 1318 |
} |
| 1319 |
} |
| 1320 |
}else{ /* can't add anything to the set */ |
| 1321 |
break; |
| 1322 |
} |
| 1323 |
} |
| 1324 |
} |
| 1325 |
} |
| 1326 |
cur_edge->scanned = TRUE; |
| 1327 |
} |
| 1328 |
FREE(in_set); |
| 1329 |
FREE(new_cut->coef); |
| 1330 |
FREE(new_cut); |
| 1331 |
return(num_cuts); |
| 1332 |
} |
| 1333 |
#endif |
| 1334 |
|
| 1335 |
/*===========================================================================*/ |
| 1336 |
|
| 1337 |
#if 0 |
| 1338 |
int find_sets(double set_fract_weight, int cust_num, char *in_set, int *route, |
| 1339 |
int vert, int num_cuts, int capacity, int *demand, |
| 1340 |
int *new_demand, int weight, double lpetol, cut_data *new_cut, |
| 1341 |
int vertnum, vertex* verts) |
| 1342 |
{ |
| 1343 |
int next_vert = route[vert]; |
| 1344 |
int vert1; |
| 1345 |
elist *e; |
| 1346 |
edge *true_edge; |
| 1347 |
double temp_fract_weight = 0; |
| 1348 |
|
| 1349 |
if (!next_vert) return(num_cuts); |
| 1350 |
|
| 1351 |
in_set[next_vert] = TRUE; |
| 1352 |
cust_num++; |
| 1353 |
weight += demand[next_vert] + new_demand[next_vert]; |
| 1354 |
new_cut->coef[next_vert >> DELETE_POWER] |= |
| 1355 |
(1 << (next_vert & DELETE_AND)); |
| 1356 |
for (e = verts[next_vert].first; e; e = e->next_edge){ |
| 1357 |
if (!(e->superlink)){ |
| 1358 |
if (in_set[e->other_end]){ |
| 1359 |
temp_fract_weight += e->data->weight; |
| 1360 |
} |
| 1361 |
}else{ |
| 1362 |
true_edge = e->edges[0]; |
| 1363 |
if (in_set[(true_edge->v0 == next_vert) ? |
| 1364 |
true_edge->v1 : true_edge->v0]){ |
| 1365 |
temp_fract_weight += e->data->weight; |
| 1366 |
} |
| 1367 |
} |
| 1368 |
} |
| 1369 |
set_fract_weight += temp_fract_weight; |
| 1370 |
if ((cust_num - set_fract_weight) < |
| 1371 |
BINS(weight, capacity) - lpetol){ |
| 1372 |
new_cut->type = (cust_num < vertnum/2 ? |
| 1373 |
SUBTOUR_ELIM_SIDE:SUBTOUR_ELIM_ACROSS); |
| 1374 |
new_cut->rhs = (new_cut->type == SUBTOUR_ELIM_SIDE ? |
| 1375 |
RHS(cust_num, weight, capacity): |
| 1376 |
2*BINS(weight, capacity)); |
| 1377 |
num_cuts += cg_send_cut(new_cut); |
| 1378 |
} |
| 1379 |
num_cuts = find_sets(set_fract_weight, cust_num, in_set, route, next_vert, |
| 1380 |
num_cuts, capacity, demand, new_demand, weight, |
| 1381 |
lpetol, new_cut, vertnum, verts); |
| 1382 |
in_set[next_vert] = FALSE; |
| 1383 |
cust_num--; |
| 1384 |
weight -= demand[next_vert] + new_demand[next_vert]; |
| 1385 |
set_fract_weight -= temp_fract_weight; |
| 1386 |
new_cut->coef[next_vert >> DELETE_POWER] &= |
| 1387 |
~(1 << (next_vert & DELETE_AND)); |
| 1388 |
num_cuts = find_sets(set_fract_weight, cust_num, in_set, route, next_vert, |
| 1389 |
num_cuts, capacity, demand, new_demand, weight, |
| 1390 |
lpetol, new_cut, vertnum, verts); |
| 1391 |
return(num_cuts); |
| 1392 |
} |
| 1393 |
|
| 1394 |
/*===========================================================================*/ |
| 1395 |
|
| 1396 |
int vrp_check_col(cg_prob *p, int *colind, double *colval, int collen, |
| 1397 |
network *n, int cur_comp, edge **row_edges) |
| 1398 |
{ |
| 1399 |
cg_vrp_spec *vrp = (cg_vrp_spec *)p->user; |
| 1400 |
int capacity = vrp->capacity, *demand = vrp->demand, vertnum = vrp->vertnum; |
| 1401 |
int i, j, weight = 0, reduced_weight, num_cuts = 0; |
| 1402 |
double set_fract_weight = 0, reduced_fract_weight; |
| 1403 |
double *new_demand = n->new_demand, *fract_weight; |
| 1404 |
int cut_size = (vrp->vertnum >> DELETE_POWER) +1; |
| 1405 |
elist *e, *e1; |
| 1406 |
vertex *verts = n->verts, *col_verts; |
| 1407 |
int cur_vert = 0, next_vert, prev_vert, max_vert, vert1, vert2, *route; |
| 1408 |
int cust_num = 0, reduced_cust_num, *new_ind; |
| 1409 |
edge *cur_edge, *true_edge; |
| 1410 |
cut_data *new_cut; |
| 1411 |
char *in_set; |
| 1412 |
network *col_net; |
| 1413 |
double lpetol = p->cur_sol.lpetol, max_val; |
| 1414 |
|
| 1415 |
new_ind = (int *) malloc(collen * ISIZE); |
| 1416 |
for (i = 0; i < collen; i++) |
| 1417 |
new_ind[i] = INDEX(row_edges[colind[i]]->v0, row_edges[colind[i]]->v1); |
| 1418 |
col_net = createnet(new_ind, colval, collen, lpetol, vrp->edges, demand, |
| 1419 |
vertnum); |
| 1420 |
col_verts = col_net->verts; |
| 1421 |
|
| 1422 |
new_cut = (cut_data *) calloc(1, sizeof(cut_data)); |
| 1423 |
new_cut->size = cut_size; |
| 1424 |
route = (int *) malloc(vertnum*ISIZE); |
| 1425 |
in_set = (char *) calloc(vertnum, sizeof(char)); |
| 1426 |
fract_weight = (double *) malloc(vertnum * sizeof(double)); |
| 1427 |
new_cut->coef = calloc(cut_size, CSIZE); |
| 1428 |
|
| 1429 |
for (cur_vert = 0, e = col_verts[0].first; e; e = e->next_edge){ |
| 1430 |
if (e->data->scanned) continue; |
| 1431 |
(cur_edge = e->data)->scanned = TRUE; |
| 1432 |
cur_vert = prev_vert = 0; |
| 1433 |
next_vert = cur_edge->v1; |
| 1434 |
weight = cust_num = 0; |
| 1435 |
memset(in_set, 0, vertnum); |
| 1436 |
route[0] = next_vert; |
| 1437 |
while(next_vert){ |
| 1438 |
in_set[next_vert] = TRUE; |
| 1439 |
cust_num++; |
| 1440 |
weight += demand[next_vert] + new_demand[next_vert]; |
| 1441 |
prev_vert = cur_vert; |
| 1442 |
cur_vert = next_vert; |
| 1443 |
if (col_verts[cur_vert].first->other_end != prev_vert){ |
| 1444 |
cur_edge = col_verts[cur_vert].first->data; |
| 1445 |
next_vert = col_verts[cur_vert].first->other_end; |
| 1446 |
}else{ |
| 1447 |
cur_edge = col_verts[cur_vert].last->data; /*This statement could |
| 1448 |
possibly be taken out to |
| 1449 |
speed things up a bit*/ |
| 1450 |
next_vert = col_verts[cur_vert].last->other_end; |
| 1451 |
} |
| 1452 |
route[cur_vert] = next_vert; |
| 1453 |
} |
| 1454 |
memset(in_set, 0, vertnum); |
| 1455 |
if (weight > capacity){ |
| 1456 |
num_cuts += find_sets(0, 0, in_set, route, 0, 0, capacity, demand, |
| 1457 |
new_demand, 0, lpetol, new_cut, vertnum, |
| 1458 |
verts); |
| 1459 |
} |
| 1460 |
} |
| 1461 |
return(num_cuts); |
| 1462 |
} |
| 1463 |
|
| 1464 |
#endif |
| 1465 |
|
| 1466 |
/*===========================================================================*/ |
| 1467 |
|
| 1468 |
#if 0 |
| 1469 |
|
| 1470 |
int vrp_check_col(cg_prob *p, int *colind, double *colval, int collen, |
| 1471 |
network *n, int cur_comp, edge **row_edges) |
| 1472 |
{ |
| 1473 |
cg_vrp_spec *vrp = (cg_vrp_spec *)p->user; |
| 1474 |
int capacity = vrp->capacity, *demand = vrp->demand, vertnum = vrp->vertnum; |
| 1475 |
int i, j, weight = 0, reduced_weight, num_cuts = 0; |
| 1476 |
double fract_weight = 0, reduced_fract_weight, *new_demand = n->new_demand; |
| 1477 |
int cut_size = (vrp->vertnum >> DELETE_POWER) +1; |
| 1478 |
elist *e; |
| 1479 |
vertex *verts = n->verts; |
| 1480 |
int cur_vert = 0, next_vert, vert1, vert2, *route; |
| 1481 |
int cust_num = 0, reduced_cust_num; |
| 1482 |
edge *cur_edge, *true_edge; |
| 1483 |
cut_data *new_cut; |
| 1484 |
char *in_set; |
| 1485 |
|
| 1486 |
new_cut = (cut_data *) calloc(1, sizeof(cut_data)); |
| 1487 |
new_cut->size = cut_size; |
| 1488 |
route = (int *) malloc(vertnum*ISIZE); |
| 1489 |
in_set = (char *) calloc(vertnum, sizeof(char)); |
| 1490 |
new_cut->coef = malloc(cut_size); |
| 1491 |
|
| 1492 |
for (i = 0; i < collen; i++){ |
| 1493 |
if (colval[i]==2) continue ; |
| 1494 |
/* if the edge makes a one-customer route, ignore it */ |
| 1495 |
if (!cur_vert){ |
| 1496 |
/* start a new route */ |
| 1497 |
weight = cust_num = 0; |
| 1498 |
fract_weight = 0; |
| 1499 |
memset(new_cut->coef, 0, cut_size); |
| 1500 |
memset(in_set, 0, vertnum); |
| 1501 |
} |
| 1502 |
cur_edge = row_edges[colind[i]]; |
| 1503 |
next_vert = ((cur_vert == cur_edge->v0) ? cur_edge->v1 : cur_edge->v0); |
| 1504 |
route[cur_vert] = next_vert; |
| 1505 |
if (!next_vert){ |
| 1506 |
cur_vert = 0; |
| 1507 |
continue; |
| 1508 |
} |
| 1509 |
in_set[next_vert] = TRUE; |
| 1510 |
cust_num++; |
| 1511 |
weight += demand[next_vert] + new_demand[next_vert]; |
| 1512 |
for (e = verts[next_vert].first; e; e = e->next_edge){ |
| 1513 |
if (!(e->superlink)){ |
| 1514 |
if (in_set[e->other_end]) fract_weight+= e->data->weight; |
| 1515 |
}else{ |
| 1516 |
true_edge = e->edges[0]; |
| 1517 |
if (in_set[(true_edge->v0 == next_vert) ? |
| 1518 |
true_edge->v1 : true_edge->v0]) |
| 1519 |
fract_weight += e->data->weight; |
| 1520 |
} |
| 1521 |
|
| 1522 |
} |
| 1523 |
new_cut->coef[next_vert >> DELETE_POWER] |= |
| 1524 |
(1 << (next_vert & DELETE_AND)); |
| 1525 |
|
| 1526 |
if ((cust_num - fract_weight) < BINS(weight, capacity) ){ |
| 1527 |
new_cut->type = (cust_num < vertnum/2 ? |
| 1528 |
SUBTOUR_ELIM_SIDE: SUBTOUR_ELIM_ACROSS); |
| 1529 |
new_cut->rhs = (new_cut->type ==SUBTOUR_ELIM_SIDE ? |
| 1530 |
RHS(cust_num, weight, capacity): |
| 1531 |
2*BINS(weight, capacity)); |
| 1532 |
|
| 1533 |
num_cuts += cg_send_cut(new_cut); |
| 1534 |
vert1 = route[0]; |
| 1535 |
reduced_fract_weight = fract_weight; |
| 1536 |
reduced_cust_num = cust_num; |
| 1537 |
reduced_weight = weight; |
| 1538 |
while(TRUE){ |
| 1539 |
reduced_cust_num--; |
| 1540 |
reduced_weight -= demand[vert1] + new_demand[vert1]; |
| 1541 |
for (e = verts[vert1].first; e; e = e->next_edge){ |
| 1542 |
if (!(e->superlink)){ |
| 1543 |
if (in_set[e->other_end]) |
| 1544 |
reduced_fract_weight -= e->data->weight; |
| 1545 |
}else{ |
| 1546 |
true_edge = e->edges[0]; |
| 1547 |
if (in_set[(true_edge->v0 == next_vert) ? |
| 1548 |
true_edge->v1 : true_edge->v0]) |
| 1549 |
reduced_fract_weight -= e->data->weight; |
| 1550 |
} |
| 1551 |
|
| 1552 |
} |
| 1553 |
|
| 1554 |
if ((reduced_cust_num - reduced_fract_weight) < |
| 1555 |
BINS(reduced_weight, capacity) ){ |
| 1556 |
in_set[vert1] = FALSE; |
| 1557 |
new_cut->coef[vert1 >> DELETE_POWER] &= |
| 1558 |
~(1 << (vert1 & DELETE_AND)); |
| 1559 |
new_cut->type = (reduced_cust_num < vertnum/2 ? |
| 1560 |
SUBTOUR_ELIM_SIDE: SUBTOUR_ELIM_ACROSS); |
| 1561 |
new_cut->rhs = (new_cut->type ==SUBTOUR_ELIM_SIDE ? |
| 1562 |
RHS(reduced_cust_num, reduced_weight, capacity): |
| 1563 |
2*BINS(reduced_weight, capacity)); |
| 1564 |
|
| 1565 |
num_cuts += cg_send_cut(new_cut); |
| 1566 |
vert1 = route[vert1]; |
| 1567 |
}else{ |
| 1568 |
break; |
| 1569 |
} |
| 1570 |
} |
| 1571 |
vert2 = route[0]; |
| 1572 |
while (vert2 != vert1){ |
| 1573 |
in_set[vert2] = TRUE; |
| 1574 |
new_cut->coef[vert2 >> DELETE_POWER] |= |
| 1575 |
(1 << (vert2 & DELETE_AND)); |
| 1576 |
vert2 = route[vert2]; |
| 1577 |
} |
| 1578 |
} |
| 1579 |
cur_vert = next_vert; |
| 1580 |
} |
| 1581 |
FREE(in_set); |
| 1582 |
FREE(new_cut->coef); |
| 1583 |
FREE(new_cut); |
| 1584 |
return(num_cuts); |
| 1585 |
} |
| 1586 |
|
| 1587 |
#endif |
| 1588 |
|
| 1589 |
/*===========================================================================*/ |
| 1590 |
/*There are several different version of this routine depending on how the lifting of the Farkas inequalities is done */ |
| 1591 |
|
| 1592 |
#ifdef FARKAS_LIFT_SEQUENTIAL |
| 1593 |
|
| 1594 |
int generate_farkas_cuts(cg_prob *p, LPdata *lp_data, network *n, |
| 1595 |
edge **row_edges, int comp_num) |
| 1596 |
{ |
| 1597 |
cg_vrp_spec *vrp = (cg_vrp_spec *)p->user; |
| 1598 |
double *unbd_row; |
| 1599 |
int unbd_row_index, mult; |
| 1600 |
int i, j, k, num_arcs, equality, num_cuts = 0; |
| 1601 |
int vertnum = vrp->vertnum, v0, v1, index, adjust; |
| 1602 |
int *arcs, *head, *nonzeros, *sort_order; |
| 1603 |
double alpha, beta; |
| 1604 |
double *weights, *z, *soln; |
| 1605 |
vertex *verts = n->verts; |
| 1606 |
edge *cur_edge; |
| 1607 |
char *coef, *indicators; |
| 1608 |
double etol = p->cur_sol.lpetol, viol; |
| 1609 |
cut_data *new_cut; |
| 1610 |
double *costs; |
| 1611 |
#ifdef COMPILE_IN_CG |
| 1612 |
lp_prob *lp = get_lp_ptr(NULL); |
| 1613 |
LPdata *lp_data2 = lp->lp_data; |
| 1614 |
char *status = lp_data2->status; |
| 1615 |
#endif |
| 1616 |
|
| 1617 |
display_support_graph(vrp->dg_id, TRUE, "fractional graph", |
| 1618 |
p->cur_sol.xlength, p->cur_sol.xind, p->cur_sol.xval, |
| 1619 |
p->cur_sol.lpetol, FALSE); |
| 1620 |
|
| 1621 |
num_arcs = lp_data->m - 1; |
| 1622 |
|
| 1623 |
z = (double *) calloc( MAX(lp_data->m, lp_data->n), DSIZE); |
| 1624 |
soln = (double *) calloc(lp_data->m, DSIZE); |
| 1625 |
head = (int *) calloc(lp_data->m, ISIZE); |
| 1626 |
unbd_row = (double *) malloc(lp_data->m * DSIZE); |
| 1627 |
new_cut = (cut_data *) calloc(1, sizeof(cut_data)); |
| 1628 |
arcs = (int *) malloc(num_arcs * ISIZE); |
| 1629 |
indicators = (char *) calloc(num_arcs, sizeof(char)); |
| 1630 |
weights = (double *) malloc(vertnum*(vertnum - 1)/2 * DSIZE); |
| 1631 |
nonzeros = (int *) malloc(vertnum*(vertnum - 1)/2 * ISIZE); |
| 1632 |
|
| 1633 |
new_cut->type = GENERAL_NONZEROS; |
| 1634 |
new_cut->sense = 'G'; |
| 1635 |
new_cut->branch = DO_NOT_BRANCH_ON_THIS_ROW; |
| 1636 |
new_cut->name = CUT__DO_NOT_SEND_TO_CP; |
| 1637 |
|
| 1638 |
/* SETTING the coef, num_arcs, arcs */ |
| 1639 |
for (i = 0; i < num_arcs; i++){ |
| 1640 |
cur_edge = row_edges[i]; |
| 1641 |
arcs[i] = INDEX(cur_edge->v0, cur_edge->v1); |
| 1642 |
if (vrp->par.follow_one_edges && |
| 1643 |
fabs(cur_edge->weight - 1.0) < etol && !(cur_edge->can_be_doubled)){ |
| 1644 |
indicators[i] = TRUE; |
| 1645 |
} |
| 1646 |
} |
| 1647 |
sort_order = (int *) malloc(num_arcs * ISIZE); |
| 1648 |
for(i = 0; i < num_arcs; sort_order[i] = i++); |
| 1649 |
qsortucb_ii(arcs, sort_order, num_arcs); |
| 1650 |
|
| 1651 |
CPXgetbhead(lp_data->cpxenv, lp_data->lp, head, soln); |
| 1652 |
|
| 1653 |
costs = (double *) malloc((vertnum*(vertnum-1)/2) * DSIZE); |
| 1654 |
for (unbd_row_index = 0; unbd_row_index < lp_data->m; unbd_row_index++){ |
| 1655 |
if (soln[unbd_row_index] < -etol || (soln[unbd_row_index] > etol && |
| 1656 |
head[unbd_row_index] < 0)){ |
| 1657 |
mult = soln[unbd_row_index] < 0 ? 1 : -1; |
| 1658 |
CPXbinvarow(lp_data->cpxenv, lp_data->lp, unbd_row_index, z); |
| 1659 |
for (i = 0, equality = 0; i < lp_data->n; i++){ |
| 1660 |
if (mult*z[i] < -etol) break; |
| 1661 |
if (fabs(z[i]) < etol) equality++; |
| 1662 |
} |
| 1663 |
if (i < lp_data->n) continue; |
| 1664 |
|
| 1665 |
CPXbinvrow(lp_data->cpxenv, lp_data->lp, unbd_row_index, unbd_row); |
| 1666 |
|
| 1667 |
if (fabs(unbd_row[lp_data->m - 1]) > etol){ |
| 1668 |
beta = mult*unbd_row[lp_data->m-1]; |
| 1669 |
}else{ |
| 1670 |
beta = 0; |
| 1671 |
} |
| 1672 |
#if 0 |
| 1673 |
for (bigM = -beta, nz = 0, i = 0; i < num_arcs; i++){ |
| 1674 |
bigM += -MIN(mult*unbd_row[i], 0); |
| 1675 |
if (unbd_row[i] != 0) nz++; |
| 1676 |
} |
| 1677 |
#endif |
| 1678 |
|
| 1679 |
memset((char *)costs, 0, vertnum*(vertnum-1)/2 * DSIZE); |
| 1680 |
|
| 1681 |
for (adjust = 0, i = 0, v1 = 1; v1 < vertnum; v1++){ |
| 1682 |
if (!(verts[v1].comp == comp_num)) continue; |
| 1683 |
for (v0 = 0; v0 < v1; v0++){ |
| 1684 |
if (v0 && !(verts[v0].comp == comp_num)) continue; |
| 1685 |
index = INDEX(v0, v1); |
| 1686 |
if (i < num_arcs && arcs[i] == index){ |
| 1687 |
if (indicators[sort_order[i]]){ |
| 1688 |
costs[arcs[i]] = -100000; |
| 1689 |
adjust++; |
| 1690 |
}else{ |
| 1691 |
if (fabs(unbd_row[sort_order[i]]) > etol) |
| 1692 |
costs[arcs[i]] = mult*unbd_row[sort_order[i]]; |
| 1693 |
} |
| 1694 |
i++; |
| 1695 |
}else{ |
| 1696 |
costs[index] = |
| 1697 |
(double)((MAXINT)/(vrp->vertnum+vrp->numroutes-1)); |
| 1698 |
} |
| 1699 |
} |
| 1700 |
} |
| 1701 |
|
| 1702 |
for (alpha = -beta, i = 0; i < num_arcs; i++){ |
| 1703 |
if (indicators[i]) |
| 1704 |
alpha -= mult*unbd_row[i]; |
| 1705 |
} |
| 1706 |
for (j = 0, i = 0; i < num_arcs; i++){ |
| 1707 |
#if defined(COMPILE_IN_CG) && 1 |
| 1708 |
if (indicators[sort_order[i]] && |
| 1709 |
!(row_edges[sort_order[i]]->status & TEMP_FIXED_TO_UB) && |
| 1710 |
!(row_edges[sort_order[i]]->status & PERM_FIXED_TO_UB) && |
| 1711 |
!(row_edges[sort_order[i]]->status & VARIABLE_BRANCHED_ON)){ |
| 1712 |
#else |
| 1713 |
if (indicators[sort_order[i]]){ |
| 1714 |
#endif |
| 1715 |
costs[arcs[i]] = |
| 1716 |
(double)((MAXINT)/(vrp->vertnum+vrp->numroutes-1)); |
| 1717 |
adjust--; |
| 1718 |
if (fabs(weights[j] = decomp_lower_bound(vrp, costs, NULL, |
| 1719 |
adjust,1) - alpha) |
| 1720 |
> etol && weights[j] < MAXDOUBLE - alpha){ |
| 1721 |
alpha += weights[j]; |
| 1722 |
costs[arcs[i]] = weights[j]; |
| 1723 |
nonzeros[j++] = arcs[i]; |
| 1724 |
}else{ |
| 1725 |
costs[arcs[i]] = 0; |
| 1726 |
} |
| 1727 |
#if 0 |
| 1728 |
if ((weights[j] = decomp_lower_bound(vrp, costs, NULL, adjust,1) |
| 1729 |
- alpha) < - etol){ |
| 1730 |
alpha += weights[j]; |
| 1731 |
costs[arcs[i]] = weights[j]; |
| 1732 |
nonzeros[j++] = arcs[i]; |
| 1733 |
}else{ |
| 1734 |
costs[arcs[i]] = 0; |
| 1735 |
if (weights[j] > etol && weights[j] < MAXDOUBLE - alpha) |
| 1736 |
printf("\n\nWarning: possible bad coefficient in farkas" |
| 1737 |
"cut %f\n\n", weights[j]); |
| 1738 |
} |
| 1739 |
#endif |
| 1740 |
}else{ |
| 1741 |
if (fabs(weights[j] = mult*unbd_row[sort_order[i]]) > etol){ |
| 1742 |
nonzeros[j++] = arcs[i]; |
| 1743 |
} |
| 1744 |
} |
| 1745 |
} |
| 1746 |
for (i = 0, k = 0, v1 = 1; v1 < vertnum; v1++){ |
| 1747 |
if (!(verts[v1].comp == comp_num)) continue; |
| 1748 |
for (v0 = 0; v0 < v1; v0++){ |
| 1749 |
if (v0 && !(verts[v0].comp == comp_num)) continue; |
| 1750 |
index = INDEX(v0, v1); |
| 1751 |
if (i < num_arcs && arcs[i] == index){ |
| 1752 |
i++; |
| 1753 |
continue; |
| 1754 |
} |
| 1755 |
#if defined(COMPILE_IN_CG) && 1 |
| 1756 |
if (k < lp_data2->n){ |
| 1757 |
while (lp_data2->vars[k]->userind < index){ |
| 1758 |
k++; |
| 1759 |
} |
| 1760 |
if (lp_data2->vars[k]->userind > index){ |
| 1761 |
continue; |
| 1762 |
}else if ((status[k] & TEMP_FIXED_TO_LB) || |
| 1763 |
(status[k] & PERM_FIXED_TO_LB) || |
| 1764 |
(status[k] & VARIABLE_BRANCHED_ON)){ |
| 1765 |
k++; |
| 1766 |
continue; |
| 1767 |
}else{ |
| 1768 |
k++; |
| 1769 |
} |
| 1770 |
}else{ |
| 1771 |
break; |
| 1772 |
} |
| 1773 |
#endif |
| 1774 |
costs[index] = -100000; |
| 1775 |
if (fabs(weights[j] = alpha - |
| 1776 |
decomp_lower_bound(vrp, costs, NULL, 1, 1)) > etol && |
| 1777 |
weights[j] > alpha - MAXDOUBLE){ |
| 1778 |
costs[index] = weights[j]; |
| 1779 |
nonzeros[j++] = index; |
| 1780 |
}else{ |
| 1781 |
costs[index] = 0; |
| 1782 |
} |
| 1783 |
#if 0 |
| 1784 |
if ((weights[j] = alpha - |
| 1785 |
decomp_lower_bound(vrp, costs, NULL, 1, 1)) > etol){ |
| 1786 |
costs[index] = weights[j]; |
| 1787 |
nonzeros[j++] = index; |
| 1788 |
}else{ |
| 1789 |
costs[index] = 0; |
| 1790 |
if (weights[j] <= -etol && weights[j] > alpha - MAXDOUBLE) |
| 1791 |
printf("\n\nWarning: possible bad coefficient in farkas" |
| 1792 |
"cut %f\n\n", weights[j]); |
| 1793 |
} |
| 1794 |
costs[index] = 0; |
| 1795 |
#endif |
| 1796 |
} |
| 1797 |
} |
| 1798 |
new_cut->rhs = alpha; |
| 1799 |
if (alpha == 0){ |
| 1800 |
printf( "FARKAS CUT RHS 0 \n" ); |
| 1801 |
} |
| 1802 |
|
| 1803 |
printf( "rhs = %f \n", new_cut->rhs) ; |
| 1804 |
printf("%i columns in the problem\n", lp_data->n); |
| 1805 |
printf("%i columns satisfy the row at equality\n", equality); |
| 1806 |
printf("%i nonzero entries in the cut\n", j); |
| 1807 |
viol = 0; |
| 1808 |
for (i = 0; i < lp_data->m - 1; i++){ |
| 1809 |
viol += mult*unbd_row[i] * row_edges[i]->weight; |
| 1810 |
} |
| 1811 |
viol += beta; |
| 1812 |
printf( " value of the b*x_star+beta: %f \n", viol); |
| 1813 |
|
| 1814 |
/* Pack cut */ |
| 1815 |
new_cut->size = ISIZE + j * (ISIZE + DSIZE); |
| 1816 |
new_cut->coef = coef = malloc(new_cut->size); |
| 1817 |
memcpy(coef, (char *)&j, ISIZE); |
| 1818 |
coef += ISIZE; |
| 1819 |
memcpy(coef, (char *)nonzeros, j * ISIZE); |
| 1820 |
coef += j * ISIZE; |
| 1821 |
memcpy(coef, (char *)weights, j * DSIZE); |
| 1822 |
cg_send_cut(new_cut); |
| 1823 |
FREE(new_cut->coef); |
| 1824 |
num_cuts++; |
| 1825 |
} |
| 1826 |
} |
| 1827 |
|
| 1828 |
FREE(costs); |
| 1829 |
FREE(head); |
| 1830 |
FREE(nonzeros); |
| 1831 |
FREE(weights); |
| 1832 |
FREE(arcs); |
| 1833 |
FREE(sort_order); |
| 1834 |
FREE(indicators); |
| 1835 |
FREE(new_cut); |
| 1836 |
FREE(unbd_row); |
| 1837 |
FREE(soln); |
| 1838 |
FREE(z); |
| 1839 |
|
| 1840 |
return(num_cuts); |
| 1841 |
} |
| 1842 |
|
| 1843 |
/*===========================================================================*/ |
| 1844 |
|
| 1845 |
#elif defined(FARKAS_LIFT_NAIVE) |
| 1846 |
|
| 1847 |
int generate_farkas_cuts(cg_prob *p, LPdata *lp_data, network *n, |
| 1848 |
edge **row_edges, int comp_num) |
| 1849 |
{ |
| 1850 |
cg_vrp_spec *vrp = (cg_vrp_spec *)p->user; |
| 1851 |
double *unbd_row; |
| 1852 |
int unbd_row_index, mult, num_fracs; |
| 1853 |
int i, k, v0, v1, index, num_arcs, nz, equality, num_cuts = 0; |
| 1854 |
int vertnum = vrp->vertnum; |
| 1855 |
int *arcs, *head; |
| 1856 |
double alpha, beta, bigM; |
| 1857 |
double *weights, *z, *soln; |
| 1858 |
vertex *verts = n->verts; |
| 1859 |
edge *cur_edge; |
| 1860 |
char *cpt, *coef, *indicators; |
| 1861 |
double etol = p->cur_sol.lpetol, viol; |
| 1862 |
cut_data *new_cut; |
| 1863 |
double *costs; |
| 1864 |
#ifdef COMPILE_IN_CG |
| 1865 |
lp_prob *lp = get_lp_ptr(NULL); |
| 1866 |
LPdata *lp_data2 = lp->lp_data; |
| 1867 |
char *status = lp_data2->status; |
| 1868 |
#endif |
| 1869 |
|
| 1870 |
num_arcs = lp_data->m - 1; |
| 1871 |
|
| 1872 |
z = (double *) calloc( MAX(lp_data->m, lp_data->n), DSIZE); |
| 1873 |
soln = (double *) calloc(lp_data->m, DSIZE); |
| 1874 |
head = (int *) calloc(lp_data->m, ISIZE); |
| 1875 |
unbd_row = (double *) malloc(lp_data->m * DSIZE); |
| 1876 |
new_cut = (cut_data *) calloc(1, sizeof(cut_data)); |
| 1877 |
arcs = (int *) malloc(num_arcs * ISIZE); |
| 1878 |
indicators = (char *) calloc(num_arcs, sizeof(char)); |
| 1879 |
weights = (double *) calloc(num_arcs, DSIZE); |
| 1880 |
|
| 1881 |
new_cut->type = FARKAS; |
| 1882 |
new_cut->sense = 'G'; |
| 1883 |
new_cut->branch = DO_NOT_BRANCH_ON_THIS_ROW; |
| 1884 |
new_cut->name = CUT__DO_NOT_SEND_TO_CP; |
| 1885 |
|
| 1886 |
/* SETTING the coef, num_arcs, arcs */ |
| 1887 |
for (i = 0; i < num_arcs; i++){ |
| 1888 |
cur_edge = row_edges[i]; |
| 1889 |
arcs[i] = INDEX(cur_edge->v0, cur_edge->v1); |
| 1890 |
if (fabs(cur_edge->weight - 1.0) < etol && !(cur_edge->can_be_doubled)){ |
| 1891 |
indicators[i] = TRUE; |
| 1892 |
} |
| 1893 |
} |
| 1894 |
|
| 1895 |
CPXgetbhead(lp_data->cpxenv, lp_data->lp, head, soln); |
| 1896 |
|
| 1897 |
costs = (double *) malloc((vertnum*(vertnum-1)/2) * DSIZE); |
| 1898 |
|
| 1899 |
/* SETTING THE RHS, bigM, weights and sending cuts*/ |
| 1900 |
for (unbd_row_index = 0; unbd_row_index < lp_data->m; unbd_row_index++){ |
| 1901 |
if (soln[unbd_row_index] < -etol || (soln[unbd_row_index] > etol && |
| 1902 |
head[unbd_row_index] < 0)){ |
| 1903 |
mult = soln[unbd_row_index] < 0 ? 1 : -1; |
| 1904 |
CPXbinvarow(lp_data->cpxenv, lp_data->lp, unbd_row_index, z); |
| 1905 |
for (i = 0, equality = 0; i < lp_data->n; i++){ |
| 1906 |
if (mult*z[i] < -etol) break; |
| 1907 |
if (fabs(z[i]) < etol) equality++; |
| 1908 |
} |
| 1909 |
if (i < lp_data->n) continue; |
| 1910 |
|
| 1911 |
CPXbinvrow(lp_data->cpxenv, lp_data->lp, unbd_row_index, unbd_row); |
| 1912 |
|
| 1913 |
if (fabs(unbd_row[lp_data->m - 1]) > etol){ |
| 1914 |
beta = mult*unbd_row[lp_data->m-1]; |
| 1915 |
}else{ |
| 1916 |
beta = 0; |
| 1917 |
} |
| 1918 |
#if 0 |
| 1919 |
for (bigM = -beta, nz = 0, i = 0; i < num_arcs; i++){ |
| 1920 |
bigM += -MIN(mult*unbd_row[i], 0); |
| 1921 |
if (unbd_row[i] != 0) nz++; |
| 1922 |
} |
| 1923 |
#endif |
| 1924 |
|
| 1925 |
memset((char *)costs, 0, vertnum*(vertnum-1)/2 * DSIZE); |
| 1926 |
|
| 1927 |
for (alpha = beta, bigM = 0, nz = 0, i = 0; i < lp_data->m - 1; i++){ |
| 1928 |
if (!indicators[i]){ |
| 1929 |
if (fabs(unbd_row[i]) > etol){ |
| 1930 |
costs[arcs[i]] = mult*unbd_row[i]; |
| 1931 |
nz++; |
| 1932 |
} |
| 1933 |
#if defined(COMPILE_IN_CG) && 1 |
| 1934 |
}else if ((row_edges[i]->status & TEMP_FIXED_TO_UB)|| |
| 1935 |
(row_edges[i]->status & PERM_FIXED_TO_UB) || |
| 1936 |
(row_edges[i]->status & VARIABLE_BRANCHED_ON)){ |
| 1937 |
costs[arcs[i]] = -100000; |
| 1938 |
#endif |
| 1939 |
}else if (fabs(unbd_row[i]) > etol){ |
| 1940 |
alpha += mult*unbd_row[i]; |
| 1941 |
} |
| 1942 |
} |
| 1943 |
#if defined(COMPILE_IN_CG) && 1 |
| 1944 |
for (i = 0, k = 0, v1 = 1, index = 0; v1 < vertnum; v1++){ |
| 1945 |
if (!(verts[v1].comp == comp_num)) continue; |
| 1946 |
for (v0 = 0; v0 < v1; v0++){ |
| 1947 |
if (v0 && !(verts[v0].comp == comp_num)) continue; |
| 1948 |
index = INDEX(v0, v1); |
| 1949 |
if (i < num_arcs && arcs[i] == index){ |
| 1950 |
i++; |
| 1951 |
continue; |
| 1952 |
} |
| 1953 |
if (k < lp_data2->n){ |
| 1954 |
while (lp_data2->vars[k]->userind < index){ |
| 1955 |
k++; |
| 1956 |
} |
| 1957 |
if (lp_data2->vars[k]->userind > index){ |
| 1958 |
costs[index] = |
| 1959 |
(double)((MAXINT)/(vrp->vertnum+vrp->numroutes-1)); |
| 1960 |
}else if ((status[k] & TEMP_FIXED_TO_LB) || |
| 1961 |
(status[k] & PERM_FIXED_TO_LB) || |
| 1962 |
(status[k] & VARIABLE_BRANCHED_ON)){ |
| 1963 |
costs[index] = |
| 1964 |
(double)((MAXINT)/(vrp->vertnum+vrp->numroutes-1)); |
| 1965 |
k++; |
| 1966 |
}else{ |
| 1967 |
k++; |
| 1968 |
} |
| 1969 |
}else{ |
| 1970 |
costs[index] = |
| 1971 |
(double)((MAXINT)/(vrp->vertnum+vrp->numroutes-1)); |
| 1972 |
} |
| 1973 |
} |
| 1974 |
} |
| 1975 |
#endif |
| 1976 |
if ((bigM = -decomp_lower_bound(vrp, costs, NULL, 0, 1))==-MAXDOUBLE) |
| 1977 |
continue; |
| 1978 |
if (bigM > -etol && bigM < etol) |
| 1979 |
bigM = 0.0; |
| 1980 |
bigM -= alpha; |
| 1981 |
for (i = 0, num_fracs = 0; i < lp_data->m - 1; i++){ |
| 1982 |
if (indicators[i]){ |
| 1983 |
alpha += bigM; |
| 1984 |
}else if (fabs(unbd_row[i]) > etol){ |
| 1985 |
weights[num_fracs++] = mult*unbd_row[i]; |
| 1986 |
}else{ |
| 1987 |
weights[num_fracs++] = 0; |
| 1988 |
} |
| 1989 |
} |
| 1990 |
new_cut->rhs = -alpha; |
| 1991 |
if (alpha == 0){ |
| 1992 |
printf( "FARKAS CUT RHS 0 \n" ); |
| 1993 |
} |
| 1994 |
|
| 1995 |
printf( "bigM = %f \n", bigM); |
| 1996 |
printf( "rhs = %f \n", new_cut->rhs) ; |
| 1997 |
printf("%i columns in the problem\n", lp_data->n); |
| 1998 |
printf("%i columns satisfy the row at equality\n", equality); |
| 1999 |
printf("%i nonzero entries in the cut\n", nz); |
| 2000 |
viol = 0; |
| 2001 |
for (i = 0; i < lp_data->m - 1; i++){ |
| 2002 |
viol += mult*unbd_row[i] * row_edges[i]->weight; |
| 2003 |
} |
| 2004 |
viol += beta; |
| 2005 |
printf( " value of the b*x_star+beta: %f \n", viol); |
| 2006 |
|
| 2007 |
/* Pack cut */ |
| 2008 |
new_cut->size = (vrp->vertnum >> DELETE_POWER) + 1 + |
| 2009 |
(num_arcs + 2) * ISIZE + num_arcs + (num_fracs + 1) * DSIZE; |
| 2010 |
new_cut->coef = coef = calloc(new_cut->size, sizeof(char)); |
| 2011 |
for (i = 1; i < vertnum; i++) |
| 2012 |
if (verts[i].comp == comp_num) |
| 2013 |
coef[i >> DELETE_POWER] |= (1 << (i & DELETE_AND)); |
| 2014 |
cpt = coef + ((vertnum >> DELETE_POWER) + 1); |
| 2015 |
memcpy(cpt, (char *)&num_arcs, ISIZE); |
| 2016 |
cpt += ISIZE; |
| 2017 |
memcpy(cpt, (char *)arcs, ISIZE*(num_arcs)); |
| 2018 |
cpt += ISIZE * num_arcs; |
| 2019 |
memcpy(cpt, (char *)indicators, num_arcs); |
| 2020 |
cpt += num_arcs; |
| 2021 |
memcpy(cpt, (char *)&num_fracs, ISIZE); |
| 2022 |
cpt+= ISIZE; |
| 2023 |
memcpy(cpt, (char *)&bigM, DSIZE); |
| 2024 |
cpt+= DSIZE; |
| 2025 |
memcpy(cpt, (char *)weights, num_fracs*DSIZE); |
| 2026 |
cg_send_cut(new_cut); |
| 2027 |
FREE(new_cut->coef); |
| 2028 |
num_cuts++; |
| 2029 |
} |
| 2030 |
} |
| 2031 |
|
| 2032 |
FREE(costs); |
| 2033 |
FREE(head); |
| 2034 |
FREE(weights); |
| 2035 |
FREE(arcs); |
| 2036 |
FREE(indicators); |
| 2037 |
FREE(new_cut); |
| 2038 |
FREE(unbd_row); |
| 2039 |
FREE(soln); |
| 2040 |
FREE(z); |
| 2041 |
|
| 2042 |
return(num_cuts); |
| 2043 |
} |
| 2044 |
|
| 2045 |
/*===========================================================================*/ |
| 2046 |
|
| 2047 |
#else |
| 2048 |
|
| 2049 |
int generate_farkas_cuts(cg_prob *p, LPdata *lp_data, network *n, |
| 2050 |
edge **row_edges, int comp_num) |
| 2051 |
{ |
| 2052 |
cg_vrp_spec *vrp = (cg_vrp_spec *)p->user; |
| 2053 |
double *unbd_row; |
| 2054 |
int unbd_row_index, mult; |
| 2055 |
int i, nz, equality, num_cuts = 0; |
| 2056 |
int vertnum = vrp->vertnum; |
| 2057 |
int *head, *nonzeros; |
| 2058 |
double beta; |
| 2059 |
double *weights, *z, *soln; |
| 2060 |
char *coef; |
| 2061 |
double etol = p->cur_sol.lpetol; |
| 2062 |
cut_data *new_cut; |
| 2063 |
|
| 2064 |
z = (double *) calloc( MAX(lp_data->m, lp_data->n), DSIZE); |
| 2065 |
soln = (double *) calloc(lp_data->m, DSIZE); |
| 2066 |
head = (int *) calloc(lp_data->m, ISIZE); |
| 2067 |
unbd_row = (double *) malloc(lp_data->m * DSIZE); |
| 2068 |
new_cut = (cut_data *) calloc(1, sizeof(cut_data)); |
| 2069 |
weights = (double *) malloc(vertnum*(vertnum - 1)/2 * DSIZE); |
| 2070 |
nonzeros = (int *) malloc(vertnum*(vertnum - 1)/2 * ISIZE); |
| 2071 |
|
| 2072 |
new_cut->type = GENERAL_NONZEROS; |
| 2073 |
new_cut->sense = 'G'; |
| 2074 |
new_cut->branch = DO_NOT_BRANCH_ON_THIS_ROW; |
| 2075 |
/*For now, we do not send these to the CP because they are only locally |
| 2076 |
valid due to the fact that we use fixed variables to generate them. |
| 2077 |
Right now, we can only do this if the LP is compiled in */ |
| 2078 |
new_cut->name = CUT__DO_NOT_SEND_TO_CP; |
| 2079 |
|
| 2080 |
CPXgetbhead(lp_data->cpxenv, lp_data->lp, head, soln); |
| 2081 |
|
| 2082 |
/* SETTING THE RHS, bigM, weights and sending cuts*/ |
| 2083 |
get_x(lp_data); |
| 2084 |
for (unbd_row_index = 0; unbd_row_index < lp_data->m; unbd_row_index++){ |
| 2085 |
if (soln[unbd_row_index] < -etol || (soln[unbd_row_index] > etol && |
| 2086 |
head[unbd_row_index] < 0)){ |
| 2087 |
mult = soln[unbd_row_index] < 0 ? 1 : -1; |
| 2088 |
CPXbinvarow(lp_data->cpxenv, lp_data->lp, unbd_row_index, z); |
| 2089 |
for (i = 0, equality = 0; i < lp_data->n; i++){ |
| 2090 |
if (mult*z[i] < -etol) break; |
| 2091 |
if (fabs(z[i]) < etol) equality++; |
| 2092 |
} |
| 2093 |
if (i < lp_data->n) continue; |
| 2094 |
|
| 2095 |
CPXbinvrow(lp_data->cpxenv, lp_data->lp, unbd_row_index, unbd_row); |
| 2096 |
|
| 2097 |
if (fabs(unbd_row[lp_data->m - 1]) > etol){ |
| 2098 |
beta = mult*unbd_row[lp_data->m-1]; |
| 2099 |
}else{ |
| 2100 |
beta = 0; |
| 2101 |
} |
| 2102 |
|
| 2103 |
new_cut->rhs = beta; |
| 2104 |
|
| 2105 |
for (i = nz = 0; i < lp_data->m - 1; i ++) |
| 2106 |
if (fabs(weights[nz] = mult*unbd_row[i]) > etol) |
| 2107 |
nonzeros[nz++] = i; |
| 2108 |
|
| 2109 |
printf( "rhs = %f \n", new_cut->rhs) ; |
| 2110 |
printf("%i columns in the problem\n", lp_data->n); |
| 2111 |
printf("%i columns satisfy the row at equality\n", equality); |
| 2112 |
printf("%i nonzero entries in the cut\n", nz); |
| 2113 |
|
| 2114 |
/* Pack cut */ |
| 2115 |
new_cut->size = ISIZE + nz * (ISIZE + DSIZE); |
| 2116 |
new_cut->coef = coef = malloc(new_cut->size); |
| 2117 |
memcpy(coef, (char *)&nz, ISIZE); |
| 2118 |
coef += ISIZE; |
| 2119 |
memcpy(coef, (char *)nonzeros, nz * ISIZE); |
| 2120 |
coef += nz * ISIZE; |
| 2121 |
memcpy(coef, (char *)weights, nz * DSIZE); |
| 2122 |
cg_send_cut(new_cut); |
| 2123 |
FREE(new_cut->coef); |
| 2124 |
num_cuts++; |
| 2125 |
} |
| 2126 |
} |
| 2127 |
|
| 2128 |
FREE(head); |
| 2129 |
FREE(weights); |
| 2130 |
FREE(new_cut); |
| 2131 |
FREE(unbd_row); |
| 2132 |
FREE(soln); |
| 2133 |
FREE(z); |
| 2134 |
|
| 2135 |
return(num_cuts); |
| 2136 |
} |
| 2137 |
#endif |
| 2138 |
|
| 2139 |
/*===========================================================================*/ |
| 2140 |
|
| 2141 |
int generate_no_cols_cut(cg_prob *p,LPdata *lp_data , network *n, |
| 2142 |
edge **row_edges, int cur_comp) |
| 2143 |
{ |
| 2144 |
cg_vrp_spec *vrp = (cg_vrp_spec *)p->user; |
| 2145 |
int i,num_arcs, cut_size, num_ones = 0, num_cuts = 0; |
| 2146 |
int vertnum = vrp->vertnum; |
| 2147 |
int *arcs; |
| 2148 |
char *indicators; |
| 2149 |
vertex *verts = n->verts; |
| 2150 |
edge *cur_edge; |
| 2151 |
char *cpt, *coef /*, *position */; |
| 2152 |
double etol = p->cur_sol.lpetol; |
| 2153 |
cut_data *new_cut; |
| 2154 |
|
| 2155 |
num_arcs = n->edgenum; |
| 2156 |
cut_size = (vrp->vertnum >> DELETE_POWER) + 1 + (num_arcs + 1) * ISIZE + |
| 2157 |
num_arcs; |
| 2158 |
|
| 2159 |
new_cut = (cut_data *) calloc(1, sizeof(cut_data)); |
| 2160 |
new_cut->coef = coef = calloc(cut_size, sizeof(char)); |
| 2161 |
arcs = (int *) calloc(num_arcs, sizeof(int)); |
| 2162 |
indicators = (char *) calloc(num_arcs, sizeof(char)); |
| 2163 |
|
| 2164 |
/* SETTING the coef, arcs, values */ |
| 2165 |
for (i = 0; i < num_arcs; i++){ |
| 2166 |
cur_edge = row_edges[i]; |
| 2167 |
arcs[i] = INDEX(cur_edge->v0, cur_edge->v1); |
| 2168 |
if (fabs(cur_edge->weight - 1) < etol && !(cur_edge->can_be_doubled)){ |
| 2169 |
indicators[i] = TRUE; |
| 2170 |
num_ones++; |
| 2171 |
} |
| 2172 |
} |
| 2173 |
#if 0 |
| 2174 |
printf("Here's the no columns cut:\n "); |
| 2175 |
printf("Number of arcs %d , rhs %d \n", num_arcs, num_ones-1); |
| 2176 |
for (i = 0; i < num_arcs; i++) |
| 2177 |
printf(" %d %d ;\n ",arcs[i], indicators[i]); |
| 2178 |
printf("End no columns cut \n\n"); |
| 2179 |
#endif |
| 2180 |
/* Pack cut */ |
| 2181 |
new_cut->type = NO_COLUMNS; |
| 2182 |
new_cut->sense = 'L'; |
| 2183 |
new_cut->size = cut_size; |
| 2184 |
new_cut->branch = ALLOWED_TO_BRANCH_ON; |
| 2185 |
new_cut->rhs = num_ones - 1.0; |
| 2186 |
|
| 2187 |
for (i = 1; i < vertnum; i++) |
| 2188 |
if (verts[i].comp == cur_comp) |
| 2189 |
coef[i >> DELETE_POWER] |= (1 << (i & DELETE_AND)); |
| 2190 |
cpt = coef + ((vertnum >> DELETE_POWER) + 1); |
| 2191 |
memcpy(cpt, (char *)&num_arcs, ISIZE); |
| 2192 |
cpt += ISIZE; |
| 2193 |
memcpy(cpt, (char *)arcs, ISIZE * num_arcs); |
| 2194 |
cpt += num_arcs * ISIZE; |
| 2195 |
memcpy(cpt, indicators, num_arcs); |
| 2196 |
|
| 2197 |
#if 0 |
| 2198 |
/* send the no_cols_cut to CUT_POOL*/ |
| 2199 |
if (p->cur_sol.cp){ |
| 2200 |
int s_bufid, info, cnt=1; |
| 2201 |
|
| 2202 |
PVM_FUNC(s_bufid, pvm_initsend(PvmDataRaw)); |
| 2203 |
PVM_FUNC(info, pvm_pkint(&cnt, 1, 1)); |
| 2204 |
PVM_FUNC(info, pvm_pkint(&p->cur_sol.xlevel, 1, 1)); |
| 2205 |
pack_cut(new_cut); |
| 2206 |
PVM_FUNC(info, pvm_send(p->cur_sol.cp, 601)); |
| 2207 |
PVM_FUNC(info, pvm_freebuf(s_bufid)); |
| 2208 |
PRINT(p->par.verbosity, 4, ("1 no_columns cut sent to cutpool\n")); |
| 2209 |
} |
| 2210 |
#endif |
| 2211 |
num_cuts += cg_send_cut(new_cut); |
| 2212 |
FREE(coef); |
| 2213 |
FREE(new_cut); |
| 2214 |
FREE(arcs); |
| 2215 |
FREE(indicators); |
| 2216 |
return(num_cuts); |
| 2217 |
} |
| 2218 |
|
| 2219 |
/*===========================================================================*/ |
| 2220 |
|
| 2221 |
int purge_infeasible_cols(cg_prob *p, LPdata *lp_data, edge **row_edges, |
| 2222 |
int *delstat) |
| 2223 |
{ |
| 2224 |
cg_vrp_spec *vrp = (cg_vrp_spec *)p->user; |
| 2225 |
int capacity = vrp->capacity, set_demand = 0; |
| 2226 |
int *demand = vrp->demand; |
| 2227 |
double *new_demand = vrp->n->new_demand; |
| 2228 |
int i, j, collen, *colind; |
| 2229 |
double *colval; |
| 2230 |
int cur_vert, next_vert; |
| 2231 |
edge *cur_edge; |
| 2232 |
int cols_deleted = 0; |
| 2233 |
|
| 2234 |
for (j = 0; j < lp_data->n; j++){ |
| 2235 |
collen = lp_data->matcnt[j]-1; |
| 2236 |
colval = lp_data->matval + lp_data->matbeg[j]; |
| 2237 |
colind = lp_data->matind + lp_data->matbeg[j]; |
| 2238 |
|
| 2239 |
cur_vert = 0; |
| 2240 |
|
| 2241 |
for ( i = 0; i < collen; i++){ |
| 2242 |
if (colval[i] == 2) continue; |
| 2243 |
/* if the edge makes a one-customer route, ignore it */ |
| 2244 |
if (!cur_vert) set_demand = 0; |
| 2245 |
/* start a new route */ |
| 2246 |
|
| 2247 |
cur_edge = row_edges[colind[i]]; |
| 2248 |
next_vert = ((cur_vert == cur_edge->v0) ? cur_edge->v1 : cur_edge->v0); |
| 2249 |
if (!next_vert){ |
| 2250 |
cur_vert = 0; |
| 2251 |
continue; |
| 2252 |
} |
| 2253 |
set_demand += demand[next_vert] + new_demand[next_vert]; |
| 2254 |
if (set_demand > capacity){ |
| 2255 |
delstat[j] = 1; |
| 2256 |
cols_deleted++; |
| 2257 |
break; |
| 2258 |
} |
| 2259 |
cur_vert = next_vert; |
| 2260 |
} |
| 2261 |
} |
| 2262 |
return(cols_deleted); |
| 2263 |
} |
| 2264 |
|
| 2265 |
/*===========================================================================*/ |
| 2266 |
/*This routine generates the new columns To do this, we need a proof of |
| 2267 |
infeasibility in order to generate new columns. The proof is basically a |
| 2268 |
Farkas inequality (row of B^{-1 }) that separates the current fractional |
| 2269 |
solution from the convex hull of the current set of columns. We try to find |
| 2270 |
a new column which violates this Farkas inequality by solving the relaxation |
| 2271 |
with the left hand side of this inequality as the objective function. Again, |
| 2272 |
there are different options based on different lifting methods. */ |
| 2273 |
|
| 2274 |
#ifndef NO_LIFTING |
| 2275 |
|
| 2276 |
int vrp_generate_new_cols(cg_prob *p, LPdata *lp_data, network *n, |
| 2277 |
edge **row_edges, int comp_num) |
| 2278 |
{ |
| 2279 |
cg_vrp_spec *vrp = (cg_vrp_spec *)p->user; |
| 2280 |
double *unbd_row; |
| 2281 |
int unbd_row_index, mult; |
| 2282 |
int i, num_arcs, equality; |
| 2283 |
int vertnum = vrp->vertnum, v0, v1, index; |
| 2284 |
int *arcs, *head, *sort_order; |
| 2285 |
double alpha, beta; |
| 2286 |
double *z, *soln; |
| 2287 |
vertex *verts = n->verts; |
| 2288 |
edge *cur_edge; |
| 2289 |
char *indicators; |
| 2290 |
double etol = p->cur_sol.lpetol; |
| 2291 |
double *costs, lb = 0.0, ub = 1.0, *matval, obj = 0.0; |
| 2292 |
int matbeg[2] = {0,0}; |
| 2293 |
int *matind, *x, nzcnt = 0, coef, cpx_status; |
| 2294 |
|
| 2295 |
num_arcs = lp_data->m - 1; |
| 2296 |
|
| 2297 |
arcs = (int *) malloc(num_arcs * ISIZE); |
| 2298 |
indicators = (char *) calloc(num_arcs, sizeof(char)); |
| 2299 |
/* SETTING the coef, num_arcs, arcs */ |
| 2300 |
for (i = 0; i < num_arcs; i++){ |
| 2301 |
cur_edge = row_edges[i]; |
| 2302 |
arcs[i] = INDEX(cur_edge->v0, cur_edge->v1); |
| 2303 |
if (vrp->par.follow_one_edges && |
| 2304 |
fabs(cur_edge->weight - 1.0) < etol && !(cur_edge->can_be_doubled)){ |
| 2305 |
indicators[i] = TRUE; |
| 2306 |
} |
| 2307 |
} |
| 2308 |
sort_order = (int *) malloc(num_arcs * ISIZE); |
| 2309 |
for(i = 0; i < num_arcs; sort_order[i] = i++); |
| 2310 |
qsortucb_ii(arcs, sort_order, num_arcs); |
| 2311 |
|
| 2312 |
if (!lp_data->n){ |
| 2313 |
costs = (double *) calloc(vertnum*(vertnum-1)/2, DSIZE); |
| 2314 |
x = (int *) calloc(vertnum*(vertnum-1)/2, ISIZE); |
| 2315 |
for (i = 0, v1 = 1; v1 < vertnum; v1++){ |
| 2316 |
if (!(verts[v1].comp == comp_num)) continue; |
| 2317 |
for (v0 = 0; v0 < v1; v0++){ |
| 2318 |
if (v0 && !(verts[v0].comp == comp_num)) continue; |
| 2319 |
index = INDEX(v0, v1); |
| 2320 |
if (i < num_arcs && arcs[i] == index){ |
| 2321 |
if (indicators[sort_order[i]]){ |
| 2322 |
costs[arcs[i]] = -100000; |
| 2323 |
} |
| 2324 |
i++; |
| 2325 |
}else{ |
| 2326 |
costs[index] = |
| 2327 |
(double)((MAXINT)/(vrp->vertnum+vrp->numroutes-1)); |
| 2328 |
} |
| 2329 |
} |
| 2330 |
} |
| 2331 |
if (decomp_lower_bound(vrp, costs, x, 0, 1) == 0){ |
| 2332 |
cpx_status = CPXsetintparam(lp_data->cpxenv, CPX_PARAM_SCAIND, -1); |
| 2333 |
cpx_status = |
| 2334 |
CPXsetintparam(lp_data->cpxenv, CPX_PARAM_BASINTERVAL, 2100000000); |
| 2335 |
cpx_status = CPXsetintparam(lp_data->cpxenv, CPX_PARAM_AGGIND, 0); |
| 2336 |
cpx_status = CPXsetintparam(lp_data->cpxenv, CPX_PARAM_DEPIND, 0); |
| 2337 |
cpx_status = CPXsetintparam(lp_data->cpxenv, CPX_PARAM_PREIND, 0); |
| 2338 |
|
| 2339 |
CPX_check_error("load_lp - CPXsetintparam"); |
| 2340 |
|
| 2341 |
lp_data->lp = |
| 2342 |
CPXloadlp(lp_data->cpxenv, |
| 2343 |
(char *) "Decomp_prob", lp_data->n, lp_data->m, 1, |
| 2344 |
lp_data->obj, |
| 2345 |
lp_data->rhs, lp_data->sense, lp_data->matbeg, |
| 2346 |
lp_data->matcnt, lp_data->matind, lp_data->matval, |
| 2347 |
lp_data->lb, lp_data->ub, lp_data->rngval, |
| 2348 |
lp_data->maxn+lp_data->maxm, lp_data->maxm, |
| 2349 |
lp_data->maxnz+lp_data->maxm); |
| 2350 |
|
| 2351 |
p->dcmp_data.iter_num = 0; |
| 2352 |
matind = (int *) malloc((vrp->vertnum+vrp->numroutes)*ISIZE); |
| 2353 |
matval = (double *) malloc((vrp->vertnum+vrp->numroutes)*DSIZE); |
| 2354 |
for (nzcnt = 0, i = 0; i < num_arcs; i++){ |
| 2355 |
cur_edge = row_edges[i]; |
| 2356 |
if ((coef = x[INDEX(cur_edge->v0, cur_edge->v1)]) > etol){ |
| 2357 |
matind[nzcnt] = i; |
| 2358 |
matval[nzcnt++] = (double)coef; |
| 2359 |
} |
| 2360 |
} |
| 2361 |
matind[nzcnt] = lp_data->m-1; |
| 2362 |
matval[nzcnt++] = 1.0; |
| 2363 |
if (nzcnt > vrp->vertnum+vrp->numroutes){ |
| 2364 |
printf("Too many nonzeros (%i) !!!!\n\n", nzcnt); |
| 2365 |
sleep(600); |
| 2366 |
exit(); |
| 2367 |
} |
| 2368 |
matbeg[1] = nzcnt; |
| 2369 |
if (lp_data->n < lp_data->maxn){ |
| 2370 |
add_cols(lp_data, 1, nzcnt, &obj, matbeg, matind, matval, &lb, |
| 2371 |
&ub, 0); |
| 2372 |
lp_data->matbeg[lp_data->n] = lp_data->nz; |
| 2373 |
} |
| 2374 |
FREE(arcs); |
| 2375 |
FREE(indicators); |
| 2376 |
FREE(costs); |
| 2377 |
FREE(x); |
| 2378 |
FREE(matval); |
| 2379 |
FREE(matind); |
| 2380 |
return(lp_data->n == lp_data->maxn ? -1 : 1); |
| 2381 |
}else{ |
| 2382 |
FREE(arcs); |
| 2383 |
FREE(indicators); |
| 2384 |
return(0); |
| 2385 |
} |
| 2386 |
} |
| 2387 |
|
| 2388 |
x = (int *) calloc(vertnum*(vertnum-1)/2, ISIZE); |
| 2389 |
z = (double *) calloc( MAX(lp_data->m, lp_data->n), DSIZE); |
| 2390 |
soln = (double *) calloc(lp_data->m, DSIZE); |
| 2391 |
head = (int *) calloc(lp_data->m, ISIZE); |
| 2392 |
unbd_row = (double *) malloc(lp_data->m * DSIZE); |
| 2393 |
|
| 2394 |
CPXgetbhead(lp_data->cpxenv, lp_data->lp, head, soln); |
| 2395 |
|
| 2396 |
costs = (double *) malloc((vertnum*(vertnum-1)/2) * DSIZE); |
| 2397 |
for (unbd_row_index = 0; unbd_row_index < lp_data->m; unbd_row_index++){ |
| 2398 |
if (soln[unbd_row_index] < -etol || (soln[unbd_row_index] > etol && |
| 2399 |
head[unbd_row_index] < 0)){ |
| 2400 |
mult = soln[unbd_row_index] < 0 ? 1 : -1; |
| 2401 |
CPXbinvarow(lp_data->cpxenv, lp_data->lp, unbd_row_index, z); |
| 2402 |
for (i = 0, equality = 0; i < lp_data->n; i++){ |
| 2403 |
if (mult*z[i] < -etol) break; |
| 2404 |
if (fabs(z[i]) < etol) equality++; |
| 2405 |
} |
| 2406 |
if (i < lp_data->n) continue; |
| 2407 |
|
| 2408 |
CPXbinvrow(lp_data->cpxenv, lp_data->lp, unbd_row_index, unbd_row); |
| 2409 |
|
| 2410 |
if (fabs(unbd_row[lp_data->m - 1]) > etol){ |
| 2411 |
beta = mult*unbd_row[lp_data->m-1]; |
| 2412 |
}else{ |
| 2413 |
beta = 0; |
| 2414 |
} |
| 2415 |
|
| 2416 |
memset((char *)costs, 0, vertnum*(vertnum-1)/2 * DSIZE); |
| 2417 |
|
| 2418 |
for (i = 0, v1 = 1; v1 < vertnum; v1++){ |
| 2419 |
if (!(verts[v1].comp == comp_num)) continue; |
| 2420 |
for (v0 = 0; v0 < v1; v0++){ |
| 2421 |
if (v0 && !(verts[v0].comp == comp_num)) continue; |
| 2422 |
index = INDEX(v0, v1); |
| 2423 |
if (i < num_arcs && arcs[i] == index){ |
| 2424 |
if (indicators[sort_order[i]]){ |
| 2425 |
costs[arcs[i]] = -100000; |
| 2426 |
}else{ |
| 2427 |
if (fabs(unbd_row[sort_order[i]]) > etol) |
| 2428 |
costs[arcs[i]] = mult*unbd_row[sort_order[i]]; |
| 2429 |
} |
| 2430 |
i++; |
| 2431 |
}else{ |
| 2432 |
costs[index] = |
| 2433 |
(double)((MAXINT)/(vrp->vertnum+vrp->numroutes-1)); |
| 2434 |
} |
| 2435 |
} |
| 2436 |
} |
| 2437 |
for (alpha = beta, i = 0; i < num_arcs; i++){ |
| 2438 |
if (indicators[i]) |
| 2439 |
alpha += mult*unbd_row[i]; |
| 2440 |
} |
| 2441 |
|
| 2442 |
memset(x, 0, (vertnum*(vertnum-1)/2)*ISIZE); |
| 2443 |
|
| 2444 |
if (decomp_lower_bound(vrp, costs, x, 0, 1) < -alpha - etol){ |
| 2445 |
matind = (int *) malloc((vrp->vertnum+vrp->numroutes)*ISIZE); |
| 2446 |
matval = (double *) malloc((vrp->vertnum+vrp->numroutes)*DSIZE); |
| 2447 |
for (nzcnt = 0, i = 0; i < num_arcs; i++){ |
| 2448 |
cur_edge = row_edges[i]; |
| 2449 |
if ((coef = x[INDEX(cur_edge->v0, cur_edge->v1)]) > etol){ |
| 2450 |
matind[nzcnt] = i; |
| 2451 |
matval[nzcnt++] = (double)coef; |
| 2452 |
} |
| 2453 |
} |
| 2454 |
matind[nzcnt] = lp_data->m-1; |
| 2455 |
matval[nzcnt++] = 1.0; |
| 2456 |
if (nzcnt > vrp->vertnum+vrp->numroutes){ |
| 2457 |
printf("Too many nonzeros (%i) !!!!\n\n", nzcnt); |
| 2458 |
sleep(600); |
| 2459 |
exit(); |
| 2460 |
} |
| 2461 |
matbeg[1] = nzcnt; |
| 2462 |
if (lp_data->n < lp_data->maxn){ |
| 2463 |
add_cols(lp_data, 1, nzcnt, &obj, matbeg, matind, matval, &lb, |
| 2464 |
&ub, 0); |
| 2465 |
lp_data->matbeg[lp_data->n] = lp_data->nz; |
| 2466 |
} |
| 2467 |
FREE(costs); |
| 2468 |
FREE(sort_order); |
| 2469 |
FREE(head); |
| 2470 |
FREE(arcs); |
| 2471 |
FREE(indicators); |
| 2472 |
FREE(unbd_row); |
| 2473 |
FREE(soln); |
| 2474 |
FREE(z); |
| 2475 |
FREE(x); |
| 2476 |
FREE(matval); |
| 2477 |
FREE(matind); |
| 2478 |
return(lp_data->n == lp_data->maxn ? -1 : 1); |
| 2479 |
} |
| 2480 |
} |
| 2481 |
} |
| 2482 |
FREE(costs); |
| 2483 |
FREE(sort_order); |
| 2484 |
FREE(head); |
| 2485 |
FREE(arcs); |
| 2486 |
FREE(indicators); |
| 2487 |
FREE(unbd_row); |
| 2488 |
FREE(soln); |
| 2489 |
FREE(z); |
| 2490 |
FREE(x); |
| 2491 |
return(0); |
| 2492 |
} |
| 2493 |
|
| 2494 |
/*===========================================================================*/ |
| 2495 |
|
| 2496 |
#else |
| 2497 |
|
| 2498 |
int vrp_generate_new_cols(cg_prob *p, LPdata *lp_data, network *n, |
| 2499 |
edge **row_edges, int comp_num) |
| 2500 |
{ |
| 2501 |
cg_vrp_spec *vrp = (cg_vrp_spec *)p->user; |
| 2502 |
double *unbd_row; |
| 2503 |
int unbd_row_index, mult; |
| 2504 |
int i, equality; |
| 2505 |
int vertnum = vrp->vertnum; |
| 2506 |
int *head; |
| 2507 |
double beta, *z, *soln; |
| 2508 |
char *indicators; |
| 2509 |
double etol = p->cur_sol.lpetol; |
| 2510 |
double *costs, lb = 0.0, ub = CPX_INFBOUND, *matval, obj = 0.0; |
| 2511 |
int matbeg[2] = {0,0}; |
| 2512 |
int *matind, *x, nzcnt = 0, coef, cpx_status; |
| 2513 |
|
| 2514 |
if (!lp_data->n){ |
| 2515 |
costs = (double *) calloc(vertnum*(vertnum-1)/2, DSIZE); |
| 2516 |
x = (int *) calloc(vertnum*(vertnum-1)/2, ISIZE); |
| 2517 |
if (decomp_lower_bound(vrp, costs, x, 0, 1) == 0){ |
| 2518 |
cpx_status = CPXsetintparam(lp_data->cpxenv, CPX_PARAM_SCAIND, -1); |
| 2519 |
cpx_status = |
| 2520 |
CPXsetintparam(lp_data->cpxenv, CPX_PARAM_BASINTERVAL, 2100000000); |
| 2521 |
cpx_status = CPXsetintparam(lp_data->cpxenv, CPX_PARAM_AGGIND, 0); |
| 2522 |
cpx_status = CPXsetintparam(lp_data->cpxenv, CPX_PARAM_DEPIND, 0); |
| 2523 |
cpx_status = CPXsetintparam(lp_data->cpxenv, CPX_PARAM_PREIND, 0); |
| 2524 |
|
| 2525 |
CPX_check_error("load_lp - CPXsetintparam"); |
| 2526 |
|
| 2527 |
lp_data->lp = |
| 2528 |
CPXloadlp(lp_data->cpxenv, |
| 2529 |
(char *) "Decomp_prob", lp_data->n, lp_data->m, 1, |
| 2530 |
lp_data->obj, |
| 2531 |
lp_data->rhs, lp_data->sense, lp_data->matbeg, |
| 2532 |
lp_data->matcnt, lp_data->matind, lp_data->matval, |
| 2533 |
lp_data->lb, lp_data->ub, lp_data->rngval, |
| 2534 |
lp_data->maxn+lp_data->maxm, lp_data->maxm, |
| 2535 |
lp_data->maxnz+lp_data->maxm); |
| 2536 |
|
| 2537 |
p->dcmp_data.iter_num = 0; |
| 2538 |
matind = (int *) malloc((vrp->vertnum+vrp->numroutes)*ISIZE); |
| 2539 |
matval = (double *) malloc((vrp->vertnum+vrp->numroutes)*DSIZE); |
| 2540 |
for (nzcnt = 0, i = 0; i < lp_data->m - 1; i++){ |
| 2541 |
if ((coef = x[i]) > etol){ |
| 2542 |
matind[nzcnt] = i; |
| 2543 |
matval[nzcnt++] = (double)coef; |
| 2544 |
} |
| 2545 |
} |
| 2546 |
matind[nzcnt] = lp_data->m - 1; |
| 2547 |
matval[nzcnt++] = 1.0; |
| 2548 |
matbeg[1] = nzcnt; |
| 2549 |
if (lp_data->n < lp_data->maxn){ |
| 2550 |
add_cols(lp_data, 1, nzcnt, &obj, matbeg, matind, matval, &lb, |
| 2551 |
&ub, 0); |
| 2552 |
lp_data->matbeg[lp_data->n] = lp_data->nz; |
| 2553 |
} |
| 2554 |
FREE(costs); |
| 2555 |
FREE(x); |
| 2556 |
FREE(matval); |
| 2557 |
FREE(matind); |
| 2558 |
return(lp_data->n == lp_data->maxn ? -1 : 1); |
| 2559 |
}else{ |
| 2560 |
return(0); |
| 2561 |
} |
| 2562 |
} |
| 2563 |
|
| 2564 |
x = (int *) calloc(vertnum*(vertnum-1)/2, ISIZE); |
| 2565 |
z = (double *) calloc( MAX(lp_data->m, lp_data->n), DSIZE); |
| 2566 |
soln = (double *) calloc(lp_data->m, DSIZE); |
| 2567 |
head = (int *) calloc(lp_data->m, ISIZE); |
| 2568 |
unbd_row = (double *) malloc(lp_data->m * DSIZE); |
| 2569 |
|
| 2570 |
CPXgetbhead(lp_data->cpxenv, lp_data->lp, head, soln); |
| 2571 |
|
| 2572 |
for (unbd_row_index = 0; unbd_row_index < lp_data->m; unbd_row_index++){ |
| 2573 |
if (soln[unbd_row_index] < -etol || (soln[unbd_row_index] > etol && |
| 2574 |
head[unbd_row_index] < 0)){ |
| 2575 |
mult = soln[unbd_row_index] < 0 ? 1 : -1; |
| 2576 |
cpx_status = |
| 2577 |
CPXbinvarow(lp_data->cpxenv, lp_data->lp, unbd_row_index, z); |
| 2578 |
for (i = 0, equality = 0; i < lp_data->n; i++){ |
| 2579 |
if (mult*z[i] < -etol) break; |
| 2580 |
if (fabs(z[i]) < etol) equality++; |
| 2581 |
} |
| 2582 |
if (i < lp_data->n) continue; |
| 2583 |
|
| 2584 |
cpx_status = |
| 2585 |
CPXbinvrow(lp_data->cpxenv, lp_data->lp, unbd_row_index, unbd_row); |
| 2586 |
|
| 2587 |
if (fabs(unbd_row[lp_data->m - 1]) > etol){ |
| 2588 |
beta = mult*unbd_row[lp_data->m-1]; |
| 2589 |
}else{ |
| 2590 |
beta = 0; |
| 2591 |
} |
| 2592 |
|
| 2593 |
memset(x, 0, (vertnum*(vertnum-1)/2)*ISIZE); |
| 2594 |
|
| 2595 |
for (i = 0; i < lp_data->m -1; i++) |
| 2596 |
unbd_row[i] *= mult; |
| 2597 |
|
| 2598 |
if (decomp_lower_bound(vrp, unbd_row, x, 0, mult) < -beta - etol){ |
| 2599 |
matind = (int *) malloc((vrp->vertnum+vrp->numroutes)*ISIZE); |
| 2600 |
matval = (double *) malloc((vrp->vertnum+vrp->numroutes)*DSIZE); |
| 2601 |
for (nzcnt = 0, i = 0; i < lp_data->m - 1; i++){ |
| 2602 |
if ((coef = x[i]) > etol){ |
| 2603 |
matind[nzcnt] = i; |
| 2604 |
matval[nzcnt++] = (double)coef; |
| 2605 |
} |
| 2606 |
} |
| 2607 |
matind[nzcnt] = lp_data->m-1; |
| 2608 |
matval[nzcnt++] = 1.0; |
| 2609 |
matbeg[1] = nzcnt; |
| 2610 |
if (lp_data->n < lp_data->maxn){ |
| 2611 |
add_cols(lp_data, 1, nzcnt, &obj, matbeg, matind, matval, &lb, |
| 2612 |
&ub, 0); |
| 2613 |
lp_data->matbeg[lp_data->n] = lp_data->nz; |
| 2614 |
} |
| 2615 |
FREE(head); |
| 2616 |
FREE(unbd_row); |
| 2617 |
FREE(soln); |
| 2618 |
FREE(z); |
| 2619 |
FREE(x); |
| 2620 |
FREE(matval); |
| 2621 |
FREE(matind); |
| 2622 |
return(lp_data->n == lp_data->maxn ? -1 : 1); |
| 2623 |
} |
| 2624 |
} |
| 2625 |
} |
| 2626 |
FREE(head); |
| 2627 |
FREE(unbd_row); |
| 2628 |
FREE(soln); |
| 2629 |
FREE(z); |
| 2630 |
FREE(x); |
| 2631 |
return(0); |
| 2632 |
} |
| 2633 |
|
| 2634 |
#endif |
| 2635 |
|
| 2636 |
/*===========================================================================*/ |
| 2637 |
|
| 2638 |
void delete_zero_rows(LPdata *lp_data, int bc_index, int iter_num) |
| 2639 |
{ |
| 2640 |
int *new_row_number = (int *) malloc(lp_data->m*ISIZE), new_row_num = 0; |
| 2641 |
char *indicators = (char *) calloc(lp_data->m, ISIZE); |
| 2642 |
FILE *f; |
| 2643 |
int i, j, termcode, stat; |
| 2644 |
char name1[50] = ""; |
| 2645 |
|
| 2646 |
for (i = 0; i < lp_data->nz; i++) |
| 2647 |
indicators[lp_data->matind[i]] = TRUE; |
| 2648 |
|
| 2649 |
for (i = 0; i < lp_data->m; i++){ |
| 2650 |
if (indicators[i]){ |
| 2651 |
new_row_number[i] = new_row_num++; |
| 2652 |
}else{ |
| 2653 |
new_row_number[i] = -1; |
| 2654 |
} |
| 2655 |
} |
| 2656 |
|
| 2657 |
for (i = 0; i < lp_data->m; i++){ |
| 2658 |
if (indicators[i]) |
| 2659 |
lp_data->sense[new_row_number[i]] = lp_data->sense[i]; |
| 2660 |
} |
| 2661 |
|
| 2662 |
for (i = 0; i < lp_data->nz; i++){ |
| 2663 |
lp_data->matind[i] = new_row_number[lp_data->matind[i]]; |
| 2664 |
} |
| 2665 |
|
| 2666 |
for (i = 0; i < lp_data->m; i++) |
| 2667 |
if (indicators[i]){ |
| 2668 |
lp_data->rhs[new_row_number[i]] = lp_data->rhs[i]; |
| 2669 |
} |
| 2670 |
|
| 2671 |
lp_data->m = new_row_num; |
| 2672 |
|
| 2673 |
#if 0 |
| 2674 |
lp_data->lp = |
| 2675 |
CPXloadlp(lp_data->cpxenv, |
| 2676 |
(char *) "Decomp_prob", lp_data->n, lp_data->m, 1, |
| 2677 |
lp_data->obj, |
| 2678 |
lp_data->rhs, lp_data->sense, lp_data->matbeg, lp_data->matcnt, |
| 2679 |
lp_data->matind, lp_data->matval, lp_data->lb, lp_data->ub, |
| 2680 |
lp_data->rngval, lp_data->maxn+lp_data->maxm, lp_data->maxm, |
| 2681 |
lp_data->maxnz+lp_data->maxm); |
| 2682 |
|
| 2683 |
|
| 2684 |
termcode = CPXdualopt(lp_data->cpxenv, lp_data->lp); |
| 2685 |
|
| 2686 |
switch (stat = CPXgetstat(lp_data->cpxenv,lp_data->lp)){ |
| 2687 |
case CPX_OPTIMAL: termcode = OPTIMAL; break; |
| 2688 |
case CPX_INFEASIBLE: termcode = D_INFEASIBLE; break; |
| 2689 |
case CPX_UNBOUNDED: termcode = D_UNBOUNDED; break; |
| 2690 |
case CPX_OBJ_LIM: termcode = D_OBJLIM; break; |
| 2691 |
case CPX_IT_LIM_FEAS: |
| 2692 |
case CPX_IT_LIM_INFEAS: termcode = D_ITLIM; break; |
| 2693 |
default: termcode = ABANDONED; break; |
| 2694 |
} |
| 2695 |
#endif |
| 2696 |
|
| 2697 |
#if 0 |
| 2698 |
sprintf(name1,"/home/tkr/tmp/matrices/test.%i.%i.mps", bc_index, iter_num); |
| 2699 |
|
| 2700 |
f = fopen(name1, "w"); |
| 2701 |
|
| 2702 |
fprintf(f, "NAME %s\nROWS\n N obj\n", name1); |
| 2703 |
|
| 2704 |
for (i = 0; i < lp_data->m; i++){ |
| 2705 |
if (indicators[i]) |
| 2706 |
fprintf(f, " %c %6ir\n", lp_data->sense[new_row_number[i]], |
| 2707 |
new_row_number[i]); |
| 2708 |
} |
| 2709 |
|
| 2710 |
fprintf(f, "COLUMNS\n"); |
| 2711 |
|
| 2712 |
for (j = 0; j < lp_data->n; j++){ |
| 2713 |
fprintf(f, " %6ix obj %f\n", j, lp_data->obj[j]); |
| 2714 |
for (i = 0; i < lp_data->matcnt[j]; i++){ |
| 2715 |
fprintf(f, " %6ix %6ir %f\n", |
| 2716 |
j, new_row_number[lp_data->matind[lp_data->matbeg[j]+i]], |
| 2717 |
lp_data->matval[lp_data->matbeg[j]+i]); |
| 2718 |
} |
| 2719 |
} |
| 2720 |
|
| 2721 |
fprintf(f, "RHS\n"); |
| 2722 |
|
| 2723 |
for (i = 0; i < lp_data->m; i++) |
| 2724 |
if (indicators[i]){ |
| 2725 |
fprintf(f, " rhs %6ir %f\n", new_row_number[i], |
| 2726 |
lp_data->rhs[new_row_number[i]]); |
| 2727 |
} |
| 2728 |
|
| 2729 |
fprintf(f, "BOUNDS\n"); |
| 2730 |
|
| 2731 |
for (j = 0; j < lp_data->n; j++){ |
| 2732 |
fprintf(f, " LO BOUND %6ix %f\n", j, lp_data->lb[j]); |
| 2733 |
fprintf(f, " UP BOUND %6ix %f\n", j, lp_data->ub[j]); |
| 2734 |
} |
| 2735 |
|
| 2736 |
fprintf(f, "ENDATA\n"); |
| 2737 |
|
| 2738 |
fclose(f); |
| 2739 |
#endif |
| 2740 |
} |
| 2741 |
|
| 2742 |
/*===========================================================================*/ |
| 2743 |
|
| 2744 |
dcmp_col_set *user_generate_new_cols(cg_prob *p) |
| 2745 |
{ |
| 2746 |
return(NULL); |
| 2747 |
} |
| 2748 |
|
| 2749 |
/*===========================================================================*/ |
| 2750 |
|
| 2751 |
void user_display_col(cg_prob *p, col_data *col) |
| 2752 |
{ |
| 2753 |
} |
| 2754 |
|
| 2755 |
/*===========================================================================*/ |
| 2756 |
|
| 2757 |
int user_check_col(cg_prob *p, int *colind, double *colval, int collen) |
| 2758 |
{ |
| 2759 |
return(0); |
| 2760 |
} |
| 2761 |
|
| 2762 |
/*===========================================================================*/ |
| 2763 |
|
| 2764 |
void user_unpack_col(cg_prob *p, col_data *col, int *nzcnt, int *matind) |
| 2765 |
{ |
| 2766 |
memcpy ((char *) matind, col->coef, col->size); |
| 2767 |
} |
| 2768 |
|
| 2769 |
/*===========================================================================*/ |
| 2770 |
|
| 2771 |
void user_pack_col(int *colind, int collen, col_data *col) |
| 2772 |
{ |
| 2773 |
} |
| 2774 |
|
| 2775 |
/*===========================================================================*/ |
| 2776 |
|
| 2777 |
void user_free_decomp_data_structures(cg_prob *p, void **user) |
| 2778 |
{ |
| 2779 |
} |
| 2780 |
|
| 2781 |
/*===========================================================================*/ |
| 2782 |
|
| 2783 |
char user_set_rhs(int varnum, double *rhs, int length, int *ind, |
| 2784 |
double *val, void *user) |
| 2785 |
{ |
| 2786 |
return(FALSE); |
| 2787 |
} |