Skip to content

For developers

As explained in our paper (see References), DD-suite is designed thinking of the developers, so each key feature can be easily modified and extended depending on the user's needs. In particular, DD-suite has separate classes for the DD structure (i.e., the graph itself), the construction procedures, the discrete problem, and each of the provided algorithms to manipulate the DD. Our Tutorial explains how to incorporate new problems (i.e., the knapsack problem) and how to use provided algorithms for optimization purposes (e.g., cutting planes). We now explain how to extend the capabilities of DD-suite in terms of construction mechanism and usability.

Incorporating new DD construction mechanisms

Given that the DD graphical structure is separate from the construction mechanism, DD-suite allows changing or incorporating different DD construction algorithms without altering its usability. Our code includes a generic top-down DD construction procedure in the AbstractDDBuilder file (in the SourceCode\DDBuilder folder), which can be personalized by creating a class that inherits from it and specifyings its beahaviour using the functions:

  • _specific_end_of_layer_function() and
  • _specific_end_of_construction_frunction().

For example, DD-suite uses this abstract class as a base for our ExactDDBuilder, RelaxedDDBuilder, and RestrictedDDBuilder.

Moreover, users can create their own DD construction class and maintain the provided graphical structure. The main advantage of doing so is that independent of how the DD is constructed, the user should be able to use all the other algorithms provided by DD-suite, such as the ShortestLongestPath algorithm. For instance, the user might want to experiment with other DD construction mechanisms for relaxed DDs (i.e., the separation procedure) and compare the bounds obtained by different construction procedures. To do so, the user would have to create a new DDBuilder class using our graphical structure as a base (see the files in the SourceCode\DDStructure folder) and then use the algorithms for ShortestLongestPath provided in DD-suite to obtain the dual bounds.

Lastly, the DD construction code we provided is quite general and can be easily tuned using some of the functions that need to be specified in the problem implementation. Specifically, the user can easily change the merging/discarding heuristics and the variable ordering for the DD without altering the DD construction procedure itself.

Extending DD-suite usability

As shown by many authors (see DD survey papers in References), DDs can be used as a supporting tool to solve different types of optimization problems. DD-suite was developed with this idea in mind so developers can freely use the constructed DD as they please. For example, DD-suite provides a cutting plane procedure to illustrate how one can create different algorithms on top of the constructed DD. In such an example, we implemented a max flow algorithm over the DD structure and other procedures to develop our cutting plane implementation. We even provide an AbstarctCutGenerator file (in the Source/Code/DDCutGenerators folder) so users can easily implement new DD-based cut generators and compare them with the provided by DD-suite.

Overall, users are free to create other algorithms that use the constructed DD for their own needs. The possibilities are endless and just limited by the imagination.