Debian Codegraph @

SYMPHONY/Applications/CNRP/include/cnrp_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 /* Capacitated Network Routing Problems. */
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 _CUT_GEN_USER_H
17 #define _CUT_GEN_USER_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 /* CNRP include files */
27 #include "network.h"
28 #include "cnrp_cg_params.h"
29
30 typedef struct CG_CNRP_SPEC{
31 cnrp_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 double *demand; /* a list of the customer demands*/
36 double 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 double *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 }cg_cnrp_spec;
69
70 /*===========================================================================*/
71 /*========================= Other user subroutines =========================*/
72 /*===========================================================================*/
73
74 int check_connectivity PROTO((network *n, double etol, double capacity,
75 int numroutes, char mult, int *num_cuts,
76 int *alloc_cuts, cut_data ***cuts));
77
78 int check_flow_connectivity PROTO((network *n, double etol, double capacity,
79 int numroutes, char mult, int *num_cuts,
80 int *alloc_cuts, cut_data ***cuts));
81
82 /*===========================================================================*/
83 /*=============================== shrink.c ==================================*/
84 /*===========================================================================*/
85
86 int reduce_graph PROTO((network *n, double etol, double *demand,
87 double capacity, int mult, cut_data *new_cut,
88 int *num_cuts, int *alloc_cuts, cut_data ***cuts));
89 int greedy_shrinking1 PROTO((network *n, double truck_cap, double etol,
90 int max_num_cuts, cut_data *new_cut,
91 int *compnodes, int *compmembers, int compnum,
92 char *in_set, double *cut_val,int *ref,
93 char *cut_list, double *demand, int mult,
94 int *num_cuts, int *alloc_cuts,
95 cut_data ***cuts));
96 int greedy_shrinking1_dicut PROTO((network *n, double truck_cap, double etol,
97 int max_num_cuts, cut_data *new_cut,
98 int *compnodes, int *compmembers, int compnum,
99 char *in_set, double *cut_val,int *ref,
100 char *cut_list, double *demand, int mult,
101 int *num_cuts, int *alloc_cuts,
102 cut_data ***cuts));
103 int greedy_shrinking6 PROTO((network *n, double truck_cap,
104 double etol, cut_data *new_cut,
105 int *compnodes,
106 int *compmembers, int compnum, char *in_set,
107 double *cut_val,int *ref, char *cut_list,
108 int max_num_cuts, double *demand, int trial_num,
109 double prob, int mult, int *num_cuts,
110 int *alloc_cuts, cut_data ***cuts));
111 int greedy_shrinking6_dicut PROTO((network *n, double truck_cap,
112 double etol, cut_data *new_cut,
113 int *compnodes,
114 int *compmembers, int compnum, char *in_set,
115 double *cut_val,int *ref, char *cut_list,
116 int max_num_cuts, double *demand, int trial_num,
117 double prob, int mult, int *num_cuts,
118 int *alloc_cuts, cut_data ***cuts));
119 int greedy_shrinking1_one PROTO((network *n, double truck_cap,
120 double etol, int max_num_cuts,
121 cut_data *new_cut, char *in_set,
122 double *cut_val, char *cut_list,
123 int num_routes, double *demand,
124 int mult, int *num_cuts,
125 int *alloc_cuts, cut_data ***cuts));
126 int greedy_shrinking6_one PROTO((network *n, double truck_cap,
127 double etol, cut_data *new_cut,
128 char *in_set, double *cut_val, int num_routes,
129 char *cut_list, int max_num_cuts,
130 double *demand,int trial_num, double prob,
131 int mult, int *num_cuts,
132 int *alloc_cuts, cut_data ***cuts));
133 int greedy_shrinking2_one PROTO((network *n, double truck_cap,
134 double etol, cut_data *new_cut,
135 char *in_set, double *cut_val, int num_routes,
136 double *demand, int mult, int *num_cuts,
137 int *alloc_cuts, cut_data ***cuts));
138
139 /*===========================================================================*/
140 /*============================ biconnected.c ================================*/
141 /*===========================================================================*/
142
143 void depth_first_search PROTO((vertex *v, int *count1, int *count2));
144 int biconnected PROTO((network *n, int *compnodes, double *compdemands,
145 double *compcuts));
146 void compute_comp_nums PROTO((vertex *v, int parent_comp, int *num_comps,
147 char parent_is_art_point));
148 int tsp_cuts PROTO((network *n, int verbosity, char tsp_prob, int which_cuts,
149 cut_data ***cuts, int *num_cuts, int *alloc_cuts));
150
151 #endif