Debian Codegraph @

SYMPHONY/Applications/MISOCO/src/LP/user_lp.c

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