Debian Codegraph @

SYMPHONY/Applications/SPP+CUTS/src/LP/spp_lp_functions.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 /* the Set Partitioning Problem. */
6 /* */
7 /* (c) Copyright 2005-2007 Marta Eso and Ted Ralphs. All Rights Reserved. */
8 /* */
9 /* This application was originally developed by Marta Eso and was modified */
10 /* Ted Ralphs ([email protected]) */
11 /* */
12 /* This software is licensed under the Eclipse Public License. Please see */
13 /* accompanying file for terms. */
14 /* */
15 /*===========================================================================*/
16
17 /* system include files */
18 #include <stdio.h>
19 #include <stdlib.h>
20 #include <math.h>
21 #include <memory.h>
22
23 /* SYMPHONY include files */
24 #include "sym_types.h"
25 #include "sym_macros.h"
26 #include "sym_constants.h"
27 #include "sym_qsort.h"
28
29 /* SPP include files */
30 #include "spp_constants.h"
31 #include "spp_types.h"
32 #include "spp_common.h"
33 #include "spp_lp.h"
34 #include "spp_lp_functions.h"
35
36
37 /*****************************************************************************/
38
39 void spp_init_lp(spp_lp_problem *spp)
40 {
41 int *matbeg = spp->cmatrix->matbeg;
42 int rownum = spp->cmatrix->rownum;
43 int colnum = spp->cmatrix->colnum;
44 int nzbd = 0; /* upper bound on the number of nonzeros in atilde */
45 int i, len;
46
47 spp->tmp = (spp_lp_tmp *) malloc(sizeof(spp_lp_tmp));
48 spp->tmp->ctmp_2nD = (char *) malloc(2 * colnum * DSIZE);
49 spp->tmp->dtmp_m = (double *) malloc(rownum * DSIZE);
50 spp->tmp->dtmp_n = (double *) malloc(colnum * DSIZE);
51 spp->tmp->itmp_m = (int *) malloc(rownum * ISIZE);
52 spp->tmp->itmp_2n = (int *) malloc(colnum * 2 * ISIZE);
53
54 if (spp->par->which_atilde == COLS_OF_A ||
55 spp->par->which_atilde == SPARS_PATTERN) {
56 /* compute nzbd = rownum * length of longest column in A */
57 for (i = spp->cmatrix->colnum - 1; i >= 0; i--) {
58 len = matbeg[i+1] - matbeg[i];
59 if (len > nzbd) nzbd = len;
60 }
61 nzbd = nzbd * rownum;
62 } else if (spp->par->which_atilde == EDGE_NODE_INC ||
63 spp->par->which_atilde == EDGE_NODE_INC_PERT) {
64 /* at most rownum^2/2 edges in graph, two 1's for each edge in the
65 matrix */
66 nzbd = rownum * rownum;
67 }
68 }
69
70 /*****************************************************************************/
71
72 void spp_free_lp_tmp(spp_lp_problem *spp)
73 {
74 FREE(spp->tmp->ctmp_2nD);
75 FREE(spp->tmp->dtmp_m);
76 FREE(spp->tmp->dtmp_n);
77 FREE(spp->tmp->itmp_m);
78 FREE(spp->tmp->itmp_2n);
79 }
80
81 /*****************************************************************************/
82
83 void disp_where_cut_is_from(int from)
84 {
85 switch (from) {
86 case CUT_FROM_CG:
87 printf("\nCut(s) received from the cut generator\n");
88 break;
89 case CUT_FROM_CP:
90 printf("\nCut(s) received from the cut pool\n");
91 break;
92 case CUT_FROM_TM:
93 printf("\nCut(s) received from the tree manager\n");
94 break;
95 case CUT_LEFTOVER:
96 printf("\nCut(s) leftover from previous lp\n");
97 break;
98 case CUT_NOT_IN_MATRIX_SLACK:
99 printf("\nCut(s) not in matrix and slack\n");
100 break;
101 #if 0
102 case CUT_VIOLATED_SLACK:
103 printf("\nCut(s) violated and slack\n");
104 break;
105 #endif
106 }
107 }
108
109 /*****************************************************************************/
110 /* Display cuts in the LP. Violation is not displayed if it is -1. */
111
112 void display_cut_in_lp(spp_lp_problem *spp, cut_data *cut, double violation)
113 {
114 int *indices = spp->tmp->itmp_2n;
115 double *coefs = spp->tmp->dtmp_n;
116 int *colnames = spp->cmatrix->colnames;
117 int j, coef_num;
118
119 switch (cut->type) {
120
121 case CLIQUE:
122 case CLIQUE_LIFTED:
123 case ODD_HOLE:
124 case ODD_ANTIHOLE:
125 coef_num = cut->size/ISIZE;
126 memcpy(indices, cut->coef, coef_num * ISIZE);
127 switch (cut->type) {
128 case CLIQUE: printf("CLIQUE\n"); break;
129 case CLIQUE_LIFTED: printf("CLIQUE_LIFTED\n"); break;
130 case ODD_HOLE: printf("ODD_HOLE\n"); break;
131 case ODD_ANTIHOLE: printf("ODD_ANTIHOLE\n"); break;
132 }
133 printf(" Indices (names): ");
134 for (j = 0; j < coef_num; j++)
135 /* printf("%i ", indices[j]); */
136 printf("%i (%i) ", indices[j], colnames[indices[j]]);
137 printf("\n");
138 if (violation == -1) {
139 printf(" type: %i, num: %i, rhs: %f\n", cut->type, coef_num,
140 cut->rhs);
141 } else {
142 printf(" type: %i, num: %i, rhs: %f, violation: %f\n",
143 cut->type, coef_num, cut->rhs, violation);
144 }
145 break;
146
147 case ODD_HOLE_LIFTED:
148 printf("ODD_HOLE_LIFTED\n");
149 break;
150 case ODD_ANTIHOLE_LIFTED:
151 printf("ODD_ANTIHOLE_LIFTED\n");
152 break;
153
154 case ORTHOCUT:
155 /* FIXME! */
156 break;
157
158 case WHEEL:
159 case OTHER_CUT:
160 coef_num = cut->size/(ISIZE + DSIZE);
161 memcpy(indices, cut->coef, coef_num * ISIZE);
162 memcpy(coefs, cut->coef + coef_num * ISIZE, coef_num * DSIZE);
163 if (cut->type == WHEEL) {
164 printf("WHEEL\n");
165 } else {
166 printf("OTHER CUT\n");
167 }
168 printf(" Indices (names) [coefs]: ");
169 for (j = 0; j < coef_num; j++)
170 printf("%i (%i) [%f] ", indices[j], colnames[indices[j]], coefs[j]);
171 printf("\n");
172 if (violation == -1) {
173 printf(" type: %i, num: %i, rhs: %f\n", cut->type, coef_num,
174 cut->rhs);
175 } else {
176 printf(" type: %i, num: %i, rhs: %f, violation: %f\n",
177 cut->type, coef_num, cut->rhs, violation);
178 }
179 break;
180
181 default:
182 printf("ERROR: Unrecognized cut type in display_cut_in_lp! \n");
183 break;
184 }
185 }
186
187 /*****************************************************************************/
188 /*===========================================================================*
189 * Convert the cut into a row. Space is allocated for matind and matval here.
190 * If the base variables are not all the variables, the part currently
191 * commented out must be used.
192 *
193 * IN: spp, n, vars, cut. OUT: pnzcnt, pmatind, pmatval.
194 *===========================================================================*/
195
196 void cut_to_row(spp_lp_problem *spp, int n, var_desc **vars, cut_data *cut,
197 int *pnzcnt, int **pmatind, double **pmatval)
198 {
199 int *matind;
200 double *matval;
201 int i, nzcnt, coef_num, oh_num, hub_num;
202
203 switch (cut->type) {
204
205 case CLIQUE:
206 case CLIQUE_LIFTED:
207 case ODD_HOLE:
208 case ODD_ANTIHOLE:
209 coef_num = nzcnt = cut->size/ISIZE;
210 matind = (int *) malloc(coef_num * ISIZE);
211 matval = (double *) malloc(coef_num * DSIZE);
212 memcpy(matind, cut->coef, coef_num * ISIZE);
213 for (i = coef_num-1; i >= 0; i--)
214 matval[i] = 1.0;
215 break;
216
217 case ORTHOCUT:
218 case WHEEL:
219 case OTHER_CUT:
220 if (cut->type == ORTHOCUT)
221 coef_num = nzcnt =
222 (cut->size-spp->cmatrix->rownum*DSIZE) / (ISIZE + DSIZE);
223 else
224 coef_num = nzcnt = cut->size / (ISIZE + DSIZE);
225 matind = (int *) malloc(coef_num * ISIZE);
226 matval = (double *) malloc(coef_num * DSIZE);
227 memcpy(matind, cut->coef, coef_num * ISIZE);
228 memcpy(matval, cut->coef + coef_num * ISIZE, coef_num * DSIZE);
229 break;
230
231 case ODD_HOLE_LIFTED:
232 case ODD_ANTIHOLE_LIFTED:
233 memcpy(&oh_num, cut->coef, ISIZE);
234 memcpy(&hub_num, cut->coef + ISIZE, ISIZE);
235 coef_num = nzcnt = oh_num + hub_num;
236 matind = (int *) malloc(coef_num * ISIZE);
237 matval = (double *) malloc(coef_num * DSIZE);
238 memcpy(matind, cut->coef + 2 * ISIZE, coef_num * ISIZE);
239 for (i = oh_num-1; i >= 0; i--)
240 matval[i] = 1.0;
241 memcpy(matval + oh_num, cut->coef + (2+coef_num)*ISIZE, hub_num * DSIZE);
242 break;
243
244 default:
245 printf("ERROR: Unrecognized cut type in cut_to_row (%i)\n", cut->type);
246 break;
247 }
248
249 #if 0
250 /* This is how the routine should look like if not all variables are
251 base variables. matind will contain those variable indices that are
252 both in vars and the cut. */
253 int *indices = spp->tmp->itmp_n;
254 double *coefs = spp->tmp->dtmp_n;
255
256 switch (cut->type) {
257
258 case CLIQUE:
259 case CLIQUE_LIFTED:
260 case ODD_HOLE:
261 case ODD_ANTIHOLE:
262 coef_num = cut->size/ISIZE;
263 matind = (int *) malloc(coef_num * ISIZE);
264 matval = (double *) malloc(coef_num * DSIZE);
265 memcpy(indices, cut->coef, coef_num * ISIZE);
266 /* i runs thru vars, j runs thru indices, nzcnt runs thru matind */
267 for (i = j = nzcnt = 0; i < n && j < coef_num; ) {
268 if (vars[i]->userind == indices[j]) {
269 matind[nzcnt] = i; /* matind is filled wrt position in vars */
270 matval[nzcnt++] = 1;
271 i++; j++;
272 } else if (vars[i]->userind < indices[j]) {
273 i++;
274 } else {
275 j++;
276 }
277 }
278 break;
279
280 case ORTHOCUT:
281 case WHEEL:
282 case OTHER_CUT:
283 if (cut->type == ORTHOCUT)
284 coef_num = (cut->size-spp->cmatrix->rownum*DSIZE) / (ISIZE + DSIZE);
285 else
286 coef_num = cut->size / (ISIZE + DSIZE);
287 matind = (int *) malloc(coef_num * ISIZE);
288 matval = (double *) malloc(coef_num * DSIZE);
289 memcpy(indices, cut->coef, coef_num * ISIZE);
290 memcpy(coefs, cut->coef + coef_num * ISIZE, coef_num * DSIZE);
291 /* i runs thru vars, j runs thru indices, nzcnt runs thru matind */
292 for (i = j = nzcnt = 0; i < n && j < coef_num; ) {
293 if (vars[i]->userind == indices[j]) {
294 matind[nzcnt] = i; /* matind is filled wrt position in vars */
295 matval[nzcnt++] = coefs[j];
296 i++; j++;
297 } else if (vars[i]->userind < indices[j]) {
298 i++;
299 } else {
300 j++;
301 }
302 }
303 break;
304
305 default:
306 printf("ERROR: Unrecognized cut type in cut_to_row (%i)\n", cut->type);
307 break;
308 }
309 #endif
310
311 *pnzcnt = nzcnt;
312 *pmatind = matind;
313 *pmatval = matval;
314 }
315
316 /*****************************************************************************/
317 /*===========================================================================*
318 * Lift cuts.
319 *
320 * Note: Only cliques are lifted rigth now.
321 * Cliques are lifted only if they come from the cut generator
322 * (since all variables are always in the formulation, it is
323 * unlikely that a lifted clique can be extended further).
324 *
325 * Algo for computing dj threshold: take the smallest of
326 * spp->par->lp_dj_threshold_abs and ..->lp_dj_threshold_frac * gap
327 * (if both > 0), lpetol if both are <= 0, and the positive of the two
328 * if only one of them is positive.
329 *===========================================================================*/
330
331 /* Needed to get access to the LP problem data structure */
332 #include "sym_lp.h"
333
334 void lift_cut_in_lp(spp_lp_problem *spp, int from, int n,
335 var_desc **vars, cut_data **cut, int *plifted_cutnum,
336 cut_data ***plifted_cuts)
337 {
338 /* FIXME: This function is temporarily broken. */
339 lp_prob *p; /* = get_lp_ptr(NULL); */
340 double lpetol = p->lp_data->lpetol;
341 double *dj = p->lp_data->dj;
342 double thres1, thres2, thres, gap, ub;
343 spp_lp_params *par = spp->par;
344 char *coef = spp->tmp->ctmp_2nD;
345 char *new_coef;
346 cut_data *new_cut;
347
348 if ((*cut)->type == CLIQUE && from == CUT_FROM_CG) {
349 /* compute threshold for dj */
350 if (p->has_ub)
351 ub = p->ub;
352 else
353 ub = 0;
354 /* gap is negative if ub is 0 ==> thres1 will be negative */
355 gap = p->ub - par->granularity - p->lp_data->objval + lpetol;
356 thres1 = gap * par->lp_dj_threshold_frac;
357 thres2 = par->lp_dj_threshold_abs;
358 if (thres1 > 0 && thres2 > 0)
359 thres = MIN(thres1, thres2);
360 else if (thres1 <= 0 && thres2 <= 0)
361 thres = lpetol;
362 else
363 thres = MAX(thres1, thres2);
364 /* allocate space for new cut */
365 new_cut = (cut_data *) malloc(sizeof(cut_data));
366 new_cut->coef = coef;
367 /* strategy: DONT_CHAGE_CUT since all vars are base vars
368 lift clique returns true if lifting was successful, false ow */
369 if (lift_clique(spp, n, vars, dj, thres, *cut, new_cut,
370 DONT_CHANGE_CUT)) {
371 new_coef = (char *) malloc(new_cut->size * CSIZE);
372 memcpy(new_coef, new_cut->coef, new_cut->size * CSIZE);
373 new_cut->coef = new_coef;
374 *plifted_cutnum = 1;
375 *plifted_cuts = (cut_data **) malloc(sizeof(cut_data *));
376 **plifted_cuts = new_cut;
377 *cut = NULL;
378 } else {
379 /* return the same cut */
380 *plifted_cutnum = 1;
381 *plifted_cuts = (cut_data **) malloc(sizeof(cut_data *));
382 **plifted_cuts = *cut;
383 *cut = NULL;
384 }
385 } else {
386 /* return the same cut */
387 *plifted_cutnum = 1;
388 *plifted_cuts = (cut_data **) malloc(sizeof(cut_data *));
389 **plifted_cuts = *cut;
390 *cut = NULL;
391 }
392 }
393
394 /*****************************************************************************/
395 /*===========================================================================*
396 *===========================================================================*/
397
398
399
400 /*****************************************************************************/
401 /* the following are functions invoked during lifting in user_unpack_cuts */
402 /*****************************************************************************/
403
404 /*===========================================================================*
405 * Given a clique with indices cl_indices, extend it with variables in
406 * indices in a greedy fashion. Return the number of variables that
407 * have been added to the clique. Overwrite indices to have these
408 * variables at the beginning of the array.
409 *===========================================================================*/
410
411 int extend_clique_greedily(col_ordered *cmatrix, int cl_length,
412 int *cl_indices, int length, int *indices)
413 {
414 int i, j, var;
415 int pos = 0; /* pos after the last var that has been added to the clique */
416
417 for (j = 0; j < length; j++) {
418 var = indices[j];
419 for (i = cl_length - 1; i >= 0; i--)
420 if (spp_is_orthogonal(cmatrix, cl_indices[i], var))
421 break;
422 if (i >= 0)
423 continue;
424 for (i = pos - 1; i >= 0; i--)
425 if (spp_is_orthogonal(cmatrix, indices[i], var))
426 break;
427 if (i < 0)
428 indices[pos++] = var;
429 }
430 return(pos);
431 }
432
433 /*****************************************************************************/
434
435 /*===========================================================================*
436 * Lift the clique given in cut. The lifted clique will be in new_cut.
437 * new_cut is already allocated (with enough space in coef).
438 *
439 * Variables in the current formulation are given in vars, their respective
440 * reduced costs in dj. Variables with reduced costs greater than
441 * dj_threshold are not considered for lifting.
442 * Returns TRUE if lifting was successful (that is, managed to add variables
443 * to the clique) and FALSE ow. new_cut contains the lifted clique if the
444 * return value is TRUE, ow new_cut is junk.
445 *
446 * strategy indicates whether variables with not sufficiently small reduced
447 * costs in the original clique can be thrown out from the clique. (if
448 * clique comes from CP, variables in clique might not be all in the basis)
449 * possible values for strategy: MAY_CHANGE_CUT, DONT_CHANGE_CUT.
450 * algo: if some variable is in cl but not in ind: throw it out from cl.
451 * if it is in both: throw it out from ind. if it is in ind but not in cl:
452 * leave it in ind.
453 *===========================================================================*/
454
455 char lift_clique(spp_lp_problem *spp, int n, var_desc **vars, double *dj,
456 double dj_threshold, cut_data *cut, cut_data *new_cut,
457 int strategy)
458 {
459 int i, j, k, length, cl_length, ind, pos_cl, pos_ind;
460 int *cl_indices = spp->tmp->itmp_2n;
461 int *indices = spp->tmp->itmp_2n + spp->cmatrix->colnum;
462
463 printf("\nLifting the following clique:\n");
464 display_cut_in_lp(spp, cut, -1);
465
466 cl_length = cut->size/ISIZE;
467 memcpy(cl_indices, cut->coef, cl_length * ISIZE);
468
469 /* extract user indices of variables with small enough reduced costs
470 and fill them into indices */
471 for (i = n - 1, length = 0; i >= 0; i--)
472 if (dj[i] < dj_threshold)
473 indices[length++] = vars[i]->userind;
474 if (length == 0) {
475 printf("... no vars with small enough reduced cost (threshold: %f)\n",
476 dj_threshold);
477 return(FALSE);
478 }
479
480 /* order indices */
481 qsort_i(indices, length);
482
483 if (strategy == MAY_CHANGE_CUT) {
484 for (i = 0, j = 0, pos_ind = 0, pos_cl = 0; i<length && j<cl_length; )
485 if (indices[i] < cl_indices[j]) {
486 indices[pos_ind++] = indices[i];
487 i++;
488 } else if (indices[i] == cl_indices[j]) {
489 i++; j++;
490 } else {
491 cl_indices[pos_cl++] = cl_indices[j];
492 j++;
493 }
494 for ( ; i < length; i++)
495 indices[pos_ind++] = indices[i];
496 /* if sg is left in cl_indices, it is thrown away: do nothing */
497 length = pos_ind; cl_length = pos_cl;
498
499 } else if (strategy == DONT_CHANGE_CUT) {
500 for (i = 0, j = 0, pos_ind = 0; i < length && j < cl_length; )
501 if (indices[i] < cl_indices[j]) {
502 indices[pos_ind++] = indices[i];
503 i++;
504 } else if (indices[i] == cl_indices[j]) {
505 i++; j++;
506 } else {
507 j++;
508 }
509 for ( ; i < length; i++)
510 indices[pos_ind++] = indices[i];
511 length = pos_ind;
512
513 } else {
514 printf("Bogus strategy in lift_clique, %i", strategy);
515 return(FALSE);
516 }
517
518 if (length == 0) {
519 printf("... no vars with small enough reduced cost (threshold: %f)\n",
520 dj_threshold);
521 return(FALSE);
522 } else {
523 printf("... %i vars with small enough reduced cost (threshold: %f)\n",
524 length, dj_threshold);
525 }
526
527 /* generate a random permutation of the indices */
528 for (i = 0; i < length - 1; i++) {
529 k = RANDOM() % (length - i);
530 ind = indices[i];
531 indices[i] = indices[i + k];
532 indices[i + k] = ind;
533 }
534
535 /* shuffle those vars that extend the clique to the beginning of
536 indices */
537 length = extend_clique_greedily(spp->cmatrix, cl_length, cl_indices,
538 length, indices);
539
540 /* if no variables extend the clique: return */
541 if (length == 0) {
542 printf("... no vars can extend the clique\n");
543 return(FALSE);
544 }
545
546 /* fill out new_cut */
547 memcpy(indices + length, cl_indices, cl_length * ISIZE);
548 length += cl_length;
549 qsort_i(indices, length);
550
551 new_cut->type = CLIQUE_LIFTED;
552 new_cut->size = length * ISIZE;
553 memcpy(new_cut->coef, indices, length * ISIZE);
554 new_cut->rhs = 1;
555 new_cut->range = 0;
556 new_cut->sense = 'L';
557 new_cut->branch = TRUE; /* ? */
558 new_cut->name = CUT__SEND_TO_CP; /* the cut is globally valid */
559
560 printf("... the lifted clique is:\n");
561 display_cut_in_lp(spp, new_cut, -1);
562
563 return(TRUE);
564 }
565