Debian Codegraph @

SYMPHONY/Applications/USER/src/Master/user_master.c

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