Debian Codegraph @

SYMPHONY/Applications/SPP/src/Master/spp_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 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_constants.h"
24 #include "sym_macros.h"
25 #include "sym_proccomm.h"
26 #include "sym_master_u.h"
27
28 /* SPP include files */
29 #include "spp.h"
30 #include "spp_common.h"
31 #include "spp_master_functions.h"
32
33 /*===========================================================================*\
34 * This file contains stubs for the user-written functions for the master
35 * process. The primary function that has to be filled in here is user_io(),
36 * where the data for the instance is read in and the user data structure
37 * that stores the instance data filled out (this data structure is defined
38 * in user.h). Other than that, the default routines should work fine.
39 \*===========================================================================*/
40
41 /*===========================================================================*/
42
43 /*===========================================================================*\
44 * This function gives help on command-line switches defined by the user.
45 * All user switches have capital letters by convention.
46 \*===========================================================================*/
47
48 void user_usage(void){
49 printf("master [ -H ] [ -F file ] \n\t%s\n\t%s\n",
50 "-H: help (user switches)",
51 "-F file: problem instance data is in 'file'");
52 }
53
54 /*===========================================================================*/
55
56 /*===========================================================================*\
57 * Initialize user-defined data structures. This basically consists of
58 * allocating the memory. If you are using the default data structure,
59 * nothing needs to be changed here.
60 \*===========================================================================*/
61
62 int user_initialize(void **user)
63 {
64 spp_problem *spp = (spp_problem *) calloc(1, sizeof(spp_problem));
65
66 *user = spp;
67
68 spp->par = (spp_parameters *) calloc(1, sizeof(spp_parameters));
69 spp->stat = (statistics *) calloc(2, sizeof(statistics));
70
71 return(USER_SUCCESS);
72 }
73
74 /*===========================================================================*/
75
76 /*===========================================================================*\
77 * Parse the user options Read in parameters from the parameter file given on the command line
78 \*===========================================================================*/
79
80 int user_readparams(void *user, char *filename, int argc, char **argv)
81 {
82 char c, tmp;
83 int i;
84 /* This gives you access to the user data structure*/
85 spp_problem *spp = (spp_problem *) user;
86 spp_parameters *par = spp->par;
87
88 spp_read_params(spp, filename);
89
90 spp_print_params(spp);
91
92 /* Here you can parse the command line for options. By convention, the
93 users options should be capital letters */
94
95 for (i = 1; i < argc; i++){
96 sscanf(argv[i], "%c %c", &tmp, &c);
97 if (tmp != '-')
98 continue;
99 switch (c) {
100 case 'H':
101 user_usage();
102 exit(0);
103 break;
104 case 'F':
105 strncpy(par->infile, argv[++i], MAX_FILE_NAME_LENGTH);
106 break;
107 case 'T':
108 par->test = TRUE;
109 if(i+1 < argc){
110 sscanf(argv[i+1], "%c", &tmp);
111 if(tmp != '-'){
112 strncpy(par->test_dir, argv[++i],MAX_FILE_NAME_LENGTH);
113 }
114 }
115 break;
116 };
117 }
118
119 return(USER_NO_PP);
120 }
121
122 /*===========================================================================*/
123
124 /*===========================================================================*\
125 * Read in the data file, whose name was given in the parameter file.
126 * This file contains instance data. Right now, this function is set up to
127 * read in just the number of columns and number of rows from the file.
128 * Add more data as needed to describe the instance and set up the LP
129 * relaxation.
130 \*===========================================================================*/
131
132 int user_io(void *user)
133 {
134 /* This gives you access to the user data structure. */
135 spp_problem *spp = (spp_problem *) user;
136 int colnum, rownum;
137
138 spp_read_input(spp);
139
140 colnum = spp->cmatrix->colnum;
141 rownum = spp->cmatrix->rownum;
142 spp->cmatrix->active_colnum = colnum;
143 spp->cmatrix->col_deleted = (char *) calloc(colnum/BITSPERBYTE + 1, CSIZE);
144 spp->feasibility = SPP_FEASIBILITY_NOT_KNOWN;
145 spp->feas_sol = (int *) malloc(rownum * ISIZE);
146
147 /* order cols into lex ascending order */
148 spp_fix_lex(spp);
149
150 return(USER_SUCCESS);
151 }
152
153 /*===========================================================================*/
154
155 /*===========================================================================*\
156 * Here is where the heuristics are performed and an upper bound is calculated.
157 * An upper bound can also be specified in the parameter file. This function
158 * need not be filled in if no upper bounding is done.
159 \*===========================================================================*/
160
161 int user_start_heurs(void *user, double *ub, double *ub_estimate)
162 {
163 return(USER_DEFAULT);
164 }
165
166 /*===========================================================================*/
167
168 /*===========================================================================*\
169 * If graph drawing will be used, the user must initialize the drawing
170 * window here. This function need not be filled in.
171 \*===========================================================================*/
172
173 int user_init_draw_graph(void *user, int dg_id)
174 {
175 return(USER_DEFAULT);
176 }
177
178 /*===========================================================================*/
179
180 /*===========================================================================*\
181 * This is the subroutine where the user specifies which variables are to be
182 * in the base set and which variables are to be active in the root node but
183 * not in the base set (these are called the "extra variables"). This is done
184 * by listing the indices of the corresponding variables in arrays named
185 * "basevars" and extravars below.
186 *
187 * The base set of variables form the core that is never removed from the LP
188 * relaxation. Extra variables, on the other hand, can be removed if they are
189 * fixed by reduced cost or by logic-based rules. Allowing the removal of
190 * variables from the relaxation can lead to efficiencies, but there is a
191 * price to pay in terms of extra bookkeeping. If possible, it is a good idea
192 * to form a base set of variables consisting of those that are "likely" to be
193 * present in some optimal solution. If this is not possible, the simplest
194 * approach is just to put all the variables in the extra set, which allows
195 * them all to be fixed by reduced cost if possible. This is implemented below
196 * as an example.
197 *
198 * Note that each variable must have a unique user index by which the variable
199 * can be identified later. Note also that it is possible to have variables
200 * that are neither in the base set or active in the root node by using column
201 * generation and filling out the function user_generate_column().
202 \*===========================================================================*/
203
204 int user_initialize_root_node(void *user, int *basevarnum, int **basevars,
205 int *basecutnum, int *extravarnum, int **extravars,
206 char *obj_sense, double *obj_offset,
207 char ***colnames, int *colgen_strat)
208 {
209 /* This gives you access to the user data structure. */
210 spp_problem *spp = (spp_problem *) user;
211 int i;
212 int *vars, varnum;
213
214 /* Since we don't know how to form a good set of base variables, we'll put
215 all the variables in the extra set */
216
217 /* Set the number of extra variables*/
218 varnum = *extravarnum = spp->cmatrix->colnum;
219
220 /* Put all the variables in the extra set */
221 vars = *extravars = (int *) malloc(varnum * ISIZE);
222 for (i = 0; i < varnum; i++){
223 vars[i] = i;
224 }
225
226 /* Set the number of rows in the initial formulation */
227 *basecutnum = spp->cmatrix->rownum;
228
229 /* The set base variables will be empty */
230 *basevarnum = 0;
231 *basevars = NULL;
232
233 return(USER_SUCCESS);
234 }
235
236 /*===========================================================================*/
237
238 /*===========================================================================*\
239 * Receive the feasible solution. Doesn't need to be filled in.
240 \*===========================================================================*/
241
242 int user_receive_feasible_solution(void *user, int msgtag, double cost,
243 int numvars, int *indices, double *values)
244 {
245 spp_problem *spp = (spp_problem *)user;
246 int *colnames = spp->cmatrix->colnames;
247 int i;
248
249 /* by default we are sent the user indices of nonzero variables.
250 choose PACK_NONZEROS in user_pack_feasible_solution in LP. */
251
252 if (spp->feasibility == SPP_FEASIBLE && cost >= spp->feas_value)
253 return(USER_SUCCESS);
254
255 spp->feasibility = SPP_FEASIBLE;
256 spp->feas_value = cost;
257 spp->feas_sol_length = numvars;
258 for (i = 0; i < numvars; i++)
259 spp->feas_sol[i] = colnames[indices[i]];
260
261 return(USER_SUCCESS);
262 }
263
264 /*===========================================================================*/
265
266 /*===========================================================================*\
267 * Here, we send the necessary data to the LP process. Notice that
268 * there are two cases to deal with. If the LP or the TM are running
269 * as separate processes, then we have to send the data by
270 * message-passing. Otherwise, we can allocate the user-defined LP data
271 * structure here and simply copy the necessary information. This is the
272 * only place the user has to sorry about this distinction between
273 * configurations. If running sequentially and using the default data
274 * structure, nothing needs to be modified in here.
275 \*===========================================================================*/
276
277 int user_send_lp_data(void *user, void **user_lp)
278 {
279 /* This gives you access to the user data structure. */
280 spp_problem *spp = (spp_problem *) user;
281
282 #if defined(COMPILE_IN_TM) && defined(COMPILE_IN_LP)
283 /* This is is the case when we are copying data directly because the LP is
284 not running separately. The easiest thing to do here is just to use the
285 same user data structure in both the master and the LP. Then this
286 subroutine would simply consist of the line
287
288 *user_lp = user;
289
290 Otherwise, this code should be virtually
291 identical to that of user_receive_lp_data() in the LP process.*/
292
293 *user_lp = spp;
294 #else
295 /* Here, we send that data using message passing and the rest is
296 done in user_receive_lp_data() in the LP process */
297
298 col_ordered *m = spp->cmatrix;
299
300 send_char_array((char *)spp->par, sizeof(spp_parameters));
301 send_int_array(&m->colnum, 1);
302 send_int_array(&m->rownum, 1);
303 send_int_array(&m->nzcnt, 1);
304 send_int_array(m->colnames, m->colnum);
305 send_dbl_array(m->obj, m->colnum);
306 send_int_array(m->matbeg, (m->colnum + 1));
307 send_char_array((char *)m->matind, m->nzcnt * sizeof(row_ind_type));
308
309 #endif
310
311 return(USER_SUCCESS);
312 }
313
314 /*===========================================================================*/
315
316 /*===========================================================================*\
317 * Here, we send the necessary data to the CG process. Notice that
318 * there are two cases to deal with. If the CG, LP, or the TM are running
319 * as separate processes, then we have to send the data by
320 * message-passing. Otherwise, we can allocate the user-defined LP data
321 * structure here and simply copy the necessary information. This is the
322 * only place the user has to sorry about this distinction between
323 * configurations. If running sequentially and using the default data
324 * structure, nothing needs to be modified in here.
325 \*===========================================================================*/
326
327 int user_send_cg_data(void *user, void **user_cg)
328 {
329 return(USER_DEFAULT);
330 }
331
332 /*===========================================================================*/
333
334 /*===========================================================================*\
335 * Here, we send the necessary data to the CP process. Notice that
336 * there are two cases to deal with. If the CP, LP, or the TM are running
337 * as separate processes, then we have to send the data by
338 * message-passing. Otherwise, we can allocate the user-defined LP data
339 * structure here and simply copy the necessary information. This is the
340 * only place the user has to sorry about this distinction between
341 * configurations. If running sequentially and using the default data
342 * structure, nothing needs to be modified in here.
343 \*===========================================================================*/
344
345 int user_send_cp_data(void *user, void **user_cp)
346 {
347 return(USER_DEFAULT);
348 }
349
350 /*===========================================================================*/
351
352 /*===========================================================================*\
353 * Generally, this function is not needed but you might find some use
354 * for it. Someone did :).
355 \*===========================================================================*/
356
357 int user_process_own_messages(void *user, int msgtag)
358 {
359 return(USER_DEFAULT);
360 }
361
362 /*===========================================================================*/
363
364 /*===========================================================================*\
365 * This is the user's chance to display the solution in whatever
366 * manner desired.
367 \*===========================================================================*/
368
369 int user_display_solution(void *user, double lpetol, int varnum,
370 int *indices, double *values, double objval)
371 {
372 spp_problem *spp = (spp_problem *)user;
373 int *colnames = spp->cmatrix->colnames;
374 int i;
375
376 printf("\nBest Solution Found:\n");
377 for (i = 0; i < varnum; i++)
378 printf("%i \n", colnames[indices[i]]);
379 printf("\n\n\n");
380
381 return(USER_NO_PP);
382 }
383
384 /*===========================================================================*/
385
386 /*===========================================================================*\
387 * This is a debugging feature which might
388 * allow you to find out why a known feasible solution is being cut off.
389 \*===========================================================================*/
390
391 int user_send_feas_sol(void *user, int *feas_sol_size, int **feas_sol)
392 {
393 #ifdef TRACE_PATH
394
395 #endif
396 return(USER_DEFAULT);
397 }
398
399 /*===========================================================================*/
400
401 /*===========================================================================*\
402 * This function frees everything.
403 \*===========================================================================*/
404
405 int user_free_master(void **user)
406 {
407 spp_problem *spp = (spp_problem *) (*user);
408
409 FREE(spp->feas_sol);
410 spp_free_cmatrix(spp->cmatrix);
411 FREE(spp->cmatrix);
412 if(!spp->par->test){
413 FREE(spp->par);
414 FREE(spp->stat);
415 FREE(*user);
416 }
417 return(USER_SUCCESS);
418 }
419
420 /*===========================================================================*/
421
422 /*===========================================================================*\
423 * This function is used to lift the user created cuts during warm starting *
424 /*===========================================================================*/
425
426 int user_ws_update_cuts (void *user, int *size, char **coef, double * rhs,
427 char *sense, char type, int new_col_num,
428 int change_type)
429 {
430 return(USER_DEFAULT);
431 }
432
433 /*===========================================================================*/
434
435
436
437
438