Debian Codegraph @

SYMPHONY/Applications/MPP/src/CutGen/mpp_cg.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 <stdlib.h>
19 #include <string.h>
20
21 /* SYMPHONY include files */
22 #include "sym_macros.h"
23 #include "sym_constants.h"
24 #include "sym_proccomm.h"
25 #include "sym_cg_u.h"
26
27 /* MPP include files */
28 #include "mpp.h"
29
30 /*===========================================================================*/
31
32 /*===========================================================================*\
33 * This file contains user-written functions used by the cut generator
34 * process.
35 \*===========================================================================*/
36
37 /*===========================================================================*\
38 * Here is where the user must receive all of the data sent from
39 * user_send_cg_data() and set up data structures. Note that this function is
40 * only called if one of COMPILE_IN_CG, COMPILE_IN_LP, or COMPILE_IN_TM is
41 * FALSE.
42 \*===========================================================================*/
43
44 int user_receive_cg_data(void **user, int dg_id)
45 {
46 return(USER_DEFAULT);
47 }
48
49 /*===========================================================================*/
50
51 int user_receive_lp_solution_cg(void *user)
52 {
53 return(USER_DEFAULT);
54 }
55
56 /*===========================================================================*/
57 /*===========================================================================*/
58
59 /*===========================================================================*\
60 * Find cuts violated by a particular LP solution. This can be a fairly
61 * involved function but the bottom line is that an LP solution comes in
62 * and cuts go out. Remember, use the function cg_send_cut() to send cuts out
63 * when they are found
64 \*===========================================================================*/
65
66 int user_find_cuts(void *user, int varnum, int iter_num, int level,
67 int index, double objval, int *indices, double *values,
68 double ub, double etol, int *cutnum, int *alloc_cuts,
69 cut_data ***cuts)
70 {
71 /* heuristic 1 */
72 mpp_problem *mpp = (mpp_problem *)user;
73 int degree, delta = 0, odd_nodes, i, j, k, num_cuts = 0;
74 int *odds;
75 cut_data *new_cut = NULL;
76 int storer = 0, counter = 0, cursor = 0;
77 int new_node = 0, current_component = 0;
78
79 int *stack, *node_visited, *component;
80 double *holder;
81 int *return_list, *cut_sizes;
82 int **matrix;
83 char *chararray;
84 double holder2;
85 int exiter;
86 /* calloc makes the rest 0 ? */
87
88 odds = (int *) calloc(mpp->numnodes, sizeof(int));
89 component = (int *) calloc(mpp->numnodes, sizeof(int));
90 node_visited = (int *) calloc(mpp->numnodes, sizeof(int));
91
92 holder = (double *) calloc(mpp->numedges*2+mpp->numarcs, sizeof(double));
93 cut_sizes = (int *) calloc(mpp->numnodes, sizeof(int));
94 matrix = (int **) calloc(mpp->numnodes, sizeof(int *));
95 new_cut = (cut_data *) calloc(1, sizeof(cut_data));
96 stack = (int *) calloc(mpp->numnodes, sizeof(int));
97 return_list = (int *) calloc(mpp->numnodes, sizeof(int));
98 for(i = 0; i <= mpp->numnodes - 1; i++){
99 matrix[i] = (int *) calloc(mpp->numnodes, sizeof(int));
100 }
101 /* puts the current solution values into an easy to use array */
102 /* make sure this for loop is right, might be varnum instead of varnum-1*/
103 for (i = 0; i <= varnum - 1; i++){
104 holder[indices[i]]=values[i];
105 }
106 for (j = 0; j <= mpp->numarcs - 1; j++){
107 if (holder[j] > 1 + delta){
108 matrix[mpp->tail[j]][mpp->head[j]]=1;
109 matrix[mpp->head[j]][mpp->tail[j]]=1;
110 }
111 }
112 /* check each edge to see if Xij +Xji >= 1 + delta */
113 for (j = mpp->numarcs; j <= mpp->numedges + mpp->numarcs - 1; j++){
114 if (holder[j] + holder[mpp->numedges + j] > 1 + delta){
115 /* put tail[j] in head[j]'s ajacency list and vice versa */
116 matrix[mpp->tail[j]][mpp->head[j]] = 1;
117 matrix[mpp->head[j]][mpp->tail[j]] = 1;
118 }
119 }
120
121 /* here we flag each node as odd or not odd */
122 if (mpp->odd_checker == 0){
123 mpp->is_odd = (int *) calloc(mpp->numnodes, sizeof(int));
124 mpp->odd_checker=1;
125 for (i = 0; i <= mpp->numnodes - 1; i++){
126 degree = 0;
127
128 /* check each arc and edge to see if it is incident to each node*/
129 for (j = 0; j <= mpp->numarcs + mpp->numedges - 1; j++){
130 if((mpp->tail[j] == i) || (mpp->head[j] == i)){
131 degree++;
132 }
133 }
134 if(degree%2 == 1){
135 mpp->is_odd[i] = 1;
136 }else{
137 mpp->is_odd[i]=0;
138 }
139 }
140 }
141 /* now we need to use a depth first search with a stack to find all the
142 components of G' from the adjacency list and assign a number to each
143 component */
144
145 /* first make an adjacency matrix for graph g' */
146 #if 0
147 for (i = 0; i <= mpp->numnodes - 1; i++){
148 counter = 0;
149 cursor = 0;
150 if (node_visited[i] == 0){
151 if (mpp->is_odd[i] == 1){
152 odds[current_component]++;
153 }
154 node_visited[i] = 1;
155 stack[cursor] = i;
156 counter++;
157 exiter = 0;
158 while (new_node != 0 || cursor >= 0){
159 new_node = 0;
160 j = 0;
161 while (j <= mpp->numnodes - 1 && new_node == 0){
162 if(((matrix[stack[cursor]][j] == 1) ||
163 (matrix[j][stack[cursor]] == 1)) &&
164 (node_visited[j] == 0)){
165 if (mpp->is_odd[j] == 1)
166 odds[current_component]++;
167 new_node = 1;
168 exiter = 1;
169 node_visited[j] = 1;
170 cursor++;
171 stack[cursor] = j;
172 counter++;
173 }
174 j++;
175 }
176 if (new_node == 0){
177 component[stack[cursor]]=current_component;
178 cursor--;
179 }
180 }
181 cut_sizes[current_component]=counter;
182 current_component++;
183 }
184 }
185 current_component--;
186 for (i = current_component; i >= 0; i--){
187 if (odds[i]%2 == 1 && cut_sizes[i] > 1){
188 counter = 0;
189 for(j = 0; j <= mpp->numnodes - 1; j++){
190 if (i == component[j]){
191 return_list[counter] = j;
192 counter++;
193 }
194 }
195 new_cut->coef = (char*)return_list;
196 new_cut->size = cut_sizes[i]*4;
197 new_cut->type = ODD_CUT;
198 new_cut->sense ='G';
199 num_cuts += cg_send_cut(new_cut);
200 }
201 }
202 *cutnum = num_cuts;
203 #endif
204
205 FREE(new_cut);
206 FREE(holder);
207 FREE(cut_sizes);
208 for (i = 0; i <= mpp->numnodes - 1; i++){
209 FREE(matrix[i]);
210 }
211 FREE(matrix);
212 FREE(new_cut);
213 FREE(stack);FREE(return_list);
214 FREE(odds);
215 FREE(node_visited);
216 FREE(component);
217
218 return(USER_SUCCESS);
219 }
220
221 /*===========================================================================*/
222
223 /*===========================================================================*\
224 * Free the user data structure
225 \*===========================================================================*/
226
227 int user_free_cg(void **user)
228 {
229 return(USER_DEFAULT);
230 }
231
232 /*===========================================================================*/
233
234 /*===========================================================================*\
235 * This is an undocumented (for now) debugging feature which can allow the user
236 * to identify the cut which cuts off a particular known feasible solution.
237 \*===========================================================================*/
238
239 #ifdef CHECK_CUT_VALIDITY
240 int user_check_validity_of_cut(void *user, cut_data *new_cut)
241 {
242 return(USER_DEFAULT);
243 }
244 #endif