R1Cs: Common Header¶

Overview¶

The file packages/rank1_cuts/common/include/rank1_macro.hpp defines constants, data structures, and a shared data class used for managing Rank-1 cuts (R1Cs) within the RouteOpt software package. This header is a critical component of the pricing process in RouteOpt, providing the foundational definitions for tolerances, maximum limits, and structures required to generate and manage Rank-1 cuts.

License¶

This software is licensed under GPL-3.0.

File Contents¶

The header file includes the following key sections:

• Constants and Macros

• Enumeration: PRICING_HARD_LEVEL

• Structure: R1c

• Class: Rank1CutsDataShared

Constants and Macros¶

• MAX_NUM_R1CS_IN_PRICING

  Maximum number of Rank-1 cuts (R1Cs) considered during the pricing process. 2048

• MAX_POSSIBLE_NUM_R1CS_FOR_VERTEX

  Maximum possible number of R1Cs that can be associated with a single vertex. 128

• RANK1_TOLERANCE

  Tolerance used for numerical comparisons within the package. 1e-6

• RANK1_INVALID

  Indicator for an invalid Rank-1 cut. -1

• INITIAL_IDX_R1C

  The initial index value for a Rank-1 cut. -1

• MAX_RANK_ROW

  Maximum \(|C|\) (cut dimension). 9

• r1cIndex

  A bitset type used to index or track Rank-1 cuts during the pricing process. Defined as: std::bitset<MAX_NUM_R1CS_IN_PRICING>

Enumeration: PRICING_HARD_LEVEL¶

The enumeration PRICING_HARD_LEVEL categorizes the complexity of the pricing subproblem. The levels are:

• EASY: Easy level of difficulty.

• HARD: Hard level of difficulty.

• EXTREMELY_HARD: Extremely hard level of difficulty (currently treated as equivalent to HARD).

Structure: R1c¶

The structure R1c represents a Rank-1 cut and includes the following members:

• info_r1c

  A pair consisting of:

  • A vector of integers representing the set \(C\). Note: The sequence of these integers is significant.

  • An integer representing the plan index. Refer to the Introduction page for details on what a plan means.

• idx_r1c

  An integer storing the row index of the Rank-1 cut (initialized to INITIAL_IDX_R1C). This corresponds to the row index in the LP model.

• rhs

  An integer representing the right-hand side (rhs) value of the cut.

• arc_mem

  A vector storing additional memory for arc-related data. Each element is a pair where:

  • The first element is a vector of integers (e.g., representing the starting customers of an arc).

  • The second element is an integer (representing the ending customer).

  Example:

  arc_mem = { { {1,2}, 3 }, { {1,2}, 4 } } This indicates that there are arcs: 1 → 3, 2 → 3, and 1 → 4, 2 → 4.

Class: Rank1CutsDataShared¶

The class Rank1CutsDataShared is responsible for pre-computing and storing optimal multipliers used in the generation of Rank-1 cuts. Its functionalities include:

• Constructor

  Initializes the shared data with a specified instance dimension and generates the optimal multiplier mapping.

• getPlanInfo()

  Retrieves the multiplier plan information for a given cut dimension and plan index. This includes:

  • The multiplier vector (enumerator)

  • The denominator value

  • The right-hand side (rhs) value

• getMultiplier()

  Returns only the multiplier vector for a specific cut dimension and plan index.

• getDenominator()

  Returns the denominator value for a specific cut dimension and plan index.

• getRhs()

  Returns the right-hand side value for a specific cut dimension and plan index.

• getDim()

  Returns the instance dimension used for generating the multipliers.

Internally, the class maintains a mapping from cut dimensions to a vector of tuples. Each tuple contains:

• A multiplier vector (enumerator)

• An integer denominator

• An integer right-hand side (rhs) value

Code Example¶

Below is an excerpt from rank1_macro.hpp that illustrates the key definitions:

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

 /*
 * @file rank1_macro.hpp
 * @brief Definitions for Rank-1 Cuts and related data structures in RouteOpt.
 *
 * This header defines constants, structures, and a shared data class used for managing
 * Rank-1 cuts (R1Cs) in the pricing process. These definitions include parameters
 * for tolerances, maximum limits, and an enumeration for pricing difficulty levels.
 */

#ifndef ROUTE_OPT_RANK1_MACRO_HPP
#define ROUTE_OPT_RANK1_MACRO_HPP

#include <vector>
#include <unordered_map>
#include <bitset>

namespace RouteOpt::Rank1Cuts {
    // Maximum number of Rank-1 cuts (R1Cs) considered during the pricing process.
    constexpr int MAX_NUM_R1CS_IN_PRICING = 2048;
    // Maximum possible number of R1Cs that can be associated with a single vertex.
    constexpr int MAX_POSSIBLE_NUM_R1CS_FOR_VERTEX = 128;
    // Tolerance used for numerical comparisons of this package.
    constexpr double RANK1_TOLERANCE = 1e-6;
    // Indicator for an invalid Rank-1 cut.
    constexpr int RANK1_INVALID = -1;
    // Initial index value for a Rank-1 cut.
    constexpr int INITIAL_IDX_R1C = -1;
    // Maximum |C|
    constexpr int MAX_RANK_ROW = 9;

    // Bitset type used to index or track R1Cs during the pricing process.
    using r1cIndex = std::bitset<MAX_NUM_R1CS_IN_PRICING>;

    // Enumeration for pricing difficulty levels.
    enum class PRICING_HARD_LEVEL {
        EASY = 0,
        HARD = 1,
        EXTREMELY_HARD = 2
    };

    /**
     * @brief Structure representing a Rank-1 cut (R1c).
     */
    struct R1c {
        std::pair<std::vector<int>, int> info_r1c{};
        int idx_r1c{INITIAL_IDX_R1C};
        int rhs{};
        std::vector<std::pair<std::vector<int>, int>> arc_mem{};
    };

    /**
     * @brief Shared data class for Rank-1 cuts multipliers.
     */
    class Rank1CutsDataShared {
    public:
        explicit Rank1CutsDataShared(int dim): dim(dim) {
            generateOptimalMultiplier();
        }

        void getPlanInfo(std::vector<int> &multiplier, int &denominator, int &rhs,
                         int cut_dim,
                         int plan_idx) const {
            const auto &plan = map_rank1_multiplier.at(cut_dim).at(plan_idx);
            multiplier = std::get<0>(plan);
            denominator = std::get<1>(plan);
            rhs = std::get<2>(plan);
        }

        [[nodiscard]] const std::vector<int> &getMultiplier(int cut_dim, int plan_idx) const {
            return std::get<0>(map_rank1_multiplier.at(cut_dim).at(plan_idx));
        }

        [[nodiscard]] int getDenominator(int cut_dim, int plan_idx) const {
            return std::get<1>(map_rank1_multiplier.at(cut_dim).at(plan_idx));
        }

        [[nodiscard]] int getRhs(int cut_dim, int plan_idx) const {
            return std::get<2>(map_rank1_multiplier.at(cut_dim).at(plan_idx));
        }

        [[nodiscard]] int getDim() const {
            return dim;
        }

    private:
        int dim{};
        std::unordered_map<int, std::vector<std::tuple<std::vector<int>, int, int>>> map_rank1_multiplier{};
        void generateOptimalMultiplier();
    };
}

#endif // ROUTE_OPT_RANK1_MACRO_HPP

Conclusion¶

The rank1_macro.hpp header is essential for the implementation of Rank-1 cuts in RouteOpt. It provides the necessary constants, data structures, and shared data management to support efficient pricing and separation of cuts in complex routing problems.