cc_lpcuts.hpp

Go to the documentation of this file.

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */  /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

#ifndef CMR_CC_LPCUTS_H
#define CMR_CC_LPCUTS_H

#include "graph.hpp"
#include "datagroups.hpp"

#include <stdexcept>
#include <string>
#include <memory>
#include <vector>

extern "C" {
#include <concorde/INCLUDE/tsp.h>
}


namespace CMR {

namespace Sep {

class TourGraph {
public:
    TourGraph() noexcept;

    TourGraph(const std::vector<double> &tour_edges,
              const std::vector<Graph::Edge> &edges,
              const std::vector<int> &perm);

    TourGraph(TourGraph &&T) noexcept;
    TourGraph &operator=(TourGraph &&T) noexcept;

    ~TourGraph();

    TourGraph(const TourGraph &T) = delete;
    TourGraph &operator=(const TourGraph &T) = delete;



    CCtsp_lpgraph* pass_ptr() { return &L; }
    double* tour_array() { return &d_tour[0]; }
    int node_count() const { return L.ncount; }

private:
    std::vector<double> d_tour;
    CCtsp_lpgraph L;
};

class LPcutList {
public:
    LPcutList() noexcept;

    LPcutList(CCtsp_lpcut_in *head, int count) noexcept;

    LPcutList(LPcutList &&L) noexcept;
    LPcutList &operator=(LPcutList &&L) noexcept;

    void push_front(CCtsp_lpcut_in *new_head);

    void splice(LPcutList &&L);

    int size() const { return cutcount; }
    bool empty() const { return cutcount == 0; }

    CCtsp_lpcut_in *begin() { return head_cut.get(); }
    const CCtsp_lpcut_in *begin() const { return head_cut.get(); }

    void filter_primal(TourGraph &TG);

    void clear();

private:
    struct hungry_delete {
        void operator()(CCtsp_lpcut_in *cut) const {
            for(auto it = cut; it; it = cut){
                cut = it->next;
                CCtsp_free_lpcut_in(it);
                CC_IFFREE(it, CCtsp_lpcut_in);
            }
        }
    };
    std::unique_ptr<CCtsp_lpcut_in, hungry_delete> head_cut;
    int cutcount;
};


class CCsepBase {
public:
    CCsepBase(std::vector<int> &supp_elist,
              std::vector<double> &supp_ecap,
              TourGraph &_TG, Sep::LPcutList &_cutq) :
        elist(supp_elist), ecap(supp_ecap), TG(_TG), cutq(_cutq) {}

    virtual bool find_cuts() = 0;

    bool filter_primal = true; 

protected:
    std::vector<int> &elist;
    std::vector<double> &ecap;

    TourGraph &TG;

    Sep::LPcutList &cutq;
};

class LocalCuts : public CCsepBase {
public:
    LocalCuts(std::vector<int> &elist, std::vector<double> &ecap,
              TourGraph &TG, Sep::LPcutList &cutq, int seed) :
        CCsepBase(elist, ecap, TG, cutq), random_seed(seed) {}

    bool find_cuts(); 

    static constexpr int MaxChunkSize = 16;
    int current_max = 8;
    int random_seed;
    bool spheres = false;
};

using CCsepCall = decltype(&CCtsp_segment_cuts);

template <CCsepCall sep_fn, bool check_filter_primal, const char *fn_name>
class ConcordeSeparator : public CCsepBase {
public:
    ConcordeSeparator(std::vector<int> &elist, std::vector<double> &ecap,
                      TourGraph &TG, Sep::LPcutList &cutq) :
        CCsepBase(elist, ecap, TG, cutq) {}

    bool find_cuts()
        {
            int cutcount = 0;
            CCtsp_lpcut_in *head = NULL;
            std::string err_msg(fn_name); err_msg += " failed";


            if (sep_fn(&head, &cutcount, TG.node_count(), ecap.size(),
                       &elist[0], &ecap[0]))
                throw std::runtime_error(err_msg);

            if (cutcount == 0)
                return false;

            cutq = LPcutList(head, cutcount);

            if (check_filter_primal && filter_primal)
                cutq.filter_primal(TG);

            return !cutq.empty();
        }
};

constexpr char seg_fname[] = "CCtsp_segment_cuts";
constexpr char con_fname[] = "CCtsp_connect_cuts";
constexpr char ex_fname[] = "CCtsp_exact_subtours";
constexpr char f2m_fname[] = "CCtsp_fastblossom";
constexpr char gh2m_fname[] = "CCtsp_ghfastblossom";
constexpr char blk_fname[] = "CCtsp_block_combs";


using SegmentCuts = ConcordeSeparator<CCtsp_segment_cuts, false, seg_fname>;

using ConnectCuts = ConcordeSeparator<CCtsp_connect_cuts, false, con_fname>;

using ExactSub = ConcordeSeparator<CCtsp_exact_subtours, false, ex_fname>;

using FastBlossoms = ConcordeSeparator<CCtsp_fastblossom, true, f2m_fname>;

using GHblossoms = ConcordeSeparator<CCtsp_ghfastblossom, true, gh2m_fname>;

inline int BlkCombCall(CCtsp_lpcut_in **c, int *cutcount,
                       int ncount, int ecount, int *elist, double *ecap)
{
    return CCtsp_block_combs(c, cutcount, ncount, ecount, elist, ecap, 1);
}

using BlockCombs = ConcordeSeparator<BlkCombCall, true, blk_fname>;


}
}

#endif