Debian Codegraph @

SYMPHONY/Applications/VRP/include/vrp_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 /* 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_LP_H
17 #define _VRP_LP_H
18
19 #define COMPILING_FOR_LP
20
21 /* SYMPHONY include files */
22 #include "sym_types.h"
23
24 /* VRP include files */
25 #include "vrp_lp_params.h"
26 #include "vrp_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 int 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 vrp specific data needed to process each node of the tree |
81 \*---------------------------------------------------------------------------*/
82
83 typedef struct VRP_LP_PROBLEM{
84 vrp_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 int *demand; /* alist of the customer demands*/
89 int 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 int *edges; /*contains a list of the edges in the current
93 subproblem*/
94 int *costs; /*contains the objective function values*/
95 _node *cur_sol;
96 }vrp_lp_problem;
97
98 /*---------------------------------------------------------------------------*\
99 | Routines entirely specific to main_lp |
100 \*---------------------------------------------------------------------------*/
101
102 lp_net *create_lp_net PROTO((vrp_lp_problem *vrp, char *status, int edgenum,
103 var_desc **vars));
104 int vrp_lp_connected PROTO((lp_net *n, int *compdemands));
105 void free_lp_net PROTO((lp_net *n));
106 void construct_feasible_solution PROTO((vrp_lp_problem *vrp, network *n,
107 double *true_objval));
108 double compute_lhs PROTO((int number, int *indices, double *values,
109 cut_data *cut, int vertnum));
110
111 #endif