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

- File List
- File Members

# /home/coin/svn-release/Blis-0.93.10/Blis/examples/VRP/VrpModel.h

Go to the documentation of this file.

    00001 /*===========================================================================*
    00002  * This file is part of a solver for the Vehicle Routing Problem             *
    00003  * developed using the BiCePS Linear Integer Solver (BLIS).                  *
    00004  *                                                                           *
    00005  * This solver is distributed under the Eclipse Public License as part of    *
    00006  * the COIN-OR repository (http://www.coin-or.org).                          *
    00007  *                                                                           *
    00008  * Authors: Yan Xu, Lehigh University                                        *
    00009  *          Ted Ralphs, Lehigh University                                    *
    00010  *                                                                           *
    00011  * Copyright (C) 2007 Yan Xu and Ted Ralphs.                                 *
    00012  * All Rights Reserved.                                                      *
    00013  *===========================================================================*/
    00014
    00015 #ifndef VrpModel_h_
    00016 #define VrpModel_h_
    00017
    00018 //#############################################################################
    00019
    00020 #include <vector>
    00021
    00022 #include "BlisModel.h"
    00023 #include "VrpVariable.h"
    00024 #include "VrpCommonTypes.h"
    00025 #include "VrpConstants.h"
    00026 #include "VrpParams.h"
    00027 #include "VrpCutGenerator.h"
    00028
    00029 //#############################################################################
    00030
    00032 class VrpModel : public BlisModel
    00033 {
    00034
    00035    friend class VrpCutGenerator;
    00036    friend class VrpSolution;
    00037
    00038  private:
    00039
    00040    char name_[100];
    00041    int vertnum_;
    00042    int edgenum_;
    00043    int numroutes_;
    00044    int depot_;
    00045    int capacity_;
    00046    int wtype_;
    00047    int *demand_;    /*vertnum_*/
    00048    int *posx_;      /*vertnum_*/
    00049    int *posy_;      /*vertnum_*/
    00050    double *coordx_; /*vertnum_*/
    00051    double *coordy_; /*vertnum_*/
    00052    double *coordz_; /*vertnum_*/
    00053    double etol_;
    00054
    00055    VrpParams *VrpPar_;
    00056    VrpNetwork *n_;  /* Allocate when readInstance (no data filled in). */
    00057
    00058    // edges_ hold the same elements as variables_ does, do not free memory.
    00059    // For parallel, reinsert elements in variables_ to edges_
    00060    std::vector<VrpVariable *> edges_;
    00061
    00062 protected:
    00063
    00068    void setModelData();
    00069
    00070 public:
    00071
    00073    VrpModel() : vertnum_(0), edgenum_(0), numroutes_(0), depot_(0),
    00074       capacity_(0), wtype_(0), etol_(1e-5){
    00075       demand_ = 0;
    00076       posx_ = 0;
    00077       posy_ = 0;
    00078       coordx_ = 0;
    00079       coordy_ = 0;
    00080       coordz_ = 0;
    00081       n_ = 0;
    00082       VrpPar_ = new VrpParams;
    00083
    00084       AlpsPar()->setEntry(AlpsParams::searchStrategy,
    00085                           AlpsSearchTypeBestFirst);
    00086       AlpsPar()->setEntry(AlpsParams::staticBalanceScheme, 1); // Spiral
    00087       AlpsPar()->setEntry(AlpsParams::nodeLogInterval, 20);
    00088       BlisPar()->setEntry(BlisParams::branchStrategy,
    00089                           BlisBranchingStrategyStrong);
    00090
    00091       BlisPar()->setEntry(BlisParams::branchStrategyRampUp,
    00092                           BlisBranchingStrategyStrong);
    00093
    00094       BlisPar()->setEntry(BlisParams::cutCliqueStrategy,BlisCutStrategyNone);
    00095       BlisPar()->setEntry(BlisParams::cutFlowCoverStrategy,
    00096                           BlisCutStrategyNone);
    00097       BlisPar()->setEntry(BlisParams::cutGomoryStrategy,BlisCutStrategyNone);
    00098       BlisPar()->setEntry(BlisParams::cutKnapsackStrategy,BlisCutStrategyNone);
    00099       BlisPar()->setEntry(BlisParams::cutMirStrategy,BlisCutStrategyNone);
    00100       BlisPar()->setEntry(BlisParams::cutOddHoleStrategy,BlisCutStrategyNone);
    00101       BlisPar()->setEntry(BlisParams::cutProbingStrategy,BlisCutStrategyNone);
    00102       BlisPar()->setEntry(BlisParams::cutTwoMirStrategy,BlisCutStrategyNone);
    00103       BlisPar()->setEntry(BlisParams::heurRoundStrategy, BlisHeurStrategyNone);
    00104
    00105       // Cuts as formulation
    00106       BlisPar()->setEntry(BlisParams::cutFactor, ALPS_DBL_MAX);
    00107       BlisPar()->setEntry(BlisParams::cutPass, ALPS_INT_MAX);
    00108       BlisPar()->setEntry(BlisParams::tailOff, -1000.0);
    00109       BlisPar()->setEntry(BlisParams::denseConFactor, ALPS_DBL_MAX);
    00110
    00111       // Seed
    00112       CoinSeedRandom(1234567);
    00113    }
    00114
    00116    virtual ~VrpModel() {
    00117       delete [] demand_; demand_ = 0;
    00118       delete [] posx_; posx_ = 0;
    00119       delete [] posy_; posy_ = 0;
    00120       delete [] coordx_; coordx_ = 0;
    00121       delete [] coordy_; coordy_ = 0;
    00122       delete [] coordz_; coordz_ = 0;
    00123       delete    VrpPar_; VrpPar_ = 0;
    00124       delete    n_; n_ = 0;
    00125    }
    00126
    00136    virtual void readInstance(const char* dateFile);
    00137
    00139    virtual void readParameters(const int argnum, const char * const *arglist);
    00140
    00149    virtual BlisSolution * userFeasibleSolution(const double *solution,
    00150                                                bool &userFeasible);
    00151
    00152    int index (int v0, int v1) {
    00153       return(v0 < v1 ? v1*(v1 - 1)/2 + v0 : v0*(v0 - 1)/2 + v1);
    00154    }
    00155
    00156    int computeCost(int v0, int v1);
    00157
    00158    int getNumVertices() { return vertnum_; }
    00159
    00160    int getNumEdges() { return edgenum_; }
    00161
    00162    std::vector<VrpVariable *> getEdgeList() { return edges_; }
    00163
    00164    // Transform dense solution to a sparse vector.
    00165    CoinPackedVector *getSolution(const double *denseSol);
    00166
    00167    void createNet(CoinPackedVector *vec);
    00168
    00170    virtual void registerKnowledge();
    00171
    00173    AlpsReturnStatus encodeVrp(AlpsEncoded *encoded) const;
    00174
    00176    AlpsReturnStatus decodeVrp(AlpsEncoded &encoded);
    00177
    00179    virtual AlpsEncoded* encode() const;
    00180
    00182    virtual void decodeToSelf(AlpsEncoded&);
    00183
    00184 };
    00185
    00186 //#############################################################################
    00187
    00188 #endif