Tutorial
Tutorial: Using ProblemKnapsack Class and DD Operations
In this tutorial, we will use the knapsack problem as an example, which is a classic combinatorial optimization problem. The goal is to select a set of items from a list, each with a specific weight and value, in such a way that we maximize the total value without exceeding a maximum weight capacity.
Example of the Knapsack Problem
The knapsack problem can be formulated as follows:
Data:
- A list of items, each with a weight and an associated value.
- Maximum weight capacity of the knapsack.
Objective:
- 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.
Implementetion of the problem
1. Setting Up the Enviroment
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
) 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:
3 .Creating the class and implement functions
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. Equals function
Description:
- Function Purpose : Checks if two states (
state_one
andstate_two
) are equal. - Return Value : Returns
True
ifstate_one
is equal tostate_two
, otherwise returnsFalse
. - Code example for knapsack:
3.2. 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, andvariable_value
is the new value assigned to the variable. - Return Value : Returns
new_state
and a booleanis_feasible
indicating if the transition satisfies the problem constraints. - Code example for knapsack:
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.3. Priority for discar 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:
3.4. 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, andstate
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:
3.5. Create merge operator function
Description:
- Function Purpose : Defines how to merge two states (
state_one
andstate_two
). - Return Value : Returns the merged state which maximizes the value between the two states.
- Code example for knapsack:
3.6. 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:
Implementation with Decision Diagrams
Once the Problem
class is created and functional, you can proceed to work with decision diagrams.
1. Setting Up the Environment
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:
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.
//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.
5. Constructing the Decision Diagram
Create an instance of DD
with the KnapsackProblem
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.
7. Exporting Graph Files (Optional)
Export the decision diagram graph to a file for visualization.
8. Setting Objective Function and Solving
Set up and solve the objective function using the decision diagram instance
#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
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
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.