Debian Codegraph @

SYMPHONY/Applications/CNRP/src/CutPool/cnrp_cp.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 <stdio.h>
19 #include <string.h>
20
21 /* SYMPHONY include files */
22 #include "sym_constants.h"
23 #include "sym_macros.h"
24 #include "sym_types.h"
25 #include "sym_proccomm.h"
26 #include "sym_cp_u.h"
27
28 /* CNRP include files */
29 #include "cnrp_cp.h"
30 #include "cnrp_const.h"
31 #include "cnrp_macros.h"
32
33 /*===========================================================================*/
34
35 /*===========================================================================*\
36 * This file contains the user-written functions of the cut pool process.
37 \*===========================================================================*/
38
39 /*===========================================================================*\
40 * Here is where the user must receive all of the data sent from
41 * user_send_cp_data() and set up data structures. Note that this function is
42 * only called if one of COMPILE_IN_CP, COMPILE_IN_LP, or COMPILE_IN_TM is
43 * FALSE.
44 \*===========================================================================*/
45
46 int user_receive_cp_data(void **user)
47 {
48 cnrp_spec_cp *vcp = (cnrp_spec_cp *) calloc (1, sizeof(cnrp_spec_cp));
49 int i, j, k;
50
51 *user = (void *) vcp;
52
53 receive_int_array(&vcp->vertnum, 1);
54 receive_dbl_array(&vcp->capacity, 1);
55 vcp->demand = (double *) malloc(vcp->vertnum * DSIZE);
56 receive_dbl_array(vcp->demand, vcp->vertnum);
57
58 vcp->edgenum = vcp->vertnum*(vcp->vertnum-1)/2 + vcp->vertnum-1;
59 vcp->edges = (int *) calloc ((int)2*vcp->edgenum, sizeof(int));
60
61 /* create the edge list (we assume a complete graph) */
62 for (i = 1, k = 0; i < vcp->vertnum; i++){
63 for (j = 0; j < i; j++){
64 vcp->edges[2*k] = j;
65 vcp->edges[2*k+1] = i;
66 k++;
67 }
68 }
69
70 /* now add the duplicate copies of the depot edges to allow for
71 routes with one customer */
72 for (i = 1; i < vcp->vertnum; i++){
73 vcp->edges[2*k] = 0;
74 vcp->edges[2*k+1] = i;
75 k++;
76 }
77 return(USER_SUCCESS);
78 }
79
80 /*===========================================================================*/
81
82 /*===========================================================================*\
83 * Here, we free up the data structures
84 \*===========================================================================*/
85
86 int user_free_cp(void **user)
87 {
88 cnrp_spec_cp *vcp = (cnrp_spec_cp *)(*user);
89
90 FREE(vcp->edges);
91 FREE(vcp->demand);
92 FREE(vcp);
93 *user = NULL;
94
95 return(USER_SUCCESS);
96 }
97
98 /*===========================================================================*/
99
100 int user_receive_lp_solution_cp(void *user)
101 {
102 /* We leave this to SYMPHONY */
103 return(USER_SUCCESS);
104 }
105
106 /*===========================================================================*/
107
108 /*===========================================================================*\
109 * When a new solution arrives to the cut pool, this function is invoked
110 * so that the user can prepare for checking many cuts (probably set up
111 * some data structures that make ckecking more efficient). In our
112 * case, we construct a fractional graph representation of the LP
113 * solution, which will be more efficient for checking the cuts.
114 \*===========================================================================*/
115
116 int user_prepare_to_check_cuts(void *user, int varnum, int *indices,
117 double *values)
118 {
119 cnrp_spec_cp *vcp = (cnrp_spec_cp *)user;
120
121 #if 0
122 #ifdef ADD_FLOW_VARS
123 int total_edgenum = vcp->vertnum*(vcp->vertnum - 1)/2;
124 int i;
125 #endif
126
127 #ifdef ADD_FLOW_VARS
128 #ifdef DIRECTED_X_VARS
129 for (i = 0; indices[i] < 2*total_edgenum; i++);
130 #else
131 for (i = 0; indices[i] < total_edgenum; i++);
132 #endif
133 varnum = i;
134 #endif
135
136 vcp->n = create_pool_net(vcp, varnum, indices, values);
137 #endif
138
139 vcp->n = NULL;
140
141 return(USER_SUCCESS);
142 }
143
144
145 /*===========================================================================*/
146
147 /*===========================================================================*\
148 * Check to see whether a particular cut is violated by the current LP sol.
149 \*===========================================================================*/
150
151 int user_check_cut(void *user, double etol, int varnum, int *indices,
152 double *values, cut_data *cut, int *is_violated,
153 double *quality)
154 {
155 cnrp_spec_cp *vcp = (cnrp_spec_cp *)user;
156 char *coef, *coef2;
157 int index, v0, v1;
158 int vertnum = vcp->vertnum;
159 double lhs = 0;
160 int i, j, k, cliquecount, size;
161 char *clique_array;
162 #if defined(ADD_FLOW_VARS) || defined(DIRECTED_X_VARS)
163 int total_edgenum = vcp->vertnum*(vcp->vertnum - 1)/2;
164 #endif
165 int *edges = vcp->edges, *matind, *arcs;
166 int edgeind, numarcs;
167 double demand, capacity = vcp->capacity;
168 char first_coeff_found, second_coeff_found, third_coeff_found, d_x_vars;
169
170 coef = cut->coef;
171
172 /*------------------------------------------------------------------------*\
173 * Here the cut is "unpacked" and checked for violation. Each cut is
174 * stored as compactly as possible. The subtour elimination constraints
175 * are stored as a vector of bits indicating which side of the cut each
176 * node is on. If the cut is violated, it is sent back to the lp.
177 * Otherwise, "touches" is incremented. "Touches" is a measure of the
178 * effectiveness of a cut and indicates how long it has been since a
179 * cut was useful
180 \*------------------------------------------------------------------------*/
181 switch (cut->type){
182
183 case SUBTOUR_ELIM:
184 case SUBTOUR_ELIM_SIDE:
185 for (i = 0; i < varnum; i++){
186 #ifdef ADD_FLOW_VARS
187 #ifdef DIRECTED_X_VARS
188 if (indices[i] < 2*total_edgenum){
189 if (indices[i] >= total_edgenum){
190 edgeind = indices[i] - total_edgenum;
191 }else{
192 edgeind = indices[i];
193 }
194 #else
195 if ((edgeind = indices[i]) < total_edgenum){
196 #endif
197 #else
198 #ifdef DIRECTED_X_VARS
199 {
200 if (indices[i] >= total_edgenum){
201 edgeind = indices[i] - total_edgenum;
202 }else{
203 edgeind = indices[i];
204 }
205 #else
206 {
207 edgeind = indices[i];
208 #endif
209 #endif
210 v0 = edges[edgeind << 1];
211 v1 = edges[(edgeind << 1) + 1];
212 if (coef[v0 >> DELETE_POWER] & (1 << (v0 & DELETE_AND)) &&
213 (coef[v1 >> DELETE_POWER]) & (1 << (v1 & DELETE_AND))){
214 lhs += values[i];
215 }
216 }
217 }
218 *is_violated = (lhs > (double)(cut->rhs)+etol);
219 *quality = lhs - (double)cut->rhs;
220 if (*quality < etol && *quality > -etol) *quality = 0;
221 return(USER_SUCCESS);
222
223 case SUBTOUR_ELIM_ACROSS:
224 for (i = 0; i < varnum; i++){
225 #ifdef DIRECTED_X_VARS
226 #ifdef ADD_FLOW_VARS
227 if (indices[i] < 2*total_edgenum){
228 #else
229 {
230 #endif
231 if (indices[i] >= total_edgenum){
232 edgeind = indices[i] - total_edgenum;
233 v1 = edges[edgeind << 1];
234 v0 = edges[(edgeind << 1) + 1];
235 }else{
236 edgeind = indices[i];
237 v0 = edges[edgeind << 1];
238 v1 = edges[(edgeind << 1) + 1];
239 }
240 if ((coef[v1 >> DELETE_POWER] >> (v1 & DELETE_AND) & 1) &&
241 !(coef[v0 >> DELETE_POWER] >> (v0 & DELETE_AND) & 1)){
242 lhs += values[i];
243 }
244 }
245 #else
246 #ifdef ADD_FLOW_VARS
247 if (indices[i] < total_edgenum){
248 #else
249 {
250 #endif
251 edgeind = indices[i];
252 v0 = edges[edgeind << 1];
253 v1 = edges[(edgeind << 1) + 1];
254 if ((coef[v1 >> DELETE_POWER] >> (v1 & DELETE_AND) & 1) ^
255 (coef[v0 >> DELETE_POWER] >> (v0 & DELETE_AND) & 1)){
256 lhs += values[i];
257 }
258 }
259 #endif
260 }
261 *is_violated = (lhs < (double)(cut->rhs)-etol);
262 *quality = (double)cut->rhs - lhs;
263 if (*quality < etol && *quality > -etol) *quality = 0;
264 return(USER_SUCCESS);
265
266 #if defined(ADD_FLOW_VARS) && defined(DIRECTED_X_VARS)
267 case MIXED_DICUT:
268 demand = ((double *)coef)[0];
269 numarcs = ((int *)(coef + DSIZE))[0];
270 /* Array of the nodes in the set S */
271 coef2 = coef + DSIZE + ISIZE;
272 /* Array of the arcs in the set C */
273 arcs = (int *) (coef + DSIZE + ISIZE + (vertnum >> DELETE_POWER)+1);
274 for (i = 0; i < varnum; i++){
275 if (indices[i] < 2*total_edgenum){
276 if (indices[i] >= total_edgenum){
277 edgeind = indices[i] - total_edgenum;
278 v1 = edges[edgeind << 1];
279 v0 = edges[(edgeind << 1) + 1];
280 }else{
281 edgeind = indices[i];
282 v0 = edges[edgeind << 1];
283 v1 = edges[(edgeind << 1) + 1];
284 }
285 if ((coef2[v1 >> DELETE_POWER] >> (v1 & DELETE_AND) & 1) &&
286 !(coef2[v0 >> DELETE_POWER] >> (v0 & DELETE_AND) & 1)){
287 for (k = 0; k < numarcs; k++){
288 if (v0 == arcs[k << 1] && v1 == arcs[(k << 1) + 1])
289 break;
290 }
291 if (k == numarcs){
292 lhs += values[i]*MIN(vcp->capacity, demand);
293 }
294 }
295 }else{
296 if (indices[i] < 3*total_edgenum){
297 edgeind = indices[i] - 2*total_edgenum;
298 v0 = edges[edgeind << 1];
299 v1 = edges[(edgeind << 1) + 1];
300 }else{
301 edgeind = indices[i] - 3*total_edgenum;
302 v1 = edges[edgeind << 1];
303 v0 = edges[(edgeind << 1) + 1];
304 }
305 if ((coef2[v1 >> DELETE_POWER] >> (v1 & DELETE_AND) & 1) &&
306 !(coef2[v0 >> DELETE_POWER] >> (v0 & DELETE_AND) & 1)){
307 for (k = 0; k < numarcs; k++){
308 if (v0 == arcs[k << 1] && v1 == arcs[(k << 1) + 1])
309 break;
310 }
311 if (k < numarcs){
312 lhs += values[i];
313 }
314 }
315 }
316 }
317 *is_violated = (lhs < (double)(cut->rhs)-etol);
318 *quality = (double)cut->rhs - lhs;
319 if (*quality < etol && *quality > -etol) *quality = 0;
320 return(USER_SUCCESS);
321 #endif
322
323 #ifdef ADD_FLOW_VARS
324 case FLOW_CAP:
325 matind = (int *) malloc(3 * ISIZE);
326 index = ((int *)coef)[0];
327 v0 = index < total_edgenum ? edges[index << 1] :
328 edges[(index - total_edgenum) << 1];
329 v1 = index < total_edgenum ? edges[(index << 1) + 1] :
330 edges[((index - total_edgenum) << 1) + 1];
331 if (v0){
332 demand =
333 index < total_edgenum ? vcp->demand[v0] : vcp->demand[v1];
334 }else{
335 demand = 0;
336 }
337
338 first_coeff_found = second_coeff_found = third_coeff_found = FALSE;
339 for (i = 0; i < varnum && (!first_coeff_found ||
340 !second_coeff_found); i++){
341 if (indices[i] == index){
342 matind[0] = i;
343 first_coeff_found = TRUE;
344 }
345 if (indices[i] == (index + 2 * total_edgenum)){
346 matind[1] = i;
347 second_coeff_found = TRUE;
348 }
349 }
350 #ifndef DIRECTED_X_VARS
351 for (i = 0; i < varnum && !third_coeff_found; i++){
352 if (indices[i] == (index + total_edgenum)){
353 matind[2] = i;
354 third_coeff_found = TRUE;
355 }
356 }
357 #endif
358 if (first_coeff_found){
359 #ifdef DIRECTED_X_VARS
360 lhs += -values[matind[0]] * (vcp->capacity - demand);
361 #else
362 if (vcp->par.prob_type == CSTP || vcp->par.prob_type == CTP){
363 lhs += -values[matind[0]]*vcp->capacity;
364 }else{
365 lhs += -values[matind[0]]*vcp->capacity/2;
366 }
367 #endif
368 if (second_coeff_found){
369 if (third_coeff_found){
370 lhs += values[matind[1]];
371 lhs += values[matind[2]];
372 }else{
373 lhs += values[matind[1]];
374 }
375 }else if (third_coeff_found){
376 matind[1] = matind[2];
377 lhs += values[matind[1]];
378 }
379 }else if (second_coeff_found){
380 matind[0] = matind[1];
381 lhs += values[matind[0]];
382 if (third_coeff_found){
383 matind[1] = matind[2];
384 lhs += values[matind[1]];
385 }
386 }else if (third_coeff_found){
387 matind[0] = matind[2];
388 lhs += values[matind[0]];
389 }
390 *is_violated = (lhs > (double)(cut->rhs)+etol);
391 *quality = lhs - (double)cut->rhs;
392 if (*quality < etol && *quality > -etol) *quality = 0;
393 FREE(matind);
394 return(USER_SUCCESS);
395
396 case TIGHT_FLOW:
397
398 if ((index = ((int *)coef)[0]) < total_edgenum){
399 v0 = edges[index << 1];
400 v1 = edges[(index << 1) + 1];
401 }else{
402 v1 = edges[(index - total_edgenum) << 1];
403 v0 = edges[((index - total_edgenum) << 1) + 1];
404 }
405
406 #ifdef DIRECTED_X_VARS
407 d_x_vars = TRUE;
408 for (k = 0; k < varnum; k++){
409 if (indices[k] == index){
410 lhs += values[k] * (v1 ? -vcp->demand[v1] : 0);
411 break;
412 }
413 }
414 #else
415 d_x_vars = FALSE;
416 for (k = 0; k < varnum; k++){
417 if (indices[k] == (index < total_edgenum ? index :
418 index - total_edgenum)){
419 lhs += values[k] * (v1 ? -vcp->demand[v1] : 0);
420 break;
421 }
422 }
423 #endif
424 for (k = 0; k < varnum; k++){
425 if (indices[k] == index + (1 + d_x_vars) * total_edgenum){
426 lhs += values[k];
427 break;
428 }
429 }
430 /* This loop is done very inefficiently and should be rewritten */
431 for (i = 0; i < v1; i++){
432 index = INDEX(i, v1) + (2 + d_x_vars) * total_edgenum;
433 for (k = 0; k < varnum; k++){
434 if (indices[k] == index){
435 lhs += -values[k];
436 break;
437 }
438 }
439 }
440 for (i = v1 + 1; i < vertnum; i++){
441 index = INDEX(i, v1) + (1 + d_x_vars) * total_edgenum;
442 for (k = 0; k < varnum; k++){
443 if (indices[k] == index){
444 lhs += -values[k];
445 break;
446 }
447 }
448 }
449 *is_violated = (lhs > (double)(cut->rhs)+etol);
450 *quality = lhs - (double)cut->rhs;
451 if (*quality < etol && *quality > -etol) *quality = 0;
452 return(USER_SUCCESS);
453 #endif
454
455 #ifdef DIRECTED_X_VARS
456 case X_CUT:
457 first_coeff_found = second_coeff_found = FALSE;
458 for (i = 0; i < varnum && (!first_coeff_found ||
459 !second_coeff_found); i++){
460 if (indices[i] == ((int *)coef)[0]){
461 lhs += values[i];
462 first_coeff_found = TRUE;
463 }
464 if (indices[i] == ((int *)coef)[0]+total_edgenum){
465 lhs += values[i];
466 second_coeff_found = TRUE;
467 }
468 }
469 *is_violated = (lhs > (double)(cut->rhs)+etol);
470 *quality = lhs - (double)cut->rhs;
471 if (*quality < etol && *quality > -etol) *quality = 0;
472 return(USER_SUCCESS);
473 #endif
474
475 #if 0
476 case CLIQUE:
477 coef = cut->coef;
478 size = (vertnum >> DELETE_POWER) + 1;
479 memcpy(&cliquecount, coef, ISIZE);
480 coef += ISIZE;
481 for (lhs = 0, v0 = 0; v0 < vertnum; v0++){
482 for (j = 0; j < cliquecount; j++){
483 clique_array = coef + size * j;
484 if (!(clique_array[v0>>DELETE_POWER] & (1<<(v0 & DELETE_AND))))
485 continue;
486 for (cur_edge = verts[v0].first; cur_edge;
487 cur_edge = cur_edge->next){
488 v1 = cur_edge->other_end;
489 if (coef[v1 >> DELETE_POWER] & (1 << (v1 & DELETE_AND)))
490 lhs += cur_edge->weight;
491 }
492 }
493 }
494 *is_violated = (lhs < cut->rhs - etol);
495 *quality = (double)cut->rhs - lhs;
496 if (*quality < etol && *quality > -etol) *quality = 0;
497 return(USER_SUCCESS);
498 #endif
499
500 default:
501 printf("Cut types not recognized! \n\n");
502 *is_violated = FALSE;
503 return(USER_SUCCESS);
504 }
505 }
506
507 /*===========================================================================*/
508
509 /*===========================================================================*\
510 * This function is invoked when all cuts that needed to be checked for
511 * the current solution have been checked already. (Disassemble the
512 * data structures built up in 'user_prepare_to_check_cuts'.
513 \*===========================================================================*/
514
515 int user_finished_checking_cuts(void *user)
516 {
517 cnrp_spec_cp *vcp = (cnrp_spec_cp *)user;
518 free_pool_net(vcp);
519
520 return(USER_SUCCESS);
521 }
522
523 /*===========================================================================*/
524
525 /*===========================================================================*\
526 * This function creates the solution graph from the current LP solution
527 \*===========================================================================*/
528
529 pool_net *create_pool_net(cnrp_spec_cp *vcp, int varnum, int *indices,
530 double *values)
531 {
532 register int *edges = vcp->edges;
533 pool_net *n;
534 pool_node *verts;
535 int nv0 = 0, nv1 = 0;
536 pool_edge *adjlist;
537 int i;
538 int vertnum = vcp->vertnum;
539 int edgenum = vcp->edgenum;
540 #ifdef DIRECTED_X_VARS
541 pool_edge *pedge;
542 int total_edgenum = vertnum*(vertnum-1)/2;
543 char edge_exists;
544 #endif
545
546 n = (pool_net *) calloc (1, sizeof(pool_net));
547 n->vertnum = vertnum;
548 n->edgenum = varnum;
549 n->verts = (pool_node *)calloc((int)vertnum, sizeof(pool_node));
550 n->adjlist = (pool_edge *)calloc(2*(int)edgenum, sizeof(pool_edge));
551 verts = n->verts;
552 adjlist = n->adjlist;
553
554 for (i = 0; i < varnum; i++){
555 #ifdef DIRECTED_X_VARS
556 if (indices[i] < total_edgenum){
557 nv0 = edges[indices[i] << 1];
558 nv1 = edges[(indices[i] << 1) + 1];
559 }else{
560 nv0 = edges[(indices[i]-total_edgenum) << 1];
561 nv1 = edges[((indices[i]-total_edgenum) << 1) + 1];
562 }
563 for (edge_exists = FALSE, pedge = verts[nv0].first; pedge;
564 pedge = pedge->next){
565 if (pedge->other_end == nv1){
566 pedge->weight += values[i];
567 for (pedge = verts[nv1].first; pedge; pedge = pedge->next){
568 if (pedge->other_end == nv0){
569 pedge->weight += values[i];
570 }
571 }
572 edge_exists = TRUE;
573 break;
574 }
575 }
576 if (edge_exists)
577 continue;
578 #else
579 nv0 = edges[indices[i] << 1];
580 nv1 = edges[(indices[i] << 1) + 1];
581 #endif
582
583 if (!verts[nv0].first)
584 verts[nv0].first = adjlist;
585 else{
586 adjlist->next = verts[nv0].first;
587 verts[nv0].first = adjlist;
588 }
589 adjlist->other_end = nv1;
590 adjlist->weight = values[i];
591 adjlist++;
592 if (!verts[nv1].first)
593 verts[nv1].first = adjlist;
594 else{
595 adjlist->next = verts[nv1].first;
596 verts[nv1].first = adjlist;
597 }
598 adjlist->other_end = nv0;
599 adjlist->weight = values[i];
600 adjlist++;
601 }
602
603 return(n);
604 }
605
606 /*===========================================================================*/
607
608 /*===========================================================================*\
609 * Frees the memory associated with a solution network
610 \*===========================================================================*/
611
612 void free_pool_net(cnrp_spec_cp *vcp)
613 {
614 if (vcp->n){
615 FREE(vcp->n->adjlist);
616 FREE(vcp->n->verts);
617 FREE(vcp->n);
618 }
619 }