Debian Codegraph @

SYMPHONY/Applications/VRP/src/LP/vrp_lp.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 <stdio.h>
18 #include <stdlib.h>
19 /*#include <sys/param.h>*/
20 #include <memory.h>
21 #include <math.h>
22
23 /* SYMPHONY include files */
24 #include "sym_constants.h"
25 #include "sym_macros.h"
26 #include "sym_proccomm.h"
27 #include "sym_messages.h"
28 #include "sym_timemeas.h"
29 #include "sym_lp_u.h"
30 #include "sym_dg_params.h"
31
32 /* VRP include files */
33 #include "vrp_lp.h"
34 #include "vrp_dg_functions.h"
35 #include "vrp_macros.h"
36 #include "vrp_const.h"
37
38 /*===========================================================================*/
39
40 /*===========================================================================*\
41 * This file contains the user-written functions for the LP process.
42 \*===========================================================================*/
43
44 /*===========================================================================*\
45 * Here is where the user must receive all of the data sent from
46 * user_send_lp_data() and set up data structures. Note that this function is
47 * only called if one of COMPILE_IN_LP or COMPILE_IN_TM is FALSE.
48 \*===========================================================================*/
49
50 int user_receive_lp_data(void **user)
51 {
52 vrp_lp_problem *vrp;
53 int vertnum;
54 int i, j, k, l;
55 int total_edgenum;
56 int zero_varnum, *zero_vars = NULL;
57
58 vrp = (vrp_lp_problem *) calloc (1, sizeof(vrp_lp_problem));
59
60 *user = (void *)vrp;
61
62 receive_char_array((char *)(&vrp->par), sizeof(vrp_lp_params));
63 receive_int_array(&vrp->window, 1);
64 receive_int_array(&vrp->numroutes, 1);
65 receive_int_array(&vrp->vertnum, 1);
66 vertnum = vrp->vertnum;
67 vrp->demand = (int *) calloc (vertnum, sizeof(int));
68 receive_int_array(vrp->demand, (int)vertnum);
69 receive_int_array(&vrp->capacity, 1);
70 total_edgenum = vertnum*(vertnum-1)/2;
71 vrp->costs = (int *) calloc (total_edgenum, sizeof(int));
72 receive_int_array(vrp->costs, total_edgenum);
73 receive_int_array(&zero_varnum, 1);
74 if (zero_varnum){
75 zero_vars = (int *) malloc (zero_varnum*sizeof(int));
76 receive_int_array(zero_vars, zero_varnum);
77 }
78
79 vrp->edges = (int *) calloc (2*total_edgenum, sizeof(int));
80
81 /*create the edge list (we assume a complete graph) The edge is set to
82 (0,0) in the edge list if it was eliminated in preprocessing*/
83 for (i = 1, k = 0, l = 0; i < vertnum; i++){
84 for (j = 0; j < i; j++){
85 if (l < zero_varnum && k == zero_vars[l]){
86 /*This is one of the zero edges*/
87 vrp->edges[2*k] = vrp->edges[2*k+1] = 0;
88 l++;
89 k++;
90 continue;
91 }
92 vrp->edges[2*k] = j;
93 vrp->edges[2*k+1] = i;
94 k++;
95 }
96 }
97 FREE(zero_vars);
98
99 vrp->cur_sol = (_node *) calloc (vrp->vertnum, sizeof(_node));
100 if (vrp->window){
101 copy_node_set(vrp->window, TRUE, (char *)"Original solution");
102 #if 0
103 copy_node_set(vrp->window, TRUE, (char *)"Compressed solution");
104 #endif
105 }
106 return(USER_SUCCESS);
107 }
108
109 /*===========================================================================*/
110
111 /*===========================================================================*\
112 * Here is where the user must create the initial LP relaxation for
113 * each search node. See the comments below.
114 \*===========================================================================*/
115
116 int user_create_subproblem(void *user, int *indices, MIPdesc *mip,
117 int *maxn, int *maxm, int *maxnz)
118 {
119 vrp_lp_problem *vrp = (vrp_lp_problem *)user;
120 int *costs = vrp->costs;
121 int *edges = vrp->edges;
122 int i;
123 int total_edgenum = vrp->vertnum*(vrp->vertnum-1)/2;
124 int cap_check = vrp->capacity*(vrp->numroutes-1);
125 int total_demand = vrp->demand[0];
126
127 /* set up the inital LP data */
128
129 /* Our base constraints are that the sum of the weights of the
130 edges adjacent to each node (except the depot) is 2. This means
131 that each column will have exactly two nonzeros, one in each of
132 the rows corresponding to its end points. Hence the total
133 nonzeros is 2*n (n is the number of active variables). */
134 mip->nz = 2 * mip->n;
135
136 /* Estimate the maximum number of nonzeros (not needed, but helpful for
137 efficiency*/
138 *maxm = 2 * mip->m;
139 *maxn = total_edgenum;
140 *maxnz = mip->nz + ((*maxm) * (*maxn) / 10);
141
142 /* Allocate the arrays. These are owned by SYMPHONY after returning. */
143 mip->matbeg = (int *) malloc((mip->n + 1) * ISIZE);
144 mip->matind = (int *) malloc((mip->nz) * ISIZE);
145 mip->matval = (double *) malloc((mip->nz) * DSIZE);
146 mip->obj = (double *) malloc(mip->n * DSIZE);
147 mip->ub = (double *) malloc(mip->n * DSIZE);
148 mip->lb = (double *) calloc(mip->n, DSIZE); /* zero lower bounds */
149 mip->rhs = (double *) malloc(mip->m * DSIZE);
150 mip->sense = (char *) malloc(mip->m * CSIZE);
151 mip->rngval = (double *) calloc(mip->m, DSIZE);
152 mip->is_int = (char *) calloc(mip->n, CSIZE);
153
154 /* Fill out the appropriate data structures -- each column has
155 exactly two entries */
156 for (i = 0; i < mip->n; i++){
157 mip->obj[i] = (double) costs[indices[i]];
158 mip->matbeg[i] = 2*i;
159 mip->matval[2*i] = 1.0;
160 mip->matval[2*i+1] = 1.0;
161 mip->matind[2*i] = edges[2*indices[i]];
162 mip->matind[2*i+1] = edges[2*indices[i] + 1];
163 mip->is_int[i] = TRUE;
164
165 /* Set the upper and lower bounds */
166 if (edges[indices[i] << 1] == 0){
167 /*This is a depot edge and we have to check what its ub should be*/
168 /*Recall vrp->demand[0] == total_demand*/
169 if (total_demand - vrp->demand[edges[(indices[i] << 1) + 1]] >
170 cap_check)
171 /*in this case, the node cannot be on its own route*/
172 mip->ub[i] = 1;
173 else
174 mip->ub[i] = 2;
175 }else{
176 mip->ub[i] = 1;
177 }
178 }
179 mip->matbeg[mip->n] = 2*mip->n;
180
181 /* set the initial right hand side */
182 mip->rhs[0] = 2*vrp->numroutes;
183 mip->sense[0] = 'E';
184 for (i = vrp->vertnum - 1; i > 0; i--){
185 mip->rhs[i] = (double) 2;
186 mip->sense[i] = 'E';
187 }
188
189 return(USER_SUCCESS);
190 }
191
192
193 /*===========================================================================*/
194
195 /*===========================================================================*\
196 * This function takes an LP solution and checks it for feasibility.
197 * In our case, that means (1) it is integral (2) it is connected, and
198 * (3) the routes obey the capacity constraints.
199 \*===========================================================================*/
200
201 int user_is_feasible(void *user, double lpetol, int varnum, int *indices,
202 double *values, int *feasible, double *true_objval,
203 char branching, double *heur_solution)
204 {
205 vrp_lp_problem *vrp = (vrp_lp_problem *)user;
206 vertex *verts;
207 int *demand = vrp->demand, capacity = vrp->capacity;
208 int rcnt, *compnodes, *compdemands;
209 int vertnum = vrp->vertnum, i;
210 network *n;
211 double *compcuts;
212
213 n = createnet(indices, values, varnum, lpetol, vrp->edges, demand, vertnum);
214
215 if (!n->is_integral){
216 *feasible = IP_INFEASIBLE;
217 free_net(n);
218 return(USER_SUCCESS);
219 }
220
221 verts = n->verts;
222 compnodes = (int *) calloc (vertnum + 1, sizeof(int));
223 compdemands = (int *) calloc (vertnum + 1, sizeof(int));
224 compcuts = (double *) calloc (vertnum + 1, sizeof(double));
225 /*get the components of the solution graph without the depot to check if the
226 graph is connected or not*/
227 rcnt = connected(n, compnodes, compdemands, NULL, compcuts, NULL);
228
229 /*------------------------------------------------------------------------*\
230 * For each component check to see if the cut it induces is nonzero -- each
231 * component's cut value must be either 0 or 2 since we have integrality
232 \*------------------------------------------------------------------------*/
233
234 for (i = 0; i<rcnt; i++){
235 if (compcuts[i+1] < lpetol || compdemands[i+1] > capacity){
236 *feasible = IP_INFEASIBLE;
237 FREE(compnodes);
238 FREE(compdemands);
239 FREE(compcuts);
240 free_net(n);
241 return(USER_SUCCESS);
242 }
243 }
244
245 FREE(compnodes);
246 FREE(compdemands);
247 FREE(compcuts);
248
249 *feasible = IP_FEASIBLE;
250
251 construct_feasible_solution(vrp, n, true_objval);
252
253 free_net(n);
254
255 return(USER_SUCCESS);
256 }
257
258 /*===========================================================================*/
259
260 /*===========================================================================*\
261 * In my case, a feasible solution is specified most compactly by
262 * essentially a permutation of the customers along with routes numbers,
263 * specifying the order of the customers on their routes. This is just
264 * sent as a character array which then gets cast to an array of
265 * structures, one for each customers specifying the route number and
266 * the next customer on the route.
267 \*===========================================================================*/
268
269 int user_send_feasible_solution(void *user, double lpetol, int varnum,
270 int *indices, double *values)
271 {
272 vrp_lp_problem *vrp = (vrp_lp_problem *)user;
273
274 send_char_array((char *)vrp->cur_sol, vrp->vertnum*sizeof(_node));
275
276 return(USER_SUCCESS);
277 }
278
279
280 /*===========================================================================*/
281
282 /*===========================================================================*\
283 * This function graphically displays the current fractional solution
284 * This is done using the Interactie Graph Drawing program.
285 \*===========================================================================*/
286
287 int user_display_lp_solution(void *user, int which_sol, int varnum,
288 int *indices, double *values)
289 {
290 vrp_lp_problem *vrp = (vrp_lp_problem *)user;
291
292 if (vrp->par.verbosity > 10 ||
293 (vrp->par.verbosity > 8 && (which_sol == DISP_FINAL_RELAXED_SOLUTION)) ||
294 (vrp->par.verbosity > 6 && (which_sol == DISP_FEAS_SOLUTION))){
295 display_support_graph(vrp->window, FALSE, (char *)"Original solution",
296 varnum, indices, values, .000001,
297 CTOI_WAIT_FOR_CLICK_AND_REPORT);
298 #if 0
299 display_compressed_support_graph(vrp->window, FALSE,
300 (char *)"Compressed solution",
301 varnum, indices, values,
302 CTOI_WAIT_FOR_CLICK_AND_REPORT);
303 #endif
304 }
305
306 if (which_sol == DISP_FINAL_RELAXED_SOLUTION){
307 return(DISP_NZ_INT);
308 }else{
309 return(USER_SUCCESS);
310 }
311 }
312
313 /*===========================================================================*/
314
315 /*===========================================================================*\
316 * You can add whatever information you want about a node to help you
317 * recreate it. I don't have a use for it, but maybe you will.
318 \*===========================================================================*/
319
320 int user_add_to_desc(void *user, int *desc_size, char **desc)
321 {
322 return(USER_DEFAULT);
323 }
324
325 /*===========================================================================*/
326
327 /*===========================================================================*\
328 * Compare cuts to see if they are the same. We use the default, which
329 * is just comparing byte by byte.
330 \*===========================================================================*/
331
332 int user_same_cuts(void *user, cut_data *cut1, cut_data *cut2, int *same_cuts)
333 {
334 /*for now, we just compare byte by byte, as in the previous version of the
335 code. Later, we might want to change this to be more efficient*/
336 return(USER_DEFAULT);
337 }
338
339 /*===========================================================================*/
340
341 /*===========================================================================*\
342 * This function receives a cut, unpacks it, and adds it to the set of
343 * rows to be added to the LP.
344 \*===========================================================================*/
345
346 int user_unpack_cuts(void *user, int from, int type, int varnum,
347 var_desc **vars, int cutnum, cut_data **cuts,
348 int *new_row_num, waiting_row ***new_rows)
349 {
350 int i, j, nzcnt = 0, nzcnt_side = 0, nzcnt_across = 0;
351 int v0, v1, *edges = ((vrp_lp_problem *)user)->edges;
352 waiting_row **row_list = NULL;
353 int *matind = NULL, *matind_across, *matind_side;
354 cut_data *cut;
355 char *coef;
356 double *matval = NULL;
357 int jj, size, vertnum = ((vrp_lp_problem *)user)->vertnum;
358 int cliquecount = 0, val;
359 char *clique_array;
360
361 /*__BEGIN_EXPERIMENTAL_SECTION__*/
362 int num_fracs, fracs;
363 int num_arcs, edge_index;
364 char *cpt;
365 int *arcs;
366 char *indicators;
367
368 double bigM, *weights;
369
370 /*___END_EXPERIMENTAL_SECTION___*/
371 *new_row_num = cutnum;
372 if (cutnum > 0)
373 *new_rows = row_list = (waiting_row **) calloc (cutnum,
374 sizeof(waiting_row *));
375
376 for (j = 0; j < cutnum; j++){
377 coef = (cut = cuts[j])->coef;
378 cuts[j] = NULL;
379 (row_list[j] = (waiting_row *) malloc(sizeof(waiting_row)))->cut = cut;
380 switch (cut->type){
381 /*-------------------------------------------------------------------*\
382 * The subtour elimination constraints are stored as a vector of
383 * bits indicating which side of the cut each customer is on
384 \*-------------------------------------------------------------------*/
385
386 case SUBTOUR_ELIM:
387 matind_side = (int *) malloc(varnum * ISIZE);
388 matind_across = (int *) malloc(varnum * ISIZE);
389 for (i = 0, nzcnt = 0; i < varnum; i++){
390 v0 = edges[(vars[i]->userind) << 1];
391 v1 = edges[((vars[i]->userind) << 1) + 1];
392 if (coef[v0 >> DELETE_POWER] &
393 (1 << (v0 & DELETE_AND)) &&
394 (coef[v1 >> DELETE_POWER]) &
395 (1 << (v1 & DELETE_AND))){
396 matind_side[nzcnt_side++] = i;
397 }else if ((coef[v0 >> DELETE_POWER] >>
398 (v0 & DELETE_AND) & 1) ^
399 (coef[v1 >> DELETE_POWER] >>
400 (v1 & DELETE_AND) & 1)){
401 matind_across[nzcnt_across++] = i;
402 }
403 }
404 cut->type = nzcnt_side < nzcnt_across ? SUBTOUR_ELIM_SIDE :
405 SUBTOUR_ELIM_ACROSS;
406 cut->deletable = TRUE;
407 switch (cut->type){
408 case SUBTOUR_ELIM_SIDE:
409 row_list[j]->nzcnt = nzcnt_side;
410 row_list[j]->matind = matind_side;
411 cut->rhs = 0; /*RHS(compnodes[i+1],compdemands[i+1], capacity)*/
412 cut->sense = 'L';
413 FREE(matind_across);
414 break;
415
416 case SUBTOUR_ELIM_ACROSS:
417 row_list[j]->nzcnt = nzcnt_across;
418 row_list[j]->matind = matind_across;
419 cut->rhs = 0; /*2*BINS(compdemands[i+1], capacity)*/
420 cut->sense = 'G';
421 FREE(matind_side);
422 break;
423 }
424
425 break;
426
427
428 case SUBTOUR_ELIM_SIDE:
429 matind = (int *) malloc(varnum * ISIZE);
430 for (i = 0, nzcnt = 0; i < varnum; i++){
431 v0 = edges[(vars[i]->userind) << 1];
432 v1 = edges[((vars[i]->userind) << 1) + 1];
433 if (coef[v0 >> DELETE_POWER] &
434 (1 << (v0 & DELETE_AND)) &&
435 (coef[v1 >> DELETE_POWER]) &
436 (1 << (v1 & DELETE_AND))){
437 matind[nzcnt++] = i;
438 }
439 }
440 cut->deletable = TRUE;
441 cut->sense = 'L';
442 break;
443
444 case SUBTOUR_ELIM_ACROSS:
445 matind = (int *) malloc(varnum * ISIZE);
446 for (i = 0, nzcnt = 0; i < varnum; i++){
447 v0 = edges[(vars[i]->userind) << 1];
448 v1 = edges[((vars[i]->userind) << 1) + 1];
449 if ((coef[v0 >> DELETE_POWER] >>
450 (v0 & DELETE_AND) & 1) ^
451 (coef[v1 >> DELETE_POWER] >>
452 (v1 & DELETE_AND) & 1)){
453 matind[nzcnt++] = i;
454 }
455 }
456 cut->deletable = TRUE;
457 cut->sense = 'G';
458 break;
459
460 case CLIQUE:
461 size = (vertnum >> DELETE_POWER) + 1;
462 memcpy(&cliquecount, coef, ISIZE);
463 matind = (int *) malloc(cliquecount*varnum*ISIZE);
464 matval = (double *) malloc(cliquecount*varnum*DSIZE);
465 coef += ISIZE;
466 for (nzcnt = 0, i = 0; i < varnum; i++){
467 v0 = edges[(vars[i]->userind) << 1];
468 v1 = edges[((vars[i]->userind) << 1) + 1];
469 val = 0;
470 for (jj = 0; jj < cliquecount; jj++){
471 clique_array = coef + size * jj;
472 if (clique_array[v0 >> DELETE_POWER] &
473 (1 << (v0 & DELETE_AND)) &&
474 (clique_array[v1 >> DELETE_POWER]) &
475 (1 << (v1 & DELETE_AND))){
476 val += 1;
477 }
478 }
479 if (val){
480 matind[nzcnt] = i;
481 matval[nzcnt++] = val;
482 }
483 }
484 cut->deletable = TRUE;
485 break;
486
487 /*__BEGIN_EXPERIMENTAL_SECTION__*/
488 case FARKAS:
489 matind = (int *) malloc(varnum * ISIZE);
490 matval = (double *) malloc(varnum * DSIZE);
491
492 cpt = coef + ((vertnum >> DELETE_POWER) + 1);
493 memcpy((char *)&num_arcs, cpt, ISIZE);
494 cpt += ISIZE;
495 arcs = (int *) malloc(num_arcs * ISIZE);
496 indicators = (char *) malloc(num_arcs);
497 memcpy((char *)arcs, cpt, num_arcs * ISIZE);
498 cpt += num_arcs * ISIZE;
499 memcpy(indicators, cpt, num_arcs);
500 cpt += num_arcs;
501 memcpy((char *)&num_fracs, cpt, ISIZE);
502 cpt += ISIZE;
503 weights = (double *) malloc((num_fracs + 1) * DSIZE);
504 memcpy((char *)weights, cpt, (num_fracs + 1) * DSIZE);
505 bigM = (*(double *)weights);
506 weights++;
507
508 for (fracs = 0, i = 0, nzcnt = 0; i < varnum; i++){
509 edge_index = vars[i]->userind;
510 v0 = edges[edge_index << 1];
511 v1 = edges[(edge_index << 1) + 1];
512
513 if (isset(coef, v1) || isset(coef,v0)){
514 for (jj = 0; jj < num_arcs; jj++){
515 if (arcs[jj] == edge_index){
516 matval[nzcnt] = indicators[jj] ? -bigM : weights[fracs++];
517 break;
518 }
519 }
520 if (jj == num_arcs) matval[nzcnt] = bigM;
521 matind[nzcnt++] = i;
522 }
523 }
524 cut->sense = 'G';
525 cut->branch = DO_NOT_BRANCH_ON_THIS_ROW;
526 --weights;
527 FREE(indicators);
528 FREE(arcs);
529 FREE(weights);
530 break;
531
532 case NO_COLUMNS:
533 matind = (int *) malloc(varnum * ISIZE);
534 matval = (double *) malloc(varnum * DSIZE);
535 cpt = coef + ((vertnum >> DELETE_POWER) + 1);
536 memcpy((char *)&num_arcs, cpt, ISIZE);
537 cpt += ISIZE;
538 arcs = (int *) calloc(num_arcs, ISIZE);
539 indicators = (char *) malloc(num_arcs);
540 memcpy((char *)arcs, cpt, num_arcs * ISIZE);
541 cpt += num_arcs * ISIZE;
542 memcpy(indicators, cpt, num_arcs);
543
544 for (i = 0, nzcnt = 0; i < varnum; i++){
545 edge_index = vars[i]->userind;
546 v0 = edges[edge_index << 1];
547 v1 = edges[(edge_index << 1) + 1];
548
549 if (isset(coef, v1) || isset(coef, v0)){
550 for (jj = 0; jj < num_arcs; jj++){
551 if (arcs[jj] == edge_index){
552 matval[nzcnt] = (indicators[jj]) ? 1.0 : 0.0;
553 break;
554 }
555 }
556 if (jj == num_arcs) matval[nzcnt]= -1.0;
557 if (fabs(matval[nzcnt]) >.5) matind[nzcnt++] = i;
558 }
559 }
560 cut->branch = DO_NOT_BRANCH_ON_THIS_ROW;
561 cut->deletable = TRUE;
562 cut->sense = 'L';
563 FREE(indicators);
564 FREE(arcs);
565 break;
566
567 case GENERAL_NONZEROS:
568 cpt = coef;
569 memcpy((char *)&num_arcs, cpt, ISIZE);
570 cpt += ISIZE;
571 matind = (int *) malloc(num_arcs * ISIZE);
572 arcs = (int *) calloc(num_arcs, ISIZE);
573 matval = (double *) malloc(num_arcs * DSIZE);
574 weights = (double *) malloc(num_arcs * DSIZE);
575 memcpy((char *)arcs, cpt, num_arcs * ISIZE);
576 cpt += num_arcs * ISIZE;
577 memcpy((char *)weights, cpt, num_arcs * DSIZE);
578
579 for (i = 0, nzcnt = 0; i < varnum; i++){
580 for (jj = 0; jj < num_arcs; jj++){
581 if (arcs[jj] == (edge_index = vars[i]->userind)){
582 matind[nzcnt] = i;
583 matval[nzcnt++] = weights[jj];
584 break;
585 }
586 }
587 }
588 cut->branch = DO_NOT_BRANCH_ON_THIS_ROW;
589 cut->deletable = TRUE;
590 FREE(weights);
591 FREE(arcs);
592 break;
593 /*___END_EXPERIMENTAL_SECTION___*/
594
595 default:
596 break;
597
598 }
599
600 row_list[j]->matind = matind =
601 (int *) realloc((char *)matind, nzcnt*ISIZE);
602 row_list[j]->nzcnt = nzcnt;
603 /*__BEGIN_EXPERIMENTAL_SECTION__*/
604 if (cut->type != CLIQUE && cut->type != FARKAS &&
605 cut->type != NO_COLUMNS && cut->type != GENERAL_NONZEROS){
606 /*___END_EXPERIMENTAL_SECTION___*/
607 /*UNCOMMENT FOR PRODUCTION CODE*/
608 #if 0
609 if (cut->type != CLIQUE){
610 #endif
611 row_list[j]->matval = matval = (double *) malloc(nzcnt * DSIZE);
612 for (i = nzcnt-1; i >= 0; i--)
613 matval[i] = 1;
614 cut->branch = ALLOWED_TO_BRANCH_ON;
615 }else{
616 row_list[j]->matval=(double *) realloc((char *)matval, nzcnt * DSIZE);
617 }
618 }
619
620 return(USER_SUCCESS);
621 }
622
623 /*===========================================================================*/
624
625 int user_send_lp_solution(void *user, int varnum, var_desc **vars, double *x,
626 int where)
627 {
628 return(SEND_NONZEROS);
629 }
630
631 /*===========================================================================*/
632
633 /*===========================================================================*\
634 * This routine does logical fixing of variables
635 \*===========================================================================*/
636
637 int user_logical_fixing(void *user, int varnum, var_desc **vars, double *x,
638 char *status, int *num_fixed)
639 {
640 vrp_lp_problem *vrp = (vrp_lp_problem *)user;
641 lp_net *lp_net;
642 int *compdemands, capacity = vrp->capacity;
643 int numchains = 0, v0, v1;
644 lp_net_node *verts;
645 int i;
646 int *edges = vrp->edges;
647 int fixed_num = 0;
648
649 /*This routine could possibly be sped up by using pointers directly
650 as in the min_cut routine */
651
652 /*set up the graph induced by the edges fixed to one*/
653 lp_net = create_lp_net(vrp, status, varnum, vars);
654
655 verts = lp_net->verts;
656
657 compdemands = (int *) calloc (varnum + 1, sizeof(int));
658
659 /*get the connected components of the 1-edge graph*/
660 numchains = vrp_lp_connected(lp_net, compdemands);
661
662 for (i = 0; i < varnum; i++){
663 if (!(status[i] & NOT_FIXED) || (status[i] & VARIABLE_BRANCHED_ON))
664 continue;
665 v0 = edges[(vars[i]->userind) << 1];
666 v1 = edges[((vars[i]->userind) << 1) + 1];
667 if (!v0){
668 if (verts[0].degree == 2*(vrp->numroutes)){
669 /* if the depot has 2*numroutes edges adjacent to it fixed to one,
670 then we can eliminate all other edges adjacent to the depot
671 from the problem*/
672 status[i] = PERM_FIXED_TO_LB;
673 fixed_num++;
674 }
675 }else if ((verts[v0].degree == 2) || (verts[v1].degree == 2)){
676 /* if a particular node has to fixed-to-one edges adjacent to it,
677 then we can eliminate all other edges adjacent to that node from
678 the problem*/
679 fixed_num++;
680 status[i] = PERM_FIXED_TO_LB;
681 }else if (verts[v0].comp == verts[v1].comp){
682 /*if two vertices are in the same component in the 1-edge graph, then
683 the edge between them can be eliminated from the problem*/
684 fixed_num++;
685 status[i] = PERM_FIXED_TO_LB;
686 }else if (compdemands[verts[v0].comp] + compdemands[verts[v1].comp]
687 > capacity){
688 /*if the sum of the demands in two components of the 1-edge graph is
689 greater than the capacity of a truck, then these two components
690 cannot be linked and so any edge that goes bewtween them can be
691 eliminated from the problem*/
692 fixed_num++;
693 status[i] = PERM_FIXED_TO_LB;
694 }
695 }
696
697 *num_fixed = fixed_num;
698
699 free_lp_net(lp_net);
700
701 free((char *)compdemands);
702
703 return(USER_SUCCESS);
704 }
705
706 /*===========================================================================*/
707
708 /*===========================================================================*\
709 * This function generates the 'next' column
710 \*===========================================================================*/
711
712 int user_generate_column(void *user, int generate_what, int cutnum,
713 cut_data **cuts, int prevind, int nextind,
714 int *real_nextind, double *colval, int *colind,
715 int *collen, double *obj, double *lb, double *ub)
716 {
717 vrp_lp_problem *vrp = (vrp_lp_problem *)user;
718 int vh, vl, i;
719 int total_edgenum = vrp->vertnum*(vrp->vertnum-1)/2;
720
721 switch (generate_what){
722 case GENERATE_NEXTIND:
723 /* Here we just have to generate the specified column. First, we
724 determine the endpoints */
725 BOTH_ENDS(nextind, &vh, &vl);
726 *real_nextind = nextind;
727 break;
728 case GENERATE_REAL_NEXTIND:
729 /* In this case, we have to determine what the "real" next edge is*/
730 *real_nextind = nextind;
731 if (prevind >= total_edgenum-1){
732 *real_nextind = -1;
733 return(USER_SUCCESS);
734 }else{
735 if (nextind == -1) nextind = total_edgenum;
736 /*first, cycle through the edges that were eliminated in the root*/
737 for (i = prevind + 1; i < nextind && !vrp->edges[(i<<1)+1]; i++);
738 /*now we should have the next nonzero edge*/
739 vl = vrp->edges[i << 1];
740 vh = vrp->edges[(i << 1) + 1];
741 }
742 if (i == nextind)
743 return(USER_SUCCESS);
744
745 *real_nextind = i;
746 break;
747 }
748
749 /* Now we just have to generate the column corresponding to (vh, vl) */
750
751 {
752 int nzcnt = 0, vertnum = vrp->vertnum;
753 char *coef;
754 cut_data *cut;
755 int j, size;
756 int cliquecount = 0, val;
757 char *clique_array;
758
759 /*__BEGIN_EXPERIMENTAL_SECTION__*/
760 int num_arcs, edge_index;
761 char *cpt;
762 int *arcs = (int *) calloc(total_edgenum, sizeof(int));
763 double bigM, *weights = (double *) calloc(total_edgenum, sizeof(double));
764 char *indicators = (char *) malloc(((vertnum*vertnum)/2)* sizeof(char));
765
766 /*___END_EXPERIMENTAL_SECTION___*/
767 colval[0] = 1;
768 colind[0] = vl; /* supposes vl < vh !!!!!!**********/
769 colval[1] = 1;
770 colind[1] = vh;
771 nzcnt = 2;
772
773 /* The coefficient for each row depends on what kind of cut it
774 is */
775 for (i = 0; i < cutnum; i++){
776 coef = (cut = cuts[i])->coef;
777 switch(cut->type){
778
779 case SUBTOUR_ELIM_SIDE:
780 if (isset(coef, vh) && isset(coef, vl)){
781 colval[nzcnt] = 1;
782 colind[nzcnt++] = vertnum + i;
783 }
784 break;
785
786 case SUBTOUR_ELIM_ACROSS:
787 /* It's important to have isclr here!!!!! see the macros */
788 if (isclr(coef, vh) ^ isclr(coef, vl)){
789 colval[nzcnt] = 1;
790 colind[nzcnt++] = vertnum + i;
791 }
792 break;
793
794 case CLIQUE:
795 size = (vertnum >> DELETE_POWER) + 1;
796 memcpy(&cliquecount, coef, ISIZE);
797 coef += ISIZE;
798 val = 0;
799 for (j = 0; j < cliquecount; j++){
800 clique_array = coef + size * j;
801 if (isset(clique_array, vh) && isset(clique_array, vl))
802 val += 1;
803 }
804 if (val){
805 colval[nzcnt] = val;
806 colind[nzcnt++] = vertnum + i;
807 }
808 break;
809
810 /*__BEGIN_EXPERIMENTAL_SECTION__*/
811 case FARKAS:
812 if (isset(coef, vh) || isset(coef,vl)){
813 cpt = coef + ((vertnum >> DELETE_POWER) + 1);
814 memcpy((char *)&num_arcs, cpt, ISIZE);
815 memcpy((char *)arcs, cpt, ISIZE*(num_arcs + 1));
816 arcs++;
817 cpt += (ISIZE * (num_arcs + 1))/CSIZE;
818 memcpy((char *)weights, cpt, DSIZE*(num_arcs + 1));
819 bigM = (*(double *)weights);
820 weights++;
821 weights = (double *) calloc( total_edgenum, sizeof(double)) ;
822 edge_index = INDEX(vh, vl);
823
824 for (j = 0; j < num_arcs; j++){
825 if ( arcs[j] == edge_index){
826 colval[nzcnt] = weights[j];
827 break;
828 }
829 }
830 if (j == num_arcs) colval[nzcnt] = bigM;
831 colind[nzcnt++] = vertnum + i;
832 arcs--;
833 weights--;
834 }
835 break;
836
837 case NO_COLUMNS:
838 if (isset(coef, vh) || isset(coef,vl)){
839 cpt=coef+ ((vertnum >> DELETE_POWER) + 1);
840 memcpy((char *)&num_arcs, cpt, ISIZE);
841 cpt+= ISIZE /CSIZE;
842 memcpy((char *)arcs, cpt, ISIZE*(num_arcs));
843 cpt+=(ISIZE*(num_arcs ))/CSIZE;
844 memcpy((char *)indicators, cpt, CSIZE*(num_arcs));
845 edge_index=INDEX(vh, vl);
846
847 for (j = 0; j < num_arcs; j++){
848 if ( arcs[j]==edge_index){
849 colval[nzcnt]=(indicators[j]) ? 1.0 : 0.0;
850 break;
851 }
852 }
853 if (j == num_arcs) colval[nzcnt] = -1.0;
854 if (fabs(colval[nzcnt]) >.5) colind[nzcnt++] = i;
855
856 }
857 break;
858
859 /*___END_EXPERIMENTAL_SECTION___*/
860 default:
861 printf("Unrecognized cut type %i!\n", cut->type);
862 }
863
864 /* Set the upper and lower bounds */
865 if (vrp->edges[i << 1] == 0){
866 /*This is a depot edge and we have to check what its ub should be*/
867 /*Recall vrp->demand[0] == total_demand*/
868 if (vrp->demand[0] - vrp->demand[vrp->edges[(i << 1) + 1]] >
869 vrp->capacity*(vrp->numroutes-1))
870 /*in this case, the node cannot be on its own route*/
871 *ub = 1;
872 else
873 *ub = 2;
874 }else{
875 *ub = 1;
876 }
877 *lb = 0;
878 }
879 *collen = nzcnt;
880 *obj = vrp->costs[*real_nextind];
881 /*__BEGIN_EXPERIMENTAL_SECTION__*/
882 FREE(indicators);
883 FREE(arcs);
884 FREE(weights);
885 /*___END_EXPERIMENTAL_SECTION___*/
886 }
887
888 return(USER_SUCCESS);
889 }
890
891 /*===========================================================================*/
892
893 /*===========================================================================*\
894 * You might want to print some statistics on the types and quantities
895 * of cuts or something like that.
896 \*===========================================================================*/
897
898 int user_print_stat_on_cuts_added(void *user, int rownum, waiting_row **rows)
899 {
900 return(USER_DEFAULT);
901 }
902
903 /*===========================================================================*/
904
905 /*===========================================================================*\
906 * You might want to eliminate rows from the local pool based on
907 * knowledge of problem structure.
908 \*===========================================================================*/
909
910 int user_purge_waiting_rows(void *user, int rownum, waiting_row **rows,
911 char *delete_rows)
912 {
913 return(USER_DEFAULT);
914 }
915
916 /*===========================================================================*/
917
918 /*===========================================================================*\
919 * The user has to generate the ubber bounds for the specified (non-base)
920 * variables. Lower bounds are always assumed (w.l.o.g.) to be zero.
921 \*===========================================================================*/
922
923 /* Deprecated function */
924
925 #if 0
926 int user_get_upper_bounds(void *user, int varnum, int *indices, double *ub)
927 {
928 vrp_lp_problem *vrp = (vrp_lp_problem *)user;
929 int *edges = vrp->edges, i;
930 int cap_check = vrp->capacity*(vrp->numroutes-1);
931 int total_demand = vrp->demand[0];
932
933 for (i = 0; i < varnum; i++){
934 if (edges[indices[i] << 1] == 0){
935 /*This is a depot edge and we have to check what its ub should be*/
936 /*Recall vrp->demand[0] == total_demand*/
937 if (total_demand - vrp->demand[edges[(indices[i] << 1) + 1]] >
938 cap_check)
939 /*on this case, the node cannot be on its own route*/
940 ub[i] = 1;
941 else
942 ub[i] = 2;
943 }else{
944 ub[i] = 1;
945 }
946 }
947
948 return(USER_SUCCESS);
949 }
950 #endif
951
952 /*===========================================================================*/
953
954 /*===========================================================================*\
955 * The user might want to generate cuts in the LP using information
956 * about the current tableau, etc. This is for advanced users only.
957 \*===========================================================================*/
958
959 int user_generate_cuts_in_lp(void *user, LPdata *lp_data, int varnum,
960 var_desc **vars, double *x,
961 int *new_row_num, cut_data ***cuts)
962 {
963 return(DO_NOT_GENERATE_CGL_CUTS);
964 }
965
966 /*===========================================================================*/
967
968 /*===========================================================================*\
969 * Free all the user data structures
970 \*===========================================================================*/
971
972 int user_free_lp(void **user)
973 {
974 vrp_lp_problem *vrp = (vrp_lp_problem *)(*user);
975
976 #ifndef COMPILE_IN_CG
977 FREE(vrp->demand);
978 #endif
979 #if 0
980 FREE(vrp->costs);
981 FREE(vrp->edges);
982 FREE(vrp->cur_sol);
983 FREE(vrp);
984 #endif
985 return(USER_SUCCESS);
986 }
987
988 /*===========================================================================*/
989
990 /*===========================================================================*\
991 * This function creates a the network of fixed edges that is used in the
992 * logical fixing routine
993 \*===========================================================================*/
994
995 lp_net *create_lp_net(vrp_lp_problem *vrp, char *status, int edgenum,
996 var_desc **vars)
997 {
998 lp_net *n;
999 lp_net_node *verts;
1000 int nv0 = 0, nv1 = 0;
1001 lp_net_edge *adjlist;
1002 int vertnum = vrp->vertnum, i;
1003 int *demand = vrp->demand;
1004 int *edges = vrp->edges;
1005
1006 n = (lp_net *) calloc (1, sizeof(lp_net));
1007 n->vertnum = vertnum;
1008 n->edgenum = vertnum*(vertnum-1)/2;
1009 n->verts = (lp_net_node *) calloc (n->vertnum, sizeof(lp_net_node));
1010 n->adjlist = (lp_net_edge *) calloc (2*(n->edgenum), sizeof(lp_net_edge));
1011 verts = n->verts;
1012 adjlist = n->adjlist;
1013
1014 for (i = 0; i < edgenum; i++, status++){
1015 if (*status != PERM_FIXED_TO_UB)
1016 continue;
1017 nv0 = edges[vars[i]->userind << 1];
1018 nv1 = edges[(vars[i]->userind << 1) +1];
1019 if (!verts[nv0].first){
1020 verts[nv0].first = adjlist;
1021 verts[nv0].degree += (int) vars[i]->ub;
1022 }
1023 else{
1024 adjlist->next = verts[nv0].first;
1025 verts[nv0].first = adjlist;
1026 verts[nv0].degree += (int) vars[i]->ub;
1027 }
1028 adjlist->other_end = nv1;
1029 adjlist++;
1030 if (!verts[nv1].first){
1031 verts[nv1].first = adjlist;
1032 verts[nv1].degree += (int) vars[i]->ub;
1033 }
1034 else{
1035 adjlist->next = verts[nv1].first;
1036 verts[nv1].first = adjlist;
1037 verts[nv1].degree += (int) vars[i]->ub;
1038 }
1039 adjlist->other_end = nv0;
1040 adjlist++;
1041 }
1042
1043 for (i=0; i< vertnum; i++)
1044 verts[i].demand = demand[i];
1045
1046 return(n);
1047 }
1048
1049 /*===========================================================================*/
1050
1051 /*===========================================================================*\
1052 * This function constructs the connected components of the 1-edges graph
1053 * used in the logical fixing routine
1054 \*===========================================================================*/
1055
1056 int vrp_lp_connected(lp_net *n, int *compdemands)
1057 {
1058 int cur_node = 0, cur_comp = 0;
1059 lp_net_node *verts = n->verts;
1060 int vertnum = n->vertnum;
1061 lp_net_edge *cur_edge;
1062 int *nodes_to_scan, num_nodes_to_scan = 0;
1063
1064 nodes_to_scan = (int *) calloc (vertnum, sizeof(int));
1065
1066 while (TRUE){
1067 for (cur_node = 1; cur_node < vertnum; cur_node++)
1068 if (!verts[cur_node].comp){ /* Look for the first node not already
1069 in a component */
1070 break;
1071 }
1072
1073 if (cur_node == n->vertnum) break; /* we are done */
1074
1075 nodes_to_scan[num_nodes_to_scan++] = cur_node;
1076 /* add the cur_node to the list of nodes to be scanned */
1077 verts[cur_node].comp = ++cur_comp;
1078 /* add the current node to the current component */
1079 compdemands[cur_comp] = verts[cur_node].demand;
1080 while(TRUE){
1081 /* In each iteration of this loop, we take the next node off the
1082 list of nodes to be scanned, add it to the current component, and
1083 then add all its neighbors to the list of nodes to be scanned */
1084 for (cur_node = nodes_to_scan[--num_nodes_to_scan],
1085 verts[cur_node].scanned = TRUE,
1086 cur_edge = verts[cur_node].first,
1087 cur_comp = verts[cur_node].comp;
1088 cur_edge; cur_edge = cur_edge->next){
1089 if (cur_edge->other_end){
1090 if (!verts[cur_edge->other_end].comp){
1091 verts[cur_edge->other_end].comp = cur_comp;
1092 compdemands[cur_comp] += verts[cur_edge->other_end].demand;
1093 nodes_to_scan[num_nodes_to_scan++] = cur_edge->other_end;
1094 }
1095 }
1096 }
1097 if (!num_nodes_to_scan) break;
1098 /* when there are no more nodes to scan, we start a new component */
1099 }
1100 }
1101
1102 free((char *) nodes_to_scan);
1103 return(cur_comp);
1104 }
1105
1106 /*===========================================================================*/
1107
1108 /*===========================================================================*\
1109 * Free the data structures associated with the 1-edges graph
1110 \*===========================================================================*/
1111
1112 void free_lp_net(lp_net *n)
1113 {
1114 if (n){
1115 FREE(n->adjlist);
1116 FREE(n->verts);
1117 FREE(n);
1118 }
1119 }
1120
1121 /*===========================================================================*/
1122
1123 void construct_feasible_solution(vrp_lp_problem *vrp, network *n,
1124 double *true_objval)
1125 {
1126 _node *tour = vrp->cur_sol;
1127 int cur_vert = 0, prev_vert = 0, cur_route, count;
1128 elist *cur_route_start = NULL;
1129 edge *edge_data;
1130 vertex *verts = n->verts;
1131 double cost = 0;
1132
1133 /*construct the tour corresponding to this solution vector*/
1134 for (cur_route_start = verts[0].first, cur_route = 1, cost = 0,
1135 edge_data = cur_route_start->data; cur_route <= vrp->numroutes;
1136 cur_route++){
1137 edge_data = cur_route_start->data;
1138 edge_data->scanned = TRUE;
1139 cur_vert = edge_data->v1;
1140 tour[prev_vert].next = cur_vert;
1141 tour[cur_vert].route = cur_route;
1142 prev_vert = 0;
1143 cost += vrp->costs[INDEX(prev_vert, cur_vert)];
1144 while (cur_vert){
1145 if (verts[cur_vert].first->other_end != prev_vert){
1146 prev_vert = cur_vert;
1147 edge_data = verts[cur_vert].first->data;
1148 cur_vert = verts[cur_vert].first->other_end;
1149 }
1150 else{
1151 prev_vert = cur_vert;
1152 edge_data = verts[cur_vert].last->data; /*This statement could
1153 possibly be taken out to
1154 speed things up a bit*/
1155 cur_vert = verts[cur_vert].last->other_end;
1156 }
1157 tour[prev_vert].next = cur_vert;
1158 tour[cur_vert].route = cur_route;
1159 cost += vrp->costs[INDEX(prev_vert, cur_vert)];
1160 }
1161 edge_data->scanned = TRUE;
1162
1163 while (cur_route_start->data->scanned){
1164 if (!(cur_route_start = cur_route_start->next_edge)) break;
1165 }
1166 }
1167 *true_objval = cost;
1168
1169 /* Display the solution */
1170
1171 printf("\nSolution Found:\n");
1172 printf("Solution Cost: %.0f\n", cost);
1173
1174 cur_vert = tour[0].next;
1175
1176 if (tour[0].route == 1)
1177 printf("\n0 ");
1178 while (cur_vert != 0){
1179 if (tour[prev_vert].route != tour[cur_vert].route){
1180 printf("\nRoute #%i: ", tour[cur_vert].route);
1181 count = 0;
1182 }
1183 printf("%i ", cur_vert);
1184 count++;
1185 if (count > 15){
1186 printf("\n");
1187 count = 0;
1188 }
1189 prev_vert = cur_vert;
1190 cur_vert = tour[cur_vert].next;
1191 }
1192 printf("\n\n");
1193 }
1194
1195 /*__BEGIN_EXPERIMENTAL_SECTION__*/
1196 #ifdef TRACE_PATH
1197
1198 #include "sym_lp.h"
1199
1200 void check_lp(lp_prob *p)
1201 {
1202 LPdata *lp_data = p->lp_data;
1203 int i, j, l;
1204 tm_prob *tm = p->tm;
1205 double *x = (double *) malloc(tm->feas_sol_size * DSIZE), lhs, cost = 0;
1206 double *lhs_totals = (double *) calloc(lp_data->m, DSIZE);
1207 MakeMPS(lp_data, 0, 0);
1208
1209 get_x(lp_data);
1210
1211 printf("Optimal Fractional Solution: %.10f\n", lp_data->lpetol);
1212 for (i = 0; i < lp_data->n; i++){
1213 if (lp_data->x[i] > lp_data->lpetol){
1214 printf("uind: %i colind: %i value: %.10f cost: %f\n",
1215 lp_data->vars[i]->userind, i, lp_data->x[i], lp_data->obj[i]);
1216 }
1217 cost += lp_data->obj[i]*lp_data->x[i];
1218 }
1219 printf("Cost: %f\n", cost);
1220
1221 printf("\nFeasible Integer Solution:\n");
1222 for (cost = 0, i = 0; i < tm->feas_sol_size; i++){
1223 printf("uind: %i ", tm->feas_sol[i]);
1224 for (j = 0; j < lp_data->n; j++){
1225 if (lp_data->vars[j]->userind == tm->feas_sol[i]){
1226 cost += lp_data->obj[j];
1227 printf("colind: %i lb: %f ub: %f obj: %f\n", j, lp_data->lb[j],
1228 lp_data->ub[j], lp_data->obj[j]);
1229 break;
1230 }
1231 }
1232 if (j == lp_data->n)
1233 printf("\n\nERROR!!!!!!!!!!!!!!!!\n\n");
1234 x[i] = 1.0;
1235 }
1236 printf("Cost: %f\n", cost);
1237
1238 printf("\nChecking LP....\n\n");
1239 printf("Number of cuts: %i\n", lp_data->m);
1240 for (i = 0; i < tm->feas_sol_size; i++){
1241 for (j = 0; j < lp_data->n; j++){
1242 if (tm->feas_sol[i] == lp_data->vars[j]->userind)
1243 break;
1244 }
1245 for (l = lp_data->matbeg[j]; l < lp_data->matbeg[j] + lp_data->matcnt[j];
1246 l++){
1247 lhs_totals[lp_data->matind[l]] += 1;
1248 }
1249 }
1250 for (i = 0; i < p->base.cutnum; i++){
1251 printf("Cut %i: %f %c %f\n", i, lhs_totals[i], lp_data->sense[i],
1252 lp_data->rhs[i]);
1253 }
1254 for (; i < lp_data->m; i++){
1255 lhs = compute_lhs(tm->feas_sol_size, tm->feas_sol, x,
1256 lp_data->rows[i].cut, p->base.cutnum);
1257 printf("Cut %i: %f %f %c %f\n", i, lhs_totals[i], lhs, lp_data->sense[i],
1258 lp_data->rhs[i]);
1259 if (lp_data->rows[i].cut->sense == 'G' ?
1260 lhs < lp_data->rows[i].cut->rhs : lhs > lp_data->rows[i].cut->rhs){
1261 printf("LP: ERROR -- row is violated by feasible solution!!!\n");
1262 sleep(600);
1263 exit(1);
1264 }
1265 }
1266 }
1267 #endif
1268 /*___END_EXPERIMENTAL_SECTION___*/