hypergraph.hpp

Go to the documentation of this file.

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

#ifndef CMR_HYPERGRAPH_H
#define CMR_HYPERGRAPH_H

#include "cut_structs.hpp"
#include "lp_interface.hpp"
#include "cliq.hpp"
#include "lp_util.hpp"
#include "price_util.hpp"
#include "err_util.hpp"

#include <algorithm>
#include <iostream>
#include <map>
#include <stdexcept>
#include <utility>
#include <vector>

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

namespace CMR {
namespace Sep {

class HyperGraph {
public:
    HyperGraph()
        : sense('\0'), source_bank(nullptr), source_toothbank(nullptr) {}

    HyperGraph(CliqueBank &bank,
               const CCtsp_lpcut_in &cc_lpcut,
               const std::vector<int> &tour);

    HyperGraph(CliqueBank &bank, ToothBank &tbank,
               const dominoparity &dp_cut, double _rhs,
               const std::vector<int> &tour);

    HyperGraph(CliqueBank &bank,
               const std::vector<int> &blossom_handle,
               const std::vector<std::vector<int>> &tooth_edges);

    HyperGraph(HyperGraph &&H) noexcept;
    HyperGraph &operator=(HyperGraph &&H) noexcept;

    void transfer_source(CliqueBank &new_source_bank);

    CCtsp_lpcut_in to_lpcut_in(const std::vector<int> &active_perm,
                               bool with_skeleton) const;

    ~HyperGraph(); 

    enum Type {
        Domino = 0, 
        Subtour = 1, 
        Comb = 2, 
        Non = 3, 
        Branch = 3, 
    };

    Type cut_type() const;

    int tour_age() const { return t_age; }
    int piv_age() const { return p_age; }

    bool fresh_cut() const { return t_age <= 0 || p_age <= 0; }

    double get_coeff(int end0, int end1) const;

    template <typename EndPt_type>
    void get_coeffs(const std::vector<EndPt_type> &edges,
                    std::vector<int> &rmatind,
                    std::vector<double> &rmatval) const;

    char get_sense() const { return sense; }
    double get_rhs() const { return rhs; }

    const std::vector<Clique::Ptr> &get_cliques() const { return cliques; }
    const std::vector<Tooth::Ptr> &get_teeth() const { return teeth; }

    friend class ExternalCuts;

private:
    char sense; 
    double rhs; 

    std::vector<Clique::Ptr> cliques; 
    std::vector<Tooth::Ptr> teeth; 

    CliqueBank *source_bank; 
    ToothBank *source_toothbank; 

    int t_age;
    int p_age;
};

inline std::ostream &operator<<(std::ostream &os, HyperGraph::Type t)
{
    using T = HyperGraph::Type;
    if (t == T::Domino)
        os << "Domino";
    else if (t == T::Subtour)
        os << "Subtour";
    else if (t == T::Comb)
        os << "Blossom/Comb/Wild Thing";
    else if (t == T::Non)
        os << "Non HyperGraph Gomory cut or branch constraint.";
    return os;
}

class ExternalCuts {
public:
    ExternalCuts(const std::vector<int> &tour, const std::vector<int> &perm);

    ~ExternalCuts();

    void add_cut(const CCtsp_lpcut_in &cc_lpcut,
                 const std::vector<int> &current_tour);

    void add_cut(const dominoparity &dp_cut, const double rhs,
                 const std::vector<int> &current_tour);

    void add_cut(const std::vector<int> &blossom_handle,
                 const std::vector<std::vector<int>> &tooth_edges);

    void add_cut(HyperGraph &H);

    void add_cut();

    void reset_ages(); 
    void tour_age_cuts(std::vector<double> duals); 
    void piv_age_cuts(std::vector<double> duals); 

    void del_cuts(std::vector<int> &delset);

    const HyperGraph &get_cut(int lp_rownum) const {
        return cuts[lp_rownum - node_count];
    }

    const std::vector<HyperGraph> &get_cuts() const { return cuts; }

    int cut_count() const { return cuts.size(); }

    int pool_count() const { return cc_pool ? cc_pool->cutcount : 0; }

    const CliqueBank &get_cbank() const { return clique_bank; }
    const ToothBank &get_tbank() const { return tooth_bank; };

    void get_col(int end0, int end1, std::vector<int> &cmatind,
                 std::vector<double> &cmatval) const;

    friend class Separator;

private:
    void pool_add(HyperGraph H);

    const int node_count;

    CliqueBank clique_bank; 
    ToothBank tooth_bank; 

    CliqueBank pool_cliques; 

    std::vector<HyperGraph> cuts; 

    std::vector<HyperGraph> cut_pool; 

    CCtsp_lpcuts *cc_pool; 

    CCtsp_cuttree tightcuts; 

};


template <typename EndPt_type>
void HyperGraph::get_coeffs(const std::vector<EndPt_type> &edges,
                            std::vector<int> &rmatind,
                            std::vector<double> &rmatval) const
{
    using std::vector;

    if (cut_type() == Type::Non)
        throw std::logic_error("Tried HyperGraph::get_coeffs on Non cut.");

    rmatind.clear();
    rmatval.clear();

    const vector<int> &def_tour = source_bank->ref_tour();
    int ncount = def_tour.size();

    std::map<int, int> coeff_map;
    vector<bool> node_marks(ncount, false);

    if (cut_type() != Type::Domino) {
        for (const Clique::Ptr &clq_ref : cliques) {
            for (const Segment &seg : clq_ref->seg_list())
                for (int k = seg.start; k <= seg.end; ++k)
                    node_marks[def_tour[k]] = true;

            for (int i = 0; i < edges.size(); ++i) {
                if (node_marks[edges[i].end[0]] !=
                    node_marks[edges[i].end[1]]) {
                    if (coeff_map.count(i))
                        coeff_map[i] += 1;
                    else
                        coeff_map[i] = 1;
                }
            }

            node_marks = vector<bool>(ncount, false);
        }

        rmatind.reserve(coeff_map.size());
        rmatval.reserve(coeff_map.size());

        for (std::pair<const int, int> &kv : coeff_map) {
            rmatind.push_back(kv.first);
            rmatval.push_back(kv.second);
        }

        return;
    } //else it is a domino cut

    const Clique::Ptr &handle_ref = cliques[0];
    for (const Segment &seg : handle_ref->seg_list())
        for (int k = seg.start; k <= seg.end; ++k)
            node_marks[def_tour[k]] = true;

    for (int i = 0; i < edges.size(); ++i) {
        bool e0 = node_marks[edges[i].end[0]];
        bool e1 = node_marks[edges[i].end[1]];

        if (e0 && e1) {
            if (coeff_map.count(i))
                coeff_map[i] += 2;
            else
                coeff_map[i] = 2;
        } else if (e0 != e1) {
            if (coeff_map.count(i))
                coeff_map[i] += 1;
            else
                coeff_map[i] = 1;
        }
    }

    node_marks = vector<bool>(ncount, false);

    const vector<int> &tooth_perm = source_toothbank->ref_perm();

    for (const Tooth::Ptr &t_ref : teeth) {
        const Clique &root_clq = t_ref->set_pair()[0];
        const Clique &bod_clq = t_ref->set_pair()[1];

        for (const Segment &seg : bod_clq.seg_list())
            for (int k = seg.start; k <= seg.end; ++k)
                node_marks[def_tour[k]] = true;

        for (int i = 0; i < edges.size(); ++i) {
            int e0 = edges[i].end[0];
            int e1 = edges[i].end[1];

            bool bod_e0 = node_marks[e0];
            bool bod_e1 = node_marks[e1];

            if (bod_e0 && bod_e1) {
                if (coeff_map.count(i))
                    coeff_map[i] += 2;
                else
                    coeff_map[i] = 2;
            } else if (bod_e0 != bod_e1) {
                if (bod_e0) {
                    if (root_clq.contains(tooth_perm[e1])) {
                        if (coeff_map.count(i))
                            coeff_map[i] += 1;
                        else coeff_map[i] = 1;
                    }
                } else { //bod_e1
                    if (root_clq.contains(tooth_perm[e0])) {
                        if (coeff_map.count(i))
                            coeff_map[i] += 1;
                        else coeff_map[i] = 1;
                    }
                }
            }
        }

        std::fill(node_marks.begin(), node_marks.end(), false);
    }

    int coeff_size = 0;

    for (std::pair<const int, int> &kv : coeff_map)
        if (kv.second % 2 == 0)
            ++coeff_size;

    rmatind.reserve(coeff_size);
    rmatval.reserve(coeff_size);

    for (std::pair<const int, int> &kv : coeff_map) {
        int ind = kv.first;
        double coeff = kv.second;
        coeff /= 2;
        coeff = floor(coeff);
        if (fabs(coeff) >= Epsilon::Zero) {
            rmatind.push_back(ind);
            rmatval.push_back(coeff);
        }
    }
}

}
}

#endif