Debian Codegraph @

SYMPHONY/Applications/MCKP/mckp_main.c

raw
1 /*===========================================================================*/
2 /* */
3 /* This file is part of a demonstration application for use with the */
4 /* SYMPHONY MILP Solver Framework. This application is a solver for */
5 /* the Vehicle Routing Problem and the Traveling Salesman Problem. */
6 /* */
7 /* (c) Copyright 2006-2023 Lehigh University. 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_macros.h"
23 #include "symphony.h"
24 #include "sym_master.h"
25
26 #define LENGTH 100
27
28 void mckp_parse_command_line(int argc, char **argv, char *infile,
29 int *num_items, int *num_constraints,
30 int *format, char *solve_mc, double *gamma,
31 double *utopia, double *ub);
32 void mckp_read_problem1(sym_environment *env, char *infile, int *num_items,
33 double ***objectives, double ***constraints,
34 double **capacity, int *num_objectives,
35 int *num_constraints);
36 void mckp_read_problem2(sym_environment *env, char *infile, int *num_items,
37 double ***objectives, double ***constraints,
38 double **capacity, int *num_objectives,
39 int *num_constraints);
40 void mckp_read_problem3(sym_environment *env, char *infile, int *num_items,
41 double ***objectives, double ***constraints,
42 double **capacity, int *num_objectives,
43 int *num_constraints);
44
45 /*===========================================================================*\
46 * This is main() for the MCKP application
47 \*===========================================================================*/
48
49 int main(int argc, char **argv)
50 {
51 char infile[LENGTH];
52 int num_items = 0, format;
53 double **objectives, **constraints;
54 int num_objectives = 0, num_constraints = 0;
55 double *capacity;
56 int i, j, k;
57 int nz;
58 int *matbeg, *matind;
59 double *matval, *lb, *ub, gamma, utopia[2];
60 char *sense, *is_int, solve_mc = TRUE;
61 char output_file[50];
62 FILE *f;
63 double mc_ub = MAXDOUBLE;
64
65 sym_environment *env = sym_open_environment();
66
67 sym_version();
68
69 sym_parse_command_line(env, argc, argv);
70
71 mckp_parse_command_line(argc, argv, infile, &num_items, &num_constraints,
72 &format, &solve_mc, &gamma, utopia, &mc_ub);
73
74 sym_set_int_param(env, "do_reduced_cost_fixing", FALSE);
75
76 if (format == 1){
77 mckp_read_problem1(env, infile, &num_items, &objectives, &constraints,
78 &capacity, &num_objectives, &num_constraints);
79 }else if (format == 2){
80 mckp_read_problem2(env, infile, &num_items, &objectives, &constraints,
81 &capacity, &num_objectives, &num_constraints);
82 }else if (format == 3){
83 mckp_read_problem3(env, infile, &num_items, &objectives, &constraints,
84 &capacity, &num_objectives, &num_constraints);
85
86 }else{
87 fprintf(stderr, "Invalid format!\n");
88 exit(0);
89 }
90
91 if (num_objectives != 2){
92 fprintf(stderr, "Wrong number of objectives specified!\n");
93 exit(0);
94 }
95
96 nz = num_items*num_constraints;
97
98 matbeg = (int *) malloc((num_items + 1) * ISIZE);
99 matind = (int *) malloc(nz * ISIZE);
100 matval = (double *) malloc(nz * DSIZE);
101 ub = (double *) malloc(num_items * DSIZE);
102 lb = (double *) calloc(num_items, DSIZE); /* zero lower bounds */
103 sense = (char *) malloc(num_constraints * CSIZE);
104 is_int = (char *) calloc(num_items, CSIZE);
105
106 /* Convert to column-ordered format */
107 for (i = 0, k = 0; i < num_items; i++){
108 matbeg[i] = k;
109 for (j = 0; j < num_constraints; j++){
110 matind[k] = j;
111 matval[k++] = constraints[j][i];
112 }
113 ub[i] = 1.0;
114 is_int[i] = TRUE;
115 }
116 matbeg[i] = k;
117
118 for (j = 0; j < num_constraints; j++){
119 sense[j] = 'L';
120 }
121
122 sym_explicit_load_problem(env, num_items, num_constraints, matbeg, matind,
123 matval, lb, ub, is_int, objectives[0],
124 objectives[1], sense, capacity, NULL, TRUE);
125
126 if (solve_mc){
127 sym_mc_solve(env);
128 }else{
129 double tau = 0.0;
130 sym_set_int_param(env, "multi_criteria", TRUE);
131 if (gamma == 1.0){
132 tau = -1.0;
133 env->utopia[0] = 0;
134 env->utopia[1] = -MAXINT;
135 }else if (gamma == 0.0){
136 gamma = -1.0;
137 tau = 1.0;
138 env->utopia[0] = -MAXINT;
139 env->utopia[1] = 0;
140 }else{
141 tau = 1 - gamma;
142 env->utopia[0] = utopia[0];
143 env->utopia[1] = utopia[1];
144 }
145 sym_set_dbl_param(env, "mc_gamma", gamma);
146 sym_set_dbl_param(env, "mc_tau", tau);
147 sym_set_int_param(env, "mc_find_supported_solutions", FALSE);
148 memcpy((char *)env->mip->obj1, (char *)env->mip->obj, DSIZE*env->mip->n);
149 if (mc_ub < MAXDOUBLE){
150 env->ub = env->mc_ub = mc_ub;
151 env->has_mc_ub = env->has_ub = TRUE;
152 }
153 env->obj[0] = env->obj[1] = 0.0;
154 env->base->cutnum += 2;
155 env->rootdesc->uind.size++;
156 env->rootdesc->uind.list = (int *) realloc(env->rootdesc->uind.list,
157 env->rootdesc->uind.size*ISIZE);
158 env->rootdesc->uind.list[env->rootdesc->uind.size-1] = env->mip->n;
159 env->par.tm_par.granularity = env->par.lp_par.granularity =
160 -MAX(env->par.lp_par.mc_rho, env->par.mc_compare_solution_tolerance);
161 sym_solve(env);
162 sprintf(output_file, "output.%s", argv[6]);
163 if (!(f = fopen(output_file, "w"))){
164 printf("\nError opening output file\n\n");
165 }else{
166 fprintf(f, "Gamma: %.10f\n", gamma);
167 if (env->obj[0] == 0.0 && env->obj[1] == 0.0){
168 fprintf(f, "Subproblem Infeasible\n");
169 }else{
170 fprintf(f, "First Objective: %lf\n", env->obj[0]);
171 fprintf(f, "Second Objective: %lf\n", env->obj[1]);
172 }
173 }
174 fclose(f);
175 }
176
177 sym_close_environment(env);
178
179 for (i = 0; i < num_objectives; i++){
180 free(objectives[i]);
181 }
182 free(objectives);
183
184 for (i = 0; i < num_constraints; i++){
185 free(constraints[i]);
186 }
187 free(constraints);
188 free(capacity);
189
190 free(matbeg);
191 free(matind);
192 free(matval);
193 free(ub);
194 free(lb);
195 free(sense);
196 free(is_int);
197
198 return(0);
199 }
200
201 /*===========================================================================*\
202 * This is the function that reads the command line
203 \*===========================================================================*/
204
205 void mckp_parse_command_line(int argc, char **argv, char *infile,
206 int *num_items, int *num_constraints,
207 int *format, char *solve_mc, double *gamma,
208 double *utopia, double *ub)
209 {
210 int i, tmpi;
211 char foundF = FALSE, foundT = FALSE;
212 char tmp, c;
213 char line[LENGTH];
214 double tmpd;
215
216 for (i = 1; i < argc; i++){
217 sscanf(argv[i], "%c %c", &tmp, &c);
218 if (tmp != '-')
219 continue;
220 switch (c) {
221 case 'F':
222 if (i < argc - 1){
223 sscanf(argv[i+1], "%c", &tmp);
224 if (tmp == '-'){
225 printf("Warning: Missing argument to command-line switch -%c\n",
226 c);
227 }else{
228 strncpy(infile, argv[++i], LENGTH);
229 foundF = TRUE;
230 }
231 }else{
232 printf("Warning: Missing argument to command-line switch -%c\n",c);
233 }
234 break;
235 case 'U':
236 if (i < argc - 1){
237 sscanf(argv[i+1], "%lf", &tmpd);
238 if (tmp == '-'){
239 printf("Warning: Missing argument to command-line switch -%c\n",
240 c);
241 }else{
242 *ub = tmpd;
243 }
244 }else{
245 printf("Warning: Missing argument to command-line switch -%c\n",c);
246 }
247 break;
248 case 'N':
249 if (i < argc - 1){
250 if (!sscanf(argv[i+1], "%d", &tmpi)){
251 printf("Warning: Missing argument to command-line switch -%c",
252 c);
253 printf("\n");
254 }else{
255 i++;
256 *num_items = tmpi;
257 }
258 }else{
259 printf("Warning: Missing argument to command-line switch -%c\n",c);
260 }
261 break;
262 case 'C':
263 if (i < argc - 1){
264 if (!sscanf(argv[i+1], "%d", &tmpi)){
265 printf("Warning: Missing argument to command-line switch -%c",
266 c);
267 printf("\n");
268 }else{
269 i++;
270 *num_constraints = tmpi;
271 }
272 }else{
273 printf("Warning: Missing argument to command-line switch -%c\n",c);
274 }
275 break;
276 case 'T':
277 if (i < argc - 1){
278 if (!sscanf(argv[i+1], "%d", &tmpi)){
279 printf("Warning: Missing argument to command-line switch -%c",
280 c);
281 printf("\n");
282 }else{
283 i++;
284 *format = tmpi;
285 foundT = TRUE;
286 }
287 }else{
288 printf("Warning: Missing argument to command-line switch -%c\n",c);
289 }
290 break;
291 case 'G':
292 if (i < argc - 1){
293 if (!sscanf(argv[i+1], "%lf", &tmpd)){
294 printf("Warning: Missing argument to command-line switch -%c",
295 c);
296 printf("\n");
297 }else{
298 i++;
299 *gamma = tmpd;
300 *solve_mc = FALSE;
301 if (tmpd != 1.0 && tmpd != 0.0){
302 if (!sscanf(argv[i+1], "%lf", &tmpd)){
303 printf("Warning: Missing argument to command-line switch -%c",
304 c);
305 printf("\n");
306 }else{
307 i++;
308 utopia[0] = tmpd;
309 }
310 if (!sscanf(argv[i+1], "%lf", &tmpd)){
311 printf("Warning: Missing argument to command-line switch -%c",
312 c);
313 printf("\n");
314 }else{
315 i++;
316 utopia[1] = tmpd;
317 }
318 }
319 }
320 }else{
321 printf("Warning: Missing argument to command-line switch -%c\n",c);
322 }
323 break;
324 default:
325 break;
326 }
327 }
328
329 if (!foundF){
330 fprintf(stderr, "MCKP I/O: file name not specified\n", infile);
331 exit(1);
332 }
333 if (!foundT){
334 fprintf(stderr, "MCKP I/O: file format not specified\n", infile);
335 exit(1);
336 }
337 }
338
339 /*===========================================================================*\
340 * This is the function that reads in the data file in format 1
341 \*===========================================================================*/
342
343 void mckp_read_problem1(sym_environment *env, char *infile, int *num_items,
344 double ***objectives, double ***constraints,
345 double **capacity, int *num_objectives,
346 int *num_constraints)
347 {
348 char line[LENGTH], line1[LENGTH];
349 FILE *f;
350 double **obj, **cons;
351 double *cap;
352 int num_obj = 0, num_cons = 0, count = 0;
353 char key[LENGTH];
354 int max_num_items = *num_items;
355 int max_num_cons = *num_constraints;
356
357 if (!max_num_items){
358 fprintf(stderr, "MCKP I/O: format 1 requires number of items to be\n");
359 fprintf(stderr, "specified.\n");
360 exit(0);
361 }
362
363 if ((f = fopen(infile, "r")) == NULL){
364 fprintf(stderr, "MCKP I/O: file '%s' can't be opened\n", infile);
365 exit(1);
366 }
367
368 if (!max_num_cons){
369 max_num_cons = 10;
370 }
371
372 obj = *objectives = (double **) calloc(2, sizeof(double *));
373 cons = *constraints = (double **) calloc(max_num_cons, sizeof(double *));
374 cap = *capacity = (double *) calloc(max_num_cons, sizeof(double));
375
376 obj[0] = (double *) calloc(max_num_items, sizeof(double));
377 obj[1] = (double *) calloc(max_num_items, sizeof(double));
378
379 while (NULL != fgets(line, LENGTH, f)){
380 strcpy(key, "");
381 sscanf(line,"%s", key); /*read in next keyword*/
382 if (strcmp("=", key) == 0){
383 if (NULL != fgets(line, LENGTH, f)){
384 strcpy(key,"");
385 sscanf(line,"%s",key); /*read in next keyword*/
386 if (strcmp("knapsack", key) == 0){
387 if (NULL != fgets(line, LENGTH, f)){
388 strcpy(key,"");
389 sscanf(line,"%s",key); /*read in next keyword*/
390 if (strcmp("capacity:", key) == 0){
391 if (strchr(line,':')){
392 strcpy(line1, strchr(line, ':')+1);
393 }
394 sscanf(line1, "%lf", (*capacity) + num_cons);
395 }else{
396 fprintf(stderr, "MCKP I/O: Unexpected keyword in",
397 "input file!\n");
398 exit(1);
399 }
400 count = 0;
401 cons[num_cons] = (double *) calloc(max_num_items,
402 sizeof(double));
403 while (NULL != fgets(line, LENGTH, f)){
404 strcpy(key,"");
405 sscanf(line,"%s",key); /*read in next keyword*/
406 if (strcmp("item", key) != 0){
407 fprintf(stderr, "MCKP I/O: Unexpected keyword in",
408 "input file!\n");
409 exit(1);
410 }
411 if (NULL != fgets(line, LENGTH, f)){
412 strcpy(key,"");
413 sscanf(line,"%s",key); /*read in next keyword*/
414 if (strcmp("weight:", key) == 0){
415 if (num_cons < max_num_cons){
416 if (strchr(line,':')){
417 strcpy(line1, strchr(line, ':')+1);
418 }
419 sscanf(line1, "%lf", (cons[num_cons]) + count);
420 }
421 }else{
422 fprintf(stderr, "MCKP I/O: Unexpected keyword in",
423 "input file!\n");
424 exit(1);
425 }
426 }else{
427 fprintf(stderr, "MCKP I/O: Unexpected end of file!\n");
428 exit(1);
429 }
430 if (NULL != fgets(line, LENGTH, f)){
431 strcpy(key,"");
432 sscanf(line,"%s",key); /*read in next keyword*/
433 if (strcmp("profit:", key) == 0){
434 if (num_obj < 2){
435 if (strchr(line,':')){
436 strcpy(line1, strchr(line, ':')+1);
437 }
438 sscanf(line1, "%lf", (obj[num_obj]) + count);
439 obj[num_obj][count] *= -1;
440 }
441 }else{
442 fprintf(stderr, "MCKP I/O: Unexpected keyword in",
443 "input file!\n");
444 exit(1);
445 }
446 }else{
447 fprintf(stderr, "MCKP I/O: Unexpected end of file!\n");
448 exit(1);
449 }
450 if (++count == max_num_items){
451 break;
452 }
453 }
454 if (count != max_num_items){
455 fprintf(stderr, "MCKP I/O: Not enough items!\n");
456 exit(1);
457 }
458 num_obj++;
459 num_cons++;
460 }else{
461 fprintf(stderr, "MCKP I/O: Unexpected end of file!\n");
462 exit(1);
463 }
464 }else{
465 fprintf(stderr,"MCKP I/O: Unexpected keyword in input file!\n");
466 exit(1);
467 }
468 }else{
469 fprintf(stderr, "MCKP I/O: Unexpected end of file!\n");
470 exit(1);
471 }
472 }
473 }
474
475 *num_objectives = num_obj > 2 ? 2 : num_obj;
476 *num_constraints = num_cons > max_num_cons ? max_num_cons : num_cons;
477
478 fclose(f);
479 }
480
481 /*===========================================================================*\
482 * This is the function that reads in the data file in format 2
483 \*===========================================================================*/
484
485 void mckp_read_problem2(sym_environment *env, char *infile, int *num_items,
486 double ***objectives, double ***constraints,
487 double **capacity, int *num_objectives,
488 int *num_constraints)
489 {
490 char line[LENGTH], line1[LENGTH];
491 FILE *f;
492 double **obj, **cons;
493 double *cap;
494 int num_obj = 0, num_cons = 0;
495 char key[LENGTH];
496 int i;
497 int max_num_items = *num_items;
498 int max_num_cons = *num_constraints;
499
500 if ((f = fopen(infile, "r")) == NULL){
501 fprintf(stderr, "MCKP I/O: file '%s' can't be opened\n", infile);
502 exit(1);
503 }
504
505 obj = *objectives = (double **) calloc(2, sizeof(double *));
506
507 while (NULL != fgets(line, LENGTH, f)){
508 strcpy(key, "");
509 sscanf(line,"%s", key); /*read in next keyword*/
510 if (strcmp("#", key) == 0){
511 switch (line[2]){
512 case 'N':
513 if (NULL != fgets(line, LENGTH, f)){
514 sscanf(line, "%i", num_items);
515 if (max_num_items){
516 max_num_items = *num_items > max_num_items ?
517 max_num_items : *num_items;
518 *num_items = max_num_items;
519 }else{
520 max_num_items = *num_items;
521 }
522 }else{
523 fprintf(stderr, "MCKP I/O: Unexpected end of file!\n");
524 exit(1);
525 }
526 obj[0] = (double *) calloc(max_num_items, sizeof(double));
527 obj[1] = (double *) calloc(max_num_items, sizeof(double));
528 break;
529
530 case 'P':
531 break;
532
533 case 'K':
534 if (NULL != fgets(line, LENGTH, f)){
535 sscanf(line, "%i", num_constraints);
536 if (max_num_cons){
537 max_num_cons = *num_constraints > max_num_cons ?
538 max_num_cons : *num_constraints;
539 *num_constraints = max_num_cons;
540 }else{
541 max_num_cons = *num_constraints;
542 }
543 }else{
544 fprintf(stderr, "MCKP I/O: Unexpected end of file!\n");
545 exit(1);
546 }
547 cons = *constraints = (double **) calloc(*num_constraints,
548 sizeof(double *));
549 cap = *capacity = (double *) calloc(*num_constraints,
550 sizeof(double));
551 break;
552
553 case 'O':
554 if (num_obj <2){
555 for (i = 0; i < max_num_items;){
556 if (NULL != fgets(line, LENGTH, f)){
557 if (strcmp("\r\n", line) != 0){
558 sscanf(line, "%lf", obj[num_obj] + i);
559 obj[num_obj][i] *= -1;
560 i++;
561 }
562 }else{
563 fprintf(stderr, "MCKP I/O: Unexpected end of file!\n");
564 exit(1);
565 }
566 }
567 num_obj++;
568 }
569 break;
570
571 case 'C':
572 if (num_cons < max_num_cons){
573 cons[num_cons] = (double *) calloc(max_num_items,
574 sizeof(double));
575 for (i = 0; i < max_num_items;){
576 if (NULL != fgets(line, LENGTH, f)){
577 if (strcmp("\r\n", line) != 0){
578 sscanf(line, "%lf", cons[num_cons] + i);
579 i++;
580 }
581 }else{
582 fprintf(stderr, "MCKP I/O: Unexpected end of file!\n");
583 exit(1);
584 }
585 }
586 while (NULL != fgets(line, LENGTH, f)){
587 if (strcmp("\r\n", line) != 0){
588 sscanf(line, "%lf", (*capacity) + num_cons);
589 break;
590 }
591 }
592 }
593 num_cons++;
594 break;
595
596 default:
597 break;
598
599 }
600 }
601 }
602
603 *num_objectives = num_obj;
604 *num_constraints = num_cons;
605
606 fclose(f);
607 }
608
609 /*===========================================================================*\
610 * This is the function that reads in the data file in format 3
611 \*===========================================================================*/
612
613 void mckp_read_problem3(sym_environment *env, char *infile, int *num_items,
614 double ***objectives, double ***constraints,
615 double **capacity, int *num_objectives,
616 int *num_constraints)
617 {
618 char line[LENGTH], line1[LENGTH];
619 FILE *f;
620 double **obj, **cons;
621 double *cap;
622 int num_obj = 0, count = 0;
623 char key[LENGTH];
624 int i;
625 int max_num_items = *num_items;
626
627 *num_constraints = 1;
628 *num_objectives = 2;
629
630 if ((f = fopen(infile, "r")) == NULL){
631 fprintf(stderr, "MCKP I/O: file '%s' can't be opened\n", infile);
632 exit(1);
633 }
634
635 obj = *objectives = (double **) calloc(2, sizeof(double *));
636 cons = *constraints = (double **) calloc(1, sizeof(double *));
637 *capacity = (double *) calloc(1, sizeof(double));
638
639 while (NULL != fgets(line, LENGTH, f)){
640 switch (line[0]){
641 case 'c':
642 break;
643
644 case 'n':
645 sscanf(line+1, "%i", num_items);
646 if (max_num_items){
647 max_num_items = *num_items > max_num_items ?
648 max_num_items : *num_items;
649 *num_items = max_num_items;
650 }else{
651 max_num_items = *num_items;
652 }
653 obj[0] = (double *) calloc(max_num_items, sizeof(double));
654 obj[1] = (double *) calloc(max_num_items, sizeof(double));
655 cons[0] = (double *) calloc(max_num_items, sizeof(double));
656 break;
657
658 case 'i':
659 if (count < max_num_items){
660 sscanf(line+1, "%lf %lf %lf", cons[0] + count, obj[0] + count,
661 obj[1] + count);
662 obj[0][count] *= -1;
663 obj[1][count] *= -1;
664 count++;
665 }
666 break;
667
668 case 'W':
669 sscanf(line+1, "%lf", *capacity);
670 }
671 }
672
673 fclose(f);
674 }