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

Ensure you import the DD class, the problem class, and the instance reader (KnapsackStructure in Python, KnapsackInstance in C++), which parses a problem file from the DataInstances folder.

PythonC++

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

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

Set the path to a problem file and define a couple of code parameters (e.g., _verbose and _width) that we will use to create our DDs.

PythonC++

# Code Parameters
_verbose = True
_width = 2

# Input data
file_path = "DataInstances/Knapsack/Custom/knapsack_instance_v4_d4_seed1.txt"

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

// Input data
string file_path = "DataInstances/Knapsack/Custom/knapsack_instance_v4_d4_seed1.txt";

1.3. Create Problem Instance

Read the instance file and create an object of your problem class. The instance reader fills in the initial state, variables, weights and capacity, which the KnapsackProblem constructor consumes.

PythonC++

# Knapsack problem
knapsack_parameters = KnapsackStructure(file_path)
knapsack_instance = KnapsackProblem(knapsack_parameters)

// Knapsack problem
KnapsackInstance knapsack_parameters(file_path);
KnapsackProblem  knapsack_instance(knapsack_parameters);

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<int> 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. For the relaxed DD, DD-Suite provides two merging strategies: create_relax_priority_decision_diagram() (merges the lowest-priority nodes one by one) and create_relax_grouping_decision_diagram() (merges nodes in groups by priority difference). For the restricted DD, we use create_restricted_decision_diagram(). In all 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_relax_priority_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<int> dd_relaxed(knapsack_instance);
dd_relaxed.create_relax_priority_decision_diagram(_width, _verbose);
dd_relaxed.reduce_decision_diagram(_verbose);

// Create restricted DD and reduce it
DD<int> dd_restricted(knapsack_instance);
dd_restricted.create_restricted_decision_diagram(_width, _verbose);
dd_restricted.reduce_decision_diagram(_verbose);