1 /*===========================================================================*/
2 /* */
3 /* This file is part of the SYMPHONY Branch, Cut, and Price Library. */
4 /* */
5 /* SYMPHONY was jointly developed by Ted Ralphs (ted@lehigh.edu) and */
6 /* Laci Ladanyi (ladanyi@us.ibm.com). */
7 /* */
8 /* (c) Copyright 2000-2007 Ted Ralphs. All Rights Reserved. */
9 /* */
10 /* This software is licensed under the Eclipse Public License. Please see */
11 /* accompanying file for terms. */
12 /* */
13 /*===========================================================================*/
14
15 /* system include files */
16 #include <stdio.h>
17
18 /* SYMPHONY include files */
19 #include "sym_constants.h"
20 #include "sym_macros.h"
21 #include "sym_lp_u.h"
22
23 /* User include files */
24 #include "user.h"
25
26 /*===========================================================================*/
27
28 /*===========================================================================*\
29 * This file contains the user-written functions for the LP process.
30 \*===========================================================================*/
31
32 /*===========================================================================*\
33 * Here is where the user must receive all of the data sent from
34 * user_send_lp_data() and set up data structures. Note that this function is
35 * only called if one of COMPILE_IN_LP or COMPILE_IN_TM is FALSE. For
36 * sequential computation, nothing is needed here.
37 \*===========================================================================*/
38
user_receive_lp_data(void ** user)39 int user_receive_lp_data(void **user)
40 {
41 return(USER_DEFAULT);
42 }
43
44 /*===========================================================================*/
45
46 /*===========================================================================*\
47 * Here is where the user must create the initial LP relaxation for
48 * each search node. Basically, this involves constructing the base matrix in
49 * column ordered format. See the documentation for an explanation of how to
50 * fill out this function.
51 \*===========================================================================*/
52
user_create_subproblem(void * user,int * indices,MIPdesc * mip,int * maxn,int * maxm,int * maxnz)53 int user_create_subproblem(void *user, int *indices, MIPdesc *mip,
54 int *maxn, int *maxm, int *maxnz)
55 {
56 user_problem *prob = (user_problem *) user;
57
58 return(USER_DEFAULT);
59 }
60
61
62 /*===========================================================================*/
63
64 /*===========================================================================*\
65 * This function takes an LP solution and checks it for feasibility. By
66 * default, SYMPHONY checks for integrality. If any integral solution for your
67 * problem is feasible, then nothing needs to be done here.
68 \*===========================================================================*/
69
user_is_feasible(void * user,double lpetol,int varnum,int * indices,double * values,int * feasible,double * objval,char branching,double * heur_solution)70 int user_is_feasible(void *user, double lpetol, int varnum, int *indices,
71 double *values, int *feasible, double *objval,
72 char branching, double *heur_solution)
73 {
74 return(USER_DEFAULT);
75 }
76
77 /*===========================================================================*/
78
79 /*===========================================================================*\
80 * Here, the user can specify a special routine for sending back the feasible
81 * solution. This need not be used unless there is a special format the user
82 * wants the solution in. This function is only called in sequential mode.
83 \*===========================================================================*/
84
user_send_feasible_solution(void * user,double lpetol,int varnum,int * indices,double * values)85 int user_send_feasible_solution(void *user, double lpetol, int varnum,
86 int *indices, double *values)
87 {
88 return(USER_DEFAULT);
89 }
90
91
92 /*===========================================================================*/
93
94 /*===========================================================================*\
95 * This function graphically displays the current fractional solution
96 * This is done using the Interactive Graph Drawing program, if it is used.
97 \*===========================================================================*/
98
user_display_lp_solution(void * user,int which_sol,int varnum,int * indices,double * values)99 int user_display_lp_solution(void *user, int which_sol, int varnum,
100 int *indices, double *values)
101 {
102 return(USER_DEFAULT);
103 }
104
105 /*===========================================================================*/
106
107 /*===========================================================================*\
108 * You can add whatever information you want about a node to help you
109 * recreate it. I don't have a use for it, but maybe you will.
110 \*===========================================================================*/
111
user_add_to_desc(void * user,int * desc_size,char ** desc)112 int user_add_to_desc(void *user, int *desc_size, char **desc)
113 {
114 return(USER_DEFAULT);
115 }
116
117 /*===========================================================================*/
118
119 /*===========================================================================*\
120 * Compare cuts to see if they are the same. We use the default, which
121 * is just comparing byte by byte.
122 \*===========================================================================*/
123
user_same_cuts(void * user,cut_data * cut1,cut_data * cut2,int * same_cuts)124 int user_same_cuts(void *user, cut_data *cut1, cut_data *cut2, int *same_cuts)
125 {
126 return(USER_DEFAULT);
127 }
128
129 /*===========================================================================*/
130
131 /*===========================================================================*\
132 * This function receives a cut, unpacks it, and adds it to the set of
133 * rows to be added to the LP. Only used if cutting planes are generated.
134 \*===========================================================================*/
135
user_unpack_cuts(void * user,int from,int type,int varnum,var_desc ** vars,int cutnum,cut_data ** cuts,int * new_row_num,waiting_row *** new_rows)136 int user_unpack_cuts(void *user, int from, int type, int varnum,
137 var_desc **vars, int cutnum, cut_data **cuts,
138 int *new_row_num, waiting_row ***new_rows)
139 {
140 /* This code is just here as a template for customization. Uncomment to use.*/
141 #if 0
142 int j;
143
144 user_problem *prob = (user_problem *) user;
145
146 *new_row_num = 0;
147 for (j = 0; j < cutnum; j++){
148 switch (cuts[j]->type){
149
150 default:
151 printf("Unrecognized cut type!\n");
152 }
153 }
154 #endif
155
156 return(USER_DEFAULT);
157 }
158
159 /*===========================================================================*/
160
161 /*===========================================================================*\
162 * If the user wants to fill in a customized routine for sending and receiving
163 * the LP solution, it can be done here. For most cases, the default routines
164 * are fine.
165 \*===========================================================================*/
166
user_send_lp_solution(void * user,int varnum,var_desc ** vars,double * x,int where)167 int user_send_lp_solution(void *user, int varnum, var_desc **vars, double *x,
168 int where)
169 {
170 return(USER_DEFAULT);
171 }
172
173 /*===========================================================================*/
174
175 /*===========================================================================*\
176 * This routine does logical fixing of variables
177 \*===========================================================================*/
178
user_logical_fixing(void * user,int varnum,var_desc ** vars,double * x,char * status,int * num_fixed)179 int user_logical_fixing(void *user, int varnum, var_desc **vars, double *x,
180 char *status, int *num_fixed)
181 {
182 *num_fixed = 0;
183
184 return(USER_DEFAULT);
185 }
186
187 /*===========================================================================*/
188
189 /*===========================================================================*\
190 * This function generates the 'next' column. Only used for column generation.
191 \*===========================================================================*/
192
user_generate_column(void * user,int generate_what,int cutnum,cut_data ** cuts,int prevind,int nextind,int * real_nextind,double * colval,int * colind,int * collen,double * obj,double * lb,double * ub)193 int user_generate_column(void *user, int generate_what, int cutnum,
194 cut_data **cuts, int prevind, int nextind,
195 int *real_nextind, double *colval, int *colind,
196 int *collen, double *obj, double *lb, double *ub)
197 {
198 switch (generate_what){
199 case GENERATE_NEXTIND:
200 /* Here we just have to generate the specified column. */
201 break;
202 case GENERATE_REAL_NEXTIND:
203 /* In this case, we have to determine what the "real" next edge is*/
204 break;
205 }
206
207 return(USER_DEFAULT);
208 }
209
210 /*===========================================================================*/
211
212 /*===========================================================================*\
213 * You might want to print some statistics on the types and quantities
214 * of cuts or something like that.
215 \*===========================================================================*/
216
user_print_stat_on_cuts_added(void * user,int rownum,waiting_row ** rows)217 int user_print_stat_on_cuts_added(void *user, int rownum, waiting_row **rows)
218 {
219 return(USER_DEFAULT);
220 }
221
222 /*===========================================================================*/
223
224 /*===========================================================================*\
225 * You might want to eliminate rows from the local pool based on
226 * knowledge of problem structure.
227 \*===========================================================================*/
228
user_purge_waiting_rows(void * user,int rownum,waiting_row ** rows,char * delete_rows)229 int user_purge_waiting_rows(void *user, int rownum, waiting_row **rows,
230 char *delete_rows)
231 {
232 return(USER_DEFAULT);
233 }
234
235 /*===========================================================================*/
236
237 /*===========================================================================*\
238 * The user might want to generate cuts in the LP using information
239 * about the current tableau, etc. This is for advanced users only.
240 \*===========================================================================*/
241
user_generate_cuts_in_lp(void * user,LPdata * lp_data,int varnum,var_desc ** vars,double * x,int * new_row_num,cut_data *** cuts)242 int user_generate_cuts_in_lp(void *user, LPdata *lp_data, int varnum,
243 var_desc **vars, double *x,
244 int *new_row_num, cut_data ***cuts)
245 {
246 return(GENERATE_CGL_CUTS);
247 }
248
249 /*===========================================================================*/
250
251 /*===========================================================================*\
252 * Free all the user data structures
253 \*===========================================================================*/
254
user_free_lp(void ** user)255 int user_free_lp(void **user)
256 {
257 return(USER_DEFAULT);
258 }
259
260 /*===========================================================================*/
261
262