Debian Codegraph @

SYMPHONY/Applications/MPP/src/Master/mpp_master.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 Mixed Postman Problem. */
6 /* */
7 /* (c) Copyright 2005-2007 Lehigh University. All Rights Reserved. */
8 /* */
9 /* This application was originally developed by Andrew Hofmann and was */
10 /* modified by 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_constants.h"
24 #include "sym_macros.h"
25 #include "sym_master_u.h"
26
27 /* MPP include files */
28 #include "mpp.h"
29
30 /*===========================================================================*\
31 * This file contains stubs for the user-written functions for the master
32 * process. The primary function that has to be filled in here is user_io(),
33 * where the data for the instance is read in and the user data structure
34 * that stores the instance data filled out (this data structure is defined
35 * in user.h). Other than that, the default routines should work fine.
36 \*===========================================================================*/
37
38 /*===========================================================================*/
39
40 /*===========================================================================*\
41 * This function gives help on command-line switches defined by the user.
42 * All user switches have capital letters by convention.
43 \*===========================================================================*/
44
45 void user_usage(void){
46 printf("master [ -H ] [ -F file ] \n\t%s\n\t%s\n",
47 "-H: help (user switches)",
48 "-F file: problem instance data is in 'file'");
49 }
50
51 /*===========================================================================*/
52
53 /*===========================================================================*\
54 * Initialize user-defined data structures. This basically consists of
55 * allocating the memory. If you are using the default data structure,
56 * nothing needs to be changed here.
57 \*===========================================================================*/
58
59 int user_initialize(void **user)
60 {
61 mpp_problem *mpp = (mpp_problem *) calloc(1, sizeof(mpp_problem));
62
63 *user = mpp;
64
65 return(USER_SUCCESS);
66 }
67
68 /*===========================================================================*/
69
70 /*===========================================================================*\
71 * Parse the user options and read in parameters from the parameter file
72 * given on the command line
73 \*===========================================================================*/
74
75 int user_readparams(void *user, char *filename, int argc, char **argv)
76 {
77 FILE *f;
78 char line[50], key[50], value[50], c, tmp;
79 int i;
80 /* This gives you access to the user data structure*/
81 mpp_problem *mpp = (mpp_problem *) user;
82 mpp_parameters *par = &(mpp->par);
83
84 if (strcmp(filename, "")){
85 if ((f = fopen(filename, "r")) == NULL){
86 printf("SYMPHONY: file %s can't be opened\n", filename);
87 exit(1); /*error check for existence of parameter file*/
88 }
89
90 /* Here you can read in the parameter settings from the file. See the
91 function bc_readparams() for an example of how this is done. */
92 while(NULL != fgets(line, MAX_LINE_LENGTH, f)){ /*read in parameters*/
93 strcpy(key, "");
94 sscanf(line, "%s%s", key, value);
95
96 if (strcmp(key, "input_file") == 0){
97 par->infile[MAX_FILE_NAME_LENGTH] = 0;
98 strncpy(par->infile, value, MAX_FILE_NAME_LENGTH);
99 }
100 }
101
102 fclose(f);
103 }
104
105 /* Here you can parse the command line for options. By convention, the
106 users options should be capital letters */
107
108 for (i = 1; i < argc; i++){
109 sscanf(argv[i], "%c %c", &tmp, &c);
110 if (tmp != '-')
111 continue;
112 switch (c) {
113 case 'H':
114 user_usage();
115 exit(0);
116 break;
117 case 'F':
118 strncpy(par->infile, argv[++i], MAX_FILE_NAME_LENGTH);
119 break;
120 case 'T':
121 par->test = TRUE;
122 if(i+1 < argc){
123 sscanf(argv[i+1], "%c", &tmp);
124 if(tmp != '-'){
125 strncpy(par->test_dir, argv[++i],MAX_FILE_NAME_LENGTH);
126 }
127 }
128 break;
129 };
130 }
131
132 return(USER_SUCCESS);
133 }
134
135 /*===========================================================================*/
136
137 /*===========================================================================*\
138 * Read in the data file, whose name was given in the parameter file.
139 * This file contains instance data. Right now, this function is set up to
140 * read in just the number of columns and number of rows from the file.
141 * Add more data as needed to describe the instance and set up the LP
142 * relaxation.
143 \*===========================================================================*/
144
145 int user_io(void *user)
146 {
147 /* This gives you access to the user data structure. */
148 mpp_problem *mpp = (mpp_problem *) user;
149 mpp_parameters *par = &(mpp->par);
150 char *infile = par->infile;
151 FILE *f = NULL;
152 char line[MAX_LINE_LENGTH], key[50], value[50];
153 int numvars, i;
154
155 /* Make sure the file exists and can be opened */
156 if (!strcmp(infile, "")){
157 printf("\nMpp I/O: No problem data file specified\n\n");
158 exit(1);
159 }
160
161 if ((f = fopen(infile, "r")) == NULL){
162 printf("Readparams: file %s can't be opened\n", infile);
163 exit(1); /*error check for existence of parameter file*/
164 }
165
166 /* The file format is to first list the number of nodes, arcs, and edges,
167 and then to specify the head, tail, and cost of each arc and edge */
168
169 /* Read in the number of nodes */
170 fgets(line, MAX_LINE_LENGTH, f);
171 sscanf(line, "%s%s", key, value);
172 if (strcmp(key, "NUMNODES") == 0){
173 READ_INT_PAR(mpp->numnodes);
174 }else{
175 printf("Error in input file: Expected number of nodes\n\n");
176 exit(1);
177 }
178
179 /* Read in the number of arcs */
180 fgets(line, MAX_LINE_LENGTH, f);
181 sscanf(line, "%s%s", key, value);
182 if (strcmp(key, "NUMARCS") == 0){
183 READ_INT_PAR(mpp->numarcs);
184 }else{
185 printf("Error in input file: Expected number of arcs\n\n");
186 exit(1);
187 }
188
189 /* Read in the number of edges */
190 fgets(line, MAX_LINE_LENGTH, f);
191 sscanf(line, "%s%s", key, value);
192 if (strcmp(key, "NUMEDGES") == 0){
193 READ_INT_PAR(mpp->numedges);
194 }else{
195 printf("Error in input file: Expected number of edges\n\n");
196 exit(1);
197 }
198
199 numvars = 2 * mpp->numedges + mpp->numarcs;
200
201 /* Allocate the arrays */
202 mpp->type = (char *) malloc (numvars * sizeof(char));
203 mpp->cost = (int *) malloc (numvars * sizeof(int));
204 mpp->head = (int *) malloc (numvars * sizeof(int));
205 mpp->tail = (int *) malloc (numvars * sizeof(int));
206
207 /* Read in the arcs and their data first */
208 for(i = 0; i < mpp->numarcs; i++){
209 if (!fgets(line, MAX_LINE_LENGTH, f)){
210 printf("Error in input file: Expected more data\n\n");
211 exit(1);
212 }
213 sscanf(line, "%c %i %i %i", mpp->type + i, mpp->tail + i,
214 mpp->head + i, mpp->cost + i);
215 if (strncmp(mpp->type + i, "A", 1) != 0 &&
216 strncmp(mpp->type + i, "a", 1) != 0 ){
217 printf("Error in input file: Expected an arc\n\n");
218 exit(1);
219 }
220 }
221
222 /* Read in the edges and their data */
223 for(i = mpp->numarcs; i < mpp->numarcs + mpp->numedges; i++){
224 if (!fgets(line, MAX_LINE_LENGTH, f)){
225 printf("Error in input file: Expected more data/n/n");
226 exit(1);
227 }
228 /*We have two variables associated with each edge, one for each direction*/
229 /* First variable */
230 sscanf(line, "%c %i %i %i", mpp->type + i,
231 mpp->tail + i,
232 mpp->head + i,
233 mpp->cost + i);
234 /* Second variable (direction reversed) */
235 sscanf(line, "%c %i %i %i", mpp->type + i + mpp->numedges,
236 mpp->head + i + mpp->numedges,
237 mpp->tail + i + mpp->numedges,
238 mpp->cost + i + mpp->numedges);
239 if (strncmp(mpp->type + i, "E", 1) != 0 &&
240 strncmp(mpp->type + i, "e", 1) != 0 ){
241 printf("Error in input file: Expected an edge/n/n");
242 exit(1);
243 }
244 }
245
246 if (fgets(line, MAX_LINE_LENGTH, f)){
247 printf("Ignoring extra data in input file./n/n");
248 }
249
250 fclose(f);
251
252 return(USER_SUCCESS);
253 }
254
255 /*===========================================================================*/
256
257 /*===========================================================================*\
258 * Here is where the heuristics are performed and an upper bound is calculated.
259 * An upper bound can also be specified in the parameter file. This function
260 * need not be filled in if no upper bounding is done.
261 \*===========================================================================*/
262
263 int user_start_heurs(void *user, double *ub, double *ub_estimate)
264 {
265 return(USER_DEFAULT);
266 }
267
268 /*===========================================================================*/
269
270 /*===========================================================================*\
271 * If graph drawing will be used, the user must initialize the drawing
272 * window here. This function need not be filled in.
273 \*===========================================================================*/
274
275 int user_init_draw_graph(void *user, int dg_id)
276 {
277 return(USER_DEFAULT);
278 }
279
280 /*===========================================================================*/
281
282 /*===========================================================================*\
283 * This is the subroutine where the user specifies which variables are to be
284 * in the base set and which variables are to be active in the root node but
285 * not in the base set (these are called the "extra variables"). This is done
286 * by listing the indices of the corresponding variables in arrays named
287 * "basevars" and extravars below.
288 *
289 * The base set of variables form the core that is never removed from the LP
290 * relaxation. Extra variables, on the other hand, can be removed if they are
291 * fixed by reduced cost or by logic-based rules. Allowing the removal of
292 * variables from the relaxation can lead to efficiencies, but there is a
293 * price to pay in terms of extra bookkeeping. If possible, it is a good idea
294 * to form a base set of variables consisting of those that are "likely" to be
295 * present in some optimal solution. If this is not possible, the simplest
296 * approach is just to put all the variables in the extra set, which allows
297 * them all to be fixed by reduced cost if possible. This is implemented below
298 * as an example.
299 *
300 * Note that each variable must have a unique user index by which the variable
301 * can be identified later. Note also that it is possible to have variables
302 * that are neither in the base set or active in the root node by using column
303 * generation and filling out the function user_generate_column().
304 \*===========================================================================*/
305
306 int user_initialize_root_node(void *user, int *basevarnum, int **basevars,
307 int *basecutnum, int *extravarnum, int **extravars,
308 char *obj_sense, double *obj_offset,
309 char ***colnames, int *colgen_strat)
310 {
311 /* This gives you access to the user data structure. */
312 mpp_problem *mpp = (mpp_problem *) user;
313 int i;
314
315 /* Since we don't know how to form a good set of base variables, we'll put all
316 the variables in the extra set */
317
318 /* Set the number of extra variables*/
319 *extravarnum = 2 * mpp->numedges + mpp->numarcs;
320
321 /* The variables are automatically put in the extra set */
322 *extravars = (int *) malloc(*extravarnum * ISIZE);
323 for (i = 0; i < *extravarnum; i++){
324 (*extravars)[i] = i;
325 }
326
327 /* Set the number of rows in the initial formulation */
328 *basecutnum = mpp->numnodes + mpp->numedges;
329
330 /* The set of base variables will be empty */
331 *basevarnum = 0;
332 *basevars = NULL;
333
334 return(USER_SUCCESS);
335 }
336
337 /*===========================================================================*/
338
339 /*===========================================================================*\
340 * Receive the feasible solution. Doesn't need to be filled in.
341 \*===========================================================================*/
342
343 int user_receive_feasible_solution(void *user, int msgtag, double cost,
344 int numvars, int *indices, double *values)
345 {
346 return(USER_DEFAULT);
347 }
348
349 /*===========================================================================*/
350
351 /*===========================================================================*\
352 * Here, we send the necessary data to the LP process. Notice that
353 * there are two cases to deal with. If the LP or the TM are running
354 * as separate processes, then we have to send the data by
355 * message-passing. Otherwise, we can allocate the user-defined LP data
356 * structure here and simply copy the necessary information. This is the
357 * only place the user has to sorry about this distinction between
358 * configurations. If running sequentially and using the default data
359 * structure, nothing needs to be modified in here.
360 \*===========================================================================*/
361
362 int user_send_lp_data(void *user, void **user_lp)
363 {
364 /* This gives you access to the user data structure. */
365 mpp_problem *mpp = (mpp_problem *) user;
366
367 #if defined(COMPILE_IN_TM) && defined(COMPILE_IN_LP)
368
369 *user_lp = mpp;
370
371 #else
372 /* Here, we send that data using message passing and the rest is
373 done in user_receive_lp_data() in the LP process */
374 #endif
375
376 return(USER_SUCCESS);
377 }
378
379 /*===========================================================================*/
380
381 /*===========================================================================*\
382 * Here, we send the necessary data to the CG process. Notice that
383 * there are two cases to deal with. If the CG, LP, or the TM are running
384 * as separate processes, then we have to send the data by
385 * message-passing. Otherwise, we can allocate the user-defined LP data
386 * structure here and simply copy the necessary information. This is the
387 * only place the user has to sorry about this distinction between
388 * configurations. If running sequentially and using the default data
389 * structure, nothing needs to be modified in here.
390 \*===========================================================================*/
391
392 int user_send_cg_data(void *user, void **user_cg)
393 {
394 /* This gives you access to the user data structure. */
395 mpp_problem *mpp = (mpp_problem *) user;
396
397 #if defined(COMPILE_IN_TM) && defined(COMPILE_IN_LP) && defined (COMPILE_IN_CG)
398
399 *user_cg = mpp;
400
401 #ifdef CHECK_CUT_VALIDITY
402 /* Send the feasible solution here */
403 #endif
404 #else
405 /* Here, we send that data using message passing and the rest is
406 done in user_receive_cg_data() in the CG process */
407 #ifdef CHECK_CUT_VALIDITY
408 /* Send the feasible solution here */
409 #endif
410 #endif
411
412 return(USER_SUCCESS);
413 }
414
415 /*===========================================================================*/
416
417 /*===========================================================================*\
418 * Here, we send the necessary data to the CP process. Notice that
419 * there are two cases to deal with. If the CP, LP, or the TM are running
420 * as separate processes, then we have to send the data by
421 * message-passing. Otherwise, we can allocate the user-defined LP data
422 * structure here and simply copy the necessary information. This is the
423 * only place the user has to sorry about this distinction between
424 * configurations. If running sequentially and using the default data
425 * structure, nothing needs to be modified in here.
426 \*===========================================================================*/
427
428 int user_send_cp_data(void *user, void **user_cp)
429 {
430 /* This gives you access to the user data structure. */
431 mpp_problem *mpp = (mpp_problem *) user;
432
433 #if defined(COMPILE_IN_TM) && defined(COMPILE_IN_LP) && defined (COMPILE_IN_CP)
434
435 *user_cp = mpp;
436
437 #else
438 /* Here, we send that data using message passing and the rest is
439 done in user_receive_cp_data() in the CP process */
440 #endif
441
442 return(USER_SUCCESS);
443 }
444
445 /*===========================================================================*/
446
447 /*===========================================================================*\
448 * Generally, this function is not needed but you might find some use
449 * for it. Someone did :).
450 \*===========================================================================*/
451
452 int user_process_own_messages(void *user, int msgtag)
453 {
454 return(USER_DEFAULT);
455 }
456
457 /*===========================================================================*/
458
459 /*===========================================================================*\
460 * This is the user's chance to display the solution in whatever
461 * manner desired. Change the return value to USER_NO_PP if you want to
462 * display the solution yourself. A return value of USER_AND_PP will cause the
463 * default solution display routine to be executed, even if the user displays
464 * the solution as well.
465 \*===========================================================================*/
466
467 int user_display_solution(void *user, double lpetol, int varnum, int *indices,
468 double *values, double objval)
469 {
470 return(USER_DEFAULT);
471 }
472
473 /*===========================================================================*/
474
475 /*===========================================================================*\
476 * This is a debugging feature which might
477 * allow you to find out why a known feasible solution is being cut off.
478 \*===========================================================================*/
479
480 int user_send_feas_sol(void *user, int *feas_sol_size, int **feas_sol)
481 {
482 #ifdef TRACE_PATH
483
484 #endif
485 return(USER_DEFAULT);
486 }
487
488 /*===========================================================================*/
489
490 /*===========================================================================*\
491 * This function frees everything.
492 \*===========================================================================*/
493
494 int user_free_master(void **user)
495 {
496 /* This gives you access to the user data structure. */
497 mpp_problem *mpp = (mpp_problem *) (*user);
498
499 FREE(mpp->cost);
500 FREE(mpp->head);
501 FREE(mpp->tail);
502 FREE(mpp->type);
503 if(!mpp->par.test){
504 FREE(mpp);
505 }
506 return(USER_SUCCESS);
507 }
508 /*===========================================================================*/
509
510 /*===========================================================================*\
511 * This function is used to lift the user created cuts during warm starting *
512 \*===========================================================================*/
513
514 int user_ws_update_cuts (void *user, int *size, char **coef, double * rhs,
515 char *sense, char type, int new_col_num,
516 int change_type)
517 {
518 return(USER_DEFAULT);
519 }
520
521 /*===========================================================================*/
522
523