VRP_GSECCut.h

Go to the documentation of this file.
00001 // $Id: VRP_GSECCut.hpp,v 1.2 2004/06/16 22:26:37 magh Exp $
00002 
00003 /*-------------------------------------------------------------------------
00004   Author: Matthew Galati (magh@lehigh.edu)
00005 
00006   (c) Copyright 2004 Lehigh University. All Rights Reserved.
00007 
00008   This software is licensed under the Common Public License. Please see 
00009   accompanying file for terms.
00010   ---------------------------------------------------------------------------*/
00011 
00012 #ifndef VRP_SUBTOUR_CUT
00013 #define VRP_SUBTOUR_CUT
00014 /*----------------------------------------------------------------------
00015   Type 1: VRP_GSEC_cut
00016  
00017   Generalized Subtour Elimination Constraints:
00018 
00019   (i) ACROSS:
00020   sum{e in delta(S)} x_e >=   2 * ceil( sum{i in S} d_i / C )
00021 
00022   (ii) SIDE:
00023   sum{e in E(S)    } x_e <= |S| - ceil( sum{i in S} d_i / C )
00024 
00025   (iii) SIDE_COMPL:
00026   sum{e in E(Shat)} + 0.5 x({0} : Shat) - 0.5 x({0} : S) <= |Shat| - k(S)
00027 
00028   if(|S| <= n/2) use (ii), else use (iii) for sparsest form
00029 
00030   Shat = V \ S (note, V does not include depot here)
00031   i.e., customers that are not in the set S
00032   ---------------------------------------------------------------------- */
00033 
00034 #include "Decomp.h"
00035 #include "DecompCut.h"
00036 
00037 #include <vector>
00038 using namespace std;
00039 
00040 //TODO: switch to just use bool vector?
00041 #include <boost/dynamic_bitset.hpp>
00042 using namespace boost;
00043 
00044 /*---------------------------------------------------------------------- */
00045 class VRP_GSECCut : public DecompCut {
00046 public:
00047    enum storageType {VECTOR, BITSET, BOTH, NONE};
00048    enum cutType     {ACROSS, SIDE, SIDE_COMPL};
00049 
00050 private:
00052    const string m_classTag;
00053 
00054 
00055    vector<int>        m_S;
00056    dynamic_bitset<>   m_inS;
00057    cutType            m_type;
00058    storageType        m_storage;
00059    int                m_nverts;
00060    int                m_demandS;
00061    int                m_capacity;
00062 
00063 public:
00064    //these (pure virutal) methods are inherited from DecompCut
00065    virtual void expandCutToRow(CoinPackedVector * row);
00066    virtual void setBounds();  
00067   
00068    //these (virutal) methods are inherited from DecompCut
00069    virtual void print(ostream * os = &cout) const;
00070    virtual bool isSame(const DecompCut * cut) const;
00071   
00072 public:
00073    void setStorage();
00074    void create_bitset();
00075    void create_vector();
00076    void setCutType();
00077    void setDemand(const int * vertex_wt);
00078    const int getSize();
00079     
00080 public:
00081    VRP_GSECCut(const dynamic_bitset<> & inS, 
00082            const int              * vertex_wt,
00083            const int                capacity,
00084            const int                demandS = 0) :
00085       m_classTag("VRP-GSEC"),
00086       m_inS     (inS),
00087       m_storage (BITSET),
00088       m_nverts  (m_inS.size()),
00089       m_demandS (demandS),
00090       m_capacity(capacity)
00091    {
00092       setStorage();
00093       setCutType();
00094       setDemand(vertex_wt);
00095       setBounds();
00096    }
00097 
00098    virtual ~VRP_GSECCut() {}
00099 };
00100 
00101 #endif

Generated on 12 Feb 2015 for Dip-All by  doxygen 1.6.1