The #cpaior2023 master class continues with Willem-Jan van Hoeve talking about decision diagram relaxations, which have been integrated with constraint programming solvers for solving traveling salesperson and with linear programming solvers for solving vehicle routing problems

Decision diagrams have been long used for representing Boolean functions (0–1 output), which are translated to assignments leading to infeasible and feasible solutions in discrete optimization; for linearly separable objectives, we can find optimal solutions w/ min/max cost paths

These diagrams can be either obtained through a top-down construction or by iterative refinement from a compact decision diagram that initially accepts all solutions as feasible

Due to the potentially explosive size, we may resort to relaxed decision diagrams with a limited number of nodes by allowing more solutions to be feasible, basically along the lines of iterative refinement — but not proceeding all the way to obtaining an exact representation

There is a vast literature on applying decision diagrams — and especially relaxed decision diagrams — to solving optimization problems in the last 15 years; and more recently also a commercial solver by @getnextmv

@thserra @getnextmv @ryanjoneil @ryanjoneil does a nice decision diagram walkthrough in this talk: youtu.be/WtdUhYH5Szs