Debian Codegraph @

SYMPHONY/Applications/MPP/src/LP/mpp_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 Mixed Postman Problem. */
6 /* */
7 /* (c) Copyright 2005-2007 Lehigh University. All Rights Reserved. */
8 /* */
9 /* This application was originally developed by Andrew Hofmann and was */
10 /* modified 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 /* MPP include files */
26 #include "mpp.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 mpp_problem *mpp = (mpp_problem *) user;
59
60 int i, j, ind;
61
62 /* set up the inital LP data */
63
64 mip->nz = (6 * mpp->numedges)+ (2 * mpp->numarcs);
65
66 /* Estimate the maximum number of nonzeros */
67 *maxm = 2 * mip->m;
68 *maxn = mip->n;
69 *maxnz = mip->nz + ((*maxm) * (*maxn) / 10);
70
71 /* Allocate the arrays. These are owned by SYMPHONY after returning. */
72 mip->matbeg = (int *) malloc((mip->n + 1) * ISIZE);
73 mip->matind = (int *) malloc((mip->nz) * ISIZE);
74 mip->matval = (double *) malloc((mip->nz) * DSIZE);
75 mip->obj = (double *) malloc(mip->n * DSIZE);
76 mip->lb = (double *) calloc(mip->n, DSIZE);
77 mip->ub = (double *) malloc(mip->n * DSIZE);
78 mip->rhs = (double *) malloc(mip->m * DSIZE);
79 mip->sense = (char *) malloc(mip->m * CSIZE);
80 mip->rngval = (double *) calloc(mip->m, DSIZE);
81 mip->is_int = (char *) calloc(mip->n, CSIZE);
82
83 for (i = 0, ind = 0; i < mip->n; i++){
84 mip->matbeg[i] = ind;
85 mip->is_int[i] = TRUE;
86 /* indegree equals outdegree constraint */
87 for (j = 0; j <= mpp->numnodes - 1; j++){
88 /* checks to see if node i is the start node of every edge arc */
89 if (mpp->head[i] == j){
90 mip->matind[ind] = j;
91 mip->matval[ind++] = 1;
92 }else if (mpp->tail[i] == j){
93 mip->matind[ind] = j;
94 mip->matval[ind++] = -1;
95 }
96 }
97
98 /* Now the constraint that each edge must be traversed at least once */
99 if (i >= mpp->numarcs){ /* Check to see if it is an edge */
100 if (i < mpp->numarcs + mpp->numedges){
101 mip->matind[ind] = mpp->numnodes + i - mpp->numarcs;
102 }else{
103 mip->matind[ind] = mpp->numnodes + i - (mpp->numarcs +
104 mpp->numedges);
105 }
106 mip->matval[ind++] = 1;
107 /* mip->lb[i] = 0; */ /* Already set to zero from calloc */
108 mip->ub[i] = (double) (mpp->numarcs + mpp->numedges);
109 }else{
110 mip->lb[i] = 1.0;
111 mip->ub[i] = (double) (mpp->numarcs + mpp->numedges);
112 }
113 mip->obj[i] = (double) (mpp->cost[i]);
114 }
115 mip->matbeg[i] = ind;
116
117 /* set the initial right hand side */
118 for (i = 0; i <= mpp->numnodes-1 ; i++){
119 mip->rhs[i] = 0;
120 mip->sense[i] = 'E';
121 }
122 for (i = mpp->numnodes; i <= mpp->numnodes+mpp->numedges-1 ; i++){
123 mip->rhs[i] = 1;
124 mip->sense[i] = 'G';
125 }
126
127 return(USER_SUCCESS);
128 }
129
130
131 /*===========================================================================*/
132
133 /*===========================================================================*\
134 * This function takes an LP solution and checks it for feasibility. By
135 * default, SYMPHONY checks for integrality. If any integral solution for your
136 * problem is feasible, then nothing needs to be done here.
137 \*===========================================================================*/
138
139 int user_is_feasible(void *user, double lpetol, int varnum, int *indices,
140 double *values, int *feasible, double *objval,
141 char branching, double *heur_solution)
142 {
143 return(USER_DEFAULT);
144 }
145
146 /*===========================================================================*/
147
148 /*===========================================================================*\
149 * Here, the user can specify a special routine for sending back the feasible
150 * solution. This need not be used unless there is a special format the user
151 * wants the solution in. For sequential computation, you can use this routine
152 * to interpret and store the feasible solution whenever one is found.
153 \*===========================================================================*/
154
155 int user_send_feasible_solution(void *user, double lpetol, int varnum,
156 int *indices, double *values)
157 {
158 return(USER_DEFAULT);
159 }
160
161
162 /*===========================================================================*/
163
164 /*===========================================================================*\
165 * This function graphically displays the current fractional solution
166 * This is done using the Interactive Graph Drawing program, if it is used.
167 \*===========================================================================*/
168
169 int user_display_lp_solution(void *user, int which_sol, int varnum,
170 int *indices, double *values)
171 {
172 return(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 mpp_problem *mpp = (mpp_problem *)user;
211 int * node_checker;
212 int * cut_holder=NULL;
213 int edge_direction=0;
214 int i, j, nzcnt = 0;
215 waiting_row **row_list = NULL;
216 int *matind = NULL;
217 cut_data *cut;
218 int rhs_count;
219 char *coef;
220 double *matval = NULL;
221 *new_row_num = cutnum;
222 node_checker= (int *) calloc(mpp->numnodes, sizeof(int));
223
224 if (cutnum > 0)
225 *new_rows = row_list = (waiting_row **) calloc (cutnum,
226 sizeof(waiting_row *));
227
228 for (j = 0; j < cutnum; j++){
229 coef = (cut = cuts[j])->coef;
230 cut_holder = (int *) cut->coef;
231
232 cuts[j] = NULL;
233 (row_list[j] = (waiting_row *) malloc(sizeof(waiting_row)))->cut = cut;
234 switch (cut->type){
235 case ODD_CUT:
236 matind = (int *) malloc(varnum * ISIZE);
237 nzcnt = 0;
238 rhs_count = 0;
239 for (i = 0; i <= mpp->numnodes - 1; i++){
240 node_checker[i]=0;
241 }
242 /*make array for 1 if node is in cut, 0 if not*/
243 for (i = 0; i < (cut->size/4); i++){
244 node_checker[cut_holder[i]]=1;
245 }
246 for (i = 0; i <= varnum - 1; i++){
247 if (vars[i]->userind >= mpp->numarcs+mpp->numedges){
248 if (node_checker[mpp->tail[(vars[i]->userind)-mpp->numedges]]==1&&
249 node_checker[mpp->head[(vars[i]->userind)-mpp->numedges]]==0){
250 matind[nzcnt] = i;
251 nzcnt++;
252 rhs_count++;
253 }
254 }else if ((vars[i]->userind >= mpp->numarcs)){
255 if ((node_checker[mpp->tail[vars[i]->userind]] == 1 &&
256 node_checker[mpp->head[vars[i]->userind]] == 0)){
257 matind[nzcnt] = i;
258 nzcnt++;
259 rhs_count++;
260 }
261 }else if (node_checker[mpp->tail[vars[i]->userind]] == 1 &&
262 node_checker[mpp->head[vars[i]->userind]] == 0){
263 matind[nzcnt] = i;
264 nzcnt++;
265 rhs_count++;
266 } else if (node_checker[mpp->tail[vars[i]->userind]] == 0 &&
267 node_checker[mpp->head[vars[i]->userind]] == 1){
268 rhs_count++;
269 }
270 }
271
272 row_list[j]->matind = matind =
273 (int *) realloc((char *)matind, nzcnt*ISIZE);
274 cut->rhs=(rhs_count+1)/2;
275 row_list[j]->nzcnt = nzcnt;
276 row_list[j]->matval = matval = (double *) malloc(nzcnt * DSIZE);
277 for (i = nzcnt-1; i >= 0; i--)
278 matval[i] = 1;
279 cut->branch = ALLOWED_TO_BRANCH_ON;
280 break;
281
282
283 default:
284 printf("Unrecognized cut type!\n");
285 }
286 }
287 FREE(node_checker);
288
289 return(USER_SUCCESS);
290 }
291
292 /*===========================================================================*/
293
294 /*===========================================================================*\
295 * If the user wants to fill in a customized routine for sending and receiving
296 * the LP solution, it can be done here. For most cases, the default routines
297 * are fine.
298 \*===========================================================================*/
299
300 int user_send_lp_solution(void *user, int varnum, var_desc **vars, double *x,
301 int where)
302 {
303 return(USER_DEFAULT);
304 }
305
306 /*===========================================================================*/
307
308 /*===========================================================================*\
309 * This routine does logical fixing of variables
310 \*===========================================================================*/
311
312 int user_logical_fixing(void *user, int varnum, var_desc **vars, double *x,
313 char *status, int *num_fixed)
314 {
315 return(USER_DEFAULT);
316 }
317
318 /*===========================================================================*/
319
320 /*===========================================================================*\
321 * This function generates the 'next' column. Only used for column generation.
322 \*===========================================================================*/
323
324 int user_generate_column(void *user, int generate_what, int cutnum,
325 cut_data **cuts, int prevind, int nextind,
326 int *real_nextind, double *colval, int *colind,
327 int *collen, double *obj, double *lb, double *ub)
328 {
329 return(USER_DEFAULT);
330 }
331
332 /*===========================================================================*/
333
334 /*===========================================================================*\
335 * You might want to print some statistics on the types and quantities
336 * of cuts or something like that.
337 \*===========================================================================*/
338
339 int user_print_stat_on_cuts_added(void *user, int rownum, waiting_row **rows)
340 {
341 return(USER_DEFAULT);
342 }
343
344 /*===========================================================================*/
345
346 /*===========================================================================*\
347 * You might want to eliminate rows from the local pool based on
348 * knowledge of problem structure.
349 \*===========================================================================*/
350
351 int user_purge_waiting_rows(void *user, int rownum, waiting_row **rows,
352 char *delete_rows)
353 {
354 return(USER_DEFAULT);
355 }
356
357 /*===========================================================================*/
358
359 /*===========================================================================*\
360 * The user might want to generate cuts in the LP using information
361 * about the current tableau, etc. This is for advanced users only.
362 \*===========================================================================*/
363
364 int user_generate_cuts_in_lp(void *user, LPdata *lp_data, int varnum,
365 var_desc **vars, double *x,
366 int *new_row_num, cut_data ***cuts)
367 {
368 return(USER_DEFAULT);
369 }
370
371 /*===========================================================================*/
372
373 /*===========================================================================*\
374 * Free all the user data structures
375 \*===========================================================================*/
376
377 int user_free_lp(void **user)
378 {
379 return(USER_DEFAULT);
380 }
381
382 /*===========================================================================*/
383