Debian Codegraph @

SYMPHONY/Applications/CNRP/src/CutGen/cnrp_cg.c

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