Skip to content

Quickstart

Getting Started

The first step to get started is to understand that this library provides the option to work with decision diagrams, so it's important to grasp what they are and their relationship with dynamic programming.

Decision diagrams (DDs) are graphical structures used to tackle discrete optimization problems by encoding the set of feasible solutions as paths within a graph. This graphical representation of the feasibility set efficiently captures intricate combinatorial structures

Dynamic Programming (DP) is a mathematical optimization technique used for solving complex problems by breaking them down into simpler subproblems and storing their solutions. It typically applies when a problem exhibits overlapping subproblems and optimal substructure, meaning the solution to a problem can be constructed efficiently from solutions to its subproblems.

Decision diagrams and dynamic programming are closely related due to their application in solving combinatorial optimization problems. Decision diagrams provide a visual and structural representation of decisions and constraints in combinatorial problems, while dynamic programming offers an algorithmic framework for finding optimal solutions by combining solutions to simpler subproblems.

Before proceeding further, it's important to understand the mathematical components involved in a problem that can be modeled using decision diagrams. This includes constraints and the requirement of an objective function if optimization is desired

The DD is a layered directed acyclic graph with a root node r and a terminal node t. Each layer is associated to a variable. Arcs are labeled with variable assignments, where x_i = 1 and x_i = 0. Each r − t path in the DD represents a feasible solution of X , and each solution of X is encoded as an r − t path. DDs fulfilling these properties are known as exact DDs for X.

To properly represent this problem and enable the program to create the decision diagram, you need to implement a class derived from AbstractProblem with several key functions. Here's an explanation of each function required:

Equals function :

  • Purpose: Determines if two states are equal.
  • Description: This function checks if two given states are identical. It helps in ensuring that representative nodes are not repeated unnecessarily.

Transition function :

  • Purpose: Transitions between states based on specified parameters.
  • Description: This function defines how the state transitions from one layer to another based on a variable and its value.

Discard node priority function :

  • Purpose: Provides the priority of a node for potential discard.
  • Description: This function computes a priority metric for a node that determines its suitability for discard during node reduction.

Merge operator function :

  • Purpose: Combines two states into a single representative state.
  • Description: This function defines how to merge two states into one, typically used during node merging in the decision diagram.

Other functions :

  • Depending on your specific implementation needs, you may also need functions like get priority for merge nodes and get state as string which are used for node merging priority and state representation as strings, respectively.

By implementing these functions within a class derived from AbstractProblem, you establish the necessary framework to model and manipulate states within the decision diagram effectively. These functions enable state comparison, transition, merging, and prioritization, crucial for constructing and optimizing decision diagrams in various applications.