The Toronto Intelligent Decision Engineering Laboratory
Decision Diagrams

Decision Diagrams for Discrete Optimization Problems


J. Christopher Beck
Margarita Castro
Andre Cire
Wen-Yang Ku
Chiara Piacentini

Project description

Over the last decade, Decision Diagrams (DD) have been used to solve challenging discrete optimization problems from the OR literature. The general approach uses a DD to represent the set of feasible solutions for a problem. Given that the feasible set can be exponential in the size of the problem, the approach uses a relaxed DD to encode a discrete relaxation of the problem (i.e., a superset of the feasible set). This discrete relaxation is then used to compute bounds on the problem and can be encoded in a branch-and-bound algorithm to solve the problem.

This project aims to extend the use of relaxed DDs solve discrete optimization problems. Given the limited number of problems that the approach can currently solve, initial work includes developing new compilation and filtering procedures to extend the use of relaxed DDs to a wide variety of OR problems. Mid/long-term works include extensions to other fields, e.g. AI Planning, theoretical analysis and hybrid approaches via decomposition and Lagrangian duality.

Start date

September 2015


University of Toronto Fellowship
TIDEL Research Assistantship


Coming soon.
University of Toronto Mechanical and Information Engineering