branch_tour.hpp

Go to the documentation of this file.

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

#ifndef CMR_BRANCH_TOUR_H
#define CMR_BRANCH_TOUR_H

#include "branch_node.hpp"
#include "datagroups.hpp"
#include "graph.hpp"
#include "core_lp.hpp"
#include "edgehash.hpp"

#include <utility>
#include <vector>


namespace CMR {
namespace ABC {

class BranchTourFind {
public:
    BranchTourFind(const Data::Instance &inst, const Data::BestGroup &bestdata,
                   const Graph::CoreGraph &coregraph, LP::CoreLP &corelp);

    void instate_branch_tour(const BranchNode &B, bool &found_tour,
                             std::vector<int> &tour);

    void estimate_tour(const std::vector<EndsDir> &constraints,
                       bool &feas, double &tour_val);

    void prune_edges(); 

    bool tour_compliant(const std::vector<int> &tour,
                        const std::vector<EndsDir> &constraints);

    bool obvious_infeas(const std::vector<EndsDir> &constraints);

    void compute_tour(const std::vector<EndsDir> &edge_stats,
                      bool &found_tour, bool &feas,
                      std::vector<int> &tour, double &tour_val,
                      bool for_use);

    std::vector<EndsDir> common_constraints(const BranchNode &parent,
                                            const EndPts &branch_edge);

    std::vector<EndsDir> branch_constraints(const BranchNode &N);

    int verbose = 0;

private:
    Graph::AdjList get_fixed_adj(const std::vector<EndsDir> &constraints);


    const Data::Instance &tsp_inst;
    const Data::BestGroup &best_data;
    const Graph::CoreGraph &core_graph;
    LP::CoreLP &core_lp;

    std::vector<int> fix_degrees; 

    enum EdgeStats : int {
        Core = 0, 
        Supply = 1, 
        Added = 2, 
    };

    util::EdgeHash tour_edge_tracker; 
    std::vector<Graph::Edge> extra_edges; 

    int default_length;

    int large_length;
};

}
}

#endif