From scratch

Using KnapsackProblem Class and DD Operations

In this tutorial, we will use the knapsack problem as an example to show how to create and export a DD.

Knapsack Problem

The knapsack problem considers:

• A list of items, each with a weight and an associated value.
• Maximum weight capacity of the knapsack.

The goal is to:

• Select a subset of items such that their combined weight does not exceed the knapsack's capacity.
• Maximize the sum of the values of the selected items.

Problem Implementation

1. Setting Up the Environment

pythonC++

Create a Python script (e.g., knapsackProblem.py) in your project directory to run the tutorial steps.

Create a C++ script (e.g., knapsackProblem.cpp and knapsackProblem.h) in your project directory to run the tutorial steps.

2. Import Dependencies

Ensure you import the required modules and classes. Here's an example import section:

pythonC++

from SourceCode.Problems.AbstractProblemClass import AbstractProblem
from SourceCode.DD import DD
from SourceCode.GraphAlgorithms.ShortestLongestPath.ShortestLongestPath import ShortestLongestPath

#include "SourceCode/Problems/AbstractProblemClass.h"
#include "SourceCode/DD.h"
#include "SourceCode/GraphAlgorithms/ShortestLongestPath/ShortestLongestPath.h"

3 .Create problem class and implement functions

pythonC++

class KnapsackProblem(AbstractProblem):

    def __init__(self, initial_state, variables, weights, capacity, sort=True):
        super().__init__(initial_state, variables, sort)
        self.weights = weights
        self.capacity = capacity

class KnapsackProblem : public AbstractProblem<int> {
public:
    KnapsackProblem(int* initial_state, const vector<pair<string, vector<int>>>& variables,
                    vector<int> weights, int capacity)
        : AbstractProblem(initial_state, variables),
          weights(weights),
          capacity(capacity) {}

private:
    vector<int> weights;
    int capacity;
};

3.1. Transition function

Description:

• Function Purpose : Computes the transition to a new state based on the previous state, a variable index, and its assigned value.
• Variables : previous_state is the current state, variable_index identifies the variable to change, variable_value is the value assigned to it, and scratch_state is a pre-allocated buffer where the new state is written.
• Return Value : Returns a boolean is_feasible indicating if the transition satisfies the problem constraints. The new state is written into scratch_state.
• Code example for knapsack:

pythonC++

def transition_function(self, previous_state, variable_index, variable_value, scratch_state):
    new_state = previous_state + self.weights[variable_index] * variable_value
    scratch_state[0] = new_state
    return new_state <= self.capacity

bool KnapsackProblem::transition_function(
    const int* previous_state, const int variable_index, int variable_value, int* scratch_state) const {

    *scratch_state = *previous_state + weights[variable_index] * variable_value;
    return *scratch_state <= capacity;
}

3.2. Priority for discard node function

Description:

• Function Purpose : Determines the priority of discarding a node based on its state. Lower-priority nodes are discarded first.
• Return Value : Returns the negation of the state (the knapsack load), so nodes with lower load are discarded first.
• Code example for knapsack:

pythonC++

def get_priority_for_discard_node(self, state):
    return -state

int KnapsackProblem::get_priority_for_discard_node(const int* state) const {
    return -(*state);
}

3.3. Create priority for merge node function

Description:

• Function Purpose : Calculates the priority for merging nodes based on a node ID and state.
• Variables : id is the identifier of the node, and state is its current state.
• Return Value : Returns the negation of the state (the knapsack load), so nodes with lower load are merged first.
• Code example for knapsack:

pythonC++

def get_priority_for_merge_nodes(self, id, state):
    return -state

int KnapsackProblem::get_priority_for_merge_nodes(const int id, const int* state) const {
    return -(*state);
}

3.4. Create merge operator function

Description:

• Function Purpose : Defines how to merge two states (state_one and state_two).
• Return Value : Returns the merged state. We keep the minimum load, which yields a valid relaxation (upper bound) for the knapsack.
• Code example for knapsack:

pythonC++

def merge_operator(self, state_one, state_two):
    return min(state_one, state_two)

int* KnapsackProblem::merge_operator(const int* state_one, const int* state_two) const {
    int* state = new int();
    *state = min(*state_one, *state_two);
    return state;
}

3.5. Implement get as string function

Description:

• Function Purpose : Converts a state (state) into its string representation.
• Return Value : Returns the string representation of state.
• Code example for knapsack:

pythonC++

def get_state_as_string(self, state):
    return str(state)

string KnapsackProblem::get_state_as_string(const int* state) const {
    return std::to_string(*state);
}

3.6. Implement get state copy function

Description:

• Function Purpose : Creates an independent copy of a state.
• Return Value : Returns a copy of state.
• Code example for knapsack:

pythonC++

def get_state_copy(self, state):
    return state  # the scalar int state is immutable, so it is safe to return as-is

int* KnapsackProblem::get_state_copy(const int* state) const {
    return new int(*state);
}

Create a Decision Diagram

Once the Problem class is created and functional, you can proceed to create a DD and work with it.

1. Setting Up the Environment

pythonC++

Create a Python script (e.g., knapsackMain.py) in your project directory to run the tutorial steps.

Create a C++ script (e.g., knapsackMain.cpp) in your project directory to run the tutorial steps.

2. Import Dependencies

Ensure you import the required modules and classes. Here's an example import section:

pythonC++

from SourceCode.DD import DD
from SourceCode.GraphAlgorithms.ShortestLongestPath.ShortestLongestPath import ShortestLongestPath
from KnapsackProblem import KnapsackProblem

#include "KnapsackProblem.h"
#include "SourceCode/DD.h"
#include "SourceCode/GraphAlgorithms/ShortestLongestPath/ShortestLongestPath.h"

3. Defining Input Parameters

Set up variables and parameters needed for the problem instance. Modify these based on your specific input data or generation methods.

pythonC++

# Replace with actual data loading logic
variable_length = 4

weights = [10, 20, 30, 40]
capacity = 50
width = capacity // 2
initial_state = 0
variables = [("x_" + str(i), [0, 1]) for i in range(1, variable_length + 1)]

objective_weights = [1, 2, 3, 4]

// Replace with actual data loading logic
int variable_length = 4;

vector<int> weights = {10, 20, 30, 40};
int capacity = 50;
int width = capacity / 2;
int* initial_state = new int(0);
vector<pair<string, vector<int>>> variables = {
    make_pair("x_1", vector<int>{0, 1}),
    make_pair("x_2", vector<int>{0, 1}),
    make_pair("x_3", vector<int>{0, 1}),
    make_pair("x_4", vector<int>{0, 1})
};

vector<double> objective_weights = {1, 2, 3, 4};

4. Creating the KnapsackProblem Instance

Instantiate the new instass of the class with the defined parameters.

pythonC++

knapsack_instance = KnapsackProblem(initial_state, variables, weights, capacity)

KnapsackProblem* knapsack_instance = new KnapsackProblem(initial_state, variables, weights, capacity);

5. Constructing the Decision Diagram

Create an instance of DD with the KnapsackProblem instance.

pythonC++

dd_instance = DD(knapsack_instance)

dd_instance = new DD(*knapsack_instance);

6. Constructing the Decision Diagram

Perform various operations on the decision diagram such as creation, reduction, restriction, and relaxation. If it's wanted to verbose, use True instead.

pythonC++

# Exact DD (and reduce it)
dd_instance.create_decision_diagram(verbose=False)
dd_instance.reduce_decision_diagram(verbose=False)

# Or use a restricted/relaxed DD instead
# dd_instance.create_restricted_decision_diagram(max_width=width, verbose=False)
# dd_instance.create_relax_priority_decision_diagram(max_width=width, verbose=False)

// Exact DD (and reduce it)
dd_instance.create_decision_diagram(false);
dd_instance.reduce_decision_diagram(false);

// Or use a restricted/relaxed DD instead:
// dd_instance.create_restricted_decision_diagram(width, false);
// dd_instance.create_relax_priority_decision_diagram(width, false);

7. Exporting Graph Files (Optional)

Export the decision diagram graph to a file for visualization.

pythonC++

dd_instance.export_graph_file("knapsack_file")

dd_instance.export_graph_file("knapsack_file")

8. Solving the Objective Function

Use ShortestLongestPath to compute the optimal solution (longest path = maximization, shortest path = minimization) over the DD.

pythonC++

longest_path = ShortestLongestPath(dd_instance)
longest_path.set_parameters(objective_weights, "max")
answer = longest_path.solve()

print("Optimal value:", answer.value)
print("Path:", answer.path_print)

ShortestLongestPath longest_path(dd_instance);
longest_path.set_parameters(objective_weights, "max");
auto answer = longest_path.solve();

cout << "Optimal value: " << answer.value << "\n";
cout << "Path: " << answer.path_print << "\n";

9. Writing results to file

pythonC++

with open("knapsack_statistics.txt", 'a') as output_file:
    now = datetime.datetime.now()
    timestamp = now.strftime("%d-%m-%Y %H:%M:%S")
    output_file.write(f"[{timestamp}] Solution value: {answer.value}\n")

auto* file = new ofstream(full_file_path, std::ios::app);

auto now = std::chrono::system_clock::now();
std::time_t now_time = std::chrono::system_clock::to_time_t(now);
std::tm* local_time = std::localtime(&now_time);
char buffer[80];
std::strftime(buffer, 80, "%d-%m-%Y %H:%M:%S", local_time);
(*file) << "[" << buffer << "]" << "  ";

(*file) << "Solution value: " << longest_path.get_solution().value << "\n";
file->close();

10 .Running the Script

pythonC++

Run your script (knapsackMain.py) to execute all the steps and solve the knapsack problem based on your setup.

Run your script (knapsackMain.cpp) to execute all the steps and solve the knapsack problem based on your setup.