Debian Codegraph @

SYMPHONY/Applications/CNRP/include/cnrp_lp.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 _CNRP_LP_H
17 #define _CNRP_LP_H
18
19 #define COMPILING_FOR_LP
20
21 /* SYMPHONY include files */
22 #include "sym_types.h"
23
24 /* CNRP include files */
25 #include "cnrp_lp_params.h"
26 #include "cnrp_common_types.h"
27 #include "network.h"
28
29 #define BEST_K 0
30 #define VARS_CLOSEST_TO_HALF 1
31 #define DEPOTS_CLOSEST_TO_HALF 2
32 #define DEPOTS_CLOSEST_TO_HALF_BRANCH_RIGHT 3
33 #define VARS_CLOSEST_TO_HALF_PREFER_DEPOT 4
34 #define DEPOTS_AT_HALF_BRANCH_RIGHT 5
35 #define DEPOTS_AT_HALF 6
36 #define VARS_AT_HALF_PREFER_DEPOT_BRANCH_RIGHT 7
37 #define VARS_AT_HALF_PREFER_DEPOT 8
38 #define VARS_CLOSEST_TO_HALF_PREFER_DEPOT_BRANCH_RIGHT 9
39 #define VARS_AT_HALF 10
40
41 typedef struct POS_WEIGHT_LHS{
42 int position;
43 double lhs;
44 }p_w_l;
45
46 /*---------------------------------------------------------------------------*\
47 | This is the data structure used to store the edges in the 1-edges graph |
48 | used the logical fixing routine |
49 \*---------------------------------------------------------------------------*/
50
51 typedef struct LP_NET_EDGE{
52 struct LP_NET_EDGE *next;
53 int other_end;
54 }lp_net_edge;
55
56 /*---------------------------------------------------------------------------*\
57 | Another data structure used to store the 1-edges graph |
58 \*---------------------------------------------------------------------------*/
59
60 typedef struct LP_NET_NODE{
61 lp_net_edge *first;
62 int degree;
63 int comp;
64 double demand;
65 char scanned;
66 }lp_net_node;
67
68 /*---------------------------------------------------------------------------*\
69 | This is where the 1-edges graph is actually stored |
70 \*---------------------------------------------------------------------------*/
71
72 typedef struct LP_NET{
73 lp_net_node *verts;
74 lp_net_edge *adjlist;
75 int vertnum;
76 int edgenum;
77 }lp_net;
78
79 /*---------------------------------------------------------------------------*\
80 | Here we store the specific data needed to process each node of the tree |
81 \*---------------------------------------------------------------------------*/
82
83 typedef struct CNRP_SPEC{
84 cnrp_lp_params par;
85 int window; /*contains the tid of the graphics window*/
86 int vertnum; /*the number of nodes in the problem,
87 including the depot */
88 double *demand; /*a list of the customer demands*/
89 double capacity; /*the capacity of the trucks*/
90 int numroutes; /*contains the number of routes that the problem
91 is to be solved with. can be prespecified. */
92 double utopia_fixed;
93 double utopia_variable;
94 int *edges; /*contains a list of the edges in the current
95 subproblem*/
96 int *costs; /*contains the objective function values*/
97 _node *cur_sol;
98 int *cur_sol_tree;
99 double variable_cost;
100 double fixed_cost;
101 double ub;
102 }cnrp_spec;
103
104 /*---------------------------------------------------------------------------*\
105 | Routines entirely specific to main_lp |
106 \*---------------------------------------------------------------------------*/
107
108 lp_net *create_lp_net PROTO((cnrp_spec *cnrp, char *status, int edgenum,
109 var_desc **vars));
110 int cnrp_lp_connected PROTO((lp_net *n, double *compdemands));
111 void free_lp_net PROTO((lp_net *n));
112 char construct_feasible_solution PROTO((cnrp_spec *cnrp, network *n,
113 double *objval, double etol,
114 char branch));
115 double compute_lhs PROTO((int number, int *indices, double *values,
116 cut_data *cut, int vertnum));
117
118 #endif