Debian Codegraph @

SYMPHONY/Applications/VRP/include/vrp_cg.h

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-2013 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 #ifndef _VRP_CG_H
17 #define _VRP_CG_H
18
19 /* system include files */
20 #include <stdio.h>
21
22 /* SYMPHONY include files */
23 #include "sym_types.h"
24 #include "sym_proto.h"
25
26 /* VRP include files */
27 #include "network.h"
28 #include "vrp_cg_params.h"
29
30 typedef struct VRP_CG_PROBLEM{
31 vrp_cg_params par;
32 int dg_id; /*contains the tid of the graphics window*/
33 int vertnum; /*the number of nodes in the problem,
34 including the depot */
35 int *demand; /* alist of the customer demands*/
36 int capacity; /*the capacity of the trucks*/
37 int numroutes;/*contains the number of routes that the problem
38 is to be solved with. can be prespecified. */
39 int *edges; /*contains a list of the edges in the current
40 subproblem*/
41 network *n;
42 int orig_edgenum;
43 int *cost;
44 int *ref; /* the last five are for the shrinking routines; */
45 char *in_set; /* They are here to optimize/speed up things */
46 int *new_demand;
47 double *cut_val;
48 char *cut_list;
49
50 /*__BEGIN_EXPERIMENTAL_SECTION__*/
51 int *dec_data;
52 int last_decomp_index;
53 double last_objval;
54 FILE *decomp_res;
55 /* the next four arrays pertain to storing no-columns cuts - kind of an
56 auxiliary cutpool*/
57 int **data;
58 char **indicators;
59 int *ones;
60 int *size;
61 int num_nocolscuts;
62 /*___END_EXPERIMENTAL_SECTION___*/
63
64 #ifdef CHECK_CUT_VALIDITY
65 int feas_sol_size;
66 int *feas_sol;
67 #endif
68 }vrp_cg_problem;
69
70 /*===========================================================================*/
71 /*========================= Other user subroutines =========================*/
72 /*===========================================================================*/
73
74 void check_connectivity PROTO((network *n, double etol, int capacity,
75 int numroutes, cut_data ***cuts,
76 int *num_cuts, int *alloc_cuts));
77
78 /*===========================================================================*/
79 /*=============================== shrink.c ==================================*/
80 /*===========================================================================*/
81
82 void reduce_graph PROTO((network *n, double etol, int *demand));
83 int greedy_shrinking1 PROTO((network *n, double truck_cap, double etol,
84 int max_num_cuts, cut_data *new_cut,
85 int *compnodes, int *compmembers, int compnum,
86 char *in_set, double *cut_val,int *ref,
87 char *cut_list, int *demand, cut_data ***cuts,
88 int *num_cuts, int *alloc_cuts));
89 int greedy_shrinking6 PROTO((network *n, double truck_cap,
90 double etol, cut_data *new_cut,
91 int *compnodes,
92 int *compmembers, int compnum, char *in_set,
93 double *cut_val,int *ref, char *cut_list,
94 int max_num_cuts, int *demand, int trial_num,
95 double prob, cut_data ***cuts, int *num_cuts,
96 int *alloc_cuts));
97 int greedy_shrinking1_one PROTO((network *n, double truck_cap,
98 double etol, int max_num_cuts,
99 cut_data *new_cut, char *in_set,
100 double *cut_val, char *cut_list,
101 int num_routes, int *demand, cut_data ***cuts,
102 int *num_cuts, int *alloc_cuts));
103 int greedy_shrinking6_one PROTO((network *n, double truck_cap,
104 double etol, cut_data *new_cut,
105 char *in_set, double *cut_val, int num_routes,
106 char *cut_list, int max_num_cuts,
107 int *demand,int trial_num, double prob,
108 cut_data ***cuts, int *num_cuts,
109 int *alloc_cuts));
110 int greedy_shrinking2_one PROTO((network *n, double truck_cap,
111 double etol, cut_data *new_cut,
112 char *in_set, double *cut_val, int num_routes,
113 int *demand, cut_data ***cuts, int *num_cuts,
114 int *alloc_cuts));
115
116 /*===========================================================================*/
117 /*============================ biconnected.c ================================*/
118 /*===========================================================================*/
119
120 void depth_first_search PROTO((vertex *v, int *count1, int *count2));
121 int biconnected PROTO((network *n, int *compnodes, int
122 *compdemands, double *compcuts));
123 void compute_comp_nums PROTO((vertex *v, int parent_comp, int *num_comps,
124 char parent_is_art_point));
125
126 /*===========================================================================*/
127 /*================================ tsp.c ====================================*/
128 /*===========================================================================*/
129
130 int tsp_cuts PROTO((network *n, int verbosity, char tsp_prob, int which_cuts,
131 cut_data ***cuts, int *num_cuts, int *alloc_cuts));
132
133 #endif