Skip to content

Heuristics

Introduction to Heuristics and Their Implementation in Decision Diagrams

Heuristics play a vital role in optimizing the performance of algorithms used to solve complex combinatorial problems like the knapsack problem. In the context of decision diagrams (DD), heuristics can significantly enhance the efficiency and effectiveness of the solution process. Heuristics in this setting can be broadly categorized into three types: ordering, elimination, and merging heuristics. Each type has its unique purpose and implementation method.

Types of Heuristics

1. Ordering Heuristics:

  • Purpose: To determine the sequence in which variables are considered.
  • Implementation: Override sort_variables() in your Problem class to return variable names in the desired order. The base class will call it during construction when sort=True. The base class also exposes dd_to_original_index, which maps each DD layer position to the corresponding original variable index — update it inside sort_variables() so callers can reindex any order-dependent parameters (see below).
  • Code example: Sort the variables in a knapsack problem based on the value each of them has in the weight matrix.
weights = [10, 9, 3, 8, 7]

variables = [('1', [0, 1]), ('2', [0, 1]), ('3', [0, 1]), ('4', [0, 1]), ('5', [0, 1])]

variables.sort(key=lambda x: weights[int(x[0]) - 1])

#include<iostream>
#include <vector>
#include <algorithm>
#include <tuple>

using namespace std;

vector<int> weights = {10, 9, 3, 8, 7};

vector<pair<string, vector<int>>> variables = {{"1", {0, 1}},
                                                 {"2", {0, 1}},
                                                 {"3", {0, 1}},
                                                 {"4", {0, 1}},
                                                 {"5", {0, 1}}};

auto compareByWeight = [](const pair<string, vector<int>>& a, const pair<string, vector <int>>& b) {
    int index_a = stoi(a.first) - 1; // Convertir string a int y restar 1 para obtener el índice correcto
    int index_b = stoi(b.first) - 1; // Convertir string a int y restar 1 para obtener el índice correcto
    return weights[index_a] < weights[index_b];
};

int main() {
    sort(variables.begin(), variables.end(), compareByWeight);

return 0;
}

2. Elimination Heuristics:

  • Purpose: To prioritize which nodes should be discarded during the decision-making process.
  • Implementation: The Problem class should include the get_priority_for_discard_node function. This function must return a numerical value representing the priority for eliminating a node. Higher priority nodes are more likely to be discarded.
  • Code example:

This heuristic unction calculates the weight-to-value ratio for the given state. Where states with higher weight-to-value ratios are given higher priorities for discarding.

def get_priority_for_discard_node(self, state):
    total_weight = sum(self.weights[i] for i in range(len(state)) if state[i] == 1)
    total_value = sum(self.values[i] for i in range(len(state)) if state[i] == 1)


    if total_value == 0:  # Avoid division by zero
        return float('inf')


    weight_to_value_ratio = total_weight / total_value
    return weight_to_value_ratio

#include<vector>

float get_priority_for_discard_node(std::vector<int>& state) {
    int total_weight = 0;
    int total_value = 0;


    for (size_t i = 0; i < state.size(); ++i) {
        if (state[i] == 1) {
            total_weight += matrix_of_weight[i];
            total_value += matrix_of_value[i];
        }
    }


    if (total_value == 0) {
        return 0.0f; // Avoid division by zero, return 0.0f as float
    }


    float weight_to_value_ratio = static_cast <float>(total_weight) / static_cast <float>(total_value);
    return weight_to_value_ratio;
}

3. Merging Heuristics:

  • Purpose: To decide which nodes should be merged to simplify the decision diagram.
  • Implementation: The Problem class should include the get_priority_for_merge_nodes function. This function must return a numerical value representing the priority for merging two nodes. Nodes with higher merge priorities are combined to reduce the complexity of the diagram.
  • Code example:

It returns the negative total value to prioritize merging nodes with lower values.

def get_priority_for_merge_nodes(self, id, state):
    # Calculate the total value for the given state
    total_value = sum(self.matrix_of_value[i] for i in range(len(state)) if state[i] == 1)


    # Return the negative total value to ensure nodes with lower values are merged first
    return -total_value

#include <vector>
#include <numeric> // para std::accumulate

vector<int> matrix_of_value;

int get_priority_for_merge_nodes(int id, const std::vector<int>& state) {
    // Calculate the total value for the given state
    int total_value = std::accumulate(state.begin(), state.end(), 0,
        [this](int sum, int val) {
            return sum + (val == 1 ? this->matrix_of_value[&val - &state[0]] : 0);
        });
    // Return the negative total value to ensure nodes with lower values are merged first
    return -total_value;
}

Reindexing order-dependent parameters with dd_to_original_index

When sort=True, variables are processed by the DD in a different order than the one in the input file. DD layer i corresponds to the variable at position i in the reordered list, not the variable at position i in the original list.

AbstractProblem exposes a public attribute dd_to_original_index that maps each DD layer position to the original variable index:

dd_to_original_index[i]  →  original index of the variable at DD layer i

Any parameter that depends on variable order must be reindexed before being used with the DD. The canonical example is the objective-weight vector passed to ShortestLongestPath:

# objective_weights is in original variable order
sorted_weights = [objective_weights[i] for i in problem.dd_to_original_index]

// objective_weights is in original variable order
vector<double> sorted_weights(problem->dd_to_original_index.size());
for (int i = 0; i < (int)problem->dd_to_original_index.size(); ++i)
    sorted_weights[i] = objective_weights[problem->dd_to_original_index[i]];

Already handled internally

The built-in create_and_solve_dd helper applies this reindexing automatically for the objective weights it passes to ShortestLongestPath. If you write your own solving loop you are responsible for doing the same.

sort_variables() must populate dd_to_original_index so that it reflects the chosen order. The base class initializes it as the identity [0, 1, ..., n-1], which is correct when no reordering occurs.