 |
Decision Diagrams for Discrete Optimization Problems
Members
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
Funding
University of Toronto Fellowship
TIDEL Research Assistantship
Publications
Coming soon.
|
