Skip to content

Overview

Foundation on DDs and DP

The first step to getting started is to understand that this library provides the tools to work with decision diagrams (DDs) in the context of discrete optimization. It's important to grasp what DDs are and their relationship with dynamic programming (DP).

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 can efficiently capture intricate combinatorial structures. On the other hand, DP is a mathematical optimization technique used for solving complex problems that are represented in a recursive model.

DDs and DP are closely related due to their application in solving combinatorial optimization problems and using recursive models to represent the problem. DDs provide a visual and structural representation of decisions and constraints in combinatorial problems, while DP offers an algorithmic framework for finding optimal solutions.

Before proceeding further, it's important to understand the mathematical components involved in a problem that can be modeled using DDs. To do so, we strongly recommend reading the paper related to this software, which can be found in References. We also provide a short list of useful DD references, which is recommended for people new to the subject.

Creating a New Problem in DD-Suite

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

Transition function:

  • Purpose: Transitions between states based on the problem caracteristics
  • Description: This function defines how the state transitions from one satge to another based on a variable value and the previous state.
  • Inputs:
    • previus_state ('State'): The previous state of the problem
    • variable_id (str): The identifier of the variable (e.g., "x_2")
    • variable_value (int): The domain that was assigned to this variable
  • Output: It returns a tuple containing a new state and a boolean value indicating whether the new state is feasible or not.

State as string function:

  • Purpose: Get the state as string for pritns or other uses.
  • Description: This function converts a state to its string representation.
  • Inputs:
    • state ('State'): The state of a node
  • Output: It returns a new state resulting from the merge of the two input states.

State copy function:

  • Purpose: Get an object copy of the state, so it can be used without fear of changing the original state.
  • Description: This function provides a copy of a given state.
  • Inputs:
    • state ('State'): The state to copy.
  • Output: It returns a new, independent copy of the state, ensuring it is not linked to the original state by references.

Final state function:

  • Purpose: Returns a final state to work with, but if it's not implemented, the initial state will be used as the default.
  • Description: This function retrieves the final state of the DD graph.
  • Output: It returns a new 'State' corresponding to the final node of the DD graph.

Discard node priority function:

  • Purpose: Provides the priority of a node for potential discard. Function needed to create Reduce DDs.
  • Description: This function computes a priority metric for a node that determines its suitability for discard during creating a reduce DD.
  • Inputs:
    • state ('State'): The state of the node.
  • Output: It returns an integer representing the priority for discarding the node.

Merge node priority function:

  • Purpose: Provides the priority of a node for potential merge. Function needed to create Relaxed DDs.
  • Description: This function computes a priority metric for a node that determines its suitability for merge when creating a relaxed DD.
  • Inputs:
    • id (int): The ID of the node
    • state ('State'): The state of the node.
  • Output: It returns an integer representing the priority for merging the node with others.

Merge operator function:

  • Purpose: Combines two states into a single representative state. Function needed to create Relaxed DDs.
  • Description: This function defines how to merge two states into one, typically used during node merging when creating a relaxed DD.
  • Inputs:
    • state_one ('State'): The first state
    • state_two ('State'): The second state
  • Output: It returns a new state resulting from the merge of the two input states.

By implementing these functions within a class derived from AbstractProblem, you establish the necessary framework to model and manipulate states within the DD effectively. These functions enable state comparison, transition, merging, and prioritization, which is crucial for constructing and optimizing DDs in various applications. Tutorial and Examples provide coding examples of the functions described here.