R1Cs: Separation¶

/*
 * Copyright (c) 2025 Zhengzhong (Ricky) You.
 * All rights reserved.
 * Software: RouteOpt
 * License: GPL-3.0
 */

/*
 * @file rank1_separation_macro.hpp
 * @brief Macro definitions and type aliases for Rank-1 separation in RouteOpt.
 *
 * This header defines various constants, type aliases, and helper macros that are used
 * in the Rank-1 separation process.
 */

#ifndef ROUTE_OPT_RANK1_SEPARATION_MACRO_HPP
#define ROUTE_OPT_RANK1_SEPARATION_MACRO_HPP

#include <bitset>
#include <Eigen/Sparse>
#include <vector>
#include "route_opt_macro.hpp"

namespace RouteOpt::Rank1Cuts::Separation {
    constexpr bool RANK1_SEPARATION_VERBOSE = false;

    constexpr double SOL_X_RANK1_TOLERANCE = 1e-3;

    constexpr double MAX_CUT_MEM_FACTOR = 0.15;

    constexpr int INITIAL_RANK_1_MULTI_LABEL_POOL_SIZE = 2048;

    constexpr int FIND_MEM_USE_ENUMERATION_OR_MIP = 1000;

    constexpr int MAX_NUMBER_SEGMENT_FOR_ONE_COLUMN = 16;

    constexpr int MAX_UNDETERMINED_ARC_NUMBER = 128;

    constexpr int MAX_LABELS = 1024;

    constexpr int MAX_HEURISTIC_SEP_ROW_RANK1 = 16;

    constexpr int MIN_CUTS_ADDED_PER_ROUND = 50;

    constexpr double TIME_LIMIT_FOR_MIP_FIND_MEM = 0.2;

    constexpr double CUT_VIO_FACTOR = 0.1;

    constexpr double RANK1_ROW_DENSITY = 0.1;

    constexpr int SOL_KEEPER_LIMIT = 20;

    enum class MemoryType {
        NO_MEMORY = 0,
        NODE_MEMORY = 1,
        ARC_MEMORY = 2
    };

    struct RouteInfo {
        double frac_x{};
        std::vector<int> col_seq{};
        int forward_concatenate_pos{};
    };

    struct VectorHashInRank1 {
        size_t operator()(const std::vector<int> &v) const {
            std::size_t hash = 0;
            for (const int num: v) {
                hash ^= std::hash<int>{}(num) + 0x9e3779b9 + (hash << 6) + (hash >> 2);
            }
            return hash;
        }
    };

    using arcBit = std::bitset<MAX_UNDETERMINED_ARC_NUMBER>;
    using cutLong = routeOptLong;
    using sparseRowMatrixXI = Eigen::SparseMatrix<int, Eigen::RowMajor>;
    using sparseRowVectorXI = Eigen::SparseVector<int, Eigen::RowMajor>;

#define RANK1_VERBOSE_EXEC(stmt) do { \
    if (RANK1_SEPARATION_VERBOSE) { \
        stmt; \
    } \
} while (0);
} // namespace RouteOpt::Rank1Cuts::Separation

#endif // ROUTE_OPT_RANK1_SEPARATION_MACRO_HPP

/*
 * Copyright (c) 2025 Zhengzhong (Ricky) You.
 * All rights reserved.
 * Software: RouteOpt
 * License: GPL-3.0
 *
 * @file rank1_separation_controller.hpp
 * @brief Rank-1 Separation Controller for handling the generation, updating, and processing of Rank-1 cuts.
 *
 * This header defines the Rank1SeparationController class which coordinates the separation process for Rank-1 cuts.
 * It integrates shared Rank-1 cuts data, cut generation, memory finding, and cut selection modules,
 * and interfaces with the underlying solver and vertex cost matrix.
 */

#ifndef ROUTE_OPT_RANK1_SEPARATION_CONTROLLER_HPP
#define ROUTE_OPT_RANK1_SEPARATION_CONTROLLER_HPP

#include "rank1_data_shared.hpp"
#include "rank1_cuts_generator.hpp"
#include "rank1_memory_finder.hpp"
#include "rank1_cuts_selector.hpp"
#include "solver.hpp"

namespace RouteOpt::Rank1Cuts::Separation {
    class Rank1SeparationController {
    public:
        Rank1SeparationController(const Rank1CutsDataShared &rank1CutsDataShared,
                                  int max_row_rank1,
                                  int max_num_r1c3_per_round,
                                  int max_num_r1c_per_round,
                                  Solver &solver,
                                  const std::vector<std::vector<double>> &cost_mat4_vertex);

        void updateInfo(MemoryType limited_memory_type,
                        PRICING_HARD_LEVEL pricing_hard_level,
                        bool if_collect_sol,
                        const std::vector<RouteInfo> &sol,
                        const std::vector<R1c> &old_cuts);

        void separateRank1Cuts(std::vector<R1c> &cuts,
                               bool if_mem = true,
                               bool if_select_cuts = true);

        void convert2ArcMemory(std::vector<R1c> &existing_cuts);

        [[nodiscard]] auto getIfOnceUseNoSymmetryMem() const {
            return if_once_use_no_symmetry_mem;
        }

        Rank1SeparationController() = delete;
        ~Rank1SeparationController() = default;

    private:
        std::vector<std::vector<RouteInfo>> sol_vec{};
        std::reference_wrapper<const Rank1CutsDataShared> rank1CutsDataShared_ref;
        DataShared sharedData;
        CutGenerator cutGen;
        MemGenerator memGen;
        CutSelector cutSelector;
        bool if_once_use_no_symmetry_mem{false};

        void cleanData() {
            sharedData.cleanData();
            cutGen.cleanData();
            memGen.cleanData();
            cutSelector.cleanData();
        }

        void setRhs(std::vector<R1c> &cuts);
    };
} // namespace RouteOpt::Rank1Cuts::Separation

#endif // ROUTE_OPT_RANK1_SEPARATION_CONTROLLER_HPP

#include <vector>
#include <iostream>
#include "rank1_data_shared.hpp"
#include "rank1_separation_controller.hpp"
#include "solver.hpp"

using namespace RouteOpt::Rank1Cuts;
using namespace RouteOpt::Rank1Cuts::Separation;

int main() {
    // Initialize shared Rank-1 cuts data with an instance dimension (e.g., 4)
    Rank1CutsDataShared sharedData(4);

    // Create an instance of the IP solver
    Solver solver{};

    // Define a sample cost matrix for vertices (e.g., for 4 vertices)
    std::vector<std::vector<double>> costMatrix = {
        {0.0, 10.0, 20.0, 30.0},
        {10.0, 0.0, 15.0, 25.0},
        {20.0, 15.0, 0.0, 35.0},
        {30.0, 25.0, 35.0, 0.0}
    };

    // Instantiate the Rank1SeparationController with parameters:
    // - max_row_rank1: Maximum Rank-1 row dimension (e.g., 4)
    // - max_num_r1c3_per_round: Maximum number of R1C3 cuts per separation round (e.g., 50)
    // - max_num_r1c_per_round: Maximum number of R1C cuts (dimension != 3) per round (e.g., 100)
    // This is one time call
    Rank1SeparationController separationController(
        sharedData,
        4,
        50,
        100,
        solver,
        costMatrix
    );

    // Prepare dummy solution routes (RouteInfo) for the update
    std::vector<RouteInfo> solutionRoutes;
    RouteInfo route;
    route.frac_x = 0.75;
    route.col_seq = {1, 2};
    route.forward_concatenate_pos = 1;
    solutionRoutes.push_back(route);
    // Add other routes as needed...

    // Prepare the cut vector for old cuts (if not have, give empty vector)
    std::vector<R1c> oldCuts;

    // Update the controller with the current solution and existing cuts.
    // You need to call this function each cutting round
    separationController.updateInfo(
        MemoryType::NODE_MEMORY,   // Using node-based memory
        PRICING_HARD_LEVEL::EASY,   // Pricing difficulty level: EASY
        true,                       // Collect current solution
        solutionRoutes,
        oldCuts
    );

    // Container to hold the new generated Rank-1 cuts
    std::vector<R1c> newCuts;

    // Perform the separation process to generate new cuts
    // You need to call this function each cutting round
    separationController.separateRank1Cuts(newCuts, true, true);

    // Optionally, convert node-memory-based cuts to arc-memory-based cuts
    separationController.convert2ArcMemory(newCuts);

    // Output the number of new cuts generated (for demonstration)
    std::cout << "Number of new Rank-1 cuts generated: " << newCuts.size() << std::endl;

    return 0;
}