Recursive Problem Implementetion

We now present how to implement a recursive model of a discrete optimization problem. As our running example, we will use the knapsack problem provided in the Examples\KnapsackInstance\ folder.

1. Setting Up the Enviroment

PythonC++

Create a Python file for the new class (e.g., KnapsackProblem.py) in your project directory.

Create C++ files for the new class (e.g., KnapsackProblem.cpp and KnapsackProblem.h) in your project directory.

2. Import Dependencies

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

PythonC++

from SourceCode.Problems.AbstractProblemClass import AbstractProblem

#include "MyExceptions.h"
#include "AbstractProblemClass.h"
#include "KnapsackInstance.h"

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cassert>
#include <set>
#include <memory>
#include <limits>

3. Create problem class and implement functions

We first create a class that inherits from AbstractProblem and implement its constructor. The constructor receives an instance object (KnapsackStructure in Python, KnapsackInstance in C++) that holds the parsed problem data, plus a sort flag. All problem classes that inherit from AbstractProblem must forward at least the initial state and the list of variables to the base constructor; all other fields are problem-specific, such as the weights and capacity of the knapsack.

Note that the state of a knapsack node is a single scalar (the current load of the knapsack), so the template type of AbstractProblem is int in C++.

PythonC++

class KnapsackProblem(AbstractProblem):

    def __init__(self, params: 'KnapsackStructure', sort: bool = True):
        super().__init__(params.initial_state, params.variables, sort)

        self.weights: list[int] = params.weights
        self.capacity: int = params.right_side_of_restrictions

        assert len(self.weights) == len(params.variables), \
            "weights and variables must have the same length"

class KnapsackProblem : public AbstractProblem<int> {
    public:

        KnapsackProblem(const KnapsackInstance& params, bool sort = true)
            : AbstractProblem(params.initial_state, params.variables),
              weights(params.weights),
              capacity(params.right_side_of_restrictions)
        {
            assert(params.variables.size() == weights.size()
                   && "weights and variables must have the same length");
        }

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

C++ only — variable ordering requires a call in the derived constructor

The example KnapsackProblem keeps the default identity variable order. If you want a custom ordering, you must place an apply_variable_order(sort_variables(variables)) call inside the derived class constructor (guarded by the sort flag). It cannot go in AbstractProblem's constructor for two reasons specific to C++:

1. No virtual dispatch during base construction. When AbstractProblem's constructor runs, the derived-class vtable is not yet active. Calling sort_variables() there would always invoke the base-class version, ignoring any override you define.
2. Template instantiation. AbstractProblem is a template whose implementation lives in a .tpp file. The compiler instantiates template bodies at compile time; without the call in the derived constructor, the overridden sort_variables is never compiled for that concrete type.

The bool sort parameter is conventionally passed through the derived constructor so callers can opt in or out of reordering at construction time.

Reindex order-dependent parameters after sorting

When sort=True, the variable order inside the DD differs from the original input order. AbstractProblem provides a public field dd_to_original_index that maps each DD layer position i to the corresponding original variable index. Any parameter that depends on variable position — such as objective weights — must be reindexed before use:

PythonC++

sorted_weights = [objective_weights[i] for i in problem.dd_to_original_index]

vector<double> sorted_weights(problem->dd_to_original_index.size());
for (int i = 0; i < (int)problem->dd_to_original_index.size(); ++i)
    sorted_weights[i] = objective_weights[problem->dd_to_original_index[i]];

Your sort_variables() override must update dd_to_original_index to reflect the chosen order. The base class initializes it as the identity [0, 1, ..., n-1]. The built-in create_and_solve_dd helper applies this reindexing automatically for the objective weights — see the Heuristics page for the full explanation.

3.1. Transition function

• 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 (its position in the DD layer), variable_value is the value assigned to that variable, and scratch_state is a pre-allocated buffer that the function fills with the resulting state.
• Return Value: Returns a boolean indicating whether the transition is feasible. The new state is written into scratch_state instead of being returned, which avoids allocating a new object on every transition.
• Code example for knapsack: The state is a single scalar holding the current load of the knapsack. The transition adds the item weight when the variable is set to 1 and checks that the load does not exceed the capacity.

PythonC++

def transition_function(self, 
    previous_state: 'State', 
    variable_index: int, 
    variable_value: int, 
    scratch_state: list) -> bool:

    if variable_value == 0:
        scratch_state[0] = previous_state
        return True

    new_val = previous_state + self.weights[variable_index] * variable_value
    scratch_state[0] = new_val
    return new_val <= 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;
    if (variable_value != 0) {
        *scratch_state += weights[variable_index] * variable_value;
        return *scratch_state <= capacity;
    }
    return true;
}

3.2. Priority for discard node function

• Function Purpose: Determines the priority of discarding a node based on its state. This function is needed to create a Restricted DD.
• Return Value: Returns an integer priority; lower-priority nodes are discarded first.
• Code example for knapsack: In this case, we prioritize states with higher knapsack load; we prefer to discard nodes with lower knapsack load. Since the state is the load itself, we simply return its negation.

PythonC++

def get_priority_for_discard_node(self, state: 'State') -> int:
    return -state

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

3.3. Create priority for merge node function

• Function Purpose: Calculates the priority for merging nodes based on an ID and state. This function is needed to create a Relaxed DD.
• Variables: node_id is the node's identifier, and state is its current state.
• Return Value: Returns an integer priority; lower-priority nodes are merged first.
• Code example for knapsack: We prefer to merge nodes with lower knapsack load, so we return the negation of the load (the state).

PythonC++

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

int KnapsackProblem::get_priority_for_merge_nodes(
    const int node_id, 
    const int* state) const {

    return -(*state);
}

3.4. Create merge operator function

• Function Purpose: Defines how to merge two states (state_one and state_two). This function is needed to create a Relaxed DD.
• Return Value: Returns the merged state.
• Code example for knapsack: The merged node keeps the minimum load of the two merged nodes, which yields a valid relaxation (upper bound) for the knapsack.

PythonC++

def merge_operator(self, state_one: 'State', state_two: 'State') -> 'State':
    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

• 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 a copy of a state
• Return Value : Returns a copy of a state
• Code example for knapsack:

PythonC++

def get_state_copy(self, state: 'State') -> 'State':
    return state

Python — scalar states are immutable

Because the knapsack state is an immutable int, returning it directly is safe. For mutable states (e.g., a list), return an actual copy such as state.copy().

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