MORBDD: Multiobjective Restricted Binary Decision Diagrams by Learning to Sparsify
This work addresses the problem of scalability in multiobjective optimization for decision-makers, offering a heuristic improvement over exact methods but is incremental as it adapts existing restricted BDD techniques to a multiobjective context.
The paper tackles the challenge of efficiently approximating the Pareto frontier in multiobjective integer linear programming by introducing MORBDD, a machine learning-based method that sparsifies binary decision diagrams to reduce computational time while maintaining solution quality, achieving superior performance over existing heuristics like NSGA-II in experiments on knapsack problems.
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.