Debian Codegraph @

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