TL;DR
This paper introduces a method called "Selection by Performance Prediction" (SPP) to automatically choose the best Branch and Bound (B&B) algorithm for a specific problem instance. By quickly estimating the performance of candidate algorithms on the given problem, SPP significantly outperforms random selection and interleaved approaches, saving valuable computation time.
What Problem Does This Paper Address?
Solving complex combinatorial optimization problems often relies on Branch and Bound (B&B) algorithms. However, the performance of B&B algorithms can vary dramatically depending on the specific problem instance and the algorithm's internal choices (like variable ordering or bound computation). This means that a "one-size-fits-all" algorithm rarely exists. In practice, when faced with a particular problem, choosing the right B&B algorithm from a list of promising candidates is crucial, especially when time is limited. A poor choice can lead to unacceptably long running times. This paper tackles the challenge of predicting which B&B algorithm will perform best on a given instance before committing to a full search.
Methods
The core of the proposed method, Selection by Performance Prediction (SPP), is based on Knuth's sampling method. This technique, originally designed to estimate the size of search trees for backtrack programs, is adapted here for B&B algorithms.
Here's how it works:
- Estimating Search Tree Size: For each candidate B&B algorithm, SPP runs a modified version of the algorithm (called
SAMPLE) on the specific problem instance. ThisSAMPLEprocedure explores random paths in the search tree, but crucially, it uses a constant upper bound (the initial one provided) rather than updating it as a regular B&B algorithm would. This allows for a statistical estimation of the number of nodes the algorithm would explore. - Estimating Time Per Node: To estimate the total running time, SPP also needs to know how long each node takes to process. This is done by running the candidate algorithm for a short, fixed duration on the instance and then calculating the average time spent per node.
- Performance Prediction: The estimated running time for each candidate algorithm is then calculated by multiplying its estimated number of nodes by its estimated time per node.
- Algorithm Selection: SPP selects the algorithm with the lowest predicted running time.
The key novelty lies in adapting Knuth's estimation to the B&B context, specifically by using a constant upper bound during sampling to make the estimation tractable and relevant.
Datasets
The paper evaluates the SPP method on two types of instances:
- Strongly Structured Instances: These are sub-instances of the Radio Link Frequency Assignment Problems (RLFAP), specifically from the CELAR instances 6 and 7. These are described as some of the most difficult instances in the set.
- Random Instances: 238 random instances were generated using a model described in Smith (1994), modified to accommodate valued constraints. These instances have 20 variables and 10 values per variable, with a graph connectivity of 50% and constraint tightness of 90%. Constraint values were uniformly drawn from {1, 10, 100, 1000, 100000}.
Key Insights and Ideas
- The "No Free Lunch" Theorem in Practice: The experiments strongly suggest that for combinatorial optimization problems, there isn't a single B&B algorithm that's best for all instances. Each instance often benefits from a specific algorithm tailored to its structure.
- Predicting Performance is Feasible and Beneficial: Despite the inherent difficulty in predicting B&B performance and the large variance in estimation, SPP proves to be surprisingly effective. The method's success hinges on comparing candidate algorithms relative to each other on the specific instance, rather than relying on absolute, potentially inaccurate, performance predictions.
- Constant Upper Bound is Key for Sampling: The adaptation of Knuth's method using a constant upper bound during sampling is crucial. While this sampled tree differs from the actual B&B search tree (which updates its bound), this difference is handled by comparing algorithms on the same basis.
- SPP Outperforms Simple Strategies: SPP significantly beats random selection and interleaved execution strategies in terms of expected running time. This highlights the value of intelligent algorithm selection.
Key Results
- On RLFAP instances: SPP successfully selected the best algorithm in the majority of runs. When it didn't select the absolute best, it typically chose a good one and rarely the worst. The method's accuracy increased with larger differences in running times between candidate algorithms.
- On random instances: SPP's cumulated running time over 238 instances was very close to that of a hypothetical "perfect selection" method, significantly outperforming random selection.
- Comparison with other approaches: SPP consistently showed lower expected running times compared to RANDOM (random choice) and INTERLEAVED (running algorithms concurrently and stopping the first one that finishes), even when accounting for the estimation overhead. For instance, on instance I1, SPP's expected running time was 1423 seconds, compared to 35892 for Random and 58756 for Interleaved.
Limitations and Future Work
- Estimation Process Improvements: The authors acknowledge that the estimation process itself could be improved. A deeper understanding of problem structures could lead to more accurate running time predictions.
- Importance Sampling and Heuristics: They suggest investigating more advanced estimation techniques like importance sampling (mentioned by Knuth) or partial backtracking (Purdom 1978) and heuristic sampling (Chen 1992) for constraint optimization problems.
- Application to Inconsistent CSPs: The current work focuses on Valued CSPs (which can be consistent or inconsistent). The authors suggest that the method could be applied to inconsistent CSP instances, as proving inconsistency also implies a complete search.
- Application to Consistent CSPs: Investigating the application of SPP to purely consistent CSP instances is also proposed as future work.
Summary updated