Debian Codegraph @

SYMPHONY/Applications/MATCH/src/Master/user_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 Matching Problem. */
6 /* */
7 /* (c) Copyright 2005-2007 Michael Trick and Ted Ralphs. All Rights Reserved.*/
8 /* */
9 /* This application was originally written by Michael Trick and was modified */
10 /* 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 /* MATCH include files */
28 #include "user.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 /* Don't need this */
62 #if 0
63 user_problem *prob = (user_problem *) calloc(1, sizeof(user_problem));
64
65 *user = prob;
66 #endif
67
68 return(USER_DEFAULT);
69 }
70
71 /*===========================================================================*/
72
73 /*===========================================================================*\
74 * Parse the user options and read in parameters from the parameter file
75 * given on the command line
76 \*===========================================================================*/
77
78 int user_readparams(void *user, char *filename, int argc, char **argv)
79 {
80
81 FILE *f;
82 char line[50], key[50], value[50], c, tmp;
83 int i;
84
85 /* This gives you access to the user data structure*/
86 user_problem *prob = (user_problem *) user;
87 user_parameters *par = &(prob->par);
88
89 /* This code is just a template for customization. Uncomment to use.*/
90
91 #if 0
92
93 if (strcmp(filename, "")){
94 if ((f = fopen(filename, "r")) == NULL){
95 printf("SYMPHONY: file %s can't be opened\n", filename);
96 exit(1); /*error check for existence of parameter file*/
97 }
98
99 /* Here you can read in the parameter settings from the file. See the
100 function bc_readparams() for an example of how this is done. */
101 while(NULL != fgets(line, MAX_LINE_LENGTH, f)){ /*read in parameters*/
102 strcpy(key, "");
103 sscanf(line, "%s%s", key, value);
104
105 if (strcmp(key, "input_file") == 0){
106 par->infile[MAX_FILE_NAME_LENGTH] = 0;
107 strncpy(par->infile, value, MAX_FILE_NAME_LENGTH);
108 }
109 }
110
111 fclose(f);
112 }
113 #endif
114
115 /* Here you can parse the command line for options. By convention, the
116 users options should be capital letters */
117
118 for (i = 1; i < argc; i++){
119 sscanf(argv[i], "%c %c", &tmp, &c);
120 if (tmp != '-')
121 continue;
122 switch (c) {
123 case 'H':
124 user_usage();
125 exit(0);
126 break;
127 case 'F':
128 strncpy(par->infile, argv[++i], MAX_FILE_NAME_LENGTH);
129 break;
130 case 'T':
131 par->test = TRUE;
132 if(i+1 < argc){
133 sscanf(argv[i+1], "%c", &tmp);
134 if(tmp != '-'){
135 strncpy(par->test_dir, argv[++i],MAX_FILE_NAME_LENGTH);
136 }
137 }
138 break;
139
140 };
141 }
142
143 return(USER_SUCCESS);
144 }
145
146 /*===========================================================================*/
147
148 /*===========================================================================*\
149 * Read in the data file, whose name was given in the parameter file.
150 * This file contains instance data. Right now, this function is set up to
151 * read in just the number of columns and number of rows from the file.
152 * Add more data as needed to describe the instance and set up the LP
153 * relaxation.
154 \*===========================================================================*/
155
156 int user_io(void *user)
157 {
158 /* This code is just a template for customization. Uncomment to use.*/
159 # if 0
160 /* This gives you access to the user data structure. */
161 user_problem *prob = (user_problem *) user;
162 user_parameters *par = &(prob->par);
163 char *infile = par->infile;
164 FILE *f = NULL;
165 int i, j;
166
167 if ((f = fopen(infile, "r")) == NULL){
168 printf("Readparams: file %s can't be opened\n", infile);
169 return(USER_ERROR); /*error check for existence of parameter file*/
170 }
171
172 /* Read in the costs */
173 fscanf(f,"%d",&(prob->nnodes));
174 for (i = 0; i < prob->nnodes; i++)
175 for (j = 0; j < prob->nnodes; j++)
176 fscanf(f, "%d", &(prob->cost[i][j]));
177
178 prob->colnum = (prob->nnodes)*(prob->nnodes-1)/2;
179 prob->rownum = prob->nnodes;
180
181 #endif
182 return(USER_SUCCESS);
183 }
184
185 /*===========================================================================*/
186
187 /*===========================================================================*\
188 * Here is where the heuristics are performed and an upper bound is calculated.
189 * An upper bound can also be specified in the parameter file. This function
190 * need not be filled in if no upper bounding is done.
191 \*===========================================================================*/
192
193 int user_start_heurs(void *user, double *ub, double *ub_estimate)
194 {
195 return(USER_DEFAULT);
196 }
197
198 /*===========================================================================*/
199
200 /*===========================================================================*\
201 * If graph drawing will be used, the user must initialize the drawing
202 * window here. This function need not be filled in.
203 \*===========================================================================*/
204
205 int user_init_draw_graph(void *user, int dg_id)
206 {
207 return(USER_DEFAULT);
208 }
209
210 /*===========================================================================*/
211
212 /*===========================================================================*\
213 * This is the subroutine where the user specifies which variables are to be
214 * in the base set and which variables are to be active in the root node but
215 * not in the base set (these are called the "extra variables"). This is done
216 * by listing the indices of the corresponding variables in arrays named
217 * "basevars" and extravars below.
218 *
219 * The base set of variables form the core that is never removed from the LP
220 * relaxation. Extra variables, on the other hand, can be removed if they are
221 * fixed by reduced cost or by logic-based rules. Allowing the removal of
222 * variables from the relaxation can lead to efficiencies, but there is a
223 * price to pay in terms of extra bookkeeping. If possible, it is a good idea
224 * to form a base set of variables consisting of those that are "likely" to be
225 * present in some optimal solution. If this is not possible, the simplest
226 * approach is just to put all the variables in the extra set, which allows
227 * them all to be fixed by reduced cost if possible. This is implemented below
228 * as an example.
229 *
230 * Note that each variable must have a unique user index by which the variable
231 * can be identified later. Note also that it is possible to have variables
232 * that are neither in the base set or active in the root node by using column
233 * generation and filling out the function user_generate_column().
234 \*===========================================================================*/
235
236 int user_initialize_root_node(void *user, int *basevarnum, int **basevars,
237 int *basecutnum, int *extravarnum,
238 int **extravars, char *obj_sense,
239 double *obj_offset, char ***colnames,
240 int *colgen_strat)
241 {
242 return(USER_DEFAULT);
243 }
244
245 /*===========================================================================*/
246
247 /*===========================================================================*\
248 * Receive the feasible solution. Doesn't need to be filled in.
249 \*===========================================================================*/
250
251 int user_receive_feasible_solution(void *user, int msgtag, double cost,
252 int numvars, int *indices, double *values)
253 {
254 return(USER_DEFAULT);
255 }
256
257 /*===========================================================================*/
258
259 /*===========================================================================*\
260 * Here, we send the necessary data to the LP process. Notice that
261 * there are two cases to deal with. If the LP or the TM are running
262 * as separate processes, then we have to send the data by
263 * message-passing. Otherwise, we can allocate the user-defined LP data
264 * structure here and simply copy the necessary information. This is the
265 * only place the user has to sorry about this distinction between
266 * configurations. If running sequentially and using the default data
267 * structure, nothing needs to be modified in here.
268 \*===========================================================================*/
269
270 int user_send_lp_data(void *user, void **user_lp)
271 {
272 /* This gives you access to the user data structure. */
273 user_problem *prob = (user_problem *) user;
274
275 #if defined(COMPILE_IN_TM) && defined(COMPILE_IN_LP)
276 /* This is is the case when we are copying data directly because the LP is
277 not running separately. The easiest thing to do here is just to use the
278 same user data structure in both the master and the LP. Then this
279 subroutine would simply consist of the line
280
281 *user_lp = user;
282
283 Otherwise, this code should be virtually
284 identical to that of user_receive_lp_data() in the LP process.*/
285
286 *user_lp = user;
287 #else
288 /* Here, we send that data using message passing and the rest is
289 done in user_receive_lp_data() in the LP process */
290 #endif
291 return(USER_SUCCESS);
292 }
293
294 /*===========================================================================*/
295
296 /*===========================================================================*\
297 * Here, we send the necessary data to the CG process. Notice that
298 * there are two cases to deal with. If the CG, LP, or the TM are running
299 * as separate processes, then we have to send the data by
300 * message-passing. Otherwise, we can allocate the user-defined LP data
301 * structure here and simply copy the necessary information. This is the
302 * only place the user has to sorry about this distinction between
303 * configurations. If running sequentially and using the default data
304 * structure, nothing needs to be modified in here.
305 \*===========================================================================*/
306
307 int user_send_cg_data(void *user, void **user_cg)
308 {
309 /* This gives you access to the user data structure. */
310 user_problem *prob = (user_problem *) user;
311
312 #if defined(COMPILE_IN_TM) && defined(COMPILE_IN_LP) && defined (COMPILE_IN_CG)
313 /* This is is the case when we are copying data directly because
314 the CG is not running separately. The easiest thing to do here is just
315 to use the same user data structure in both the master and the cut
316 generator. Then this subroutine would simply consist of
317
318 *user_cg = user;
319
320 Otherwise, this code should be virtually
321 identical to that of user_receive_cg_data() in the CG process.*/
322
323 *user_cg = user;
324 #ifdef CHECK_CUT_VALIDITY
325 /* Send the feasible solution here */
326 #endif
327 #else
328 /* Here, we send that data using message passing and the rest is
329 done in user_receive_cg_data() in the CG process */
330 #ifdef CHECK_CUT_VALIDITY
331 /* Send the feasible solution here */
332 #endif
333 #endif
334 return(USER_SUCCESS);
335 }
336
337 /*===========================================================================*/
338
339 /*===========================================================================*\
340 * Here, we send the necessary data to the CP process. Notice that
341 * there are two cases to deal with. If the CP, 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_cp_data(void *user, void **user_cp)
351 {
352 return(USER_DEFAULT);
353 }
354
355 /*===========================================================================*/
356
357 /*===========================================================================*\
358 * Generally, this function is not needed but you might find some use
359 * for it. Someone did :).
360 \*===========================================================================*/
361
362 int user_process_own_messages(void *user, int msgtag)
363 {
364 return(USER_DEFAULT);
365 }
366
367 /*===========================================================================*/
368
369 /*===========================================================================*\
370 * This is the user's chance to display the solution in whatever
371 * manner desired. A return value of USER_DEFAULT will cause the
372 * default solution display routine to be executed, even if the user displays
373 * the solution as well.
374 \*===========================================================================*/
375
376 int user_display_solution(void *user, double lpetol, int varnum, int *indices,
377 double *values, double objval)
378 {
379 /* This gives you access to the user data structure. */
380 user_problem *prob = (user_problem *) user;
381 int index;
382
383 for (index = 0; index < varnum; index++){
384 if (values[index] > lpetol) {
385 printf("%2d matched with %2d at cost %6d\n",
386 prob->match1[indices[index]],
387 prob->match2[indices[index]],
388 prob->cost[prob->match1[indices[index]]]
389 [prob->match2[indices[index]]]);
390 }
391 }
392
393 return(USER_SUCCESS);
394 }
395
396 /*===========================================================================*/
397
398 /*===========================================================================*\
399 * This is a debugging feature which might
400 * allow you to find out why a known feasible solution is being cut off.
401 \*===========================================================================*/
402
403 int user_send_feas_sol(void *user, int *feas_sol_size, int **feas_sol)
404 {
405 #ifdef TRACE_PATH
406
407 #endif
408 return(USER_DEFAULT);
409 }
410
411 /*===========================================================================*/
412
413 /*===========================================================================*\
414 * This function frees everything.
415 \*===========================================================================*/
416
417 int user_free_master(void **user)
418 {
419 user_problem *prob = (user_problem *) calloc(1, sizeof(user_problem));
420
421 FREE(prob);
422
423 return(USER_SUCCESS);
424 }
425
426 /*===========================================================================*/
427
428 /*===========================================================================*\
429 * This function is used to lift the user created cuts during warm starting *
430 /*===========================================================================*/
431
432 int user_ws_update_cuts (void *user, int *size, char **coef, double * rhs,
433 char *sense, char type, int new_col_num,
434 int change_type)
435 {
436 return(USER_DEFAULT);
437 }
438 /*===========================================================================*/
439
440
441
442