1 /*===========================================================================*/
2 /* */
3 /* This file is part of a demonstration application for use with the */
4 /* SYMPHONY Branch, Cut, and Price Library. This application is a solver for */
5 /* the Vehicle Routing Problem and the Traveling Salesman Problem. */
6 /* */
7 /* (c) Copyright 2000-2007 Ted Ralphs. All Rights Reserved. */
8 /* */
9 /* This application was developed by Ted Ralphs (ted@lehigh.edu) */
10 /* */
11 /* This software is licensed under the Eclipse Public License. Please see */
12 /* accompanying file for terms. */
13 /* */
14 /*===========================================================================*/
15
16 /* system include files */
17 #include <stdlib.h>
18 #include <string.h>
19
20 /* SYMPHONY include files */
21 #include "sym_macros.h"
22 #include "sym_constants.h"
23 #include "sym_proccomm.h"
24 #include "sym_cg_u.h"
25
26 /* VRP include files */
27 #include "vrp_cg.h"
28 /*__BEGIN_EXPERIMENTAL_SECTION__*/
29 #ifdef COMPILE_DECOMP
30 #include "my_decomp.h"
31 #include "decomp.h"
32 #endif
33 #include "sym_dg_params.h"
34 #include "vrp_dg.h"
35 /*___END_EXPERIMENTAL_SECTION___*/
36 #include "vrp_macros.h"
37 #include "vrp_const.h"
38
39 /*__BEGIN_EXPERIMENTAL_SECTION__*/
40 #if 0
41 #include "util.h"
42 CCrandstate rand_state;
43 #endif
44 /*___END_EXPERIMENTAL_SECTION___*/
45
46 /*===========================================================================*/
47
48 /*===========================================================================*\
49 * This file contains user-written functions used by the cut generator
50 * process.
51 \*===========================================================================*/
52
53 /*===========================================================================*\
54 * Here is where the user must receive all of the data sent from
55 * user_send_cg_data() and set up data structures. Note that this function is
56 * only called if one of COMPILE_IN_CG, COMPILE_IN_LP, or COMPILE_IN_TM is
57 * FALSE.
58 \*===========================================================================*/
59
user_receive_cg_data(void ** user,int dg_id)60 int user_receive_cg_data(void **user, int dg_id)
61 {
62 int i, j, k;
63 /* This is the user-defined data structure, a pointer to which will
64 be passed to each user function. It must contain all the
65 problem-specific data needed for computations within the CG */
66 vrp_cg_problem *vrp = (vrp_cg_problem *) malloc(sizeof(vrp_cg_problem));
67 int edgenum;
68
69 *user = vrp;
70
71 vrp->n = NULL;
72
73 /*------------------------------------------------------------------------*\
74 * Receive the data
75 \*------------------------------------------------------------------------*/
76
77 receive_char_array((char *)(&vrp->par), sizeof(vrp_cg_params));
78
79 receive_int_array(&vrp->dg_id, 1);
80 receive_int_array(&vrp->numroutes, 1);
81 receive_int_array(&vrp->vertnum, 1);
82 vrp->demand = (int *) calloc(vrp->vertnum, sizeof(int));
83 receive_int_array(vrp->demand, vrp->vertnum);
84 receive_int_array(&vrp->capacity, 1);
85 edgenum = vrp->vertnum*(vrp->vertnum-1)/2;
86 #ifdef CHECK_CUT_VALIDITY
87 receive_int_array(&vrp->feas_sol_size, 1);
88 if (vrp->feas_sol_size){
89 vrp->feas_sol = (int *) calloc(vrp->feas_sol_size, sizeof(int));
90 receive_int_array(vrp->feas_sol, vrp->feas_sol_size);
91 }
92 #endif
93
94 /*------------------------------------------------------------------------*\
95 * Set up some data structures
96 \*------------------------------------------------------------------------*/
97
98 /*__BEGIN_EXPERIMENTAL_SECTION__*/
99 #ifdef COMPILE_OUR_DECOMP
100 if (vrp->par.do_our_decomp){
101 vrp->cost = (int *) calloc(edgenum, sizeof(int));
102 receive_int_array(vrp->cost, edgenum);
103 usr_open_decomp_lp( get_cg_ptr(NULL), edgenum );
104 }
105
106 vrp->last_decomp_index = -1;
107 #endif
108 /*___END_EXPERIMENTAL_SECTION___*/
109 vrp->in_set = (char *) calloc(vrp->vertnum, sizeof(char));
110 vrp->ref = (int *) malloc(vrp->vertnum*sizeof(int));
111 vrp->new_demand = (int *) malloc(vrp->vertnum*sizeof(int));
112 vrp->cut_val = (double *) calloc(vrp->vertnum, sizeof(double));
113 vrp->cut_list = (char *) malloc(((vrp->vertnum >> DELETE_POWER)+1)*
114 (vrp->par.max_num_cuts_in_shrink + 1)*
115 sizeof(char));
116
117 vrp->edges = (int *) calloc(2*edgenum, sizeof(int));
118
119 /*create the edge list (we assume a complete graph)*/
120 for (i = 1, k = 0; i < vrp->vertnum; i++){
121 for (j = 0; j < i; j++){
122 vrp->edges[k << 1] = j;
123 vrp->edges[(k << 1) + 1] = i;
124 k++;
125 }
126 }
127
128 vrp->dg_id = dg_id;
129
130 return(USER_SUCCESS);
131 }
132
133 /*===========================================================================*/
134
user_receive_lp_solution_cg(void * user)135 int user_receive_lp_solution_cg(void *user)
136 {
137 /* Leave this job to SYMPHONY. We don't need anything special */
138 return(USER_DEFAULT);
139 }
140
141 /*===========================================================================*/
142
143 /*===========================================================================*\
144 * Free the user data structure
145 \*===========================================================================*/
146
user_free_cg(void ** user)147 int user_free_cg(void **user)
148 {
149 vrp_cg_problem *vrp = (vrp_cg_problem *)(*user);
150
151 #if defined(CHECK_CUT_VALIDITY) && !defined(COMPILE_IN_TM)
152 if (vrp->feas_sol_size)
153 FREE(vrp->feas_sol);
154 #endif
155 /*__BEGIN_EXPERIMENTAL_SECTION__*/
156 #ifdef COMPILE_OUR_DECOMP
157 #if !defined(COMPILE_IN_CG)
158 if (vrp->par.do_our_decomp){
159 close_decomp_lp( get_cg_ptr(NULL) );
160 FREE(vrp->cost);
161 }
162 #endif
163 CClp_close();
164 #endif
165 /*___END_EXPERIMENTAL_SECTION___*/
166 #pragma omp master
167 {
168 #if 0
169 FREE(vrp->demand);
170 FREE(vrp->edges);
171 FREE(vrp->in_set);
172 FREE(vrp->ref);
173 FREE(vrp->new_demand);
174 FREE(vrp->cut_val);
175 FREE(vrp->cut_list);
176
177 FREE(*user);
178 #endif
179 }
180
181 return(USER_SUCCESS);
182 }
183
184 /*===========================================================================*/
185
186 /*===========================================================================*\
187 * Find cuts violated by a particular LP solution. This is a fairly
188 * involved function but the bottom line is that an LP solution comes in
189 * and cuts go out.
190 \*===========================================================================*/
191
user_find_cuts(void * user,int varnum,int iter_num,int level,int index,double objval,int * indices,double * values,double ub,double etol,int * num_cuts,int * alloc_cuts,cut_data *** cuts)192 int user_find_cuts(void *user, int varnum, int iter_num, int level,
193 int index, double objval, int *indices, double *values,
194 double ub, double etol, int *num_cuts, int *alloc_cuts,
195 cut_data ***cuts)
196 {
197 vrp_cg_problem *vrp = (vrp_cg_problem *)user;
198 int vertnum = vrp->vertnum;
199 network *n;
200 vertex *verts = NULL;
201 int *compdemands = NULL, *compnodes = NULL, *compnodes_copy = NULL;
202 int *compmembers = NULL, comp_num = 0;
203 /*__BEGIN_EXPERIMENTAL_SECTION__*/
204 int *compdemands_copy = NULL;
205 double *compcuts_copy = NULL, *compdensity = NULL, density;
206 /*___END_EXPERIMENTAL_SECTION___*/
207 double node_cut, max_node_cut, *compcuts = NULL;
208 int rcnt, cur_bins = 0, k;
209 char **coef_list;
210 int i, max_node;
211 double cur_slack = 0.0;
212 int capacity = vrp->capacity;
213 int cut_size = (vertnum >> DELETE_POWER) + 1;
214 cut_data *new_cut = NULL;
215 elist *cur_edge = NULL;
216 int which_connected_routine = vrp->par.which_connected_routine;
217 int *ref = vrp->ref;
218 double *cut_val = vrp->cut_val;
219 char *in_set = vrp->in_set;
220 char *cut_list = vrp->cut_list;
221
222 elist *cur_edge1 = NULL, *cur_edge2 = NULL;
223 /*__BEGIN_EXPERIMENTAL_SECTION__*/
224 #ifdef COMPILE_OUR_DECOMP
225 edge *edge_pt;
226 #endif
227 /*___END_EXPERIMENTAL_SECTION___*/
228 int node1 = 0, node2 = 0;
229 int *demand = vrp->demand;
230 int *new_demand = vrp->new_demand;
231 int total_demand = demand[0];
232 int num_routes = vrp->numroutes, num_trials;
233 int triangle_cuts = 0;
234 char *coef;
235
236 if (iter_num == 1) SRANDOM(1);
237 /*__BEGIN_EXPERIMENTAL_SECTION__*/
238 #if 0
239 CCutil_sprand(1, &rand_state);
240 #endif
241 /*___END_EXPERIMENTAL_SECTION___*/
242
243 /*__BEGIN_EXPERIMENTAL_SECTION__*/
244
245 #if 0
246 if (vrp->dg_id && vrp->par.verbosity > 3){
247 sprintf(name, "support graph");
248 display_support_graph(vrp->dg_id, (p->cur_sol.xindex == 0 &&
249 p->cur_sol.xiter_num == 1) ? TRUE: FALSE, name,
250 varnum, xind, xval,
251 etol, CTOI_WAIT_FOR_CLICK_AND_REPORT);
252 }
253 #endif
254 /*___END_EXPERIMENTAL_SECTION___*/
255
256 /* This creates a fractional graph representing the LP solution */
257 n = createnet(indices, values, varnum, etol, vrp->edges, demand, vertnum);
258 if (n->is_integral){
259 /* if the network is integral, check for connectivity */
260 check_connectivity(n, etol, capacity, num_routes, cuts, num_cuts,
261 alloc_cuts);
262 free_net(n);
263 return(USER_SUCCESS);
264 }
265
266 #ifdef DO_TSP_CUTS
267 if (vrp->par.which_tsp_cuts && vrp->par.tsp_prob){
268 tsp_cuts(n, vrp->par.verbosity, vrp->par.tsp_prob,
269 vrp->par.which_tsp_cuts, cuts, num_cuts, alloc_cuts);
270 free_net(n);
271 return(USER_SUCCESS);
272 }
273 #endif
274
275 /*__BEGIN_EXPERIMENTAL_SECTION__*/
276 if (!vrp->par.always_do_mincut){/*user_par.always_do_mincut indicates
277 whether we should just always do the
278 min_cut routine or whether we should also
279 try this routine*/
280 /*___END_EXPERIMENTAL_SECTION___*/
281 /*UNCOMMENT FOR PRODUCTION CODE*/
282 #if 0
283 {
284 #endif
285 verts = n->verts;
286 if (which_connected_routine == BOTH)
287 which_connected_routine = CONNECTED;
288
289 new_cut = (cut_data *) calloc(1, sizeof(cut_data));
290 new_cut->size = cut_size;
291 compnodes_copy = (int *) malloc((vertnum + 1) * sizeof(int));
292 compmembers = (int *) malloc((vertnum + 1) * sizeof(int));
293 /*__BEGIN_EXPERIMENTAL_SECTION__*/
294 compdemands_copy = (int *) calloc(vertnum + 1, sizeof(int));
295 compcuts_copy = (double *) calloc(vertnum + 1, sizeof(double));
296 #ifdef COMPILE_OUR_DECOMP
297 compdensity = vrp->par.do_our_decomp ?
298 (double *) calloc(vertnum+1, sizeof(double)) : NULL;
299 #endif
300 /*___END_EXPERIMENTAL_SECTION___*/
301
302 do{
303 compnodes = (int *) calloc(vertnum + 1, sizeof(int));
304 compdemands = (int *) calloc(vertnum + 1, sizeof(int));
305 compcuts = (double *) calloc(vertnum + 1, sizeof(double));
306
307 /*------------------------------------------------------------------*\
308 * Get the connected components of the solution graph without the
309 * depot and see if the number of components is more than one
310 \*------------------------------------------------------------------*/
311 rcnt = (which_connected_routine == BICONNECTED ?
312 biconnected(n, compnodes, compdemands, compcuts) :
313 connected(n, compnodes, compdemands, compmembers,
314 /*__BEGIN_EXPERIMENTAL_SECTION__*/
315 compcuts, compdensity));
316 /*___END_EXPERIMENTAL_SECTION___*/
317 /*UNCOMMENT FOR PRODUCTION CODE*/
318 #if 0
319 compcuts, NULL));
320 #endif
321
322 /* copy the arrays as they will be needed later */
323 if (!which_connected_routine &&
324 /*__BEGIN_EXPERIMENTAL_SECTION__*/
325 (vrp->par.do_greedy || vrp->par.do_our_decomp)){
326 /*___END_EXPERIMENTAL_SECTION___*/
327 /*UNCOMMENT FOR PRODUCTION CODE*/
328 #if 0
329 vrp->par.do_greedy){
330 #endif
331 compnodes_copy = (int *) memcpy((char *)compnodes_copy,
332 (char*)compnodes,
333 (vertnum+1)*sizeof(int));
334 /*__BEGIN_EXPERIMENTAL_SECTION__*/
335 compdemands_copy = (int *) memcpy((char *)compdemands_copy,
336 (char *)compdemands, (vertnum+1)*ISIZE);
337 compcuts_copy = (double *) memcpy((char *)compcuts_copy,
338 (char *)compcuts,
339 (vertnum+1)*DSIZE);
340 /*___END_EXPERIMENTAL_SECTION___*/
341 n->compnodes = compnodes_copy;
342 comp_num = rcnt;
343 }
344 if (rcnt > 1){
345 /*---------------------------------------------------------------*\
346 * If the number of components is more then one, then check each
347 * component to see if it violates a capacity constraint
348 \*---------------------------------------------------------------*/
349
350 coef_list = (char **) calloc(rcnt, sizeof(char *));
351 coef_list[0] = (char *) calloc(rcnt*cut_size, sizeof(char));
352 for(i = 1; i<rcnt; i++)
353 coef_list[i] = coef_list[0]+i*cut_size;
354
355 for(i = 1; i < vertnum; i++)
356 (coef_list[(verts[i].comp)-1][i >> DELETE_POWER]) |=
357 (1 << (i & DELETE_AND));
358
359 for (i = 0; i < rcnt; i++){
360 if (compnodes[i+1] < 2) continue;
361 /*check ith component to see if it violates a constraint*/
362 if (vrp->par.which_connected_routine == BOTH &&
363 which_connected_routine == BICONNECTED && compcuts[i+1]==0)
364 continue;
365 if (compcuts[i+1] < 2*BINS(compdemands[i+1], capacity)-etol){
366 /*the constraint is violated so impose it*/
367 new_cut->coef = (char *) (coef_list[i]);
368 new_cut->type = (compnodes[i+1] < vertnum/2 ?
369 SUBTOUR_ELIM_SIDE:SUBTOUR_ELIM_ACROSS);
370 new_cut->rhs = (new_cut->type == SUBTOUR_ELIM_SIDE ?
371 RHS(compnodes[i+1],compdemands[i+1],
372 capacity): 2*BINS(compdemands[i+1],
373 capacity));
374 cg_send_cut(new_cut, num_cuts, alloc_cuts, cuts);
375 }
376 else{/*if the constraint is not violated, then try generating a
377 violated constraint by deleting customers that don't
378 change the number of trucks required by the customers in
379 the component but decrease the value of the cut*/
380 cur_bins = BINS(compdemands[i+1], capacity);/*the current
381 number of trucks required*/
382 /*current slack in the constraint*/
383 cur_slack = (compcuts[i+1] - 2*cur_bins);
384 while (compnodes[i+1]){/*while there are still nodes in the
385 component*/
386 for (max_node = 0, max_node_cut = 0, k = 1;
387 k < vertnum; k++){
388 if (verts[k].comp == i+1){
389 if (BINS(compdemands[i+1]-verts[k].demand, capacity)
390 == cur_bins){
391 /*if the number of trucks doesn't decrease upon
392 deleting this customer*/
393 for (node_cut = 0, cur_edge = verts[k].first;
394 cur_edge; cur_edge = cur_edge->next_edge){
395 node_cut += (cur_edge->other_end ?
396 -cur_edge->data->weight :
397 cur_edge->data->weight);
398 }
399 if (node_cut > max_node_cut){/*check whether the
400 value of the cut decrease is the best
401 seen so far*/
402 max_node = k;
403 max_node_cut = node_cut;
404 }
405 }
406 }
407 }
408 if (!max_node){
409 break;
410 }
411 /*delete the customer that exhibited the greatest
412 decrease in cut value*/
413 compnodes[i+1]--;
414 compdemands[i+1] -= verts[max_node].demand;
415 compcuts[i+1] -= max_node_cut;
416 cur_slack -= max_node_cut;
417 verts[max_node].comp = 0;
418 coef_list[i][max_node >> DELETE_POWER] ^=
419 (1 << (max_node & DELETE_AND));
420 if (cur_slack < 0){/*if the cut is now violated, impose
421 it*/
422 new_cut->coef = (char *) (coef_list[i]);
423 new_cut->type = (compnodes[i+1] < vertnum/2 ?
424 SUBTOUR_ELIM_SIDE:SUBTOUR_ELIM_ACROSS);
425 new_cut->size = cut_size;
426 new_cut->rhs = (new_cut->type == SUBTOUR_ELIM_SIDE ?
427 RHS(compnodes[i+1], compdemands[i+1],
428 capacity): 2*cur_bins);
429 cg_send_cut(new_cut, num_cuts, alloc_cuts, cuts);
430 break;
431 }
432 }
433 }
434 }
435 FREE(coef_list[0]);
436 FREE(coef_list);
437 }
438 which_connected_routine++;
439 FREE(compnodes);
440 FREE(compdemands);
441 FREE(compcuts);
442 }while((!(*num_cuts) && vrp->par.which_connected_routine == BOTH)
443 && which_connected_routine < 2);
444 }
445
446 /*__BEGIN_EXPERIMENTAL_SECTION__*/
447 #if 0
448 if (!*(num_cuts) && vrp->par.do_mincut){
449 min_cut(vrp, n, etol);
450 }
451 #endif
452
453 if (!vrp->par.do_greedy && !vrp->par.do_our_decomp){
454 /*___END_EXPERIMENTAL_SECTION___*/
455 /*UNCOMMENT FOR PRODUCTION CODE*/
456 #if 0
457 if (!vrp->par.do_greedy){
458 #endif
459 free_net(n);
460 return(USER_SUCCESS);
461 }
462
463 if (*num_cuts < 10 && vrp->par.do_greedy){
464 coef = (char *) malloc(cut_size * sizeof(char));
465 for (cur_edge=verts[0].first; cur_edge; cur_edge=cur_edge->next_edge){
466 for (cur_edge1 = cur_edge->other->first; cur_edge1;
467 cur_edge1 = cur_edge1->next_edge){
468 if (cur_edge1->data->weight + cur_edge->data->weight < 1 - etol)
469 continue;
470 node1 = cur_edge->other_end;
471 node2 = cur_edge1->other_end;
472 for (cur_edge2 = verts[node2].first; cur_edge2;
473 cur_edge2 = cur_edge2->next_edge){
474 if (!(cur_edge2->other_end) && node2){
475 if ((BINS(total_demand - demand[node1] - demand[node2],
476 capacity) > num_routes -1) &&
477 (cur_edge1->data->weight + cur_edge->data->weight +
478 cur_edge2->data->weight>2+etol)){
479 new_cut->type = SUBTOUR_ELIM_ACROSS;
480 new_cut->size =cut_size;
481 new_cut->rhs =2*BINS(total_demand - demand[node1] -
482 demand[node2],capacity);
483 memset(coef, 0, cut_size);
484 for (i = 1; i <vertnum ; i++)
485 if ((i != node1) && (i != node2))
486 (coef[i >> DELETE_POWER]) |= (1 << (i&DELETE_AND));
487 new_cut->coef =coef;
488 triangle_cuts += cg_send_cut(new_cut, num_cuts, alloc_cuts,
489 cuts);
490 }
491 break;
492 }
493 }
494 }
495 }
496 FREE(coef);
497 if (vrp->par.verbosity > 2)
498 printf("Found %d triangle cuts\n",triangle_cuts);
499 }
500
501 if (*num_cuts < 10 && vrp->par.do_greedy){
502 memcpy((char *)new_demand, (char *)demand, vertnum*ISIZE);
503 reduce_graph(n, etol, new_demand);
504 if (comp_num > 1){
505 greedy_shrinking1(n, capacity, etol,
506 vrp->par.max_num_cuts_in_shrink,
507 new_cut, compnodes_copy, compmembers,
508 comp_num, in_set, cut_val,
509 ref, cut_list, new_demand, cuts,
510 num_cuts, alloc_cuts);
511 }else{
512 greedy_shrinking1_one(n, capacity, etol,
513 vrp->par.max_num_cuts_in_shrink,
514 new_cut, in_set, cut_val, cut_list,
515 num_routes, new_demand, cuts,
516 num_cuts, alloc_cuts);
517 }
518 }
519
520 if (*num_cuts < 10 && vrp->par.do_greedy){
521 if (vrp->par.do_extra_in_root)
522 num_trials = level ? vrp->par.greedy_num_trials :
523 2 * vrp->par.greedy_num_trials;
524 else
525 num_trials = vrp->par.greedy_num_trials;
526 if (comp_num){
527 greedy_shrinking6(n, capacity, etol, new_cut,
528 compnodes_copy, compmembers, comp_num,
529 in_set, cut_val, ref, cut_list,
530 vrp->par.max_num_cuts_in_shrink,
531 new_demand, num_cuts ? num_trials :
532 2 * num_trials, 10.5, cuts,
533 num_cuts, alloc_cuts);
534 }else{
535 greedy_shrinking6_one(n, capacity, etol, new_cut, in_set,
536 cut_val, num_routes, cut_list,
537 vrp->par.max_num_cuts_in_shrink,
538 new_demand, num_cuts ? num_trials :
539 2 * num_trials, 10.5, cuts,
540 num_cuts, alloc_cuts);
541 }
542 }
543 /*__BEGIN_EXPERIMENTAL_SECTION__*/
544 #if 0
545 if (!(*num_cuts) && comp_num==1){
546 greedy_shrinking2_one(n, capacity, etol, new_cut, in_set,
547 cut_val, num_routes, new_demand, cuts
548 num_cuts, alloc_cuts);
549 }
550 #endif
551 /*___END_EXPERIMENTAL_SECTION___*/
552
553 #ifdef DO_TSP_CUTS
554 if (!(*num_cuts) && vrp->par.which_tsp_cuts){
555 tsp_cuts(n, vrp->par.verbosity, vrp->par.tsp_prob,
556 vrp->par.which_tsp_cuts, cuts, num_cuts, alloc_cuts);
557 }
558 #endif
559
560 /*__BEGIN_EXPERIMENTAL_SECTION__*/
561 FREE(compdemands_copy);
562 FREE(compcuts_copy);
563 density = n->edgenum/n->vertnum;
564 /*___END_EXPERIMENTAL_SECTION___*/
565 FREE(compmembers);
566 FREE(new_cut);
567 free_net(n);
568
569 /*__BEGIN_EXPERIMENTAL_SECTION__*/
570 #ifdef COMPILE_OUR_DECOMP
571 if (!(*num_cuts) && vrp->par.do_our_decomp &&
572 (vrp->last_decomp_index != index ||
573 (vrp->last_decomp_index == index &&
574 (objval - vrp->last_objval)/ub >= vrp->par.gap_threshold))){
575 if (!vrp->par.decomp_decompose){
576 comp_num = 1;
577 compdensity[1] = density;
578 compnodes_copy[1] = vertnum - 1;
579 }
580 for (i = 1; i <= comp_num; i++){
581 if (compdensity[i] < vrp->par.graph_density_threshold &&
582 compnodes_copy[i] > 3){
583 vrp->last_decomp_index = index;
584 vrp->last_objval = objval;
585 #if 0
586 ind_sort(indices, values, varnum);*/
587 #endif
588 /*need to recreate the network as it has been altered*/
589 vrp->n = n = status ? createnet2(indices, values, varnum, etol,
590 vrp->edges, demand, vertnum,
591 status) :
592 createnet(indices, values, varnum, etol,
593 vrp->edges, demand, vertnum);
594
595 /* fill out the cost fields */
596 for (edge_pt=n->edges+n->edgenum-1; edge_pt >= n->edges; edge_pt--)
597 edge_pt->cost = vrp->cost[INDEX(edge_pt->v0, edge_pt->v1)];
598
599 #if 0
600 aux = n->edgenum-n->verts[0].degree;
601 aux /= n->vertnum;
602 printf("Calling decomp: density %f , depot degree %d, obj %f, ",
603 aux, n->verts[0].degree, p->cur_sol.objval);
604 printf("level %d \n", p->cur_sol.xlevel);
605 fprintf("Calling decomp: density %f , depot degree %d, obj %f, ",
606 aux, n->verts[0].degree, p->cur_sol.objval);
607 fprintf("level %d \n", p->cur_sol.xlevel);
608 #endif
609 vrp_decomp(comp_num, compdensity);
610 free_net(n);
611 break;
612 }
613 }
614 }
615 #endif
616
617 FREE(compdensity);
618 /*___END_EXPERIMENTAL_SECTION___*/
619 FREE(compnodes_copy);
620
621 return(USER_SUCCESS);
622 }
623
624 /*__BEGIN_EXPERIMENTAL_SECTION__*/
625 #if 0
626 /*This is the original version*/
627 int user_find_cuts(void *user, int xlength, int *xind,
628 double *xval, double etol, int *pnumcuts)
629 {
630 vrp_cg_problem *vrp = (vrp_cg_problem *)user;
631 int vertnum = vrp->vertnum;
632 network *n;
633 vertex *verts;
634 int *compdemands = NULL;
635 double *compcuts = NULL, node_cut, max_node_cut;
636 int rcnt, cur_bins = 0, k;
637 char **coef_list, name[20];
638 int i, *compnodes = NULL, max_node;
639 int num_cuts = 0;
640 double cur_slack = 0.0;
641 int capacity = vrp->capacity;
642 int cut_size = (vrp->vertnum >> DELETE_POWER) + 1;
643 cut_data *new_cut;
644 elist *cur_edge = NULL;
645 int which_connected_routine = vrp->par.which_connected_routine;
646
647 if (vrp->dg_id && vrp->par.verbosity > 3){
648 sprintf(name, "support graph");
649 /*display_support_graph(vrp->dg_id, (p->cur_sol->xindex == 0 &&
650 p->cur_sol->xiter_num == 1) ? TRUE: FALSE, name,
651 p->cur_sol->xlength, p->cur_sol->xind,
652 p->cur_sol->xval,
653 etol, CTOI_WAIT_FOR_CLICK_AND_REPORT);*/
654 }
655
656 /*create the solution graph*/
657 n = createnet(xind, xval, xlength, etol, vrp->edges, vrp->demand,
658 vrp->vertnum);
659 if (n->is_integral){ /*if the network is integral, check for feasibility*/
660 /* Feasibility is already tested in the LP process, thus in this
661 * case we are just checking for connectivity and violation of
662 * capacity constraints*/
663 num_cuts = check_feasibility(n, xind, xval, xlength, etol, capacity,
664 numroutes);
665 free_net(n);
666 *pnumcuts = num_cuts;
667 return(USER_SUCCESS);
668 }
669
670 if (!vrp->par.always_do_mincut){/*user_par.always_do_mincut indicates
671 whether we should just always do the
672 min_cut routine or whether we should also
673 try this routine*/
674 verts = n->verts;
675 if (which_connected_routine == BOTH)
676 which_connected_routine = CONNECTED;
677
678 new_cut = (cut_data *) calloc(1, sizeof(cut_data));
679 new_cut->size = cut_size;
680 do{
681 compnodes = (int *) calloc(vertnum + 1, sizeof(int));
682 compdemands = (int *) calloc(vertnum + 1, sizeof(int));
683 compcuts = (double *) calloc(vertnum + 1, sizeof(double));
684
685 /*------------------------------------------------------------------*\
686 | Get the connected components of the solution graph without the |
687 | depot and see if the number of components is more than one |
688 \*------------------------------------------------------------------*/
689 if ((rcnt = (which_connected_routine == BICONNECTED?
690 biconnected(n, compnodes, compdemands, compcuts) :
691 connected(n, compnodes, compdemands, NULL, compcuts))) > 1){
692
693 /*---------------------------------------------------------------*\
694 | If the number of components is more then one, then check each |
695 | component to see if it violates a capacity constraint |
696 \*---------------------------------------------------------------*/
697
698 coef_list = (char **) calloc(rcnt, sizeof(char *));
699 coef_list[0] = (char *) calloc(rcnt*cut_size, sizeof(char));
700 for(i = 1; i<rcnt; i++)
701 coef_list[i] = coef_list[0]+i*cut_size;
702
703 for(i = 1; i < vertnum; i++)
704 (coef_list[(verts[i].comp)-1][i >> DELETE_POWER]) |=
705 (1 << (i & DELETE_AND));
706
707 for (i = 0; i < rcnt; i++){
708 if (compnodes[i+1] < 2) continue;
709 /*check ith component to see if it violates a constraint*/
710 if (vrp->par.which_connected_routine == BOTH &&
711 which_connected_routine == BICONNECTED && compcuts[i+1]==0)
712 continue;
713 if (compcuts[i+1] < 2*BINS(compdemands[i+1], capacity)-etol){
714 /*the constraint is violated so impose it*/
715 new_cut->coef = (char *) (coef_list[i]);
716 new_cut->type = (compnodes[i+1] < vertnum/2 ?
717 SUBTOUR_ELIM_SIDE:SUBTOUR_ELIM_ACROSS);
718 new_cut->rhs = (new_cut->type == SUBTOUR_ELIM_SIDE ?
719 RHS(compnodes[i+1],compdemands[i+1],
720 capacity): 2*BINS(compdemands[i+1],
721 capacity));
722 cg_send_cut(new_cut, num_cuts, alloc_cuts, cuts);
723 }
724 else{/*if the constraint is not violated, then try generating a
725 violated constraint by deleting customers that don't
726 change the number of trucks required by the customers in
727 the component but decrease the value of the cut*/
728 cur_bins = BINS(compdemands[i+1], capacity);/*the current
729 number of trucks required*/
730 cur_slack = compcuts[i+1] - 2*cur_bins;/*current slack in the
731 constraint*/
732 while (compnodes[i+1]){/*while there are still nodes in the
733 component*/
734 for (max_node = 0, max_node_cut = 0, k = 1;
735 k<vertnum; k++){
736 if (verts[k].comp == i+1){
737 if (BINS(compdemands[i+1]-verts[k].demand, capacity)
738 == cur_bins){
739 /*if the number of trucks doesn't decrese upon
740 deleting this customer*/
741 for (node_cut = 0, cur_edge = verts[k].first;
742 cur_edge; cur_edge = cur_edge->next_edge){
743 node_cut += (cur_edge->other_end ?
744 -cur_edge->data->weight :
745 cur_edge->data->weight);
746 }
747 if (node_cut > max_node_cut){/*check whether the
748 value of the cut decrease is the best
749 seen so far*/
750 max_node = k;
751 max_node_cut = node_cut;
752 }
753 }
754 }
755 }
756 if (!max_node){
757 break;
758 }
759 /*delete the customer that exhibited the greatest
760 decrease in cut value*/
761 compnodes[i+1]--;
762 compdemands[i+1] -= verts[max_node].demand;
763 compcuts[i+1] -= max_node_cut;
764 cur_slack -= max_node_cut;
765 verts[max_node].comp = 0;
766 coef_list[i][max_node >> DELETE_POWER] ^=
767 (1 << (max_node & DELETE_AND));
768 if (cur_slack < 0){/*if the cut is now violated, impose
769 it*/
770 new_cut->coef = (char *) (coef_list[i]);
771 new_cut->type = (compnodes[i+1] < vertnum/2 ?
772 SUBTOUR_ELIM_SIDE:SUBTOUR_ELIM_ACROSS);
773 new_cut->size = cut_size;
774 new_cut->rhs = (new_cut->type == SUBTOUR_ELIM_SIDE ?
775 RHS(compnodes[i+1], compdemands[i+1],
776 capacity): 2*cur_bins);
777 cg_send_cut(new_cut, num_cuts, alloc_cuts, cuts);
778 break;
779 }
780 }
781 }
782 }
783 FREE(coef_list[0]);
784 FREE(coef_list);
785 }
786 which_connected_routine++;
787 FREE(compnodes);
788 FREE(compdemands);
789 FREE(compcuts);
790 }while((!num_cuts || vrp->par.which_connected_routine == BOTH)
791 && which_connected_routine < 2);
792 FREE(new_cut);
793 }
794 if (num_cuts){/*if we found some cuts using the above routines, then exit*/
795 free_net(n);
796 *pnumcuts = num_cuts;
797 return(USER_SUCCESS);
798 }
799 else{/*if we still haven't found any cuts, then try the min cut routine*/
800 num_cuts = min_cut(vrp, n, etol);/*find cuts using min cut routine*/
801 free_net(n);
802 *pnumcuts = num_cuts;
803 return(USER_SUCCESS);
804 }
805 }
806 #endif
807
808 /*___END_EXPERIMENTAL_SECTION___*/
809 /*===========================================================================*/
810
811 /*===========================================================================*\
812 * This routine takes a solution which is integral and checkes whether it is
813 * feasible by first checking if it is connected and then checking to make
814 * sure each route obeys the capacity constraints.
815 \*===========================================================================*/
816
817 void check_connectivity(network *n, double etol, int capacity, int numroutes,
818 cut_data ***cuts, int *num_cuts, int *alloc_cuts)
819 {
820 vertex *verts;
821 elist *cur_route_start;
822 int weight = 0, reduced_weight, *compdemands, *route;
823 edge *edge_data;
824 int cur_vert = 0, prev_vert, cust_num = 0, cur_route, rcnt, *compnodes;
825 cut_data *new_cut;
826 char **coef_list;
827 int i, reduced_cust_num;
828 int vertnum = n->vertnum, vert1, vert2;
829 int cut_size = (vertnum >> DELETE_POWER) +1;
830 double *compcuts;
831
832 if (!n->is_integral) return;
833
834 verts = n->verts;
835 compnodes = (int *) calloc(vertnum + 1, sizeof(int));
836 compdemands = (int *) calloc(vertnum + 1, sizeof(int));
837 compcuts = (double *) calloc(vertnum + 1, sizeof(double));
838 /*get the components of the solution graph without the depot to check if the
839 graph is connected or not*/
840 rcnt = connected(n, compnodes, compdemands, NULL, compcuts, NULL);
841 coef_list = (char **) calloc(rcnt, sizeof(char *));
842 coef_list[0] = (char *) calloc(rcnt*cut_size, sizeof(char));
843 for(i = 1; i<rcnt; i++)
844 coef_list[i] = coef_list[0]+i*cut_size;
845
846 for(i = 1; i < vertnum; i++)
847 (coef_list[(verts[i].comp)-1][i >> DELETE_POWER]) |=
848 (1 << (i & DELETE_AND));
849
850 /*-------------------------------------------------------------------------*\
851 | For each component check to see if the cut it induces is nonzero -- each |
852 | component's cut value must be either 0 or 2 since we have integrality |
853 \*-------------------------------------------------------------------------*/
854
855 new_cut = (cut_data *) calloc(1, sizeof(cut_data));
856 new_cut->size = cut_size;
857 for (i = 0; i<rcnt; i++){
858 if (compcuts[i+1] < etol){/*if the cut value is zero, the graph is
859 disconnected and we have a violated cut*/
860 new_cut->coef = (char *) (coef_list[i]);
861 new_cut->type = (compnodes[i+1] < vertnum/2 ?
862 SUBTOUR_ELIM_SIDE:SUBTOUR_ELIM_ACROSS);
863 new_cut->rhs = (new_cut->type == SUBTOUR_ELIM_SIDE ?
864 RHS(compnodes[i+1], compdemands[i+1], capacity):
865 2*BINS(compdemands[i+1], capacity));
866 cg_send_cut(new_cut, num_cuts, alloc_cuts, cuts);
867 }
868 }
869
870 FREE(coef_list[0]);
871 FREE(coef_list);
872 FREE(compnodes);
873 FREE(compdemands);
874 FREE(compcuts);
875
876 /*-------------------------------------------------------------------------*\
877 | if the graph is connected, check each route to see if it obeys the |
878 | capacity constraints |
879 \*-------------------------------------------------------------------------*/
880
881 route = (int *) malloc(vertnum*ISIZE);
882 for (cur_route_start = verts[0].first, cur_route = 0,
883 edge_data = cur_route_start->data; cur_route < numroutes;
884 cur_route++){
885 edge_data = cur_route_start->data;
886 edge_data->scanned = TRUE;
887 cur_vert = edge_data->v1;
888 prev_vert = weight = cust_num = 0;
889
890 new_cut->coef = (char *) calloc(cut_size, sizeof(char));
891
892 route[0] = cur_vert;
893 while (cur_vert){
894 /*keep tracing around the route and whenever the addition
895 of the next customer causes a violation, impose the
896 constraint induced
897 by the set of customers seen so far on the route*/
898 new_cut->coef[cur_vert >> DELETE_POWER]|=(1 << (cur_vert & DELETE_AND));
899 cust_num++;
900 if ((weight += verts[cur_vert].demand) > capacity){
901 new_cut->type = (cust_num < vertnum/2 ?
902 SUBTOUR_ELIM_SIDE:SUBTOUR_ELIM_ACROSS);
903 new_cut->rhs = (new_cut->type ==SUBTOUR_ELIM_SIDE ?
904 RHS(cust_num, weight, capacity):
905 2*BINS(weight, capacity));
906 cg_send_cut(new_cut, num_cuts, alloc_cuts, cuts);
907 vert1 = route[0];
908 reduced_weight = weight;
909 reduced_cust_num = cust_num;
910 while (TRUE){
911 if ((reduced_weight -= verts[vert1].demand) > capacity){
912 reduced_cust_num--;
913 new_cut->coef[vert1 >> DELETE_POWER] &=
914 ~(1 << (vert1 & DELETE_AND));
915 new_cut->type = (reduced_cust_num < vertnum/2 ?
916 SUBTOUR_ELIM_SIDE:SUBTOUR_ELIM_ACROSS);
917 new_cut->rhs = (new_cut->type ==SUBTOUR_ELIM_SIDE ?
918 RHS(reduced_cust_num, reduced_weight, capacity):
919 2*BINS(reduced_weight, capacity));
920 cg_send_cut(new_cut, num_cuts, alloc_cuts, cuts);
921 vert1 = route[vert1];
922 }else{
923 break;
924 }
925 }
926 vert2 = route[0];
927 while (vert2 != vert1){
928 new_cut->coef[vert2 >> DELETE_POWER] |=
929 (1 << (vert2 & DELETE_AND));
930 vert2 = route[vert2];
931 }
932 }
933 if (verts[cur_vert].first->other_end != prev_vert){
934 prev_vert = cur_vert;
935 edge_data = verts[cur_vert].first->data;
936 cur_vert = verts[cur_vert].first->other_end;
937 }
938 else{
939 prev_vert = cur_vert;
940 edge_data = verts[cur_vert].last->data; /*This statement could
941 possibly be taken out to
942 speed things up a bit*/
943 cur_vert = verts[cur_vert].last->other_end;
944 }
945 route[prev_vert] = cur_vert;
946 }
947 edge_data->scanned = TRUE;
948
949 FREE(new_cut->coef);
950
951 while (cur_route_start->data->scanned){/*find the next edge leading out of
952 the depot which has not yet been
953 traversed to start the next
954 route*/
955 if (!(cur_route_start = cur_route_start->next_edge)) break;
956 }
957 }
958 FREE(route);
959 FREE(new_cut);
960
961 for (cur_route_start = verts[0].first; cur_route_start;
962 cur_route_start = cur_route_start->next_edge)
963 cur_route_start->data->scanned = FALSE;
964 }
965
966 /*__BEGIN_EXPERIMENTAL_SECTION__*/
967 /*===========================================================================*/
968
969 #ifdef COMPILE_DECOMP
970 void user_send_to_sol_pool(cg_prob *p)
971 {
972 #if 0
973 int size = p->cur_sol.xlength*sizeof(int);
974 int s_bufid;
975
976 if (p->sol_pool){
977 s_bufid = init_send(DataInPlace);
978 send_int_array(&size, 1);
979 send_int_array(&p->cur_sol.xlevel, 1);
980 send_char_array((char *)(p->cur_sol.xind), size);
981 send_msg(p->sol_pool, PACKED_COL);
982 freebuf(s_bufid);
983 }
984 #endif
985 }
986 #endif
987
988 /*___END_EXPERIMENTAL_SECTION___*/
989 /*===========================================================================*/
990
991 /*===========================================================================*\
992 * This is an undocumented (for now) debugging feature which can allow the user
993 * to identify the cut which cuts off a particular known feasible solution.
994 \*===========================================================================*/
995
996 #ifdef CHECK_CUT_VALIDITY
997 /*__BEGIN_EXPERIMENTAL_SECTION__*/
998
999 #include "sym_cg.h"
1000 /*___END_EXPERIMENTAL_SECTION___*/
1001
1002 int user_check_validity_of_cut(void *user, cut_data *new_cut)
1003 {
1004 vrp_cg_problem *vrp = (vrp_cg_problem *)user;
1005 int *edges = vrp->edges;
1006 int *feas_sol = vrp->feas_sol;
1007 double lhs = 0;
1008 char *coef;
1009 int v0, v1;
1010 int i, j, vertnum = vrp->vertnum;
1011 int size, cliquecount = 0;
1012 char *clique_array;
1013 /*__BEGIN_EXPERIMENTAL_SECTION__*/
1014
1015 int num_arcs, edge_index ;
1016 char *cpt;
1017 int *arcs ;
1018 char *indicators;
1019 double bigM, *weights ;
1020 int jj, num_fracs, fracs;
1021 /*___END_EXPERIMENTAL_SECTION___*/
1022
1023 if (vrp->feas_sol_size){
1024 switch (new_cut->type){
1025
1026 /*------------------------------------------------------------------*\
1027 * The subtour elimination constraints are stored as a vector of bits
1028 * indicating which side of the cut each customer is on.
1029 \*-----------------------------------------------------------------*/
1030
1031 case SUBTOUR_ELIM_SIDE:
1032 /*Here, I could just allocate enough memory up front and then
1033 reallocate at the end istead of counting the number of entries in
1034 the row first*/
1035 coef = new_cut->coef;
1036 for (i = 0; i<vrp->feas_sol_size; i++){
1037 v0 = edges[feas_sol[i] << 1];
1038 v1 = edges[(feas_sol[i] << 1) + 1];
1039 if ((coef[v0 >> DELETE_POWER] & (1 << (v0 & DELETE_AND))) &&
1040 (coef[v1 >> DELETE_POWER] & (1 << (v1 & DELETE_AND)))){
1041 lhs += 1;
1042 }
1043 }
1044 new_cut->sense = 'L';
1045 break;
1046
1047 case SUBTOUR_ELIM_ACROSS:
1048 /*I could just allocate enough memory up front and then reallocate
1049 at the end instead of counting the number of entries first*/
1050 coef = new_cut->coef;
1051 for (i = 0; i < vrp->feas_sol_size; i++){
1052 v0 = edges[feas_sol[i] << 1];
1053 v1 = edges[(feas_sol[i] << 1) + 1];
1054 if ((coef[v0 >> DELETE_POWER] >> (v0 & DELETE_AND) & 1) ^
1055 (coef[v1 >> DELETE_POWER] >> (v1 & DELETE_AND) & 1)){
1056 lhs += 1;
1057 }
1058 }
1059 new_cut->sense = 'G';
1060 break;
1061
1062 case CLIQUE:
1063 coef = new_cut->coef;
1064 size = (vertnum >> DELETE_POWER) + 1;
1065 memcpy(&cliquecount, coef, ISIZE);
1066 coef += ISIZE;
1067 for (i = 0; i < vrp->feas_sol_size; i++){
1068 v0 = edges[feas_sol[i] << 1];
1069 v1 = edges[(feas_sol[i] << 1) + 1];
1070 for (j = 0; j < cliquecount; j++){
1071 clique_array = coef + size * j;
1072 if ((clique_array[v0 >> DELETE_POWER] &
1073 (1 << (v0 & DELETE_AND))) &&
1074 (clique_array[v1 >> DELETE_POWER] &
1075 (1 << (v1 & DELETE_AND)))){
1076 lhs += 1;
1077 }
1078 }
1079 }
1080 break;
1081 /*__BEGIN_EXPERIMENTAL_SECTION__*/
1082
1083 case FARKAS:
1084 coef = new_cut->coef;
1085 cpt = coef + ((vertnum >> DELETE_POWER) + 1);
1086 memcpy((char *)&num_arcs, cpt, ISIZE);
1087 cpt += ISIZE;
1088 arcs = (int *) malloc(num_arcs * ISIZE);
1089 indicators = (char *) malloc(num_arcs);
1090 memcpy((char *)arcs, cpt, num_arcs * ISIZE);
1091 cpt += num_arcs * ISIZE;
1092 memcpy(indicators, cpt, num_arcs);
1093 cpt += num_arcs;
1094 memcpy((char *)&num_fracs, cpt, ISIZE);
1095 cpt += ISIZE;
1096 weights = (double *) malloc((num_fracs + 1) * DSIZE);
1097 memcpy((char *)weights, cpt, (num_fracs + 1) * DSIZE);
1098 bigM = (*(double *)weights);
1099 weights++;
1100
1101 for (fracs = 0, i = 0, lhs = 0; i < vrp->feas_sol_size; i++){
1102 v0 = edges[feas_sol[i] << 1];
1103 v1 = edges[(feas_sol[i] << 1) + 1];
1104 edge_index = feas_sol[i];
1105 if (isset(coef, v1) || isset(coef,v0)){
1106 for (jj = 0; jj < num_arcs; jj++){
1107 if (arcs[jj] == edge_index){
1108 lhs += indicators[jj] ? -bigM : weights[fracs++];
1109 break;
1110 }
1111 }
1112 if (jj == num_arcs) lhs += bigM;
1113 }
1114 }
1115 weights--;
1116 FREE(arcs);
1117 FREE(indicators);
1118 FREE(weights);
1119 break;
1120
1121 case NO_COLUMNS:
1122 coef = new_cut->coef;
1123 cpt = coef+ ((vertnum >> DELETE_POWER) + 1);
1124 memcpy((char *)&num_arcs, cpt, ISIZE);
1125 cpt += ISIZE;
1126 arcs = (int *) malloc(num_arcs * ISIZE);
1127 indicators = (char *) malloc(num_arcs);
1128 memcpy((char *)arcs, cpt, num_arcs * ISIZE);
1129 cpt += num_arcs * ISIZE;
1130 memcpy(indicators, cpt, num_arcs);
1131
1132 for (i = 0, lhs = 0 ; i < vrp->feas_sol_size; i++){
1133 v0 = vrp->edges[feas_sol[i] << 1];
1134 v1 = vrp->edges[(feas_sol[i] << 1) + 1];
1135 edge_index = feas_sol[i];
1136 if (isset(coef, v1) || isset(coef,v0)){
1137 for (jj = 0; jj < num_arcs; jj++){
1138 if ( arcs[jj] == edge_index){
1139 lhs += indicators[jj] ? 1.0 : 0.0;
1140 break;
1141 }
1142 }
1143 if (jj == num_arcs) lhs -= 1;
1144 }
1145 }
1146 FREE(arcs);
1147 FREE(indicators);
1148 break;
1149
1150 case GENERAL_NONZEROS:
1151 cpt = new_cut->coef;
1152 memcpy((char *)&num_arcs, cpt, ISIZE);
1153 cpt += ISIZE;
1154 arcs = (int *) calloc(num_arcs, ISIZE);
1155 weights = (double *) calloc(num_arcs, DSIZE);
1156 memcpy((char *)arcs, cpt, num_arcs * ISIZE);
1157 cpt += num_arcs * ISIZE;
1158 memcpy((char *)weights, cpt, num_arcs * DSIZE);
1159
1160 for (i = 0, lhs = 0; i < vrp->feas_sol_size; i++){
1161 edge_index = feas_sol[i];
1162 for (j = 0; j < num_arcs; j++){
1163 if (arcs[j] == edge_index){
1164 lhs += weights[j];
1165 break;
1166 }
1167 }
1168 }
1169 FREE(arcs);
1170 FREE(weights);
1171 break;
1172 /*___END_EXPERIMENTAL_SECTION___*/
1173
1174 default:
1175 printf("Unrecognized cut type!\n");
1176 }
1177
1178 /*check to see if the cut is actually violated by the current solution --
1179 otherwise don't add it -- also check to see if its a duplicate*/
1180 if (new_cut->sense == 'G' ? lhs < new_cut->rhs : lhs > new_cut->rhs){
1181 printf("CG: ERROR -- cut is violated by feasible solution!!!\n");
1182 exit(1);
1183 }
1184 }
1185
1186 return(USER_SUCCESS);
1187 }
1188 #endif
1189