Approaches based on Binary decision diagrams (BDDs) have recently achieved
state-of-the-art results for multiobjective integer programming problems. The
variable ordering used in constructing BDDs can have a significant impact on
their size and on the quality of bounds derived from relaxed or restricted BDDs
for single-objective optimization problems. We first showcase a similar impact
of variable ordering on the Pareto frontier (PF) enumeration time for the
multiobjective knapsack problem, suggesting the need for deriving variable
ordering methods that improve the scalability of the multiobjective BDD
approach. To that end, we derive a novel parameter configuration space based on
variable scoring functions which are linear in a small set of interpretable and
easy-to-compute variable features. We show how the configuration space can be
efficiently explored using black-box optimization, circumventing the curse of
dimensionality (in the number of variables and objectives), and finding good
orderings that reduce the PF enumeration time. However, black-box optimization
approaches incur a computational overhead that outweighs the reduction in time
due to good variable ordering. To alleviate this issue, we propose LEO, a
supervised learning approach for finding efficient variable orderings that
reduce the enumeration time. Experiments on benchmark sets from the knapsack
problem with 3-7 objectives and up to 80 variables show that LEO is ~30-300%
and ~10-200% faster at PF enumeration than common ordering strategies and
algorithm configuration. Our code and instances are available at
this https URL

基于二进制决策图的方法在多目标整数规划问题上取得了最先进的结果，本文提出了一种基于变量顺序的新颖参数配置空间，并通过监督学习方法找到了有效的变量顺序，以降低枚举时间。