Debian Codegraph @

SYMPHONY/Applications/VRP/src/CutPool/vrp_cp.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 Vehicle Routing Problem and the Traveling Salesman Problem. */
6 /* */
7 /* (c) Copyright 2000-2007 Ted Ralphs. All Rights Reserved. */
8 /* */
9 /* This application was developed by Ted Ralphs ([email protected]) */
10 /* */
11 /* This software is licensed under the Eclipse Public License. Please see */
12 /* accompanying file for terms. */
13 /* */
14 /*===========================================================================*/
15
16 /* system include files */
17 #include <string.h>
18 #include <stdlib.h>
19 #include <stdio.h>
20
21 /* SYMPHONY include files */
22 #include "sym_constants.h"
23 #include "sym_macros.h"
24 #include "sym_types.h"
25 #include "sym_proccomm.h"
26 #include "sym_cp_u.h"
27
28 /* VRP include files */
29 #include "vrp_cp.h"
30 #include "vrp_const.h"
31 #include "vrp_macros.h"
32
33 /*===========================================================================*/
34
35 /*===========================================================================*\
36 * This file contains the user-written functions of the cut pool process.
37 \*===========================================================================*/
38
39 /*===========================================================================*\
40 * Here is where the user must receive all of the data sent from
41 * user_send_cp_data() and set up data structures. Note that this function is
42 * only called if one of COMPILE_IN_CP, COMPILE_IN_LP, or COMPILE_IN_TM is
43 * FALSE.
44 \*===========================================================================*/
45
46 int user_receive_cp_data(void **user)
47 {
48 vrp_cp_problem *vcp = (vrp_cp_problem *) calloc (1, sizeof(vrp_cp_problem));
49 int i, j, k;
50
51 *user = (void *) vcp;
52
53 receive_int_array(&vcp->vertnum, 1);
54
55 vcp->edgenum = vcp->vertnum*(vcp->vertnum-1)/2 + vcp->vertnum-1;
56 vcp->edges = (int *) calloc ((int)2*vcp->edgenum, sizeof(int));
57
58 /* create the edge list (we assume a complete graph) */
59 for (i = 1, k = 0; i < vcp->vertnum; i++){
60 for (j = 0; j < i; j++){
61 vcp->edges[2*k] = j;
62 vcp->edges[2*k+1] = i;
63 k++;
64 }
65 }
66
67 /* now add the duplicate copies of the depot edges to allow for
68 routes with one customer */
69 for (i = 1; i < vcp->vertnum; i++){
70 vcp->edges[2*k] = 0;
71 vcp->edges[2*k+1] = i;
72 k++;
73 }
74 return(USER_SUCCESS);
75 }
76
77 /*===========================================================================*/
78
79 /*===========================================================================*\
80 * Here, we free up the data structures
81 \*===========================================================================*/
82
83 int user_free_cp(void **user)
84 {
85 vrp_cp_problem *vcp = (vrp_cp_problem *)(*user);
86
87 FREE(vcp->edges);
88 FREE(vcp);
89 *user = NULL;
90
91 return(USER_SUCCESS);
92 }
93
94 /*===========================================================================*/
95
96 int user_receive_lp_solution_cp(void *user)
97 {
98 /* We leave this to SYMPHONY */
99 return(USER_DEFAULT);
100 }
101
102 /*===========================================================================*/
103
104 /*===========================================================================*\
105 * When a new solution arrives to the cut pool, this function is invoked
106 * so that the user can prepare for checking many cuts (probably set up
107 * some data structures that make ckecking more efficient). In our
108 * case, we construct a fractional graph representation of the LP
109 * solution, which will be more efficient for checking the cuts.
110 \*===========================================================================*/
111
112 int user_prepare_to_check_cuts(void *user, int varnum, int *indices,
113 double *values)
114 {
115 vrp_cp_problem *vcp = (vrp_cp_problem *)user;
116 vcp->n = create_pool_net(vcp, varnum, indices, values);
117
118 return(USER_SUCCESS);
119 }
120
121
122 /*===========================================================================*/
123
124 /*===========================================================================*\
125 * Check to see whether a particular cut is violated by the current LP sol.
126 \*===========================================================================*/
127
128 int user_check_cut(void *user, double etol, int varnum, int *indices,
129 double *values, cut_data *cut, int *is_violated,
130 double *quality)
131 {
132 vrp_cp_problem *vcp = (vrp_cp_problem *)user;
133 pool_net *n;
134 char *coef;
135 int v0, v1;
136 pool_node *verts;
137 int vertnum;
138 double lhs = 0;
139 pool_edge *cur_edge;
140 int i;
141 int j, cliquecount, size;
142 char *clique_array;
143 /*__BEGIN_EXPERIMENTAL_SECTION__*/
144
145 int num_arcs = 0, edge_index;
146 char *cpt;
147 int *arcs ;
148 char *indicators;
149 double bigM, *weights ;
150 int jj, num_fracs = 0, fracs = 0;
151 /*___END_EXPERIMENTAL_SECTION___*/
152
153 n = vcp->n;
154 verts = n->verts;
155 vertnum = n->vertnum;
156
157 /*------------------------------------------------------------------------*\
158 * Here the cut is "unpacked" and checked for violation. Each cut is
159 * stored as compactly as possible. The subtour elimination constraints
160 * are stored as a vector of bits indicating which side of the cut each
161 * node is on. If the cut is violated, it is sent back to the lp.
162 * Otherwise, "touches" is incremented. "Touches" is a measure of the
163 * effectiveness of a cut and indicates how long it has been since a
164 * cut was useful
165 \*------------------------------------------------------------------------*/
166 switch (cut->type){
167
168 case SUBTOUR_ELIM_SIDE:
169 coef = cut->coef;
170 for (lhs = 0, v0 = 0; v0 < vertnum; v0++){
171 if (!(coef[v0 >> DELETE_POWER] & (1 << (v0 & DELETE_AND))))
172 continue;
173 for(cur_edge = verts[v0].first; cur_edge; cur_edge = cur_edge->next){
174 v1 = cur_edge->other_end;
175 if (coef[v1 >> DELETE_POWER] & (1 << (v1 & DELETE_AND)))
176 lhs += cur_edge->weight;
177 }
178 }
179 *is_violated = (lhs/2 > (double)(cut->rhs)+etol);
180 *quality = lhs/2 - (double)cut->rhs;
181 if (*quality < etol && *quality > -etol) *quality = 0;
182 return(USER_SUCCESS);
183
184 case SUBTOUR_ELIM_ACROSS:
185 coef = cut->coef;
186 for (lhs = 0, i = 0; i<varnum; i++){
187 v0 = vcp->edges[indices[i] << 1];
188 v1 = vcp->edges[(indices[i] << 1) + 1];
189 if ((coef[v0 >> DELETE_POWER] >> (v0 & DELETE_AND) & 1) ^
190 (coef[v1 >> DELETE_POWER] >> (v1 & DELETE_AND) & 1))
191 lhs += values[i];
192 }
193 *is_violated = (lhs < (double)(cut->rhs)-etol);
194 *quality = (double)cut->rhs - lhs;
195 if (*quality < etol && *quality > -etol) *quality = 0;
196 return(USER_SUCCESS);
197
198 case CLIQUE:
199 coef = cut->coef;
200 size = (vertnum >> DELETE_POWER) + 1;
201 memcpy(&cliquecount, coef, ISIZE);
202 coef += ISIZE;
203 for (lhs = 0, v0 = 0; v0 < vertnum; v0++){
204 for (j = 0; j < cliquecount; j++){
205 clique_array = coef + size * j;
206 if (!(clique_array[v0>>DELETE_POWER] & (1<<(v0 & DELETE_AND))))
207 continue;
208 for (cur_edge = verts[v0].first; cur_edge;
209 cur_edge = cur_edge->next){
210 v1 = cur_edge->other_end;
211 if (coef[v1 >> DELETE_POWER] & (1 << (v1 & DELETE_AND)))
212 lhs += cur_edge->weight;
213 }
214 }
215 }
216 *is_violated = (lhs < cut->rhs - etol);
217 *quality = (double)cut->rhs - lhs;
218 if (*quality < etol && *quality > -etol) *quality = 0;
219 return(USER_SUCCESS);
220
221 /*__BEGIN_EXPERIMENTAL_SECTION__*/
222 case FARKAS:
223 coef = cut->coef;
224 cpt = coef+ ((vertnum >> DELETE_POWER) + 1);
225 memcpy((char *)&num_arcs, cpt, ISIZE);
226 cpt += ISIZE;
227 arcs = (int *) malloc(num_arcs * ISIZE);
228 indicators = (char *) malloc(num_arcs);
229 memcpy((char *)arcs, cpt, ISIZE*(num_arcs));
230 cpt += num_arcs * ISIZE;
231 memcpy(indicators, cpt, num_arcs);
232 cpt += num_arcs;
233 memcpy((char *)&num_fracs, cpt, ISIZE);
234 cpt += ISIZE;
235 weights = (double *) malloc((num_fracs + 1) * DSIZE);
236 memcpy((char *)weights, cpt, (num_fracs + 1) * DSIZE);
237 bigM = (*(double *)weights);
238 weights++;
239
240 for (fracs = 0, i = 0, lhs = 0 ; i < varnum; i++){
241 v0 = vcp->edges[indices[i] << 1];
242 v1 = vcp->edges[(indices[i] << 1) + 1];
243 /*edge_index=INDEX(v0, v1);*/
244 edge_index = indices[i];
245 if (isset(coef, v1) || isset(coef,v0)){
246 for (jj = 0; jj < num_arcs; jj++){
247 if (arcs[jj] == edge_index){
248 if (indicators[jj]){
249 lhs += -bigM*values[i];
250 break;
251 }else{
252 lhs += weights[fracs++]*values[i];
253 break;
254 }
255 }
256 }
257 if (jj == num_arcs) lhs += bigM*values[i];
258 }
259 }
260 weights--;
261 FREE(arcs);
262 FREE(indicators);
263 FREE(weights);
264 *is_violated = (lhs < cut->rhs - etol);
265 *quality = (double)cut->rhs - lhs;
266 if (*quality < etol && *quality > -etol) *quality = 0;
267 return(USER_SUCCESS);
268
269 case NO_COLUMNS:
270 coef = cut->coef;
271 cpt = coef+ ((vertnum >> DELETE_POWER) + 1);
272 memcpy((char *)&num_arcs, cpt, ISIZE);
273 arcs = (int *) malloc(num_arcs * ISIZE);
274 indicators = (char *) malloc(num_arcs);
275 cpt += ISIZE;
276 memcpy((char *)arcs, cpt, num_arcs * ISIZE);
277 cpt += num_arcs * ISIZE;
278 memcpy(indicators, cpt, num_arcs);
279
280 for (i = 0, lhs = 0 ; i < varnum; i++){
281 v0 = vcp->edges[indices[i] << 1];
282 v1 = vcp->edges[(indices[i] << 1) + 1];
283 /*edge_index = INDEX(v0, v1);*/
284 edge_index = indices[i];
285 if (isset(coef, v1) || isset(coef,v0)){
286 for (jj = 0; jj < num_arcs; jj++){
287 if ( arcs[jj] == edge_index){
288 lhs += indicators[jj] ? values[i] : 0.0;
289 break;
290 }
291 }
292 if (jj == num_arcs) lhs -= values[i];
293 }
294 }
295 FREE(arcs);
296 FREE(indicators);
297 *is_violated = (lhs > cut->rhs + etol);
298 *quality = lhs - (double)cut->rhs;
299 if (*quality < etol && *quality > -etol) *quality = 0;
300 return(USER_SUCCESS);
301
302 case GENERAL_NONZEROS:
303 cpt = cut->coef;
304 memcpy((char *)&num_arcs, cpt, ISIZE);
305 cpt += ISIZE;
306 arcs = (int *) calloc(num_arcs, ISIZE);
307 weights = (double *) calloc(num_arcs, DSIZE);
308 memcpy((char *)arcs, cpt, num_arcs * ISIZE);
309 cpt += num_arcs * ISIZE;
310 memcpy((char *)weights, cpt, num_arcs * DSIZE);
311
312 for (i = 0, lhs = 0; i < varnum; i++){
313 edge_index = indices[i];
314 for (j = 0; j < num_arcs; j++){
315 if (arcs[j] == edge_index)
316 lhs += values[i]*weights[j];
317 }
318 }
319 FREE(arcs);
320 FREE(weights);
321 *is_violated = (cut->sense == 'G' ? (lhs < cut->rhs + etol) :
322 (lhs > cut->rhs - etol));
323 *quality = (cut->sense == 'G' ? (double)cut->rhs - lhs :
324 lhs - (double)cut->rhs);
325 if (*quality < etol && *quality > -etol) *quality = 0;
326 return(USER_SUCCESS);
327
328 /*___END_EXPERIMENTAL_SECTION___*/
329 default:
330 printf("Cut types not recognized! \n\n");
331 *is_violated = FALSE;
332 return(USER_SUCCESS);
333 }
334 }
335
336 /*===========================================================================*/
337
338 /*===========================================================================*\
339 * This function is invoked when all cuts that needed to be checked for
340 * the current solution have been checked already. (Disassemble the
341 * data structures built up in 'user_prepare_to_check_cuts'.
342 \*===========================================================================*/
343
344 int user_finished_checking_cuts(void *user)
345 {
346 vrp_cp_problem *vcp = (vrp_cp_problem *)user;
347 free_pool_net(vcp);
348
349 return(USER_SUCCESS);
350 }
351
352 /*===========================================================================*/
353
354 /*===========================================================================*\
355 * This function creates the solution graph from the current LP solution
356 \*===========================================================================*/
357
358 pool_net *create_pool_net(vrp_cp_problem *vcp, int varnum, int *indices,
359 double *values)
360 {
361 register int *edges = vcp->edges;
362 pool_net *n;
363 pool_node *verts;
364 int nv0 = 0, nv1 = 0;
365 pool_edge *adjlist;
366 int i;
367 int vertnum = vcp->vertnum;
368 int edgenum = vcp->edgenum;
369
370 n = (pool_net *) calloc (1, sizeof(pool_net));
371 n->vertnum = vertnum;
372 n->edgenum = varnum;
373 n->verts = (pool_node *)calloc((int)vertnum, sizeof(pool_node));
374 n->adjlist = (pool_edge *)calloc(2*(int)edgenum, sizeof(pool_edge));
375 verts = n->verts;
376 adjlist = n->adjlist;
377
378 for (i = 0; i < varnum; i++){
379 nv0 = edges[indices[i] << 1];
380 nv1 = edges[(indices[i] << 1) + 1];
381 if (!verts[nv0].first)
382 verts[nv0].first = adjlist;
383 else{
384 adjlist->next = verts[nv0].first;
385 verts[nv0].first = adjlist;
386 }
387 adjlist->other_end = nv1;
388 adjlist->weight = values[i];
389 adjlist++;
390 if (!verts[nv1].first)
391 verts[nv1].first = adjlist;
392 else{
393 adjlist->next = verts[nv1].first;
394 verts[nv1].first = adjlist;
395 }
396 adjlist->other_end = nv0;
397 adjlist->weight = values[i];
398 adjlist++;
399 }
400
401 return(n);
402 }
403
404 /*===========================================================================*/
405
406 /*===========================================================================*\
407 * Frees the memory associated with a solution network
408 \*===========================================================================*/
409
410 void free_pool_net(vrp_cp_problem *vcp)
411 {
412 if (vcp->n){
413 FREE(vcp->n->adjlist);
414 FREE(vcp->n->verts);
415 FREE(vcp->n);
416 }
417 }