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 <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 that receives the problem parameters. Note that all problem classes that inherit from AbstractProblem need a constructor that receives at least the initial state and the list of variables of the recursive model. All other parameters are problem-specific, such as the weights and capacity of the knapsack.

PythonC++

KnapsackProblem(AbstractProblem):

    def __init__(self,  
        initial_state: 'State', 
        variables: list[tuple['Variable', 'Domain']], 
        weights: list[int], 
        capacity: int):

        super().init(initial_state, variables)

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

class KnapsackProblem : public AbstractProblem<vector<int>> {
    public:

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

        }
};

3.1. Transition function

• 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, and variable_value is the value assigned to such variable.
• Return Value: Returns new_state and a boolean is_feasible indicating if the transition satisfies the problem constraints.
• Code example for knapsack: The state is a two-dimensional vector that stores the minimum and maximum load of the knapsack. The transition function updates the knapsack load and checks if the minimum load exceeds the capacity.

PythonC++

def transition_function(self, 
    previus_state: 'State', 
    variable_id: str, 
    variable_value: int) -> tuple['State', bool]:

    is_feasible: bool = False
    new_state: 'State' = [0,0]

    for i in range(2):
        new_state[i] = previus_state[i] + self.weights[int(variable_id[2:]) - 1] * variable_value

        if new_state[i] <= self.capacity:
            is_feasible = True

    return new_state, is_feasible

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

    bool isFeasible = false;
    pair<vector<int>*, bool> to_return = make_pair(new vector<int>(2), false);

    for (int i = 0; i < 2; i++) {
        to_return.first->at(i) = previous_state->at(i) + weights[stoi(variable_id.substr(2)) - 1] * variable_value;

        if (to_return.first->at(i) <= capacity ) isFeasible = true; //at least one side is feasible
    }

    to_return.second = isFeasible;

    return to_return;
}

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 the state itself (state) as its priority for discarding nodes.
• Code example for knapsack: In this case, we prioritize states with higher knapsack load; we prefer to discard nodes with lower knapsack load.

PythonC++

def get_priority_for_discard_node(self, state: 'State') -> int:
    total: int = 0
    for i in range(len(state)):
        total += state[i]
    return -total

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

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: id is the node's identifier, 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: This implementation merges nodes in inverse lexicographic order (i.e., node id). It gives the lowest priority to nodes where the minimum and maximum knapsack loads differ (i.e., relaxed states).

PythonC++

def get_priority_for_merge_nodes(self, id: int, state: 'State') -> int:
    if state[0] != state[1]:
        return -float('-inf')
    return -int(id)

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

    if (state->at(0) != state->at(1)) {
        return -numeric_limits<int>::infinity();
    }

    return -node_id;
}

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 new node includes the two previous nodes' minimum and maximum knapsack load.

PythonC++

def merge_operator(self, state_one: 'State', state_two: 'State') -> 'State':

    state: 'State' = [
        min(state_one[0], state_two[0]), 
        max(state_one[1], state_two[1]) 
    ]
    return state

vector<int>* KnapsackProblem::merge_operator(
    const vector<int>* state_one, 
    const vector<int>* state_two) const {

    vector<int>* state = new vector<int>(2);

    state->at(0) = min(state_one->at(0), state_two->at(0));
    state->at(1) = max(state_one->at(1), state_two->at(1));

    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 vector<int>* state) const {

    string result = "[";
    for (int i = 0; i < state->size(); ++i) {

        result += std::to_string(state->at(i));

        if (i != state->size() - 1) {
            result += ", ";
        }
    }

    result += "]";
    return result;
}

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.copy()

vector<int>* KnapsackProblem::get_state_copy(const vector<int>* state) const {
    vector<int>* copy_vector = new vector<int>;
    copy_vector->reserve(state->size());
    copy(state->begin(), state->end(), back_inserter(*copy_vector));
    return copy_vector;
}