Debian Codegraph @

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