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: The variables given to the DD must be arranged in a specific order. This means that the variables vector of the problem should be organized in the desired order to traverse the different levels of the decision diagram.
  • Code example: Sort the variables in a knapsack problem based on the value each of them has in the weight matrix.
matrix_of_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: matrix_of_weights[int(x[0]) - 1])

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

using namespace std;

vector`<int>` matrix_of_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 matrix_of_weights[index_a] < matrix_of_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 should 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.matrix_of_weight[i] for i in range(len(state)) if state[i] == 1)
    total_value = sum(self.matrix_of_value[i] for i in range(len(state)) if state[i] == 1)

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

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 should 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;
}