/home/coin/SVN-release/CoinAll-1.1.0/SYMPHONY/Applications/VRP/include/vrp_cg.h

Go to the documentation of this file.

/*===========================================================================*/
/*                                                                           */
/* This file is part of a demonstration application for use with the         */
/* SYMPHONY Branch, Cut, and Price Library. This application is a solver for */
/* the Vehicle Routing Problem and the Traveling Salesman Problem.           */
/*                                                                           */
/* (c) Copyright 2000-2008 Ted Ralphs. All Rights Reserved.                  */
/*                                                                           */
/* This application was developed by Ted Ralphs (tkralphs@lehigh.edu)        */
/*                                                                           */
/* This software is licensed under the Common Public License. Please see     */
/* accompanying file for terms.                                              */
/*                                                                           */
/*===========================================================================*/

#ifndef _VRP_CG_H
#define _VRP_CG_H

/* system include files */
#include <stdio.h>

/* SYMPHONY include files */
#include "sym_types.h"
#include "sym_proto.h"

/* VRP include files */
#include "network.h"
#include "vrp_cg_params.h"

typedef struct VRP_CG_PROBLEM{
   vrp_cg_params par;
   int           dg_id;   /*contains the tid of the graphics window*/
   int           vertnum;  /*the number of nodes in the problem,
                              including the depot                */
   int          *demand;   /* alist of the customer demands*/
   int           capacity; /*the capacity of the trucks*/
   int           numroutes;/*contains the number of routes that the problem
                              is to be solved with. can be prespecified.  */
   int          *edges;    /*contains a list of the edges in the current
                              subproblem*/
   network      *n;
   int           orig_edgenum;
   int          *cost;
   int          *ref;      /* the last five  are for the shrinking routines; */
   char         *in_set;   /* They are here to optimize/speed up things */
   int          *new_demand;
   double       *cut_val;
   char         *cut_list;


#ifdef CHECK_CUT_VALIDITY
   int           feas_sol_size;
   int          *feas_sol;
#endif
}vrp_cg_problem;

/*===========================================================================*/
/*========================= Other user subroutines =========================*/
/*===========================================================================*/

void check_connectivity PROTO((network *n, double etol, int capacity,
                              int numroutes, cut_data ***cuts,
                              int *num_cuts, int *alloc_cuts));

/*===========================================================================*/
/*=============================== shrink.c ==================================*/
/*===========================================================================*/

void reduce_graph PROTO((network *n, double etol, int *demand));
int greedy_shrinking1 PROTO((network *n, double truck_cap, double etol,
                             int max_num_cuts, cut_data *new_cut,
                             int *compnodes, int *compmembers, int compnum,
                             char *in_set, double *cut_val,int *ref,
                             char *cut_list, int *demand, cut_data ***cuts,
                             int *num_cuts, int *alloc_cuts));
int greedy_shrinking6 PROTO((network *n, double truck_cap,
                             double etol, cut_data *new_cut,
                             int *compnodes,
                             int *compmembers, int compnum, char *in_set,
                             double *cut_val,int *ref, char *cut_list,
                             int max_num_cuts, int *demand, int trial_num,
                             double prob, cut_data ***cuts, int *num_cuts,
                             int *alloc_cuts));
int greedy_shrinking1_one PROTO((network *n, double truck_cap,
                                 double etol, int max_num_cuts,
                                 cut_data *new_cut, char *in_set,
                                 double *cut_val, char *cut_list,
                                 int num_routes, int *demand, cut_data ***cuts,
                                 int *num_cuts, int *alloc_cuts));
int greedy_shrinking6_one PROTO((network *n, double truck_cap,
                                 double etol, cut_data *new_cut,
                                 char *in_set, double *cut_val, int num_routes,
                                 char *cut_list, int max_num_cuts,
                                 int *demand,int trial_num, double prob,
                                 cut_data ***cuts, int *num_cuts,
                                 int *alloc_cuts));
int greedy_shrinking2_one PROTO((network *n, double truck_cap,
                                 double etol, cut_data *new_cut,
                                 char *in_set, double *cut_val, int num_routes,
                                 int *demand, cut_data ***cuts, int *num_cuts,
                                 int *alloc_cuts));

/*===========================================================================*/
/*============================ biconnected.c ================================*/
/*===========================================================================*/

void depth_first_search PROTO((vertex *v, int *count1, int *count2));
int biconnected PROTO((network *n, int *compnodes, int
                           *compdemands, double *compcuts));
void compute_comp_nums PROTO((vertex *v, int parent_comp, int *num_comps,
                       char parent_is_art_point));

/*===========================================================================*/
/*================================ tsp.c ====================================*/
/*===========================================================================*/

int tsp_cuts PROTO((network *n, int verbosity, char tsp_prob, int which_cuts,
                    cut_data ***cuts, int *num_cuts, int *alloc_cuts));

#endif

---