00001 /*===========================================================================*/ 00002 /* */ 00003 /* This file is part of a demonstration application for use with the */ 00004 /* SYMPHONY Branch, Cut, and Price Library. This application is a solver for */ 00005 /* the Vehicle Routing Problem and the Traveling Salesman Problem. */ 00006 /* */ 00007 /* (c) Copyright 2000-2008 Ted Ralphs. All Rights Reserved. */ 00008 /* */ 00009 /* This application was developed by Ted Ralphs (tkralphs@lehigh.edu) */ 00010 /* */ 00011 /* This software is licensed under the Common Public License. Please see */ 00012 /* accompanying file for terms. */ 00013 /* */ 00014 /*===========================================================================*/ 00015 00016 #ifndef _VRP_LP_H 00017 #define _VRP_LP_H 00018 00019 #define COMPILING_FOR_LP 00020 00021 /* SYMPHONY include files */ 00022 #include "sym_types.h" 00023 00024 /* VRP include files */ 00025 #include "vrp_lp_params.h" 00026 #include "vrp_common_types.h" 00027 #include "network.h" 00028 00029 #define BEST_K 0 00030 #define VARS_CLOSEST_TO_HALF 1 00031 #define DEPOTS_CLOSEST_TO_HALF 2 00032 #define DEPOTS_CLOSEST_TO_HALF_BRANCH_RIGHT 3 00033 #define VARS_CLOSEST_TO_HALF_PREFER_DEPOT 4 00034 #define DEPOTS_AT_HALF_BRANCH_RIGHT 5 00035 #define DEPOTS_AT_HALF 6 00036 #define VARS_AT_HALF_PREFER_DEPOT_BRANCH_RIGHT 7 00037 #define VARS_AT_HALF_PREFER_DEPOT 8 00038 #define VARS_CLOSEST_TO_HALF_PREFER_DEPOT_BRANCH_RIGHT 9 00039 #define VARS_AT_HALF 10 00040 00041 typedef struct POS_WEIGHT_LHS{ 00042 int position; 00043 double lhs; 00044 }p_w_l; 00045 00046 /*---------------------------------------------------------------------------*\ 00047 | This is the data structure used to store the edges in the 1-edges graph | 00048 | used the logical fixing routine | 00049 \*---------------------------------------------------------------------------*/ 00050 00051 typedef struct LP_NET_EDGE{ 00052 struct LP_NET_EDGE *next; 00053 int other_end; 00054 }lp_net_edge; 00055 00056 /*---------------------------------------------------------------------------*\ 00057 | Another data structure used to store the 1-edges graph | 00058 \*---------------------------------------------------------------------------*/ 00059 00060 typedef struct LP_NET_NODE{ 00061 lp_net_edge *first; 00062 int degree; 00063 int comp; 00064 int demand; 00065 char scanned; 00066 }lp_net_node; 00067 00068 /*---------------------------------------------------------------------------*\ 00069 | This is where the 1-edges graph is actually stored | 00070 \*---------------------------------------------------------------------------*/ 00071 00072 typedef struct LP_NET{ 00073 lp_net_node *verts; 00074 lp_net_edge *adjlist; 00075 int vertnum; 00076 int edgenum; 00077 }lp_net; 00078 00079 /*---------------------------------------------------------------------------*\ 00080 | Here we store the vrp specific data needed to process each node of the tree | 00081 \*---------------------------------------------------------------------------*/ 00082 00083 typedef struct VRP_LP_PROBLEM{ 00084 vrp_lp_params par; 00085 int window; /*contains the tid of the graphics window*/ 00086 int vertnum; /*the number of nodes in the problem, 00087 including the depot */ 00088 int *demand; /* alist of the customer demands*/ 00089 int capacity; /*the capacity of the trucks*/ 00090 int numroutes; /*contains the number of routes that the problem 00091 is to be solved with. can be prespecified. */ 00092 int *edges; /*contains a list of the edges in the current 00093 subproblem*/ 00094 int *costs; /*contains the objective function values*/ 00095 _node *cur_sol; 00096 }vrp_lp_problem; 00097 00098 /*---------------------------------------------------------------------------*\ 00099 | Routines entirely specific to main_lp | 00100 \*---------------------------------------------------------------------------*/ 00101 00102 lp_net *create_lp_net PROTO((vrp_lp_problem *vrp, char *status, int edgenum, 00103 var_desc **vars)); 00104 int vrp_lp_connected PROTO((lp_net *n, int *compdemands)); 00105 void free_lp_net PROTO((lp_net *n)); 00106 void construct_feasible_solution PROTO((vrp_lp_problem *vrp, network *n, 00107 double *true_objval)); 00108 double compute_lhs PROTO((int number, int *indices, double *values, 00109 cut_data *cut, int vertnum)); 00110 00111 #endif
1.4.7