- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

VrpModel.h
Go to the documentation of this file.
1 /*===========================================================================*
2 * This file is part of a solver for the Vehicle Routing Problem *
3 * developed using the BiCePS Linear Integer Solver (BLIS). *
4 * *
5 * This solver is distributed under the Eclipse Public License as part of *
6 * the COIN-OR repository (http://www.coin-or.org). *
7 * *
8 * Authors: Yan Xu, Lehigh University *
9 * Ted Ralphs, Lehigh University *
10 * *
11 * Copyright (C) 2007 Yan Xu and Ted Ralphs. *
12 * All Rights Reserved. *
13 *===========================================================================*/
14
15 #ifndef VrpModel_h_
16 #define VrpModel_h_
17
18 //#############################################################################
19
20 #include <vector>
21
22 #include "BlisModel.h"
23 #include "VrpVariable.h"
24 #include "VrpCommonTypes.h"
25 #include "VrpConstants.h"
26 #include "VrpParams.h"
27 #include "VrpCutGenerator.h"
28
29 //#############################################################################
30
32 class VrpModel : public BlisModel
33 {
34
35 friend class VrpCutGenerator;
36 friend class VrpSolution;
37
38 private:
39
40 char name_[100];
41 int vertnum_;
42 int edgenum_;
43 int numroutes_;
44 int depot_;
45 int capacity_;
46 int wtype_;
47 int *demand_; /*vertnum_*/
48 int *posx_; /*vertnum_*/
49 int *posy_; /*vertnum_*/
50 double *coordx_; /*vertnum_*/
51 double *coordy_; /*vertnum_*/
52 double *coordz_; /*vertnum_*/
53 double etol_;
54
55 VrpParams *VrpPar_;
56 VrpNetwork *n_; /* Allocate when readInstance (no data filled in). */
57
58 // edges_ hold the same elements as variables_ does, do not free memory.
59 // For parallel, reinsert elements in variables_ to edges_
60 std::vector<VrpVariable *> edges_;
61
62 protected:
63
68 void setModelData();
69
70 public:
71
73 VrpModel() : vertnum_(0), edgenum_(0), numroutes_(0), depot_(0),
74 capacity_(0), wtype_(0), etol_(1e-5){
75 demand_ = 0;
76 posx_ = 0;
77 posy_ = 0;
78 coordx_ = 0;
79 coordy_ = 0;
80 coordz_ = 0;
81 n_ = 0;
82 VrpPar_ = new VrpParams;
83
84 AlpsPar()->setEntry(AlpsParams::searchStrategy,
85 AlpsSearchTypeBestFirst);
86 AlpsPar()->setEntry(AlpsParams::staticBalanceScheme, 1); // Spiral
87 AlpsPar()->setEntry(AlpsParams::nodeLogInterval, 20);
88 BlisPar()->setEntry(BlisParams::branchStrategy,
89 BlisBranchingStrategyStrong);
90
91 BlisPar()->setEntry(BlisParams::branchStrategyRampUp,
92 BlisBranchingStrategyStrong);
93
94 BlisPar()->setEntry(BlisParams::cutCliqueStrategy,BlisCutStrategyNone);
95 BlisPar()->setEntry(BlisParams::cutFlowCoverStrategy,
96 BlisCutStrategyNone);
97 BlisPar()->setEntry(BlisParams::cutGomoryStrategy,BlisCutStrategyNone);
98 BlisPar()->setEntry(BlisParams::cutKnapsackStrategy,BlisCutStrategyNone);
99 BlisPar()->setEntry(BlisParams::cutMirStrategy,BlisCutStrategyNone);
100 BlisPar()->setEntry(BlisParams::cutOddHoleStrategy,BlisCutStrategyNone);
101 BlisPar()->setEntry(BlisParams::cutProbingStrategy,BlisCutStrategyNone);
102 BlisPar()->setEntry(BlisParams::cutTwoMirStrategy,BlisCutStrategyNone);
103 BlisPar()->setEntry(BlisParams::heurRoundStrategy, BlisHeurStrategyNone);
104
105 // Cuts as formulation
106 BlisPar()->setEntry(BlisParams::cutFactor, ALPS_DBL_MAX);
107 BlisPar()->setEntry(BlisParams::cutPass, ALPS_INT_MAX);
108 BlisPar()->setEntry(BlisParams::tailOff, -1000.0);
109 BlisPar()->setEntry(BlisParams::denseConFactor, ALPS_DBL_MAX);
110
111 // Seed
112 CoinSeedRandom(1234567);
113 }
114
116 virtual ~VrpModel() {
117 delete [] demand_; demand_ = 0;
118 delete [] posx_; posx_ = 0;
119 delete [] posy_; posy_ = 0;
120 delete [] coordx_; coordx_ = 0;
121 delete [] coordy_; coordy_ = 0;
122 delete [] coordz_; coordz_ = 0;
123 delete VrpPar_; VrpPar_ = 0;
124 delete n_; n_ = 0;
125 }
126
136 virtual void readInstance(const char* dateFile);
137
139 virtual void readParameters(const int argnum, const char * const *arglist);
140
149 virtual BlisSolution * userFeasibleSolution(const double *solution,
150 bool &userFeasible);
151
152 int index (int v0, int v1) {
153 return(v0 < v1 ? v1*(v1 - 1)/2 + v0 : v0*(v0 - 1)/2 + v1);
154 }
155
156 int computeCost(int v0, int v1);
157
158 int getNumVertices() { return vertnum_; }
159
160 int getNumEdges() { return edgenum_; }
161
162 std::vector<VrpVariable *> getEdgeList() { return edges_; }
163
164 // Transform dense solution to a sparse vector.
165 CoinPackedVector *getSolution(const double *denseSol);
166
167 void createNet(CoinPackedVector *vec);
168
170 virtual void registerKnowledge();
171
173 AlpsReturnStatus encodeVrp(AlpsEncoded *encoded) const;
174
176 AlpsReturnStatus decodeVrp(AlpsEncoded &encoded);
177
179 virtual AlpsEncoded* encode() const;
180
182 virtual void decodeToSelf(AlpsEncoded&);
183
184 };
185
186 //#############################################################################
187
188 #endif
VrpModel::name_
char name_[100]
Definition: VrpModel.h:40
BlisModel
Definition: BlisModel.h:60
VrpParams.h
VrpModel::posy_
int * posy_
Definition: VrpModel.h:49
VrpModel::getSolution
CoinPackedVector * getSolution(const double *denseSol)
AlpsSearchTypeBestFirst
Definition: Alps.h:75
BlisParams::cutProbingStrategy
Definition: BlisParams.h:92
BlisParams::cutOddHoleStrategy
Definition: BlisParams.h:91
BlisModel::BlisPar
BlisParams * BlisPar()
Access parameters.
Definition: BlisModel.h:638
ALPS_INT_MAX
#define ALPS_INT_MAX
Definition: Alps.h:150
BlisParams::setEntry
void setEntry(const boolParams key, const char *val)
char* is true(1) or false(0), not used
Definition: BlisParams.h:207
VrpModel
Model class for VRP.
Definition: VrpModel.h:32
AlpsReturnStatus
AlpsReturnStatus
Definition: Alps.h:118
BlisParams::cutGomoryStrategy
Definition: BlisParams.h:87
VrpModel::registerKnowledge
virtual void registerKnowledge()
Register knowledge.
AlpsParams::staticBalanceScheme
Static load balancing scheme – root initialization (0) – spiral (1)
Definition: AlpsParams.h:128
VrpModel::depot_
int depot_
Definition: VrpModel.h:44
VrpModel::n_
VrpNetwork * n_
Definition: VrpModel.h:56
BlisParams::branchStrategy
-1: disable, 0: default, 1: verbose.
Definition: BlisParams.h:64
BlisParams::tailOff
Tail off.
Definition: BlisParams.h:168
VrpModel::readParameters
virtual void readParameters(const int argnum, const char *const *arglist)
Read in Alps, Blis, Vrp parameters.
ALPS_DBL_MAX
#define ALPS_DBL_MAX
Definition: Alps.h:143
VrpModel::~VrpModel
virtual ~VrpModel()
Destructor.
Definition: VrpModel.h:116
BlisHeurStrategyNone
Definition: Blis.h:79
BlisParams::heurRoundStrategy
Definition: BlisParams.h:114
AlpsModel::AlpsPar
AlpsParams * AlpsPar()
Access Alps Parameters.
Definition: AlpsModel.h:77
VrpModel::vertnum_
int vertnum_
Definition: VrpModel.h:41
VrpVariable.h
AlpsEncoded
This data structure is to contain the packed form of an encodable knowledge.
Definition: AlpsEncoded.h:25
VrpModel::edges_
std::vector< VrpVariable * > edges_
Definition: VrpModel.h:60
VrpModel::getEdgeList
std::vector< VrpVariable * > getEdgeList()
Definition: VrpModel.h:162
VrpModel::coordx_
double * coordx_
Definition: VrpModel.h:50
VrpModel::setModelData
void setModelData()
1) Set colMatrix_, varLB_, varUB_, conLB_, conUB, numCols_, numRows_ 2) Set objCoef_ and objSense_ 3)...
VrpCommonTypes.h
VrpNetwork
Definition: VrpNetwork.h:80
VrpModel::getNumEdges
int getNumEdges()
Definition: VrpModel.h:160
BlisParams::cutMirStrategy
Definition: BlisParams.h:90
BlisParams::branchStrategyRampUp
Definition: BlisParams.h:72
VrpModel::readInstance
virtual void readInstance(const char *dateFile)
For parallel code, only the master calls this function.
VrpModel::VrpPar_
VrpParams * VrpPar_
Definition: VrpModel.h:55
BlisCutStrategyNone
Definition: Blis.h:71
AlpsParams::searchStrategy
Search strategy – best-first (0) – best-first-estimate (1) – breadth-first (2) – depth-first (3) – hy...
Definition: AlpsParams.h:137
BlisParams::cutKnapsackStrategy
Definition: BlisParams.h:89
BlisParams::cutCliqueStrategy
The pass to generate cuts for quick branching.
Definition: BlisParams.h:86
BlisParams::cutTwoMirStrategy
Definition: BlisParams.h:93
BlisSolution
This class contains the solutions generated by the LP solver (either primal or dual.
Definition: BlisSolution.h:36
BlisParams::cutFlowCoverStrategy
Definition: BlisParams.h:88
VrpModel::etol_
double etol_
Definition: VrpModel.h:53
VrpModel::getNumVertices
int getNumVertices()
Definition: VrpModel.h:158
VrpModel::wtype_
int wtype_
Definition: VrpModel.h:46
VrpModel::posx_
int * posx_
Definition: VrpModel.h:48
AlpsParams::setEntry
void setEntry(const boolParams key, const char *val)
char* is true(1) or false(0), not used
Definition: AlpsParams.h:309
VrpModel::coordz_
double * coordz_
Definition: VrpModel.h:52
VrpModel::demand_
int * demand_
Definition: VrpModel.h:47
CoinSeedRandom
void CoinSeedRandom(int iseed)
Set the seed for the random number generator.
Definition: CoinHelperFunctions.hpp:786
VrpSolution
This class contains a vrp solution.
Definition: VrpSolution.h:26
VrpCutGenerator.h
VrpModel::numroutes_
int numroutes_
Definition: VrpModel.h:43
VrpModel::edgenum_
int edgenum_
Definition: VrpModel.h:42
BlisBranchingStrategyStrong
Definition: Blis.h:106
BlisParams::cutPass
Definition: BlisParams.h:83
VrpModel::encodeVrp
AlpsReturnStatus encodeVrp(AlpsEncoded *encoded) const
Pack Vrp portion of the model into an encoded object.
VrpModel::coordy_
double * coordy_
Definition: VrpModel.h:51
CoinPackedVector
Sparse Vector.
Definition: CoinPackedVector.hpp:123
VrpModel::VrpModel
VrpModel()
Default construtor.
Definition: VrpModel.h:73
VrpModel::userFeasibleSolution
virtual BlisSolution * userFeasibleSolution(const double *solution, bool &userFeasible)
User&#39;s criteria for a feasible solution.
VrpModel::decodeVrp
AlpsReturnStatus decodeVrp(AlpsEncoded &encoded)
Unpack Vrp portion of the model from an encoded object.
BlisParams::cutFactor
Limit the max number cuts applied at a node.
Definition: BlisParams.h:118
VrpCutGenerator
Definition: VrpCutGenerator.h:34
VrpModel::decodeToSelf
virtual void decodeToSelf(AlpsEncoded &)
The method that decodes the model from an encoded object.
VrpModel::index
int index(int v0, int v1)
Definition: VrpModel.h:152
AlpsParams::nodeLogInterval
Node log interval.
Definition: AlpsParams.h:116
VrpModel::computeCost
int computeCost(int v0, int v1)
VrpModel::encode
virtual AlpsEncoded * encode() const
The method that encodes the model into an encoded object.
BlisParams::denseConFactor
Dense constraint factor.
Definition: BlisParams.h:121
VrpParams
Definition: VrpParams.h:24
VrpModel::createNet
void createNet(CoinPackedVector *vec)
VrpModel::capacity_
int capacity_
Definition: VrpModel.h:45
VrpConstants.h