Debian Codegraph @

SYMPHONY/Applications/SPP/src/Master/spp_master_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 <string.h>
21
22 /* SYMPHONY include files */
23 #include "sym_timemeas.h"
24 #include "sym_macros.h"
25 #include "sym_constants.h"
26
27 /* SPP include files */
28 #include "spp.h"
29 #include "spp_common.h"
30 #include "spp_macros.h"
31 #include "spp_master_functions.h"
32
33 /*****************************************************************************/
34
35 void spp_read_params(spp_problem *spp, char *filename)
36 {
37 char line[MAX_LINE_LENGTH], key[50], value[50];
38 FILE *f;
39
40 /* defaults for the parameters in spp_master */
41 spp->par->dupc_at_loadtime = FALSE;
42 spp->par->our_format_file_counter = -1;
43 spp->par->matlab_format_file_counter = -1;
44 spp->par->granularity = 0;
45
46 if (!strcmp(filename, ""))
47 return;
48
49 if ((f = fopen(filename, "r")) == NULL){
50 printf("SYMPHONY: file %s can't be opened\n", filename);
51 exit(1); /*error check for existence of parameter file*/
52 }
53
54 /* read in parameters from file */
55 while ( fgets(line, MAX_LINE_LENGTH, f) != NULL ) {
56 strcpy(key,"");
57 sscanf(line, "%s%s", key, value);
58
59 /* spp_master */
60
61 if ( !strcmp(key, "input_file") || !strcmp(key, "infile") ) {
62 READ_STR_PAR(spp->par->infile);
63
64 } else if ( !strcmp(key, "dupc_at_loadtime") ) {
65 READ_INT_PAR(spp->par->dupc_at_loadtime);
66
67 } else if ( !strcmp(key, "our_format_file") ) {
68 READ_STR_PAR(spp->par->our_format_file);
69
70 } else if ( !strcmp(key, "our_format_file_counter") ) {
71 READ_INT_PAR(spp->par->our_format_file_counter);
72
73 } else if ( !strcmp(key, "matlab_format_file") ) {
74 READ_STR_PAR(spp->par->matlab_format_file);
75
76 } else if ( !strcmp(key, "matlab_format_file_counter") ) {
77 READ_INT_PAR(spp->par->matlab_format_file_counter);
78
79 } else if ( !strcmp(key, "granularity") ) {
80 READ_DBL_PAR(spp->par->granularity);
81
82 }
83 }
84
85 fclose(f);
86 }
87
88 /*****************************************************************************/
89
90 void spp_print_params(spp_problem *spp)
91 {
92 spp_parameters *par = spp->par;
93
94 printf("###########################################################\n");
95 printf("Parameter settings:\n");
96 printf(" infile: %s\n", par->infile);
97 printf(" dupc_at_loadtime: %i\n", par->dupc_at_loadtime);
98 printf(" our_format_file: %s\n", par->our_format_file);
99 printf(" our_format_file_counter: %i\n",par->our_format_file_counter);
100 printf(" matlab_format_file: %s\n", par->matlab_format_file);
101 printf(" matlab_format_file_counter: %i\n",
102 par->matlab_format_file_counter);
103 printf(" granularity: %f\n", par->granularity);
104 printf("\n\n");
105 }
106 /*****************************************************************************/
107
108 /*===========================================================================*
109 * The following routine reads in the data from the input file. The input *
110 * file has to be in the following format: *
111 * First row of the input file: *
112 * <t> <m> <n> <nzcnt> *
113 * where <t>: type of input file. (currently: OUR_FORMAT only) *
114 * <m>: # of rows in the matrix of the problem. *
115 * Rows are assumed to be numbered from 1 to m. *
116 * <n>: # of columns in the matrix of the problem. *
117 * <nzcnt>: # of nonzeros (=ones) in the matrix. *
118 * *
119 * A general row of the input file describing a COLUMN of the matrix: *
120 * <col_name_j> <c_j> <nzcnt_j> <pos_1> ... <pos_nzcnt_j> *
121 * where <col_name_j>: the name of the column (integer). *
122 * <c_j>: objective function coefficient. Integral in HP *
123 * problems, double in telebus problems. *
124 * <nzcnt_j>: number of nonzeros in this column. *
125 * <pos_1> ... : indices of rows where the nonzeros are. *
126 * Note that in the case of the set partitioning *
127 * problem, the matrix is 0-1. *
128 * *
129 * our0 format: same as above but rows are numbered from 0 to rownum-1.
130 *===========================================================================*/
131
132 void spp_read_input(spp_problem *spp)
133 {
134 FILE *f;
135 col_ordered *matrix;
136 int deleted_cols; /* number of columns deleted */
137 int colnum;
138 double T = 0;
139
140 used_time(&T);
141
142 if ((f = fopen(spp->par->infile, "r")) == NULL)
143 OPEN_READ_ERROR(spp->par->infile);
144 if(spp->par->verbosity > -1){
145 printf("########################################################\n");
146 printf("Reading input file %s...\n", spp->par->infile);
147 }
148 matrix = spp->cmatrix = (col_ordered *) calloc(1, sizeof(col_ordered));
149
150 /* read in the type of the problem, rownum, colnum and nzcnt */
151 if (fscanf(f, "%i", &spp->input_type) != 1) IO_ERROR;
152 if (fscanf(f, "%i%i%i", &matrix->rownum, &matrix->colnum,
153 &matrix->nzcnt) != 3) IO_ERROR;
154 colnum = matrix->colnum;
155 if(spp->par->verbosity > -1){
156 printf(" input type: %i, rownum: %i, colnum: %i, nzcnt: %i\n",
157 spp->input_type, matrix->rownum, colnum, matrix->nzcnt);
158 }
159 matrix->colnames = (int *) malloc(colnum * ISIZE);
160 matrix->obj = (double *) malloc(colnum * DSIZE);
161 matrix->matbeg = (int *) malloc((colnum+1) * ISIZE);
162 matrix->matind = (row_ind_type *)
163 malloc(matrix->nzcnt * sizeof(row_ind_type));
164
165 switch (spp->input_type){
166
167 case OUR_FORMAT:
168
169 if ( spp->par->dupc_at_loadtime ) {
170 if ( (deleted_cols = read_our_del_dupl(matrix, f)) >= 0 ) {
171 printf(" Deleted %i columns at loadtime,\n",deleted_cols);
172 printf(" rownum: %i, colnum: %i, nzcnt: %i\n",
173 matrix->rownum, matrix->colnum, matrix->nzcnt);
174 }
175 } else {
176 read_our_no_del(matrix, f);
177 }
178 break;
179
180 case OUR_FORMAT_0:
181
182 if ( spp->par->dupc_at_loadtime ) {
183 if ( (deleted_cols = read_our0_del_dupl(matrix, f)) >= 0 ) {
184 printf(" Deleted %i columns at loadtime,\n",deleted_cols);
185 printf(" rownum: %i, colnum: %i, nzcnt: %i\n",
186 matrix->rownum, matrix->colnum, matrix->nzcnt);
187 }
188 } else {
189 read_our0_no_del(matrix, f);
190 }
191 break;
192
193 default:
194 IO_ERROR;
195
196 } /* end switch */
197
198 matrix->col_deleted = (char *) calloc(matrix->colnum/BITSPERBYTE +1, CSIZE);
199
200 fclose(f);
201 printf("\n\n");
202
203 spp->stat[READ_INPUT].time += used_time(&T);
204 spp->stat[READ_INPUT].freq++;
205 }
206
207 /*===========================================================================*
208 * read our format, no deletion of duplicate columns at loadtime.
209 *===========================================================================*/
210
211 void read_our_no_del(col_ordered *matrix, FILE *f)
212 {
213 int colnum = matrix->colnum;
214 int rownum = matrix->rownum;
215 int *colnames = matrix->colnames;
216 double *obj = matrix->obj;
217 int *matbeg = matrix->matbeg;
218 row_ind_type *matind = matrix->matind;
219
220 int j; /* runs thru columns */
221 int i; /* runs thru rows intersecting a column */
222 int nz_count; /* count nonzeros */
223 int col_nzcnt; /* number of nonzeros in a column */
224 int value; /* a temporary variable */
225
226
227 for ( j = 0, nz_count = 0, matbeg[0] = 0; j < colnum; j++ ) {
228
229 /* read in the name of the column, obj fn coeff and
230 num of rows intersecting this column */
231 if (fscanf(f, "%i%lf%i", &colnames[j], &obj[j], &col_nzcnt) != 3)
232 IO_ERROR;
233
234 /* read in row indices */
235 for ( i = 0; i < col_nzcnt; i++){
236 if (fscanf(f, "%i", &value) != 1)
237 IO_ERROR;
238 if ( !value || (value > rownum))
239 IO_ERROR;
240 matind[nz_count++] = value-1;
241 }
242 matbeg[j+1] = matbeg[j] + col_nzcnt;
243 }
244 }
245
246 /*===========================================================================*
247 * read our format, delete duplicate columns (that are next to
248 * each other) at loadtime. returns the number of columns deleted, or
249 * -1 in case of failure.
250 *===========================================================================*/
251
252 int read_our_del_dupl(col_ordered *matrix, FILE *f)
253 {
254 int colnum = matrix->colnum;
255 int rownum = matrix->rownum;
256 int *colnames = matrix->colnames;
257 double *obj = matrix->obj;
258 int *matbeg = matrix->matbeg;
259 row_ind_type *matind = matrix->matind;
260
261 int j; /* runs thru columns */
262 int i; /* runs thru rows intersecting a column */
263 int col_count, nz_count; /* count columns and nonzeros */
264 int col_nzcnt; /* number of nonzeros in a column */
265 int value; /* a temporary variable */
266 int deleted_cols; /* number of columns deleted */
267
268
269 for ( j = 0, nz_count = 0, col_count = 0, deleted_cols = 0,
270 matbeg[0] = 0; j < colnum; j++ ) {
271
272 /* read in the name of the column, obj fn coeff and
273 num of rows intersecting this column */
274 if (fscanf(f, "%i%lf%i",
275 &colnames[col_count], &obj[col_count], &col_nzcnt) != 3)
276 IO_ERROR;
277
278 /* read in row indices */
279 for ( i = 0; i < col_nzcnt; i++){
280 if (fscanf(f, "%i", &value) != 1)
281 IO_ERROR;
282 if ( !value || (value > rownum))
283 IO_ERROR;
284 matind[nz_count++] = value-1;
285 }
286 matbeg[col_count+1] = matbeg[col_count] + col_nzcnt;
287
288 /* if this this and the previous column are of the same length */
289 if ( col_count > 0 &&
290 matbeg[col_count] - matbeg[col_count-1] == col_nzcnt ) {
291 /* if the two columns ARE the same */
292 if (!memcmp( matind+matbeg[col_count-1], matind+matbeg[col_count],
293 col_nzcnt * sizeof(row_ind_type)) ) {
294 /* if new column has a better obj fn coeff then keep this;
295 no change in matind or matbeg since cols are same */
296 if ( obj[col_count] < obj[col_count-1] ) {
297 obj[col_count-1] = obj[col_count];
298 colnames[col_count-1] = colnames[col_count];
299 }
300 deleted_cols++;
301 nz_count -= col_nzcnt;
302 } else {
303 col_count++;
304 }
305 } else {
306 col_count++;
307 }
308 }
309
310 if ( deleted_cols ) {
311 matrix->colnum = col_count;
312 matrix->rownum = rownum;
313 matrix->nzcnt = nz_count;
314 matrix->colnames = (int *) realloc((char *)matrix->colnames,
315 col_count * ISIZE);
316 matrix->obj = (double *) realloc((char *)matrix->obj,
317 col_count * DSIZE );
318 matrix->matbeg = (int *) realloc((char *)matrix->matbeg,
319 (col_count+1) * ISIZE );
320 matrix->matind = (row_ind_type *)
321 realloc((char *)matrix->matind, nz_count * sizeof(row_ind_type) );
322 }
323 return(deleted_cols);
324 }
325
326 /*===========================================================================*
327 * read our0 format, no deletion of duplicate columns at loadtime.
328 *===========================================================================*/
329
330 void read_our0_no_del(col_ordered *matrix, FILE *f)
331 {
332 int colnum = matrix->colnum;
333 int rownum = matrix->rownum;
334 int *colnames = matrix->colnames;
335 double *obj = matrix->obj;
336 int *matbeg = matrix->matbeg;
337 row_ind_type *matind = matrix->matind;
338
339 int j; /* runs thru columns */
340 int i; /* runs thru rows intersecting a column */
341 int nz_count; /* count nonzeros */
342 int col_nzcnt; /* number of nonzeros in a column */
343 int value; /* a temporary variable */
344 int rownum_minus_1 = rownum - 1;
345
346
347 for ( j = 0, nz_count = 0, matbeg[0] = 0; j < colnum; j++ ) {
348
349 /* read in the name of the column, obj fn coeff and
350 num of rows intersecting this column */
351 if (fscanf(f, "%i%lf%i", &colnames[j], &obj[j], &col_nzcnt) != 3)
352 IO_ERROR;
353
354 /* read in row indices */
355 for ( i = 0; i < col_nzcnt; i++){
356 if (fscanf(f, "%i", &value) != 1)
357 IO_ERROR;
358 if ( value < 0 || value > rownum_minus_1 )
359 IO_ERROR;
360 matind[nz_count++] = value;
361 }
362 matbeg[j+1] = matbeg[j] + col_nzcnt;
363 }
364 }
365
366 /*===========================================================================*
367 * read our0 format, delete duplicate columns (that are next to
368 * each other) at loadtime. returns the number of columns deleted, or
369 * -1 in case of failure.
370 *===========================================================================*/
371
372 int read_our0_del_dupl(col_ordered *matrix, FILE *f)
373 {
374 int colnum = matrix->colnum;
375 int rownum = matrix->rownum;
376 int *colnames = matrix->colnames;
377 double *obj = matrix->obj;
378 int *matbeg = matrix->matbeg;
379 row_ind_type *matind = matrix->matind;
380 int rownum_minus_1 = rownum - 1;
381
382 int j; /* runs thru columns */
383 int i; /* runs thru rows intersecting a column */
384 int col_count, nz_count; /* count columns and nonzeros */
385 int col_nzcnt; /* number of nonzeros in a column */
386 int value; /* a temporary variable */
387 int deleted_cols; /* number of columns deleted */
388
389
390 for ( j = 0, nz_count = 0, col_count = 0, deleted_cols = 0,
391 matbeg[0] = 0; j < colnum; j++ ) {
392
393 /* read in the name of the column, obj fn coeff and
394 num of rows intersecting this column */
395 if (fscanf(f, "%i%lf%i",
396 &colnames[col_count], &obj[col_count], &col_nzcnt) != 3)
397 IO_ERROR;
398
399 /* read in row indices */
400 for ( i = 0; i < col_nzcnt; i++){
401 if (fscanf(f, "%i", &value) != 1)
402 IO_ERROR;
403 if ( value < 0 || value > rownum_minus_1)
404 IO_ERROR;
405 matind[nz_count++] = value;
406 }
407 matbeg[col_count+1] = matbeg[col_count] + col_nzcnt;
408
409 /* if this this and the previous column are of the same length */
410 if ( col_count > 0 &&
411 matbeg[col_count] - matbeg[col_count-1] == col_nzcnt ) {
412 /* if the two columns ARE the same */
413 if (!memcmp( matind+matbeg[col_count-1], matind+matbeg[col_count],
414 col_nzcnt * sizeof(row_ind_type)) ) {
415 /* if new column has a better obj fn coeff then keep this;
416 no change in matind or matbeg since cols are same */
417 if ( obj[col_count] < obj[col_count-1] ) {
418 obj[col_count-1] = obj[col_count];
419 colnames[col_count-1] = colnames[col_count];
420 }
421 deleted_cols++;
422 nz_count -= col_nzcnt;
423 } else {
424 col_count++;
425 }
426 } else {
427 col_count++;
428 }
429 }
430
431 if ( deleted_cols ) {
432 matrix->colnum = col_count;
433 matrix->rownum = rownum;
434 matrix->nzcnt = nz_count;
435 matrix->colnames = (int *) realloc((char *)matrix->colnames,
436 col_count * ISIZE);
437 matrix->obj = (double *) realloc((char *)matrix->obj,
438 col_count * DSIZE );
439 matrix->matbeg = (int *) realloc((char *)matrix->matbeg,
440 (col_count+1) * ISIZE );
441 matrix->matind = (row_ind_type *)
442 realloc((char *)matrix->matind, nz_count * sizeof(row_ind_type) );
443 }
444 return(deleted_cols);
445 }
446
447 /*****************************************************************************/
448
449 void spp_fix_lex(spp_problem *spp)
450 {
451 int *order; /* order is allocated in lexsort() */
452 col_ordered *matrix = spp->cmatrix;
453 int colnum = matrix->colnum;
454 int *colnames = matrix->colnames;
455 double *obj = matrix->obj;
456 int *matbeg = matrix->matbeg;
457 row_ind_type *matind = matrix->matind;
458
459 int *new_colnames = (int *) malloc(colnum * ISIZE);
460 double *new_obj = (double *) malloc( colnum * DSIZE);
461 int *new_matbeg = (int *) malloc((colnum+1) * ISIZE);
462 row_ind_type *new_matind = (row_ind_type *)
463 malloc( matrix->nzcnt * sizeof(row_ind_type));
464
465 int i, col, col_length;
466
467 /* order is a permutation of column indices that shows their lex order */
468 order = spp_lexsort(matrix);
469
470 /* copy the columns into the new data structure */
471 for ( i = 0, new_matbeg[0] = 0; i < colnum; i++) {
472 col = order[i];
473 new_colnames[i] = colnames[col];
474 new_obj[i] = obj[col];
475 col_length = matbeg[col+1] - matbeg[col];
476 memcpy((char *)(new_matind + new_matbeg[i]),
477 (char *)(matind + matbeg[col]),
478 col_length * sizeof(row_ind_type) );
479 new_matbeg[i+1] = new_matbeg[i] + col_length;
480 }
481
482 FREE(colnames);
483 FREE(obj);
484 FREE(matbeg);
485 FREE(matind);
486
487 matrix->colnames = new_colnames;
488 matrix->obj = new_obj;
489 matrix->matbeg = new_matbeg;
490 matrix->matind = new_matind;
491
492 FREE(order);
493 }
494
495
496 /*****************************************************************************/
497
498 /*===========================================================================*
499 * Write the column ordered matrix into a file (or stdout), in our format.
500 * counter is increased here.
501 *===========================================================================*/
502
503 void spp_matrix_to_our(col_ordered *matrix, char *filename, int *counter)
504 {
505 char fname[MAX_FILE_NAME_LENGTH];
506 FILE *f;
507
508 int i; /* runs thru columns */
509 int colnum = matrix->colnum;
510 int *colnames = matrix->colnames;
511 double *obj = matrix->obj;
512 int *matbeg = matrix->matbeg;
513 row_ind_type *matind = matrix->matind;
514 int col_nzcnt; /* number of rows intersecting a column */
515 int j; /* runs thru rows intersecting a column */
516 row_ind_type *col_beg; /* pointer to the beginning of a column in matind */
517
518 f = get_filehandler(*counter, filename, fname);
519 (*counter)++;
520
521 /* first row: type, rownum, colnum, nzcnt */
522 fprintf(f, "%8i %8i %15i %15i\n", OUR_FORMAT_0, matrix->rownum,
523 colnum, matrix->nzcnt);
524
525 /* for each column: colname, obj, col_nzcnt, row indices */
526 for ( i = 0; i < colnum; i++ ) {
527 col_nzcnt = matbeg[i+1]-matbeg[i];
528 col_beg = matind + matbeg[i];
529 fprintf(f, "%8i%9.2f%3i ", colnames[i], obj[i], col_nzcnt);
530 for ( j = 0; j < col_nzcnt; j++ )
531 fprintf(f, " %4i", col_beg[j]);
532 fprintf(f, "\n");
533 }
534
535 if ( f != stdout )
536 fclose(f);
537
538 printf("########################################################\n");
539 printf("Saved problem matrix into file %s\n\n\n", fname);
540 }
541
542 /*****************************************************************************/
543
544 /*===========================================================================*
545 * Write the column ordered matrix into a file (or stdout), in flat (matlab
546 * readable) format. (note that vectors indices start from 1 in matlab)
547 * counter is increased here.
548 *===========================================================================*/
549
550 void spp_matrix_to_matlab(col_ordered *matrix, char *filename, int *counter)
551 {
552 char fname[MAX_FILE_NAME_LENGTH];
553 FILE *f;
554
555 int i; /* runs thru columns */
556 int colnum = matrix->colnum;
557 int col_nzcnt; /* number of rows intersecting a column */
558 int *matbeg = matrix->matbeg;
559 row_ind_type *matind = matrix->matind;
560 int j; /* runs thru rows intersecting a column */
561 row_ind_type *col_beg; /* pointer to the beginning of a column in matind */
562
563 f = get_filehandler(*counter, filename, fname);
564 (*counter)++;
565
566 /* first print out "rownum colnum 0" */
567 fprintf(f, "%10i %10i %10i\n", matrix->rownum, colnum, 0);
568
569 /* for each column, and for each row intersecting this column
570 print "row_index column_index 1" */
571 for ( i = 0; i < colnum; i++ ) {
572 col_nzcnt = matbeg[i+1] - matbeg[i];
573 col_beg = matind + matbeg[i];
574 for ( j = 0; j < col_nzcnt; j++ ) {
575 fprintf(f, "%10i %10i %10i\n", col_beg[j]+1, i+1, 1);
576 }
577 }
578
579 if ( f != stdout )
580 fclose(f);
581
582 printf("########################################################\n");
583 printf("Saved problem matrix into file %s\n\n", fname);
584 }