# Diderot.jl

Diderot.DiderotModule

Diderot.jl

Decision Diagrams for Discrete Optimization in Julia.

Provides a generic implementation of decisision diagrams (top-down construction of layered state transition graph). Implements a branch-and-bound algorithms with subproblems defined by nodes in an exact cutset of the diagram.

To support new problem classes, the several methods have to be implemented that are dispatched on the user-defined types for the instance, describing the states and transition functions.

The solver behavior (restrictions, relaxations, variable order, diagram width) can also be fully customized through user-defined layer processing.

Motivation

The package is mostly written as a learning experiment. Implementing an idea gives a deeper understanding of the challenges than just reading about it.

The appeal of decision diagrams for discrete optimization is two-fold:

1. The simplicity of the algorithm makes implementation from scratch a reasonable endeavor.
2. It seems that the DD-based branch-and-bound lends itself to parallelization, yielding better speed-ups than MIP solvers.

Limitations

This is (still) mostly a naive text book implementation. I'm sure there's room for improvement in the choice of data structures and avoing frequent allocation.

It's currently assumed that the objective function is to be maximized, and the transition values are combined by addition. That is, we're looking for a longest path in the diagram, using as arc weights the values of the transitions. In principle, one could also choose minimization or use another operator (multiplication, maximum), but this would require even more type parametrization.

The decision diagram does not keep all transition arcs, but computes the longest path on the fly. That is, after a new layer is created, each node only remembers a single ingoing arc. This simplification works OK for the purpose of finding an optimal solution, but it rules out other use cases, such as enumeration of feasible solutions or post-optimality analysis.

Problem Classes

Models and methods for some specific problem classes are also implemented in the context of this package as submodules. The main motivation is test-driving the current API, to make sure it's sufficiently general and not too verbose.

Currently included are:

• Binary Knapsack Problem.
• Set Cover Problem.

References

The implementation is informed by the book Decision Diagrams for Optimization by D Bergman, A Cire, WJ van Hoeve and J Hooker.

The MDD website also contains a lot of valuable resources, in particular the INFORMS article Discrete Optimization with Decision Diagrams.

Contributions

Pull requests with various forms of contributions are very welcome. In particular, I would appreciate suggestions to simplify the current interface, improve overall performance or cover more problem classes.

source

## Types

The type parameters specify the (user-defined) State, variable Domain and objective Value, respectively.

Diderot.ArcType
Arc{S,D,V}

An arc in the decision diagram, representing a state transition.

It points to the original/previous state and also stores the decision made (variable assignment) as well as the contribution to the objective function.

source
Diderot.NodeType
Node{S,D,V}

Meta-data for a node in the decision diagram.

Stores the distance from the root node on the longest path so far, the ingoing arc on such a path (but no other ingoing arcs) and a flag to specify whether the state is exact, as opposed to relaxed.

source
Diderot.LayerType
Layer{S,D,V}

A layer of nodes in the decision diagram.

Represented by mapping from (user-defined) states to the Node meta-data. Also has a flag exact to indicate whether all states are represented exactly (neither restricted nor relaxed).

source
Diderot.DiagramType
Diagram{S,D,V}

A (multi-valued) decision diagram.

It's a directed acyclic graph where the nodes represent (feasible) states and the arcs transitions triggered by decision variable assignments. Decisions are made sequentially and arcs only connect consecutive layers. The initial layer contains the single, given root node. All nodes in the final layer are merged to a single terminal node.

As the variable order can be defined dynamically, the variable indices are also stored. Note that the constructed diagram will have N+1 layers for N variables.

There is also a property partial_sol containing indices of variables that are already assigned outside this diagram (in the context of branch-and-bound).

source
Diderot.SubproblemType
Subproblem{D,V}

A subproblem in the context of branch-and-bound, as defined by an exact node in the diagram. It's represented by the partial solution given by a longest path from the root that node and the current state.

source

## Modeling Interface

Diderot.next_variableFunction
next_variable(instance, diagram::Diagram{S,D,V}, variable_order)::Int

The variable to build the next layer, as an integer index.

Optional: Defaults to order 1:length(instance).

Multiple strategies can be implemented for an instance type by defining and passing objects as variable_order.

The (work-in-progress) diagram is also passed and can be queried about already assigned variables or the nodes & states of the last layer.

source
Diderot.transitionsFunction
transitions(instance, state, variable::Int)::Dict{Arc{S,D,V},S}

All feasible transitions from the given state by any assignment in the variable's domain.

Arcs specify the original state, the variable assignment and the contribution the objective and are mapped to the new state.

source
Diderot.processFunction
process(processing, layer::Layer{S,D,V})::Layer{S,D,V}

Build a new layer by processing the nodes of the given layer.

For restrictions, this could mean simply selecting a subset of the nodes, to stay within the width limit.

For relaxations, new nodes are created by merging existing nodes (and setting exact=false).

Optional: Defaults to identity.

source

## Usage

Solving an instance by branch-and-bound.

solution = branch_and_bound(instance, restrict=Restrict(), relax=Relax())
Diderot.branch_and_boundFunction
branch_and_bound(instance; restrict, relax, variable_order)

Solve given instance using branch-and-bound. For each subproblem, a restriction is computed to update the incumbent. Then a relaxation is computed. If the problem can not be pruned from the relaxation bound, new subproblems are created from an exact cutset in the relaxation's diagram.

source

Solving an instance with a single exact diagram:

diagram = Diagram(instance)
top_down!(diagram, instance)
solution = longest_path(diagram)

Similarly, a single restriction or relaxation can be computed.

Diderot.top_down!Function
top_down!(diagram::Diagram{S,D,V}, instance; variable_order, processing)

Build a decision diagram for given instance. It is developed layer by layer, from the top, by following the state transitions. The first layer with a single root node should already be present in the diagram.

Without any layer processing, the diagram will be exact, that is will contain a path representing an optimal solution.

Restrictions or relaxations are achieved by dropping or merging the nodes and states in each layer.

source

TBD

TBD