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