Debian Codegraph @

SYMPHONY/Applications/SPP/src/LP/spp_lp.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 <memory.h>
20
21 /* SYMPHONY include files */
22 #include "sym_constants.h"
23 #include "sym_macros.h"
24 #include "sym_proccomm.h"
25 #include "sym_lp_u.h"
26
27 /* SPP include files */
28 #include "spp.h"
29 #include "spp_common.h"
30
31 /*===========================================================================*/
32
33 /*===========================================================================*\
34 * This file contains the user-written functions for the LP process.
35 \*===========================================================================*/
36
37 /*===========================================================================*\
38 * Here is where the user must receive all of the data sent from
39 * user_send_lp_data() and set up data structures. Note that this function is
40 * only called if one of COMPILE_IN_LP or COMPILE_IN_TM is FALSE. For
41 * sequential computation, nothing is needed here.
42 \*===========================================================================*/
43
44 int user_receive_lp_data(void **user)
45 {
46 spp_problem *spp;
47 col_ordered *m;
48 int colnum, info;
49
50 spp = (spp_problem *) calloc(1, sizeof(spp_problem));
51 *user = spp;
52
53 spp->par = (spp_parameters *) calloc(1, sizeof(spp_parameters));
54
55 receive_char_array((char *)spp->par, sizeof(spp_parameters));
56 m = spp->cmatrix = (col_ordered *) calloc(1, sizeof(col_ordered));
57 receive_int_array(&m->colnum, 1);
58 colnum = m->active_colnum = m->colnum;
59 receive_int_array(&m->rownum, 1);
60 receive_int_array(&m->nzcnt, 1);
61 m->colnames = (int *) malloc(colnum * ISIZE);
62 m->col_deleted = (char *) calloc(colnum/BITSPERBYTE + 1, CSIZE); /*calloc!*/
63 m->obj = (double *) malloc(colnum * DSIZE);
64 m->matbeg = (int *) malloc((colnum + 1) * ISIZE);
65 m->matind = (row_ind_type *) malloc(m->nzcnt * sizeof(row_ind_type));
66 receive_int_array(m->colnames, colnum);
67 receive_dbl_array(m->obj, colnum);
68 receive_int_array(m->matbeg, (colnum + 1));
69 receive_char_array((char *)m->matind, m->nzcnt * sizeof(row_ind_type));
70
71 return(USER_SUCCESS);
72 }
73
74 /*===========================================================================*/
75
76 /*===========================================================================*\
77 * Here is where the user must create the initial LP relaxation for
78 * each search node. Basically, this involves constructing the base matrix in
79 * column ordered format. See the documentation for an explanation of how to
80 * fill out this function.
81 \*===========================================================================*/
82
83 int user_create_subproblem(void *user, int *indices, MIPdesc *mip,
84 int *maxn, int *maxm, int *maxnz)
85 {
86 spp_problem *spp = (spp_problem *) user;
87 col_ordered *cm = spp->cmatrix;
88 int i;
89
90 mip->nz = cm->nzcnt;
91 *maxn = mip->n; /* note that the number of columns cannot increase */
92 *maxm = 2 * mip->m;
93 *maxnz = mip->nz + ((*maxm) * (*maxn) / 100);
94
95 mip->matbeg = (int *) malloc((mip->n + 1) * ISIZE);
96 mip->matind = (int *) malloc(mip->nz * ISIZE);
97 mip->matval = (double *) malloc(mip->nz * DSIZE);
98 mip->obj = (double *) malloc(mip->n * DSIZE);
99 mip->lb = (double *) calloc(mip->n, DSIZE);
100 mip->ub = (double *) malloc(mip->n * DSIZE);
101 mip->rhs = (double *) malloc(mip->m * DSIZE);
102 mip->sense = (char *) malloc(mip->m * CSIZE);
103 mip->rngval = (double *) malloc(mip->m * DSIZE);
104 mip->is_int = (char *) calloc (mip->n, CSIZE);
105
106 memcpy((char *) mip->matbeg, (char *) cm->matbeg, (cm->colnum+1) * ISIZE);
107 memcpy((char *) mip->obj, (char *) cm->obj, cm->colnum * DSIZE);
108
109 for (i = cm->nzcnt - 1; i >= 0; i--) {
110 mip->matind[i] = cm->matind[i]; /* cannot memcpy b/c int vs. short */
111 mip->matval[i] = 1.0;
112 }
113
114 for (i = mip->n - 1; i >= 0; --i){
115 mip->is_int[i] = TRUE;
116 mip->ub[i] = 1.0;
117 /* mip->lb[i] = 0.0; */ /* Set by calloc */
118 }
119
120 for (i = mip->m - 1; i >= 0; i--) {
121 mip->rhs[i] = 1.0;
122 mip->sense[i] = 'E';
123 }
124
125 return(USER_SUCCESS);
126 }
127
128
129 /*===========================================================================*/
130
131 /*===========================================================================*\
132 * This function takes an LP solution and checks it for feasibility. By
133 * default, SYMPHONY checks for integrality. If any integral solution for your
134 * problem is feasible, then nothing needs to be done here.
135 \*===========================================================================*/
136
137 int user_is_feasible(void *user, double lpetol, int varnum, int *indices,
138 double *values, int *feasible, double *objval,
139 char branching, double *heur_solution)
140 {
141 return(TEST_ZERO_ONE);
142 }
143
144 /*===========================================================================*/
145
146 /*===========================================================================*\
147 * Here, the user can specify a special routine for sending back the feasible
148 * solution. This need not be used unless there is a special format the user
149 * wants the solution in. For sequential computation, you can use this routine
150 * to interpret and store the feasible solution whenever one is found.
151 \*===========================================================================*/
152
153 int user_send_feasible_solution(void *user, double lpetol, int varnum,
154 int *indices, double *values)
155 {
156 return(USER_DEFAULT);
157 }
158
159
160 /*===========================================================================*/
161
162 /*===========================================================================*\
163 * This function graphically displays the current fractional solution
164 * This is done using the Interactive Graph Drawing program, if it is used.
165 \*===========================================================================*/
166
167 int user_display_lp_solution(void *user, int which_sol, int varnum,
168 int *indices, double *values)
169 {
170 /* note that names of variables in the current solution will not be
171 displayed by the default option */
172 return(which_sol == DISP_RELAXED_SOLUTION ? DISP_NOTHING : DISP_NZ_INT);
173 }
174
175 /*===========================================================================*/
176
177 /*===========================================================================*\
178 * You can add whatever information you want about a node to help you
179 * recreate it. I don't have a use for it, but maybe you will.
180 \*===========================================================================*/
181
182 int user_add_to_desc(void *user, int *desc_size, char **desc)
183 {
184 return(USER_DEFAULT);
185 }
186
187 /*===========================================================================*/
188
189 /*===========================================================================*\
190 * Compare cuts to see if they are the same. We use the default, which
191 * is just comparing byte by byte.
192 \*===========================================================================*/
193
194 int user_same_cuts(void *user, cut_data *cut1, cut_data *cut2, int *same_cuts)
195 {
196 return(USER_DEFAULT);
197 }
198
199 /*===========================================================================*/
200
201 /*===========================================================================*\
202 * This function receives a cut, unpacks it, and adds it to the set of
203 * rows to be added to the LP. Only used if cutting planes are generated.
204 \*===========================================================================*/
205
206 int user_unpack_cuts(void *user, int from, int type, int varnum,
207 var_desc **vars, int cutnum, cut_data **cuts,
208 int *new_row_num, waiting_row ***new_rows)
209 {
210 /* No cutting planes */
211
212 return(USER_DEFAULT);
213 }
214
215 /*===========================================================================*/
216
217 /*===========================================================================*\
218 * If the user wants to fill in a customized routine for sending and receiving
219 * the LP solution, it can be done here. For most cases, the default routines
220 * are fine.
221 \*===========================================================================*/
222
223 int user_send_lp_solution(void *user, int varnum, var_desc **vars, double *x,
224 int where)
225 {
226 return(USER_DEFAULT);
227 }
228
229 /*===========================================================================*/
230
231 /*===========================================================================*\
232 * This routine does logical fixing of variables
233 \*===========================================================================*/
234
235 int user_logical_fixing(void *user, int varnum, var_desc **vars, double *x,
236 char *status, int *num_fixed)
237 {
238 return(USER_DEFAULT);
239 }
240
241 /*===========================================================================*/
242
243 /*===========================================================================*\
244 * This function generates the 'next' column. Only used for column generation.
245 \*===========================================================================*/
246
247 int user_generate_column(void *user, int generate_what, int cutnum,
248 cut_data **cuts, int prevind, int nextind,
249 int *real_nextind, double *colval, int *colind,
250 int *collen, double *obj, double *lb, double *ub)
251 {
252 return(USER_DEFAULT);
253 }
254
255 /*===========================================================================*/
256
257 /*===========================================================================*\
258 * You might want to print some statistics on the types and quantities
259 * of cuts or something like that.
260 \*===========================================================================*/
261
262 int user_print_stat_on_cuts_added(void *user, int rownum, waiting_row **rows)
263 {
264 return(USER_DEFAULT);
265 }
266
267 /*===========================================================================*/
268
269 /*===========================================================================*\
270 * You might want to eliminate rows from the local pool based on
271 * knowledge of problem structure.
272 \*===========================================================================*/
273
274 int user_purge_waiting_rows(void *user, int rownum, waiting_row **rows,
275 char *delete_rows)
276 {
277 return(USER_DEFAULT);
278 }
279
280 /*===========================================================================*/
281
282 /*===========================================================================*\
283 * The user might want to generate cuts in the LP using information
284 * about the current tableau, etc. This is for advanced users only.
285 \*===========================================================================*/
286
287 int user_generate_cuts_in_lp(void *user, LPdata *lp_data, int varnum,
288 var_desc **vars, double *x,
289 int *new_row_num, cut_data ***cuts)
290 {
291 return(USER_DEFAULT);
292 }
293
294 /*===========================================================================*/
295
296 /*===========================================================================*\
297 * Free all the user data structures
298 \*===========================================================================*/
299
300 int user_free_lp(void **user)
301 {
302 spp_problem *spp = (spp_problem *)(*user);
303
304 #ifndef COMPILE_IN_LP
305 FREE(spp->par);
306 spp_free_cmatrix(spp->cmatrix);
307 FREE(*user);
308 #endif
309
310 return(USER_SUCCESS);
311
312 }
313
314 /*===========================================================================*/
315