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 /* Capacitated Network Routing Problems. */ 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 _CNRP_TYPES_H 00017 #define _CNRP_TYPES_H 00018 00019 /* SYMPHONY include files */ 00020 #include "sym_proto.h" 00021 00022 /* CNRP include files */ 00023 #include "cnrp_common_types.h" 00024 #include "cnrp_cg_params.h" 00025 #include "cnrp_lp_params.h" 00026 #include "cnrp_cp_params.h" 00027 00028 /*---------------------------------------------------------------------------*\ 00029 * The "small_graph" data structure is used to store the subset of the 00030 * edges that will be used initially in actually solving the problem. 00031 * These edges usually consist of any edges found among the ones used in 00032 * the heuristics solutions and the set of shortest edges adjacent to 00033 * each node in the graph 00034 \*---------------------------------------------------------------------------*/ 00035 00036 typedef struct SMALL_GRAPH{ /* this gets passed eg. to lin-kerninghan */ 00037 int vertnum; /* vertnum in the restricted (small) graph */ 00038 int edgenum; /* edgenum in the restricted (small) graph */ 00039 int allocated_edgenum; 00040 int del_edgenum; 00041 edge_data *edges; /* The data for these edges */ 00042 }small_graph; 00043 00044 typedef struct CLOSENODE{ /*close node to a particular one */ 00045 int node; 00046 int cost; 00047 }closenode; 00048 00049 typedef struct CNRP_PARAMS{ 00050 char infile[MAX_FILE_NAME_LENGTH + 1]; 00051 int verbosity; 00052 char prob_type; 00053 int k_closest; 00054 int min_closest; 00055 int max_closest; 00056 int add_all_edges; 00057 int add_depot_edges; 00058 int base_variable_selection; 00059 int use_small_graph; 00060 char small_graph_file[MAX_FILE_NAME_LENGTH]; 00061 int colgen_strat[2]; 00062 #ifdef MULTI_CRITERIA 00063 double binary_search_tolerance; 00064 double compare_solution_tolerance; 00065 #endif 00066 int test; 00067 char test_dir[MAX_FILE_NAME_LENGTH +1]; /* Test files directory */ 00068 }cnrp_params; 00069 00070 /*---------------------------------------------------------------------------*\ 00071 * The problem data structure contains the data for a problem instance, as 00072 * well as some of the tours that have been generated. 00073 \*---------------------------------------------------------------------------*/ 00074 00075 typedef struct CNRP_PROBLEM{ 00076 char name[100]; /* the name of the problem instance */ 00077 cnrp_params par; 00078 cnrp_cg_params cg_par; 00079 cnrp_lp_params lp_par; 00080 cnrp_cp_params cp_par; 00081 int dg_id; /* drawgraph process id */ 00082 int vertnum; /* the number of nodes in the problem, including 00083 the depot */ 00084 int edgenum; /* number of edges in the problem */ 00085 int *edges; 00086 int numroutes; /* contains the number of routes that the problem 00087 is to be solved with. can be prespecified. */ 00088 int depot; /* the index of the depot, usually 1 */ 00089 double capacity; /* the capacity of a truck */ 00090 double *demand; /* an array containing the demands for each node. 00091 node i's demand is p->demand[i-1] */ 00092 int *posx; /* x coordinate for display purposes */ 00093 int *posy; /* y coordinate for display purposes */ 00094 00095 distances dist; /* the data about the distances in the problem */ 00096 00097 best_tours *cur_tour; /* temporary tour storage */ 00098 int *cur_sol_tree; 00099 double fixed_cost; 00100 double variable_cost; 00101 double utopia_fixed; 00102 double utopia_variable; 00103 double ub; 00104 small_graph *g; /* contains the edge data for the reduced graph*/ 00105 #if defined(CHECK_CUT_VALIDITY) || defined(TRACE_PATH) 00106 int feas_sol_size; 00107 int *feas_sol; 00108 #endif 00109 int basecutnum; 00110 int *basevars; 00111 int basevarnum; 00112 int *extravars; 00113 int extravarnum; 00114 int *zero_vars; 00115 int zero_varnum; 00116 }cnrp_problem; 00117 00118 #endif