LEO: Learning Efficient Orderings for Multiobjective Binary Decision Diagrams

Abstract

Approaches based on Binary decision diagrams (BDDs) have recently achieved state-of-the-art results for some 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 that 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 $3{\times }$ and $1.3{\times }$ faster at PF enumeration than a lexicographic ordering and algorithm configuration, respectively. Our code and instances are available at https://github.com/khalil-research/leo.

Appendices

A Feature Engineering

Table 5 lists the features for an MKP. It can be divided into two types: variable features and context features. The role of variable features is to summarize the information associated with a particular variable, whereas the context features contain the instance level information. The variable features can be further partitioned into two main categories: property-based and rank-based. The property-based features are based on properties detailed in Table 1 and rank-based features are derived by sorting variables based on property values. In summary, we have 18 variable features and 19 context features, resulting in a total of 37 features per variable. Note that our learning models are based on GBT. However, we do not use context features in all its variants. Specifically, ML and ML+A do not use them whereas ML+C and ML+AC do. Finally, we would like to highlight that similar features can be derived for the problem classes with more than one constraint as given in [36, 51].

Table 5. Features for an MKP.

B SMAC Setup

Initialization. For both uses of SMAC, we use the MinWt ordering as a warm-start by assigning all the property weights to zero except the weight property, which is set to -1. This reduces the need for extensive random exploration of the configuration space by providing a reasonably good ordering heuristic.

Random Seeds. As SMAC is a randomized optimization algorithm, running it with multiple random seeds increases the odds of finding a good solution. We leverage this idea for SmacI as its outputs will be used as labels for supervised learning and are thus expected to be of very high quality, i.e., we seek instance-specific parameter configurations that yield variable orderings with minimal solution times. We run SmacD with a single seed and use its average run time on the training set as a target to beat for SmacI. Since the latter optimizes at the instance level, one would hope it can do better than the distribution-level configuration of SmacD.

As such, for SmacI, we run SMAC on each instance with 5 seeds for all sizes except (5, 40) and (6, 40), for which we used one seed. We start with one seed, then average the run time of the best-performing seed per instance to that of the average enumeration time of SmacD on the training set, and relaunch SMAC with a new seed until a desired performance gap between SmacI and SmacD is achieved.

Computational Budget. In the SmacD setting, we run SMAC with a 12-hour time limit, whereas in the SmacI case the time limit is set to 20 min per instance except for sizes (3, 60), (4, 50), (5, 40), for which it is set to 5 min per instance. In both settings, SMAC runs on a 4-core machine with a 20GB memory limit. It can be observed that generating the labels can be computationally expensive. This dictates the choice of sizes in the set of instance sizes, $\mathcal S$. Specifically, we select instance sets with an average running time of at most 100 s (not too hard) and at least 5 s (nor too easy) using the top-down compilation method described in Bergman et al. [5].

SmacI Performance Profile. Having established in Q1 that the search for high-quality variable orderings is justified, we now turn to a key component of Phase 1: the use of SMAC as a black-box optimizer that produces “label” variable orderings for subsequent ML in Phase 2. Figure 3 shows the average run time, on the training instances, of the incumbent property-weight configurations found by SMAC. These should be interpreted as standard optimization convergence curves where we seek small values (vertical axis) as quickly as possible (horizontal axis). Indeed, SMAC performs well, substantially improving over its initial warm-start solution (the MinWt ordering). The flat horizontal lines in the figure show the average run time of the single configuration found by SmacD. The latter is ultimately outperformed by the SmacI configurations on average, as desired.

C Additional Results

1.1 C.1 Impact of Variable Ordering on PF Enumeration Time

The heuristic orderings are constructed using the variable properties. For example, the heuristic ordering called max_avg-value-by-weight sorts the variables in descending order of the ratio of a variable’s average value by its weight.

Table 6 summarizes the results of this experiment. We work with 250 MKP instances of the problem sizes (3, 20), (3, 40), (3, 60), (3, 80), (5, 20), (5, 30), (5, 40), (7, 20), (7, 30), and (7, 40). The values in the table are the ratios of the average run time of a heuristic ordering to that of the 5 random orderings; values smaller than one indicate that a heuristic ordering is faster than a random one, on average. The best heuristic ordering for each size is highlighted.

Fig. 3.

SmacI performance w.r.t. wallclock time across different sizes. For a given size, we first of all find the best seed, i.e., the seed which finds an incumbent property-weight having minimum PF enumeration time, for each instance. Then for a given wallclock time, we calculate the mean and standard error of the PF enumeration time across instances for the incumbent property-weight up to that wallclock time. The mean and standard error are plotted as a blue line and blue error band around it, respectively. The horizontal black line represents the average PF enumeration time of SmacD configuration on the validation set.

First, it is clear that some heuristic orderings consistently outperform the random ones across all problem sizes (min_weight, max_min-value), and by a significant margin. In contrast, some heuristic orderings are consistently worse than random. For example, the heuristic ordering max_weight, min_avg-value, and min_min-value consistently underperform when the number of variables is more than 20. Second, the choice of MinWt as a baseline was motivated by the results of this experiment as min_weight wins on most sizes as highlighted in Table 6. Altogether, this experiment validates the hypothesis that VO has an impact on the PF enumeration time and that there exists EVO that can significantly reduce this time.

1.2 C.2 Performance of LEO in Comparison to Other Baselines

Fig. 4.

Box plots of time to enumerate the PF for different sizes.

Fig. 5.

Performance profile of different methods in terms of the fraction of instances solved w.r.t. time for various sizes.

The detailed version of Table 3, with additional statistics, is provided in Table 7. To complement this further, we present box plots and performance profiles in Fig. 4 and Fig. 5, respectively. Note how the PF enumeration time distribution for the ML method is much more concentrated, with a smaller median and only a few outliers compared to other methods. Note that the instances that had a timeout are omitted from this analysis. This performance improvement leads to a larger fraction of instances being solved in a smaller amount of time as highlighted in Fig. 5.

Table 6. Ratio of the average time taken by a heuristic ordering to that of 5 random orderings across 250 MKP instances across sizes specified. A ratio of less (greater) than 1 indicates that heuristic ordering performs better (worse) than random ordering, on average. The name of a heuristic ordering follows the structure $\langle$sort$\rangle$_$\langle$property-name$\rangle$, where $\langle$sort$\rangle$ can either be min or max and $\langle$property-name$\rangle$ can be equal to one of the properties defined in Table 1. A value of max (min) for $\langle$sort$\rangle$ would sort the variables in the descending (ascending) order of the property $\langle$property-name$\rangle$.

Table 7. PF enumeration time statistics on the test set containing 100 instances with a time limit of 1800 s. Each row represents aggregate statistics for a given instance “Size” and “Method”. “Count” stands for the number of instances on which the algorithm ran successfully without hitting the time or memory limits. “GMean”, “Mean”, “Min”, “Max” and “Std” denotes the geometric mean, arithmetic mean, minimum, maximum and standard deviation of the enumeration time computed across “count” many instances. We use a shift of 5 to compute the “GMean”.

1.3 C.3 BDD Topology Analysis

The mean cumulative number of solutions generated at a given level are given in Fig. 6 and the BDD topology analysis for all sizes is detailed in Table 8. It is evident from both of these that ML-based VO leads to fewer intermediate solutions, which results in smaller number of Checks and improved PF enumeration time.

Fig. 6.

Cumulative number of intermediate solutions generated at a particular layer across all sizes.

Fig. 7.

Feature importance plot for ML+A model. Refer to the caption of Fig. 2 for an explanation of the feature naming conventions.

Table 8. Analyzing the impact of BDD topology on the PF enumeration time on the test set. For a given “Size” and “Method”, the metric value indicates the percentage of mean performance by that “Method” compared to the Lex method. The “Nodes” (“Width”) represents the percentage of the mean of the number of nodes (mean width) of the BDDs generated by “Method” to that of Lex. “Degree” denotes the percentage of the mean ratio of the in-degree of the top 50 nodes with the highest in-degree in BDDs generated by “Method” to that of Lex. Similarly, “Checks” and “Time” indicate the percentage of the average Pareto-dominance checks and the average geometric mean of the PF enumeration time, respectively. For all metrics, values less than 100 are preferred. For example, a value of $\delta$ for “Nodes” indicates that the mean number of nodes for “Method” is $\delta /100 {\times }$ the mean number of nodes of “Lex”.

1.4 C.4 Feature Importance Plots for Size-Independent ML Models

Figure 7 and Fig. 8 shows the feature importance plots for the ML+A and ML+AC models, respectively. The std-value and min-value-by-weight features are ranked highly by both models. The usefulness of the context features is clearly highlighted by their presence in the top 5 features of the ML+AC model.

Fig. 8.

Feature importance plot for ML+AC model. Features that start with “c_” are context features; see Table 5.