Debian Codegraph @

SYMPHONY/Applications/VRP/src/CutGen/Decomp/my_decomp_user.c

raw
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 }