On Solving Boolean Multilevel Optimization Problemse

Josep Argelich, Inês Lynce, João Marques-SilvaIJCAI 2009

Abstract

Hierarchical optimization problems, where constraints and objectives are organized by strict priority, are prevalent in fields like software package management. Traditional methods using weighted Pseudo-Boolean (PB) or Maximum Satisfiability (MaxSAT) encodings often encounter a "weight explosion" problem, where exponential weight growth leads to numerical instability and solver inefficiency. This paper presents Boolean Multilevel Optimization (BMO), a framework that decomposes hierarchical problems into a sequence of subproblems. We introduce two algorithms: $BMO^{rsc}$ for MaxSAT and $BMO^{ipb}$ for PB optimization. Experimental results on Linux Debian package management benchmarks show that BMO significantly improves solver scalability and robustness, enabling the solution of large-scale instances that were previously intractable.

Introduction

Many combinatorial optimization tasks involve a hierarchy of preferences. For instance, in software package management, one must first satisfy hard dependency constraints, then maximize the installation of requested packages, and finally minimize the removal of existing packages or the addition of unnecessary dependencies.

To solve these using standard optimization tools, researchers typically assign weights to goals. To ensure that a higher-priority goal is always preferred over any combination of lower-priority goals, weights must grow exponentially. This "weight explosion" creates significant challenges for modern solvers, leading to numerical overflows or excessive search times ("thrashing") on low-level decisions.

Methodology: The BMO Framework

The Boolean Multilevel Optimization (BMO) framework shifts from a single-objective approach to an iterative multilevel strategy. By solving a sequence of smaller subproblems, BMO maintains numerical stability.

$BMO^{rsc}$ (Weight Rescaling)

Designed for MaxSAT solvers, $BMO^{rsc}$ solves a sequence of subproblems corresponding to each priority tier. After finding an optimal solution for a higher-priority tier, the algorithm "rescales" weights for the subsequent tier. This ensures that the integers used for weights remain small and manageable, preventing the solver from being overwhelmed by astronomical values.

$BMO^{ipb}$ (Iterative Pseudo-Boolean Optimization)

$BMO^{ipb}$ avoids weights entirely by treating the hierarchy as a sequence of constrained optimization problems. It solves the most important tier, fixes the resulting optimal value as a new hard constraint, and then proceeds to optimize the next tier. This iterative refinement ensures that the final solution respects the global hierarchy without requiring large coefficients.

Experimental Evaluation

The proposed framework was evaluated using real-world data from the Linux Debian distribution archives. The benchmarks consist of daily snapshots of the Debian repository, creating instances denoted as $i<x>u<y>$, where $x$ is the number of installed packages (up to 4,000) and $y$ is the number of packages to be upgraded. These instances represent a rigorous stress test for dependency solvers.

Results and Discussion

The experimental results demonstrate a dramatic performance boost across various solver architectures.

Pseudo-Boolean Solver Performance

Standard PB solvers like Bsolo and Minisat+ frequently timed out (exceeding the 900-second limit) on large instances when using default encodings. However, when integrated into the $BMO^{ipb}$ framework, Bsolo successfully solved every instance, often in under 90 seconds. This improvement is detailed in the performance table below.

Performance comparison of Pseudo-Boolean solvers using the $BMO^{ipb}$ framework.

MaxSAT Solver Performance

Similarly, MaxSAT solvers benefited significantly from the $BMO^{rsc}$ approach. The solver IncWMaxSatz reduced its runtime on the largest instances from 45.69 seconds to just 7.39 seconds. The framework effectively linearizes the scaling behavior of these solvers relative to problem size, as shown in the comparative data.

Performance comparison of MaxSAT solvers using the $BMO^{rsc}$ framework.

Conclusion

The BMO framework provides a robust solution to the weight explosion problem in hierarchical optimization. By decomposing complex problems into iterative subproblems, BMO allows off-the-shelf solvers to handle large-scale, preference-heavy tasks with greater efficiency and numerical stability. Future work will explore extending BMO to non-Boolean variables and deeper integration into solver core logic.

Summary updated

BibTeX
@inproceedings{argelich2009solving,
  author = {Josep Argelich and Inês Lynce and João Marques-Silva},
  title = {{On Solving Boolean Multilevel Optimization Problemse}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2009},
}
Figure