Debian Codegraph @

SYMPHONY/Applications/SPP+CUTS/src/CutGen/spp_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 /* 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 <memory.h>
19 #include <math.h>
20 #include <string.h>
21 #include <stdlib.h>
22
23 /* SYMPHONY include files */
24 #include "sym_proccomm.h"
25 #include "sym_constants.h"
26 #include "sym_macros.h"
27 #include "sym_qsort.h"
28 #include "sym_cg_u.h"
29
30 /* SPP include files */
31 #include "spp_cg.h"
32 #include "spp_cg_clique.h"
33 #include "spp_cg_functions.h"
34 #include "spp_common.h"
35
36 /*===========================================================================*/
37
38 /*===========================================================================*\
39 * This file contains user-written functions used by the cut generator
40 * process.
41 \*===========================================================================*/
42
43 /*===========================================================================*\
44 * Here is where the user must receive all of the data sent from
45 * user_send_cg_data() and set up data structures. Note that this function is
46 * only called if one of COMPILE_IN_CG, COMPILE_IN_LP, or COMPILE_IN_TM is
47 * FALSE. For sequential computation, nothing is needed here.
48 \*===========================================================================*/
49
50 int user_receive_cg_data(void **user, int dg_id)
51 {
52 spp_cg_problem *spp;
53 col_ordered *m;
54 int colnum, rownum, info;
55
56 spp = (spp_cg_problem *) calloc(1, sizeof(spp_cg_problem));
57 *user = spp;
58
59 spp->par = (spp_cg_params *) calloc(1, sizeof(spp_cg_params));
60 receive_char_array((char *)spp->par, sizeof(spp_cg_params));
61 m = spp->cmatrix = (col_ordered *) calloc(1, sizeof(col_ordered));
62 receive_int_array(&m->colnum, 1);
63 colnum = m->active_colnum = m->colnum;
64 receive_int_array(&m->rownum, 1);
65 rownum = m->rownum;
66 receive_int_array(&m->nzcnt, 1);
67 m->colnames = (int *) malloc(colnum * ISIZE);
68 m->col_deleted = (char *) calloc(colnum/BITSPERBYTE + 1, CSIZE); /*calloc!*/
69 m->obj = (double *) malloc(colnum * DSIZE);
70 m->matbeg = (int *) malloc((colnum + 1) * ISIZE);
71 m->matind = (row_ind_type *) malloc(m->nzcnt * sizeof(row_ind_type));
72 receive_int_array(m->colnames, colnum);
73 receive_dbl_array(m->obj, colnum);
74 receive_int_array(m->matbeg, (colnum + 1));
75 receive_char_array((char *)m->matind, m->nzcnt * sizeof(row_ind_type));
76
77 spp->max_sol_length = rownum;
78
79 /* allocate space for tmp arrays */
80 spp->tmp = (spp_cg_tmp *) calloc(1, sizeof(spp_cg_tmp));
81 spp->tmp->itmp_m = (int *) malloc(rownum * ISIZE);
82 spp->tmp->istartmp_m = (int **) malloc(rownum * sizeof(int *));
83 spp->tmp->cuttmp = (cut_data *) calloc(1, sizeof(cut_data));
84
85 /* initialize cg data structures */
86 spp->fgraph = (frac_graph *) calloc(1, sizeof(frac_graph));
87 spp->cfgraph = (frac_graph *) calloc(1, sizeof(frac_graph));
88 spp->cm_frac = (col_ordered *) calloc(1, sizeof(col_ordered));
89 spp->rm_frac = (row_ordered *) calloc(1, sizeof(row_ordered));
90 spp->rm_frac->rmatbeg = (int *) malloc((rownum+1) * ISIZE);
91 spp->lgraph = (level_graph *) calloc(1, sizeof(level_graph));
92
93 allocate_var_length_structures(spp, spp->max_sol_length);
94
95 /* cut collection is a local cut pool that contains the cuts that have
96 been sent back to the lp */
97 spp->cut_coll = (cut_collection *) calloc(1, sizeof(cut_collection));
98 spp->cut_coll->max_size = 1000;
99 spp->cut_coll->cuts = (cut_data **) calloc(spp->cut_coll->max_size,
100 sizeof(cut_data *));
101 spp->cut_coll->violation = (double *)
102 malloc(spp->cut_coll->max_size * DSIZE);
103 spp->cut_coll->mult = (int *)
104 malloc(spp->cut_coll->max_size * ISIZE);
105
106 return(USER_SUCCESS);
107 }
108
109 /*===========================================================================*/
110
111 /*===========================================================================*\
112 * If the user wants to fill in a customized routine for sending and receiving
113 * the LP solution, it can be done here. For most cases, the default routines
114 * are fine.
115 \*===========================================================================*/
116
117 int user_receive_lp_solution_cg(void *user)
118 {
119 return(USER_DEFAULT);
120 }
121
122 /*===========================================================================*/
123
124 /*===========================================================================*\
125 * Find cuts violated by a particular LP solution. This can be a fairly
126 * involved function but the bottom line is that an LP solution comes in
127 * and cuts go out. Remember, use the function cg_send_cut() to send cuts out
128 * when they are found.
129 \*===========================================================================*/
130
131 int user_find_cuts(void *user, int varnum, int iter_num, int level,
132 int index, double objval, int *indices, double *values,
133 double ub, double etol, int *cutnum, int *alloc_cuts,
134 cut_data ***cuts)
135 {
136 spp_cg_problem *spp = (spp_cg_problem *)user;
137 int numcuts = 0;
138 int i;
139
140 spp->num_cuts = cutnum;
141 spp->alloc_cuts= alloc_cuts;
142 spp->cuts = cuts;
143
144 /* reallocate space if needed */
145 if (varnum > spp->max_sol_length) {
146 spp->max_sol_length = varnum;
147 free_var_length_structures(spp);
148 allocate_var_length_structures(spp, spp->max_sol_length);
149 }
150
151 /* construct the fractional graph, etc. */
152 construct_fractional_graph(spp, varnum, indices, values);
153 construct_cm_frac(spp);
154 construct_rm_frac(spp);
155 construct_complement_graph(spp->fgraph, spp->cfgraph);
156
157 /* generate cuts */
158 numcuts += find_violated_star_cliques(spp, etol);
159 /* numcuts += find_violated_row_cliques(spp); */
160 numcuts += find_violated_odd_antiholes(spp, etol);
161 numcuts += find_violated_odd_holes(spp, etol);
162
163 *cutnum = numcuts;
164
165 /* print stat about cut_coll */
166 if (spp->cut_coll) {
167 printf("CG: Number of cuts in cut_coll: %i\n", spp->cut_coll->size);
168 printf(" Type and multiplicity of cuts: ");
169 for (i = 0; i < spp->cut_coll->size; i++) {
170 printf("[%i, %i] ", spp->cut_coll->cuts[i]->type,
171 spp->cut_coll->mult[i]);
172 }
173 printf("\n\n");
174 }
175
176 /* clean up cut_coll */
177 if (spp->cut_coll) {
178 for (i = 0; i < spp->cut_coll->size; i++) {
179 FREE(spp->cut_coll->cuts[i]->coef);
180 FREE(spp->cut_coll->cuts[i]);
181 }
182 spp->cut_coll->size = 0;
183 }
184
185 return(USER_SUCCESS);
186 }
187
188 /*===========================================================================*/
189
190 /*===========================================================================*\
191 * Free the user data structure. If the default setup is used with sequential
192 * computation, nothing needs to be filled in here.
193 \*===========================================================================*/
194
195 int user_free_cg(void **user)
196 {
197 spp_cg_problem *spp = (spp_cg_problem *)(*user);
198 int i;
199
200 free_var_length_structures(spp);
201 if (spp->tmp) {
202 FREE(spp->tmp->cuttmp);
203 FREE(spp->tmp->itmp_m);
204 FREE(spp->tmp->istartmp_m);
205 FREE(spp->tmp);
206 }
207 #if !defined(COMPILE_IN_LP) || !defined(COMPILE_IN_CG)
208 FREE(spp->par);
209 spp_free_cmatrix(spp->cmatrix);
210 FREE(spp->cmatrix);
211 #endif
212 FREE(spp->cm_frac);
213 FREE(spp->rm_frac->rmatbeg);
214 FREE(spp->rm_frac);
215 FREE(spp->fgraph);
216 FREE(spp->cfgraph);
217 FREE(spp->lgraph);
218 if (spp->cut_coll) {
219 for (i = 0; i < spp->cut_coll->size; i++) {
220 FREE(spp->cut_coll->cuts[i]->coef);
221 FREE(spp->cut_coll->cuts[i]);
222 }
223 FREE(spp->cut_coll->cuts);
224 FREE(spp->cut_coll->violation);
225 FREE(spp->cut_coll->mult);
226 FREE(spp->cut_coll);
227 }
228 FREE(*user);
229
230 return(USER_SUCCESS);
231 }
232
233 /*===========================================================================*/
234
235 /*===========================================================================*\
236 * This is an undocumented (for now) debugging feature which can allow the user
237 * to identify the cut which cuts off a particular known feasible solution.
238 \*===========================================================================*/
239
240 #ifdef CHECK_CUT_VALIDITY
241 int user_check_validity_of_cut(void *user, cut_data *new_cut)
242 {
243 return(USER_DEFAULT);
244 }
245 #endif
246
247 /*===========================================================================*/
248
249 void allocate_var_length_structures(spp_cg_problem *spp, int max_ln)
250 {
251 int max_nzcnt = max_ln * max_ln;
252 int rownum = spp->cmatrix->rownum;
253
254 /* tmp arrays */
255 spp->tmp->itmp_8nodenum = (int *) malloc(8 * max_ln * ISIZE);
256 spp->tmp->dtmp_2nodenum = (double *) malloc(2 * max_ln * DSIZE);
257 spp->tmp->ctmp_2nodenum = (char *) malloc(2 * max_ln * CSIZE);
258 spp->tmp->cuttmp->coef = (char *) malloc(max_ln*(ISIZE + DSIZE)+ 2*ISIZE);
259
260 /* cm_frac and rm_frac */
261 spp->cm_frac->matbeg = (int *) malloc((max_ln+1) * ISIZE);
262 spp->cm_frac->matind = (row_ind_type *)
263 malloc(max_ln * rownum * sizeof(row_ind_type));
264 spp->rm_frac->rmatind = (int *) malloc(max_ln * rownum * ISIZE);
265
266 /* fgraph */
267 spp->fgraph->nodes = (fnode *) malloc(max_ln * sizeof(fnode));
268 spp->fgraph->all_nbr = (int *) malloc(max_nzcnt * ISIZE);
269 spp->fgraph->all_edgecost = (double *) malloc(max_nzcnt * DSIZE);
270 spp->fgraph->node_node = (char *) malloc(max_nzcnt * CSIZE);
271
272 /* cfgraph */
273 spp->cfgraph->nodes = (fnode *) malloc(max_ln * sizeof(fnode));
274 spp->cfgraph->all_nbr = (int *) malloc(max_nzcnt * ISIZE);
275 spp->cfgraph->all_edgecost = (double *) malloc(max_nzcnt * DSIZE);
276 spp->cfgraph->node_node = (char *) malloc(max_nzcnt * CSIZE);
277
278 /* lgraph */
279 spp->lgraph->lnodes = (int *) malloc(max_ln * ISIZE);
280 spp->lgraph->lbeg = (int *) malloc((max_ln + 1) * ISIZE);
281 spp->lgraph->level_of_node = (int *) malloc(max_ln * ISIZE);
282 }
283
284 /*===========================================================================*/
285
286 void free_var_length_structures(spp_cg_problem *spp)
287 {
288 /* tmp */
289 FREE(spp->tmp->itmp_8nodenum);
290 FREE(spp->tmp->dtmp_2nodenum);
291 FREE(spp->tmp->ctmp_2nodenum);
292 FREE(spp->tmp->cuttmp->coef);
293
294 /* cm_frac and rm_frac */
295 FREE(spp->cm_frac->matbeg);
296 FREE(spp->cm_frac->matind);
297 FREE(spp->rm_frac->rmatind);
298
299 /* fgraph */
300 FREE(spp->fgraph->nodes);
301 FREE(spp->fgraph->all_nbr);
302 FREE(spp->fgraph->all_edgecost);
303 FREE(spp->fgraph->node_node);
304
305 /* cfgraph */
306 FREE(spp->cfgraph->nodes);
307 FREE(spp->cfgraph->all_nbr);
308 FREE(spp->cfgraph->all_edgecost);
309 FREE(spp->cfgraph->node_node);
310
311 /* lgraph */
312 FREE(spp->lgraph->lnodes);
313 FREE(spp->lgraph->lbeg);
314 FREE(spp->lgraph->level_of_node);
315 }
316
317 /*===========================================================================*/
318
319 /*===========================================================================*
320 * Construct the fractional graph. 'number', 'indices' and 'values' describe
321 * the variables at fractional level in the solution.
322 *===========================================================================*/
323
324 void construct_fractional_graph(spp_cg_problem *spp, int number,
325 int *indices, double *values)
326 {
327 frac_graph *fgraph = spp->fgraph;
328 int *all_nbr = spp->fgraph->all_nbr;
329 double *all_edgecost = spp->fgraph->all_edgecost;
330 fnode *nodes = fgraph->nodes;
331 int min_degree, max_degree, min_deg_node, max_deg_node;
332
333 int i, j, total_deg, old_total;
334
335 fgraph->nodenum = number;
336
337 /*========================================================================*
338 Construct the adjacency lists (neighbors) of the nodes in fgraph.
339 Two nodes are adjacent iff the columns corresponding to them are
340 non-orthogonal.
341 *========================================================================*/
342
343 for ( i = 0, total_deg = 0; i < number; i++ ) {
344 old_total = total_deg;
345 for ( j = 0; j < number; j++ ) {
346 if ( j != i &&
347 !spp_is_orthogonal(spp->cmatrix, indices[i], indices[j])) {
348 all_nbr[total_deg] = j;
349 all_edgecost[total_deg++] = 1 - values[i] - values[j];
350 }
351 }
352 nodes[i].ind = indices[i];
353 nodes[i].val = values[i];
354 nodes[i].degree = total_deg - old_total;
355 nodes[i].nbrs = all_nbr + old_total;
356 nodes[i].edgecosts = all_edgecost + old_total;
357 }
358
359 fgraph->edgenum = total_deg / 2;
360 fgraph->density = 2 * (double)fgraph->edgenum / (number * (number-1));
361
362 /*========================================================================*
363 Compute the min and max degree.
364 *========================================================================*/
365 min_deg_node = 0; max_deg_node = 0;
366 min_degree = max_degree = nodes[0].degree;
367 for ( i = 0; i < number; i++ ) {
368 if ( nodes[i].degree < min_degree ) {
369 min_deg_node = i;
370 min_degree = nodes[i].degree;
371 }
372 if ( nodes[i].degree > max_degree ) {
373 max_deg_node = i;
374 max_degree = nodes[i].degree;
375 }
376 }
377 fgraph->min_degree = min_degree; fgraph->max_degree = max_degree;
378 fgraph->min_deg_node = min_deg_node;
379 fgraph->max_deg_node = max_deg_node;
380
381 /*========================================================================*
382 Now create the node-node incidence matrix of the graph.
383 *========================================================================*/
384 for ( i = number*number-1; i >=0 ; i-- )
385 fgraph->node_node[i] = FALSE;
386 for ( i = 0; i < number; i++ )
387 for ( j = 0; j < nodes[i].degree; j++ )
388 fgraph->node_node[i * number + nodes[i].nbrs[j]] = TRUE;
389
390 }
391
392 /*===========================================================================*/
393
394 /*===========================================================================*
395 * Construct the column ordered matrix corresponding to the fractional
396 * solution. Only colnum, rownum, nzcnt, matbeg and matind are filled out.
397 *
398 * Space must be already allocated to cm_frac, matbeg and matind.
399 *===========================================================================*/
400
401 void construct_cm_frac(spp_cg_problem *spp)
402 {
403 fnode *nodes = spp->fgraph->nodes;
404 int *matbeg = spp->cmatrix->matbeg;
405 row_ind_type *matind = spp->cmatrix->matind;
406 int *mb = spp->cm_frac->matbeg;
407 row_ind_type *mi = spp->cm_frac->matind;
408 int nodenum = spp->fgraph->nodenum;
409 int i, col, len;
410
411 for (i = 0, mb[0] = 0; i < nodenum; i++) {
412 col = nodes[i].ind;
413 len = matbeg[col+1] - matbeg[col];
414 memcpy(mi + mb[i], matind + matbeg[col], len * sizeof(row_ind_type));
415 mb[i+1] = mb[i] + len;
416 }
417
418 spp->cm_frac->colnum = nodenum;
419 spp->cm_frac->rownum = spp->cmatrix->rownum;
420 spp->cm_frac->nzcnt = mb[nodenum];
421 }
422
423 /*===========================================================================*/
424
425 /*===========================================================================*
426 * Construct row ordered version of cm_frac.
427 * Note: columns in this row ordered matrix are indexed by integers from
428 * 0 to fgraph->nodenum-1.
429 *
430 * Space must be already allocated for rm_frac, rmatbeg and rmatind.
431 *===========================================================================*/
432
433 void construct_rm_frac(spp_cg_problem *spp)
434 {
435 col_ordered *cm = spp->cm_frac;
436 row_ordered *rm = spp->rm_frac;
437
438 rm->colnum = cm->colnum;
439 rm->rownum = cm->rownum;
440 rm->nzcnt = cm->nzcnt;
441 spp_column_to_row(cm, rm, spp->tmp->itmp_m, spp->tmp->istartmp_m);
442 }
443
444 /*===========================================================================*/
445
446 /*===========================================================================*
447 * Construct the complement of the fractional graph.
448 *===========================================================================*/
449
450 void construct_complement_graph(frac_graph *fgraph, frac_graph *cfgraph)
451 {
452 fnode *nodes = fgraph->nodes;
453 fnode *cnodes = cfgraph->nodes;
454 char *node_node = cfgraph->node_node;
455 int nodenum, edgenum, nminusone, i, j, start, degree;
456 double dtmp;
457
458 nodenum = cfgraph->nodenum = fgraph->nodenum;
459 nminusone = nodenum - 1;
460 edgenum = cfgraph->edgenum = nodenum * nminusone / 2 - fgraph->edgenum;
461 cfgraph->density = 1 - fgraph->density;
462
463 /* node_node */
464 memcpy(node_node, fgraph->node_node, nodenum * nodenum);
465 for (i = nodenum*nodenum-1; i >= 0; i--)
466 node_node[i] = 1 - node_node[i];
467 for (i = nodenum-1; i >= 0; i--)
468 node_node[i*nodenum + i] = 0;
469 /* nodes */
470 for (i = nodenum-1; i >= 0; i--) {
471 cnodes[i].degree = nminusone - nodes[i].degree;
472 cnodes[i].ind = nodes[i].ind;
473 cnodes[i].val = nodes[i].val;
474 }
475 cnodes[0].nbrs = cfgraph->all_nbr;
476 cnodes[0].edgecosts = cfgraph->all_edgecost;
477 for (i = 1; i < nodenum; i++) {
478 cnodes[i].nbrs = cnodes[i-1].nbrs + cnodes[i-1].degree;
479 cnodes[i].edgecosts = cnodes[i-1].edgecosts + cnodes[i-1].degree;
480 }
481 for (i = 0; i < nodenum; i++) {
482 start = i * nodenum;
483 dtmp = 1 - cnodes[i].val;
484 for (j = 0, degree = 0; j < nodenum; j++) {
485 if (node_node[start + j]) {
486 cnodes[i].nbrs[degree] = j;
487 cnodes[i].edgecosts[degree++] = dtmp - cnodes[j].val;
488 }
489 }
490 }
491 /* min, max degree nodes */
492 cfgraph->min_deg_node = fgraph->max_deg_node;
493 cfgraph->min_degree = cnodes[cfgraph->min_deg_node].degree;
494 cfgraph->max_deg_node = fgraph->min_deg_node;
495 cfgraph->max_degree = cnodes[cfgraph->max_deg_node].degree;
496 }
497
498 /*===========================================================================*/
499
500 /*********** root is an index wrt fgraph ********/
501
502 void construct_level_graph(frac_graph *fgraph, int root, level_graph *lgraph)
503 {
504 int *lnodes = lgraph->lnodes;
505 int *lbeg = lgraph->lbeg;
506 int *level_of_node = lgraph->level_of_node;
507 int nodenum = fgraph->nodenum;
508 fnode *nodes = fgraph->nodes;
509
510 int next_pos = 1; /* pos in lnodes where the next node can be written */
511 int curr_pos = 0; /* pos of currently examined node in lnodes */
512 int curr_lev = 0; /* current level */
513 int u; /* current node */
514 int w; /* neighbor of u */
515
516 int i, j, deg;
517
518 /* nothing is in the level graph initially */
519 for (i = 0; i < nodenum; i++) level_of_node[i] = -1;
520
521 /* first node: root */
522 lgraph->root = root;
523 lnodes[0] = root;
524 level_of_node[root] = 0;
525 lbeg[0] = 0;
526
527 while (curr_pos < next_pos) {
528 u = lnodes[curr_pos++];
529 deg = nodes[u].degree;
530 for (j = 0; j < deg; j++) {
531 w = nodes[u].nbrs[j];
532 if (level_of_node[w] < 0) {
533 lnodes[next_pos++] = w;
534 level_of_node[w] = curr_lev + 1;
535 }
536 }
537 if (curr_pos < next_pos &&
538 level_of_node[u] < level_of_node[lnodes[curr_pos]])
539 lbeg[++curr_lev] = curr_pos;
540 }
541 lbeg[++curr_lev] = curr_pos;
542
543 lgraph->lnodenum = curr_pos;
544 lgraph->levelnum = curr_lev;
545 }
546
547 /*===========================================================================*/
548
549 /*===========================================================================*
550 * Compare 'new_cut' that has just been generated to all cuts in the
551 * cut collection. If the new cut is not in the collection, and it is
552 * violated enough, register it and send it back to the LP. If the cut is
553 * in the collection and is stronger than the one in the colection, send
554 * it back to the lp. Otherwise don't register or send it.
555 * Violation is by how much the new cut violates the current solution.
556 *
557 * Note: DO NOT FREE new_cut!! Will be done from parent function if needed.
558 *
559 * Returns 1 if cut has been sent to lp, 0 if not.
560 *===========================================================================*/
561
562 int register_and_send_cut(spp_cg_problem *spp, cut_data *new_cut,
563 double violation, double etol)
564 {
565 cut_collection *cut_coll = spp->cut_coll;
566 cut_data **cuts = cut_coll->cuts;
567 int nodenum = spp->fgraph->nodenum;
568 int *colnames = spp->cmatrix->colnames;
569
570 int i, j, pos, coef_num, oh_len, hub_len;
571 int *indices = spp->tmp->itmp_8nodenum + 7 * nodenum;
572 double *coefs = spp->tmp->dtmp_2nodenum;
573 char *coef;
574
575 /* check if cut is violated enough. if not, return */
576 switch (new_cut->type) {
577
578 case CLIQUE:
579 /* try to extend the clique on fgraph, in case it was not maximal.
580 'violation' will increase if cut was not maximal...
581 extend_clique_on_fgraph(spp, new_cut, &violation); */
582
583 if (violation < spp->par->min_violation_clique)
584 return 0;
585 break;
586
587 case ODD_HOLE:
588 case ODD_HOLE_LIFTED:
589 if (violation < spp->par->min_violation_oddhole)
590 return 0;
591 break;
592
593 case ODD_ANTIHOLE:
594 case ODD_ANTIHOLE_LIFTED:
595 if (violation < spp->par->min_violation_oddantihole)
596 return 0;
597 break;
598
599 case WHEEL:
600 if (violation < spp->par->min_violation_wheel)
601 return 0;
602 break;
603
604 case ORTHOCUT:
605 if (violation < spp->par->min_violation_orthocut)
606 return 0;
607 break;
608
609 case OTHER_CUT:
610 if (violation < spp->par->min_violation_othercut)
611 return 0;
612 break;
613
614 default:
615 printf("\nUnrecognized cut type! (register_and_send_cut)\n");
616 return 0;
617 break;
618 }
619
620 /* if the cut does not need to be added: return */
621 switch (new_cut->type) {
622
623 case CLIQUE:
624 case ODD_HOLE:
625 case ODD_HOLE_LIFTED:
626 case ODD_ANTIHOLE:
627 case ODD_ANTIHOLE_LIFTED:
628 case ORTHOCUT:
629 for (i = cut_coll->size - 1; i >= 0; i--) {
630 if (cuts[i]->type == new_cut->type &&
631 cuts[i]->size == new_cut->size &&
632 !memcmp(cuts[i]->coef, new_cut->coef, new_cut->size))
633 break;
634 }
635 break;
636
637 case WHEEL:
638 for (i = cut_coll->size - 1; i >= 0; i--) {
639 if (cuts[i]->type == WHEEL &&
640 cuts[i]->size == new_cut->size &&
641 cuts[i]->rhs <= new_cut->rhs + etol &&
642 !memcmp(cuts[i]->coef, new_cut->coef, new_cut->size))
643 break;
644 }
645 break;
646
647 case OTHER_CUT:
648 for (i = cut_coll->size - 1; i >= 0; i--) {
649 if (cuts[i]->type == OTHER_CUT &&
650 cuts[i]->size == new_cut->size &&
651 cuts[i]->sense == new_cut->sense &&
652 !memcmp(cuts[i]->coef, new_cut->coef, new_cut->size))
653 if ((cuts[i]->sense == 'L' && cuts[i]->rhs <= new_cut->rhs+etol) ||
654 (cuts[i]->sense == 'G' && cuts[i]->rhs >= new_cut->rhs-etol) ||
655 (cuts[i]->sense == 'E' && cuts[i]->rhs <= new_cut->rhs+etol &&
656 cuts[i]->rhs >= new_cut->rhs-etol) ||
657 (cuts[i]->sense == 'R' && cuts[i]->rhs >= new_cut->rhs-etol &&
658 cuts[i]->rhs+cuts[i]->range<=new_cut->rhs+new_cut->range+etol)
659 )
660 break;
661 }
662 break;
663 }
664
665 /* if cut (or a stronger cut) has been found: return */
666 if ( i >= 0 ) {
667 cut_coll->mult[i]++;
668 return 0;
669 }
670
671 /* We get here only if the cut is new... */
672
673 /* store the cut in the collection. allocate more space if needed */
674 if (cut_coll->size == cut_coll->max_size) {
675 cut_coll->max_size += 500;
676 cuts = spp->cut_coll->cuts = (cut_data **)
677 realloc((char *)cuts, cut_coll->max_size * sizeof(cut_data *));
678 spp->cut_coll->violation = (double *)
679 realloc((char *)cut_coll->violation, cut_coll->max_size * DSIZE);
680 spp->cut_coll->mult = (int *)
681 realloc((char *)cut_coll->mult, cut_coll->max_size * ISIZE);
682 }
683 pos = cut_coll->size;
684 cut_coll->size++;
685 /* allocate space for the cut in the collection */
686 cuts[pos] = (cut_data *) malloc(sizeof(cut_data));
687 *cuts[pos] = *new_cut;
688 cuts[pos]->coef = (char *) malloc(new_cut->size);
689 memcpy(cuts[pos]->coef, new_cut->coef, new_cut->size);
690 cut_coll->violation[pos] = violation;
691 cut_coll->mult[pos] = 0;
692
693 /* now we send the cut indexed by 'pos' to the lp */
694 cg_add_user_cut(cuts[pos], spp->num_cuts, spp->alloc_cuts, spp->cuts);
695
696 /* for debugging purposes: print out info which cut was sent to the lp */
697 switch (cuts[pos]->type) {
698
699 case CLIQUE:
700 case ODD_HOLE:
701 case ODD_ANTIHOLE:
702 coef_num = cuts[pos]->size/ISIZE;
703 memcpy(indices, cuts[pos]->coef, coef_num * ISIZE);
704 if (cuts[pos]->type == CLIQUE) {
705 printf("\nViolated CLIQUE inequality found\n");
706 } else if (cuts[pos]->type == ODD_HOLE) {
707 printf("\nViolated ODD HOLE inequality found\n");
708 } else {
709 printf("\nViolated ODD ANTIHOLE inequality found\n");
710 }
711 printf(" Indices (names): ");
712 for ( j = 0; j < coef_num; j++ )
713 /* printf("%i ", indices[j]); */
714 printf("%i (%i) ", indices[j], colnames[indices[j]]);
715 printf("\n");
716 printf(" type: %i, num: %i, rhs: %f, violation: %f\n",
717 cuts[pos]->type, coef_num, cuts[pos]->rhs, violation);
718 break;
719
720 case ODD_HOLE_LIFTED:
721 case ODD_ANTIHOLE_LIFTED:
722 coef = cuts[pos]->coef;
723 memcpy(&oh_len, coef, ISIZE);
724 memcpy(&hub_len, coef + ISIZE, ISIZE);
725 coef_num = oh_len + hub_len;
726 memcpy(indices, coef + 2 * ISIZE, coef_num * ISIZE);
727 memcpy(coefs, coef + (2+coef_num) * ISIZE, hub_len * DSIZE);
728 if (cuts[pos]->type == ODD_HOLE_LIFTED)
729 printf("\nViolated LIFTED ODD HOLE inequality found\n");
730 else
731 printf("\nViolated LIFTED ODD ANTIHOLE inequality found\n");
732 printf(" Indices (names) of nodes in odd hole: ");
733 for (j = 0; j < oh_len; j++)
734 printf("%i (%i) ", indices[j], colnames[indices[j]]);
735 printf("\n");
736 printf(" Indices (names) [coefs] of hubs: ");
737 for (j = 0; j < hub_len; j++)
738 printf("%i (%i) [%f] ", indices[oh_len+j],
739 colnames[indices[oh_len+j]], coefs[j]);
740 printf("\n");
741 if (cuts[pos]->type == ODD_HOLE_LIFTED)
742 printf(" type: %i, oh_num: %i, hub_num: %i, rhs: %f, violation: %f\n",
743 cuts[pos]->type, oh_len, hub_len, cuts[pos]->rhs, violation);
744 else
745 printf(" type: %i, oah_num: %i, hub_num: %i, rhs: %f, violation: %f\n",
746 cuts[pos]->type, oh_len, hub_len, cuts[pos]->rhs, violation);
747 /* we don't print this cut into the message window right now FIXME */
748 break;
749
750 case ORTHOCUT:
751 /* FIXME! */
752 break;
753
754 case WHEEL:
755 case OTHER_CUT:
756 coef_num = cuts[pos]->size/(ISIZE + DSIZE);
757 memcpy(indices, cuts[pos]->coef, coef_num * ISIZE);
758 memcpy(coefs, cuts[pos]->coef + coef_num * ISIZE, coef_num * DSIZE);
759 if (cuts[pos]->type == WHEEL) {
760 printf("\nViolated WHEEL inequality found\n");
761 } else {
762 printf("\nViolated OTHER CUT found\n");
763 }
764 printf(" Indices (names) [coefs]: ");
765 for ( j = 0; j < coef_num; j++ )
766 printf("%i (%i) [%f] ", indices[j], colnames[indices[j]], coefs[j]);
767 printf("\n");
768 printf(" type: %i, num: %i, rhs: %f, violation: %f\n",
769 cuts[pos]->type, coef_num, cuts[pos]->rhs, violation);
770 break;
771 }
772
773 return 1;
774 }
775
776 /*===========================================================================*/
777
778 /*===========================================================================*
779 * Try to extend a clique on fgraph (greedily).
780 *===========================================================================*/
781
782 void extend_clique_on_fgraph(spp_cg_problem *spp, cut_data *new_cut,
783 double *pviolation)
784 {
785 int old_coef_num, coef_num, i, j, k;
786 double lhs = 1 + *pviolation;
787 fnode *nodes = spp->fgraph->nodes;
788 int nodenum = spp->fgraph->nodenum;
789 int *indices = spp->tmp->itmp_8nodenum + 7 * nodenum;
790 /* same tmp array is used in parent fn, but only after this fn returns */
791 int userind;
792
793
794 old_coef_num = coef_num = new_cut->size/ISIZE;
795 memcpy(indices, new_cut->coef, coef_num * ISIZE);
796
797 /* i runs thru nodes in fgraph, j runs thru nodes in the clique.
798 note that the clique is a subgraph of fgraph */
799 for ( i = j = 0; i < nodenum && j < old_coef_num; i++ ) {
800 userind = nodes[i].ind;
801 if ( userind < indices[j] ) {
802 /* check if the node can be added to the clique */
803 for ( k = 0; k < coef_num; k++ )
804 if (spp_is_orthogonal(spp->cmatrix, userind, indices[k]))
805 break;
806 if ( k == coef_num ) {
807 /* node can be added ... */
808 indices[coef_num++] = userind;
809 lhs += nodes[i].val;
810 }
811 } else {
812 /* node is in the clique */
813 j++;
814 }
815 }
816 for ( ; i < nodenum; i++ ) {
817 userind = nodes[i].ind;
818 /* check if the node can be added to the clique */
819 for ( k = 0; k < coef_num; k++ )
820 if (spp_is_orthogonal(spp->cmatrix, userind, indices[k]))
821 break;
822 if ( k == coef_num ) {
823 /* node can be added ... */
824 indices[coef_num++] = userind;
825 lhs += nodes[i].val;
826 }
827 }
828
829 /* if some nodes were added to the clique ... */
830 if (old_coef_num < coef_num) {
831 new_cut->size = coef_num * ISIZE;
832 qsort_i(indices, coef_num);
833 memcpy(new_cut->coef, indices, new_cut->size);
834 *pviolation = lhs - 1;
835 }
836 }
837
838 /*****************************************************************************/
839 /*****************************************************************************/
840 /* UTILITY */
841 /*****************************************************************************/
842 /*****************************************************************************/
843
844 /*===========================================================================*
845 * Cuts coming from the graph drawing application are given in terms of
846 * variable names, not indices. This function changes the names into indices.
847 *===========================================================================*/
848
849 void translate_cut_to_indices(spp_cg_problem *spp, cut_data *cut)
850 {
851 int *colnames = spp->cmatrix->colnames;
852 int colnum = spp->cmatrix->colnum;
853 int nodenum = spp->fgraph->nodenum;
854 int i, j, name, coef_num;
855 int *names = spp->tmp->itmp_8nodenum;
856 int *itmp = spp->tmp->itmp_8nodenum + nodenum;
857
858 switch (cut->type) {
859 case CLIQUE:
860 case ODD_HOLE:
861 case ODD_ANTIHOLE:
862 coef_num = cut->size/ISIZE;
863 break;
864
865 case ORTHOCUT:
866 case OTHER_CUT:
867 coef_num = cut->size/(ISIZE + DSIZE);
868 break;
869 }
870
871 memcpy(names, cut->coef, coef_num * ISIZE);
872 for (i = 0; i < coef_num; i++) {
873 name = names[i];
874 for (j = colnum-1; j >=0; j--)
875 if (colnames[j] == name)
876 break;
877 if (j >= 0)
878 names[i] = j;
879 else
880 printf("ERROR: Variable with name %i is not found\n", name);
881 }
882
883 switch (cut->type) {
884 case CLIQUE:
885 case ORTHOCUT:
886 case OTHER_CUT:
887 qsort_i(names, coef_num);
888 break;
889
890 case ODD_HOLE:
891 case ODD_ANTIHOLE:
892 /* find smallest indexed node and rotate cycle to have that first */
893 rotate_odd_hole(coef_num, names, itmp);
894 break;
895 }
896
897 memcpy(cut->coef, names, coef_num * ISIZE);
898 }
899
900 /*===========================================================================*/
901
902 /*===========================================================================*
903 * Rotate indices of odd hole so that entry with smallest index is first and
904 * smaller indexed neighbor of first node is the second.
905 *===========================================================================*/
906
907 void rotate_odd_hole(int length, int *indices, int *itmp)
908 {
909 int i, minind, minval, tmp;
910
911 for (i = 1, minval = indices[0], minind = 0; i < length; i++)
912 if (indices[i] < minval) {
913 minval = indices[i];
914 minind = i;
915 }
916 if (indices[(minind-1+length)%length] < indices[(minind+1)%length]) {
917 /* reverse cycle */
918 for (i = (int)(floor((double)length/2)) - 1; i >= 0; i--) {
919 tmp = indices[i];
920 indices[i] = indices[length - 1 - i];
921 indices[length - 1 - i] = tmp;
922 }
923 minind = length - 1 - minind;
924 }
925 if (minind > 0) {
926 memcpy(itmp, indices, minind * ISIZE);
927 memmove(indices, indices + minind, (length - minind) * ISIZE);
928 memcpy(indices + (length - minind), itmp, minind * ISIZE);
929 }
930 }
931