Create a DD

We now explain how to create a DD using DD-Suite with our running example, the knapsack problem. Make sure your Problem class is created and functional (see Problem Implementation) before proceeding.

1. Setting Up the Environment

PythonC++

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

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

1.1. Import Dependencies

Ensure you import the required modules and classes. In this case, we import the problem class created in the previous step (see Problem Implementation) and the DD class provided in the SourceCode folder.

1.2. Define Input Parameters

PythonC++

from SourceCode.DD import DD
from Examples.KnapsackInstance.KnapsackProblem import KnapsackProblem

#include "SourceCode/DD.h"
#include "Examples/KnapsackInstance/KnapsackProblem.h"

Set up variables and parameters needed for the problem instance, such as initial state, variables, and problem-specific parameters (i.e., item weights and knapsack capacity). You can modify these values based on your specific input data. We also include some additional code parameters (e.g., _verbose and _width), which we will use to create our DDs.

PythonC++

# Code Parameters
_verbose = True
_width = 2

# Input data
initial_state: list[int] = [0, 0]
variables: list[tuple[str, list[int]]] = [('x_1', [0, 1]), ('x_2', [0, 1]), ('x_3', [0, 1]), ('x_4', [0, 1])]
weights: list[int] = [7, 5, 4, 1]
capacity: int = 8

// Code Parameters
bool _verbose = false;
int _width = 2;

// Input data
vector <int>* initial_state =  new vector <int>({0, 0});
vector<pair<string, vector <int>>> variables = {
        {"x_1", {0, 1}},
        {"x_2", {0, 1}},
        {"x_3", {0, 1}},
        {"x_4", {0, 1}}
};

vector<int> weights = {7, 5, 4, 1};
int capacity = 8;

1.3. Create Problem Instance

Create an object of your problem class using the parameters defined in the previous step. Here we show how to create an object for the KnapsackProblem class.

PythonC++

# Knapsack problem
knapsack_instance = KnapsackProblem(initial_state, variables, weights, capacity)

// Knapsack problem
KnapsackProblem knapsack_instance(initial_state, variables, weights, capacity);

2. Construct and reduce a DD

We now proceeded to construct our DD using the DD class. It is important to note that we need one object for each DD we want to create, even if it is over the same problem instance. Also, the DD constructor will use the variable ordering provided in the problem class to assign each variable to a layer.

2.1. Exact DD

To construct a DD, we first create an object of the DD class and pass the problem instance as an argument. Then, we make the actual DD with one of the create functions provided by the class. Specifically, we use the create_decision_diagram() function to construct an exact DD for such problem instances. We can also specify the verbose flag, which will print the step-by-step construction procedure in the console (recommended for debugging purposes on small DDs).

Alternatively, we can reduce the resulting DD with the reduce_decision_diagram() function to obtain a DD graph with fewer nodes and arcs.

PythonC++

# Create exact DD and reduce it
dd_exact = DD(knapsack_instance)
dd_exact.create_decision_diagram(verbose=_verbose)
dd_exact.reduce_decision_diagram(verbose=_verbose)

// Create exact DD and reduce it
DD dd_exact(knapsack_instance);
dd_exact.create_decision_diagram(verbose);
dd_exact.reduce_decision_diagram(verbose);

2.2. Relaxed and Restricted DDs

Similarly, we can construct relaxed and restricted DDs for the same problem instance by creating a new DD object for each. We use the create_relaxed_decision_diagram() function for the relaxed DD and the create_restricted_decision_diagram() for the restricted DD. In both cases, we must specify the maximum width (i.e., maximum number of nodes per layer). As in the exact case, we can use the verbose flag to print the construction steps and the reduce_decision_diagram() function to reduce the resulting DD.

Recall that these construction procedures will use the specific merging/discarding functions that the user specified in the problem class (see Problem Implementation). You can see the DD Builder files (e.g., DDBuilder\RelaxedDDBuilder\RelaxedDDBuilder.py for the relaxed DD builder in Python) to have an in-depth understanding of how these functions are used during the construction procedure. We also refer to our paper (see References) for further explanations on the DD construction procedure implemented in DD-Suite.

PythonC++

# Create relaxed DD and reduce it
dd_relaxed = DD(knapsack_instance)
dd_relaxed.create_relaxed_decision_diagram(max_width=_width, verbose=_verbose)
dd_relaxed.reduce_decision_diagram(verbose=_verbose)

# Create restricted DD and reduce it
dd_restricted = DD(knapsack_instance)
dd_restricted.create_restricted_decision_diagram(max_width=_width, verbose=_verbose)
dd_restricted.reduce_decision_diagram(verbose=_verbose)

// Create relaxed DD and reduce it
DD dd_relaxed(knapsack_instance);
dd_relaxed.create_relaxed_decision_diagram(width, verbose);
dd_relaxed.reduce_decision_diagram(verbose);

// Create restricted DD and reduce it
DD dd_restricted(knapsack_instance);
dd_restricted.create_restricted_decision_diagram(width, verbose);
dd_restricted.reduce_decision_diagram(verbose);