In multicriteria decision-making, a user seeks a set of non-dominated
solutions to a (constrained) multiobjective optimization problem, the so-called
Pareto frontier. In this work, we seek to bring a state-of-the-art method for
exact multiobjective integer linear programming into the heuristic realm. We
focus on binary decision diagrams (BDDs) which first construct a graph that
represents all feasible solutions to the problem and then traverse the graph to
extract the Pareto frontier. Because the Pareto frontier may be exponentially
large, enumerating it over the BDD can be time-consuming. We explore how
restricted BDDs, which have already been shown to be effective as heuristics
for single-objective problems, can be adapted to multiobjective optimization
through the use of machine learning (ML). MORBDD, our ML-based BDD sparsifier,
first trains a binary classifier to eliminate BDD nodes that are unlikely to
contribute to Pareto solutions, then post-processes the sparse BDD to ensure
its connectivity via optimization. Experimental results on multiobjective
knapsack problems show that MORBDD is highly effective at producing very small
restricted BDDs with excellent approximation quality, outperforming
width-limited restricted BDDs and the well-known evolutionary algorithm
NSGA-II.

通过机器学习方法，本研究使用二进制决策图在多准则决策中精确求解多目标整数线性规划问题，发现适用于单目标问题的局限二进制决策图可通过 ML 方法进行改进，产生具有优秀近似精度且规模较小的稀疏解。