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 Implementetion

1. Setting Up the Enviroment

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

#include "AbstractProblemClass.h"

#include`<iostream>`
#include `<string>`
#include `<vector>`
#include `<algorithm>`
#include `<map>`
#include `<cassert>`
#include `<set>`

3 .Create problem class and implement functions

pythonC++

KnapsackProblem(AbstractProblem):

def init(self, initial_state, variables, matrix_of_weight, right_side_of_restrictions):
    super().init(initial_state, variables)

self.matrix_of_weight = matrix_of_weight
    self.right_side_of_restrictions = right_side_of_restrictions

KnapsackProblem::KnapsackProblem(vector`<int>` &initial_state, const vector<pair<string, vector `<int>`>>& variables,
                             vector<vector `<int>`> matrix_of_wheight, vector `<int>` right_side_of_restrictions)
    : AbstractProblem(initial_state, variables),
      matrix_of_wheight(matrix_of_wheight),
      right_side_of_restrictions(right_side_of_restrictions){}

3.1. Transition function

Description:

• Function Purpose : Computes the transition to a new state based on the previous state, a variable ID, and its assigned value.
• Variables : previous_state represents the current state, variable_id identifies the variable to change, and variable_value is the new value assigned to the variable.
• Return Value : Returns new_state and a boolean is_feasible indicating if the transition satisfies the problem constraints.
• Code example for knapsack:

pythonC++

def transition_function(self, previus_state, variable_id, variable_value):
    new_state = [int(previus_state)+matrix_of_weigth[int(variable_id[2:])-1]*int(variable_value)]
    isFeasible = int(state) <= self.right_side_of_restrictions
    return new_state, isFeasible

pair<vector`<int>`, bool> KnapsackProblem::transition_function(const vector`<int>`& previous_state, const string& variable_id, int variable_value) const {

bool isFeasible = true;
    vector`<int>` state = {};

for (size_t row = 0; row < matrix_of_wheight.size(); ++row) {
        const vector`<int>`& row_of_matrix = matrix_of_wheight[row];
        int new_state = previous_state[row] + row_of_matrix[stoi(variable_id.substr(2)) - 1] * variable_value;
        state.push_back(new_state);
        state.push_back(new_state);

bool isFeasible_this_row = state[row] <= right_side_of_restrictions[row];
        isFeasible = isFeasible && isFeasible_this_row;
    }

return make_pair(state, isFeasible);

}

3.2. Priority for discard node function

Description:

• Function Purpose : Determines the priority of discarding a node based on its state.
• Return Value : Returns the state itself (state) as its priority for discarding nodes.
• Code example for knapsack:

pythonC++

def get_priority_for_discard_node(self, state):
    return state

int KnapsackProblem::get_priority_for_discard_node(const vector`<int>`& state) const {
    int total = 0;
    for (int i : state) {
        total += i;
    }
    return -total;
}

3.3. Create priority for merge node function

Description:

• Function Purpose : Calculates the priority for merging nodes based on an ID and state.
• Variables : id is the identifier of the node, and state is its current state.
• Return Value : Returns -int(id), which assigns a priority where nodes with smaller IDs have higher priority for merging.
• Code example for knapsack:

pythonC++

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

int KnapsackProblem::get_priority_for_merge_nodes(const int id, const vector`<int>`& state) const {
    return -id;
}

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 which maximizes the value between the two states.
• Code example for knapsack:

pythonC++

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

vector`<int>` KnapsackProblem::merge_operator(const vector`<int>`& state_one, const vector`<int>`& state_two) const {
    vector`<int>` state = {};

state.push_back(state_one[0]);
    state.push_back(state_two.back());

sort(state.begin(), state.end());

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 vector`<int>`& state) const {
    string result = "[";
    for (int i = 0; i < state.size(); ++i) {
        result += std::to_string(state[i]);
        if (i != state.size() - 1) {
            result += ", ";
        }
    }
    result += "]";
    return result;
}

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++

import datetime
import time

from Class.DD import DD
from Class.ObjectiveFunction.ObjectiveFunction import ObjectiveFunction, LinearObjectiveDP
from KnapsackProblem import KnapsackProblem

#include`<iostream>`
#include `<vector>`
#include `<string>`
#include `<algorithm>`
#include `<fstream>`
#include `<ctime>`

#include "KnapsackProblem.h"
#include "DD.h"
#include "LinearObjectiveDP.h"
#include "ObjectiveFunction.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

matrix_of_weight = [10, 20, 30, 40]
right_side_of_restrictions = 50
width = right_side_of_restrictions // 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<vector`<int>`> matrix_of_wheight = {{10, 20, 30, 40}};
vector `<int>` right_side_of_restrictions = {50};
int width = right_side_of_restrictions/2
vector `<int>` initial_state = {0, 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`<int>` 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, matrix_of_weight, right_side_of_restrictions)

knapsack_instance = new KnapsackProblem(initial_state, variables, matrix_of_wheight, right_side_of_restrictions);

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++

#Example operations on DD

dd_instance.create_decision_diagram(verbose=False)
dd_instance.create_reduce_decision_diagram(verbose=False)
dd_instance.create_restricted_decision_diagram(width, verbose=False)
dd_instance.create_relaxed_decision_diagram(width, verbose=False)

//Example operations on DD

dd_instance.create_decision_diagram(verbose=False)
dd_instance.create_reduce_decision_diagram(false);
dd_instance.create_restricted_decision_diagram(width, verbose=False)
dd_instance.create_relaxed_decision_diagram(width, verbose=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. Setting Objective Function and Solving

Set up and solve the objective function using the decision diagram instance

pythonC++

#Example setting up objective function
objective_function_instance = ObjectiveFunction(dd_instance)
linear_objective_instance = LinearObjectiveDP(objective_weights, 'max')
objective_function_instance.set_objective(linear_objective_instance)

#Solve the objective function
objective_function_instance.solve_dd()
solution_value = objective_function_instance.get_the_solution().value

//Example setting up objective function
ObjectiveFunction objective_function_instance = ObjectiveFunction<vector`<int>`>(dd_instance);
LinearObjectiveDP linear_objective_instance = LinearObjectiveDP<vector`<int>`>(objective_weights, "max");
objective_function_instance.set_objective_function(linear_objective_instance);

//Solve the objective function
objective_function_instance.solve_dd();
solution_value = objective_function_instance.get_the_solution().value;

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: {solution_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: " << objective_function_instance.get_the_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.