Debian Codegraph @

SYMPHONY/Applications/CNRP/src/LP/cnrp_lp_branch.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 #define COMPILING_FOR_LP
17
18 /* system include files */
19 #include <math.h>
20 #include <stdio.h>
21
22 /* SYMPHONY include files */
23 #include "sym_constants.h"
24 #include "sym_macros.h"
25 #include "sym_qsort.h"
26 #include "sym_lp_u.h"
27 /*__BEGIN_EXPERIMENTAL_SECTION__*/
28 #include "sym_lp.h"
29 /*___END_EXPERIMENTAL_SECTION___*/
30
31 /* CNRP include files */
32 #include "cnrp_lp.h"
33 #include "cnrp_macros.h"
34 #include "cnrp_const.h"
35
36 /*===========================================================================*/
37
38 /*===========================================================================*\
39 * This file contains the user-written functions for the LP process related
40 * to branching.
41 \*===========================================================================*/
42
43 /*===========================================================================*\
44 * This function determines whether to branch. You can eseentially
45 * leave this up to SYMPHONY unless there is some compelling reason not to.
46 \*===========================================================================*/
47
48 int user_shall_we_branch(void *user, double lpetol, int cutnum,
49 int slacks_in_matrix_num, cut_data **slacks_im_matrix,
50 int slack_cut_num, cut_data **slack_cuts, int varnum,
51 var_desc **vars, double *x, char *status,
52 int *cand_num, branch_obj ***candidates,
53 int *action)
54 {
55 int i;
56 double fracx, lpetol1 = 1 - lpetol;
57
58 cnrp_spec *cnrp = (cnrp_spec *) user;
59
60
61 for (i = varnum - 1; i >= 0; i--){
62 if (vars[i]->is_int){
63 fracx = x[i] - floor(x[i]);
64 if (fracx > lpetol && fracx < lpetol1){
65 break;
66 }
67 }
68 }
69
70 if(i >= 0 ){
71 *action = USER__BRANCH_IF_TAILOFF;
72 } else{
73 *action = USER__BRANCH_IF_MUST;
74 }
75
76 #if 0
77 if (cnrp->par.detect_tailoff){
78 *action = USER__BRANCH_IF_MUST;
79 return(USER_SUCCESS);
80 }
81
82 *action = USER__BRANCH_IF_TAILOFF;
83 #endif
84
85 return(USER_SUCCESS);
86 }
87
88 /*===========================================================================*/
89
90 /*===========================================================================*\
91 * Here, we select the branching candidates. This can essentially be
92 * left to SYMPHONY too using one of the built-in functions, but here, I
93 * demonstrate how to branch on cuts, which must be done by the user.
94 \*===========================================================================*/
95
96 int user_select_candidates(void *user, double lpetol, int cutnum,
97 int slacks_in_matrix_num,
98 cut_data **slacks_in_matrix, int slack_cut_num,
99 cut_data **slack_cuts, int varnum, var_desc **vars,
100 double *x, char *status, int *cand_num,
101 branch_obj ***candidates, int *action,
102 int bc_level)
103
104 {
105 cnrp_spec *cnrp = (cnrp_spec *)user;
106 cut_data *cut;
107 branch_obj **cand_list, *can;
108 int i, candnum, found_violated = FALSE;
109 p_w_l *pwl;
110 double left_hand_side, lpetol1 = 1 - lpetol, lpetol5=.95, slack, fracx;
111 waiting_row **new_rows;
112 int new_row_num;
113 int *userind;
114 int sim_cand_num = 0, sc_cand_num = 0;
115 int total_edgenum = cnrp->vertnum*(cnrp->vertnum - 1)/2;
116 int j, cnt = 0;
117 double lim[7] = {.1, .15, .20, .233333, .266667, .3, 1};
118 branch_obj *cand;
119
120 int *xind = (int *) malloc(varnum * ISIZE);
121 double *xval = (double *) calloc(varnum, DSIZE);
122
123 #if 0
124 if (!cnrp->par.branch_on_cuts && cnrp->par.branching_rule == 2)
125 /* use the built-in rule */
126 return(USER_DEFAULT);
127 #endif
128
129 /* first try the fixed-charge variables */
130 for (i = varnum - 1; i >= 0; i--){
131 if (vars[i]->is_int){
132 fracx = x[i] - floor(x[i]);
133 if (fracx > lpetol && fracx < lpetol1){
134 xind[cnt] = i;
135 xval[cnt++] = fabs(fracx - .5);
136 }
137 }
138 }
139
140 #ifdef ADD_FLOW_VARS
141 if (cnt == 0){
142 /* Now try the flow variables */
143 for (i = varnum - 1; i >= 0; i--){
144 if (!vars[i]->is_int){
145 fracx = x[i] - floor(x[i]);
146 if (fracx > lpetol && fracx < lpetol1){
147 xind[cnt] = i;
148 xval[cnt++] = fabs(fracx - .5);
149 }
150 }
151 }
152 }
153 #endif
154
155 qsort_di(xval, xind, cnt);
156
157 for (j = 0, i = 0; i < cnt;){
158 if (xval[i] > lim[j]){
159 if (i == 0){
160 j++; continue;
161 }else{
162 break;
163 }
164 }else{
165 i++;
166 }
167 }
168 cnt = i;
169
170 *cand_num = cnrp->par.strong_branching_cand_num_max;
171 *cand_num = MAX(*cand_num, cnrp->par.strong_branching_cand_num_min);
172 *cand_num = MIN(*cand_num, cnt);
173
174 if (!*candidates)
175 *candidates = (branch_obj **) malloc(*cand_num * sizeof(branch_obj *));
176 for (i=*cand_num-1; i>=0; i--){
177 cand = (*candidates)[i] = (branch_obj *) calloc(1, sizeof(branch_obj) );
178 cand->type = CANDIDATE_VARIABLE;
179 cand->child_num = 2;
180 cand->position = xind[i];
181 cand->sense[0] = 'L';
182 cand->sense[1] = 'G';
183 cand->rhs[0] = floor(x[xind[i]]);
184 cand->rhs[1] = cand->rhs[0] + 1;
185 cand->range[0] = cand->range[1] = 0;
186 }
187
188 FREE(xind);
189 FREE(xval);
190
191 return(USER_SUCCESS);
192
193 #if 0
194 #ifdef DIRECTED_X_VARS
195 nz = collect_nonzeros(p, x, xind, xval, status);
196
197 for (j = 0; j < nz && xind[j] < total_edgenum; j++);
198 for (i = 0; i < nz && xind[i] < total_edgenum; i++){
199 for (; j < nz && xind[j] < xind[i] + total_edgenum; j++){
200 if (xind[i] == xind[j] + total_edgenum){
201 xval[i] += xval[j];
202 break;
203 }else{
204 xind[j] -= total_edgenum;
205 }
206 }
207 }
208 for (i = 0; i < nz; i++){
209 if (xind[i] < total_edgenum){
210 if ((xval[i] = fabs(xval[i] - floor(xval[i]) - .5)) < .5 - lpetol)
211 cnt++;
212 }
213 }
214 qsort_di(xval, xind, nz);
215
216 candnum = cnrp->par.strong_branching_cand_num_max;
217 candnum = MAX(candnum, cnrp->par.strong_branching_cand_num_min);
218 candnum = MIN(candnum, cnt);
219
220 FREE(xind);
221 FREE(xval);
222 #endif
223 #endif
224
225 *cand_num = 0;
226 candnum = 0;
227 /* allocate also memory for the basic vars */
228 *candidates = cand_list = (branch_obj **)
229 malloc((varnum + (cnrp->par.branch_on_cuts ?
230 (slacks_in_matrix_num + slack_cut_num) : 0)) *
231 sizeof(branch_obj *));
232 switch (cnrp->par.branch_on_cuts){
233 case TRUE:
234 pwl = (p_w_l *) malloc((slacks_in_matrix_num + slack_cut_num)*
235 sizeof(p_w_l));
236 userind = (int *) malloc(varnum*ISIZE);
237
238 for (i = varnum - 1; i >= 0; i--)
239 userind[i] = vars[i]->userind;
240
241 /* First go through the slack cuts and enlist the violated ones */
242 for (i = 0; i < slack_cut_num; i++){
243 left_hand_side = compute_lhs(varnum, userind, x, cut = slack_cuts[i],
244 cnrp->vertnum);
245 switch (cut->type){
246 case SUBTOUR_ELIM_SIDE:
247 slack = cut->rhs - left_hand_side;
248 if (slack < -lpetol){/*---------------- This cut became violated */
249 found_violated = TRUE;
250 can = cand_list[candnum++] =
251 (branch_obj *) calloc(1, sizeof(branch_obj));
252 can->type = VIOLATED_SLACK;
253 can->position = i;
254 }else if ((!found_violated) && (slack>lpetol) &&
255 !(cut->sense == 'R' || cut->sense == 'E')){
256 pwl[sc_cand_num].lhs = left_hand_side;
257 pwl[sc_cand_num++].position = i;
258 }
259 break;
260
261 case SUBTOUR_ELIM_ACROSS:
262 slack = left_hand_side - cut->rhs;
263 if (slack < -lpetol){/*---------------- This cut became violated */
264 found_violated = TRUE;
265 can = cand_list[candnum++] =
266 (branch_obj *) calloc(1, sizeof(branch_obj));
267 can->type = VIOLATED_SLACK;
268 can->position = i;
269 }else if ((!found_violated) && (slack>lpetol) &&
270 !(cut->sense=='R' || cut->sense=='E')){
271 pwl[sc_cand_num].lhs = left_hand_side;
272 pwl[sc_cand_num++].position = i;
273 }
274 break;
275
276 default:
277 break;
278 }
279 }
280 if (found_violated){
281 *cand_num = candnum;
282 FREE(pwl);
283 *action = USER__DO_NOT_BRANCH;
284 return(USER_SUCCESS);
285 }
286
287 /* now go through the slack rows in the matrix and add the potential
288 candidates to the end of the pos/weight lists */
289 for (i = 0; i < slacks_in_matrix_num; i++)
290 if ((cut = slacks_in_matrix[i]) &&
291 (cut->type==SUBTOUR_ELIM_SIDE || cut->type== SUBTOUR_ELIM_ACROSS)
292 && !(cut->sense=='R' || cut->sense=='E')){
293 left_hand_side = compute_lhs(varnum, userind, x, cut,
294 cnrp->vertnum);
295 switch (cut->type){
296 case SUBTOUR_ELIM_SIDE:
297 slack = cut->rhs - left_hand_side;
298 /* if (slack > lpetol && slack < lpetol1){*/
299 if (slack > lpetol ){
300 pwl[sc_cand_num+sim_cand_num].lhs = left_hand_side;
301 pwl[sc_cand_num+sim_cand_num].position = i;
302 sim_cand_num++;
303 }
304 break;
305
306 case SUBTOUR_ELIM_ACROSS:
307 slack = left_hand_side - cut->rhs;
308 /* if (slack > lpetol && slack < 2-lpetol){*/
309 if (slack > lpetol ){
310 pwl[sc_cand_num+sim_cand_num].lhs = left_hand_side;
311 pwl[sc_cand_num+sim_cand_num].position = i;
312 sim_cand_num++;
313 }
314 break;
315
316 default:
317 break;
318 }
319 }
320
321 /* set the children's rhs etc */
322 for (i = 0 ; i < sc_cand_num + sim_cand_num; i++){
323 can = cand_list[candnum++] =
324 (branch_obj *) calloc(1, sizeof(branch_obj));
325 if (i < sc_cand_num ){
326 can->type = CANDIDATE_CUT_NOT_IN_MATRIX;
327 cut = slack_cuts[can->position = pwl[i].position ];
328 user_unpack_cuts(user, CUT_NOT_IN_MATRIX_SLACK,
329 UNPACK_CUTS_SINGLE, varnum, vars, 1,
330 slack_cuts+can->position, &new_row_num,
331 &new_rows);
332 can->row = *new_rows;
333 cut = can->row->cut;
334 FREE(new_rows);
335 }else{
336 can->type = CANDIDATE_CUT_IN_MATRIX;
337 cut = slacks_in_matrix[can->position = pwl[i].position ];
338 }
339 can->child_num = 2;
340 can->lhs = pwl[i].lhs;
341 /* no need to allocate these. they are of fixed length
342 can->sense = (char *) malloc(2 * CSIZE);
343 can->rhs = (double *) malloc(2 * DSIZE);
344 can->range = (double *) malloc(2 * DSIZE);
345 */
346 switch (cut->type){
347 case SUBTOUR_ELIM_SIDE:
348 if ((slack = cut->rhs - can->lhs) < lpetol1){
349 can->sense[0] = 'E';
350 can->rhs[0] = cut->rhs;
351 can->range[0] = 0;
352 can->branch[0] = DO_NOT_BRANCH_ON_THIS_ROW;
353 can->sense[1] = 'L';
354 can->rhs[1] = cut->rhs - 1;
355 can->range[1] = 0;
356 can->branch[1] = ALLOWED_TO_BRANCH_ON;
357 }else{
358 can->sense[0] = 'R';
359 can->rhs[0] = cut->rhs;
360 can->range[0] = -floor(slack) ;
361 can->branch[0] = DO_NOT_BRANCH_ON_THIS_ROW;
362 can->sense[1] = 'L';
363 can->rhs[1] = cut->rhs - ceil(slack);
364 can->range[1] = 0;
365 can->branch[1] = ALLOWED_TO_BRANCH_ON;
366 }
367 break;
368 case SUBTOUR_ELIM_ACROSS:
369 if ((slack = can->lhs - cut->rhs) < 2-lpetol){
370 can->sense[0] = 'E';
371 can->rhs[0] = cut->rhs;
372 can->range[0] = 0;
373 can->branch[0] = DO_NOT_BRANCH_ON_THIS_ROW;
374 can->sense[1] = 'G';
375 can->rhs[1] = cut->rhs + 2;
376 can->range[1] = 0;
377 can->branch[1] = ALLOWED_TO_BRANCH_ON;
378 }else{
379 can->sense[0] = 'R';
380 can->rhs[0] = cut->rhs;
381 can->range[0] = 2*floor(slack/2);
382 can->branch[0] = DO_NOT_BRANCH_ON_THIS_ROW;
383 can->sense[1] = 'G';
384 can->rhs[1] = cut->rhs + 2*floor(slack/2) +2;
385 can->range[1] = 0;
386 can->branch[1] = ALLOWED_TO_BRANCH_ON;
387 }
388 break;
389 }
390 }
391 FREE(pwl);
392 FREE(userind);
393 *cand_num = candnum;
394 cand_list = *candidates + *cand_num;
395
396 case FALSE:
397
398 switch (((cnrp_spec *)user)->par.branching_rule){
399 case 0:
400 {
401 int *xind = (int *) malloc(varnum*ISIZE);
402 double *xval = (double *) malloc(varnum*DSIZE);
403 int cnt = 0;
404
405 for (i = varnum-1; i >= 0; i--){
406 fracx = x[i] - floor(x[i]);
407 if (fracx > lpetol && fracx < 1-lpetol){
408 xind[cnt] = i;
409 xval[cnt++] = fabs(fracx - .5);
410 }
411 }
412 qsort_di(xval, xind, cnt);
413
414 candnum = cnrp->par.strong_branching_cand_num_max -
415 cnrp->par.strong_branching_red_ratio * bc_level;
416 candnum = MAX(candnum, cnrp->par.strong_branching_cand_num_min);
417 candnum = MIN(candnum, cnt);
418
419 for (i = candnum-1; i >= 0; i--){
420 can=cand_list[i]=(branch_obj *) calloc(1, sizeof(branch_obj));
421 can->type = CANDIDATE_VARIABLE;
422 can->child_num = 2;
423 can->position = xind[i];
424 can->sense[0] = 'L';
425 can->sense[1] = 'G';
426 can->rhs[0] = floor(x[xind[i]]);
427 can->rhs[1] = can->rhs[0] + 1;
428 can->range[0] = can->range[1] = 0;
429 }
430 FREE(xind);
431 FREE(xval);
432 }
433 break;
434
435 case 1:
436 candnum = 0;
437 for (i = varnum-1; i >= 0; i--){
438 fracx = x[i] - floor(x[i]);
439 if (fracx > lpetol && fracx < lpetol5){
440 can = cand_list[candnum++] =
441 (branch_obj *) calloc(1, sizeof(branch_obj));
442 can->type = CANDIDATE_VARIABLE;
443 can->child_num = 2;
444 can->position = i;
445 can->sense[0] = 'L';
446 can->sense[1] = 'G';
447 can->rhs[0] = floor(x[i]);
448 can->rhs[1] = can->rhs[0] + 1;
449 can->range[0] = can->range[1] = 0;
450 }
451 }
452 break;
453
454 case 2:
455 return(USER__CLOSE_TO_HALF);
456 }
457 *cand_num += candnum;
458 *action = USER__DO_BRANCH;
459 }
460 return(USER_SUCCESS);
461 }
462
463 /*===========================================================================*/
464
465 double compute_lhs(int number, int *indices, double *values, cut_data *cut,
466 int vertnum)
467 {
468 char *coef;
469 int v0, v1;
470 double lhs = 0;
471 int i;
472
473 switch (cut->type){
474
475 case SUBTOUR_ELIM_SIDE:
476 coef = (char *)(cut->coef);
477 for (i = 0, lhs = 0; i<number; i++){
478 BOTH_ENDS(indices[i], &v1, &v0);
479 if (coef[v0 >> DELETE_POWER] & (1 << (v0 & DELETE_AND)) &&
480 (coef[v1 >> DELETE_POWER]) & (1 << (v1 & DELETE_AND)))
481 lhs += values[i];
482
483 }
484 return(lhs);
485
486 case SUBTOUR_ELIM_ACROSS:
487 coef = (char *)(cut->coef);
488 for (lhs = 0, i = 0; i<number; i++){
489 BOTH_ENDS(indices[i], &v1, &v0);
490 if ((coef[v0 >> DELETE_POWER] >> (v0 & DELETE_AND) & 1) ^
491 (coef[v1 >> DELETE_POWER] >> (v1 & DELETE_AND) & 1))
492 lhs += values[i];
493 }
494
495 return(lhs);
496
497 default:
498 printf("Cut type's not recognized! \n\n");
499 return(0);
500 }
501 }
502
503 /*===========================================================================*/
504
505 /*===========================================================================*\
506 * I wrote my own function to compare candidates. Maybe this should go
507 * into SYMPHONY.
508 \*===========================================================================*/
509
510 int user_compare_candidates(void *user, branch_obj *can1, branch_obj *can2,
511 double ub, double granularity,
512 int *which_is_better)
513 {
514 int i, j;
515 double low1, low2;
516
517 for (i = 1; i >= 0; i--)
518 if (can1->termcode[i] == LP_OPT_FEASIBLE ||
519 can1->termcode[i] == LP_OPT_FEASIBLE_BUT_CONTINUE ||
520 can1->termcode[i] == LP_D_OBJLIM ||
521 can1->termcode[i] == LP_D_UNBOUNDED ||
522 (can1->termcode[i] == LP_OPTIMAL && can1->objval[i] > ub - granularity))
523 break;
524
525 for (j = 1; j >= 0; j--)
526 if (can2->termcode[j] == LP_OPT_FEASIBLE ||
527 can1->termcode[i] == LP_OPT_FEASIBLE_BUT_CONTINUE ||
528 can2->termcode[j] == LP_D_OBJLIM ||
529 can2->termcode[j] == LP_D_UNBOUNDED ||
530 (can2->termcode[j] == LP_OPTIMAL && can2->objval[j] > ub - granularity))
531 break;
532
533 if (i < 0 && j < 0)
534 return(USER_DEFAULT);
535
536 if (i < 0 && j > 0){
537 *which_is_better = SECOND_CANDIDATE_BETTER;
538 return(USER_SUCCESS);
539 }
540
541 if (i > 0 && j < 0){
542 *which_is_better = FIRST_CANDIDATE_BETTER;
543 return(USER_SUCCESS);
544 }
545
546 low1 = i ? can1->objval[0] : can1->objval[1];
547 low2 = j ? can2->objval[0] : can2->objval[1];
548
549 *which_is_better = low1 > low2 ? FIRST_CANDIDATE_BETTER :
550 SECOND_CANDIDATE_BETTER;
551
552 return(USER_SUCCESS);
553 }
554
555 /*===========================================================================*/
556
557 /*===========================================================================*\
558 * You can let SYMPHONY choose which child to retain. The default is
559 * to keep the one with the lower objective function value.
560 \*===========================================================================*/
561
562 int user_select_child(void *user, double ub, branch_obj *can, char *action)
563 {
564 return(USER_DEFAULT);
565 }
566
567 /*===========================================================================*/
568
569 /*===========================================================================*\
570 * Here, you can print out a more identifiable description of the
571 * branching object than just "variable 51". I print out the end points
572 * of the edge if an edge is branched on.
573 \*===========================================================================*/
574
575 int user_print_branch_stat(void *user, branch_obj *can, cut_data *cut,
576 int n, var_desc **vars, char *action)
577 {
578 cnrp_spec *cnrp = (cnrp_spec *)user;
579 int v0, v1, i;
580 char *coef;
581 int total_edgenum = cnrp->vertnum*(cnrp->vertnum - 1)/2;
582
583 if (cut){
584 switch(cut->type){
585 case SUBTOUR_ELIM_SIDE:
586 coef = (char *)(cut->coef);
587 for (i = 0; i < n; i++){
588 BOTH_ENDS(vars[i]->userind, &v1, &v0);
589 if (coef[v0 >> DELETE_POWER] & (1 << (v0 & DELETE_AND)) &&
590 (coef[v1 >> DELETE_POWER]) & (1 << (v1 & DELETE_AND)))
591 printf("Edge (%i, %i)\n", v0, v1);
592 }
593
594 case SUBTOUR_ELIM_ACROSS:
595 coef = (char *)(cut->coef);
596 for (i = 0; i < n; i++){
597 BOTH_ENDS(vars[i]->userind, &v1, &v0);
598 if ((coef[v0 >> DELETE_POWER] >> (v0 & DELETE_AND) & 1) ^
599 (coef[v1 >> DELETE_POWER] >> (v1 & DELETE_AND) & 1))
600 printf("Edge (%i, %i)\n", v0, v1);
601 }
602 }
603 }else{
604 if (vars[can->position]->userind < total_edgenum){
605 BOTH_ENDS(vars[can->position]->userind, &v1, &v0);
606 }else if (vars[can->position]->userind < 2*total_edgenum){
607 BOTH_ENDS(vars[can->position]->userind-total_edgenum, &v1, &v0);
608 }else{
609 printf("ERROR in branching.../n/n");
610 }
611 printf("Edge (%i, %i)\n", v0, v1);
612 }
613
614 return(USER_SUCCESS);
615 }