On Solving Boolean Multilevel Optimization Problemse
Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 393-397.
© 2009 International Joint Conferences on Artificial Intelligence
Abstract
Many combinatorial optimization problems entail a number of hierarchically dependent optimization problems. An often used solution is to associate a suitably large cost with each individual optimization problem, such that the solution of the resulting aggregated optimization problem solves the original set of optimization problems. This paper starts by studying the package upgradeability problem in software distributions. Straightforward solutions based on Maximum Satisfiability (MaxSAT) and pseudo-Boolean (PB) optimization are shown to be ineffective, and unlikely to scale for large problem instances. Afterwards, the package upgradeability problem is related to multilevel optimization. The paper then develops new algorithms for Boolean Multilevel Optimization (BMO) and highlights a large number of potential applications. The experimental results indicate that the proposed algorithms for BMO allow solving optimization problems that existing MaxSAT and PB solvers would otherwise be unable to solve.Josep Argelich, Inês Lynce, Joao Marques-Silva
- [Aloul et al., 2002] F. A. Aloul, A. Ramani, I. L. Markov, and K. A. Sakallah. Generic ILP versus specialized 0-1 ILP: an update. In International Conference on Computer- Aided Design, pages 450-457, 2002.
- [Amgoud et al., 1996] L. Amgoud, C. Cayrol, and D. Le Berre. Comparing arguments using preference ordering for argument-based reasoning. In Int. Conf. on Tools with Artificial Intelligence, pages 400-403, 1996.
- [Anandalingam and Friesz, 1992] G. Anandalingam and T. L. Friesz. Hierarchical optimization: An introduction. Annals of Operations Research, 34:1-11, 1992.
- [Argelich and Lynce, 2008] J. Argelich and I. Lynce. CNF instances from the software package installation problem. In RCRA Workshop, 2008.
- [Argelich and Manyà, 2007] J. Argelich and F. Manyà. An improved exact solver for partial Max-SAT. In Int. Conf. on Nonconvex Programming: Local & Global Ap- proaches, pages 230-231, 2007.
- [Boutilier et al., 2004] C. Boutilier, R. I. Brafman, C. Domshlak, H. H. Hoos, and D. Poole. CP-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements. Journal of Artificial Intelligence Research, 21:135-191, 2004.
- [Bracken and McGill, 1973] J. Bracken and J. T. McGill. Mathematical programs with optimization problems in the constraints. Operations Research, 21:37-44, 1973.
- [Candler and Norton, 1977] W. Candler and R. Norton. Multi-level programming. Technical Report DRD-20, World Bank, January 1977.
- [Colson et al., 2007] B. Colson, P. Marcotte, and G. Savard. An overview of bilevel programming. Annals of Opera- tions Research, 153:235-256, 2007.
- [Denegre and Ralphs, 2009] S. Denegre and T. Ralphs. A branch-and-cut algorithm for integer bilevel linear pro- grams. In INFORMS Comp. Soc. Meeting, January 2009.
- [Eén and Sörensson, 2006] N. Eén and N. Sörensson. Trans- lating pseudo-Boolean constraints into SAT. Journal on Satisfiability, Boolean Modeling and Computation, 2:226, 2006.
- Freuder et al., In Press] E. Freuder, R. Heffernan, R. Wal- lace, and N. Wilson. Lexicographically-ordered constraint satisfaction problems. Constraints, In Press.
- [Giunchiglia and Maratea, 2007] E. Giunchiglia and M. Maratea. Planning as satisfiability with preferences. In AAAI Conference on Artificial Intelligence, pages 987-992, 2007.
- [Heras et al., 2008] F. Heras, J. Larrosa, and A. Oliveras. MiniMaxSAT: An efficient weighted Max-SAT solver. Journal of Artificial Intelligence Research, 31:1-32, 2008.
- [Junker, 2004] U. Junker. Preference-based search and multi-criteria optimization. Annals of Operations Re- search, 130(1-4):75-115, 2004.
- [Lin et al., 2008] H. Lin, K. Su, and C.-M. Li. Within- problem learning for efficient lower bound computation in max-sat solving. In AAAI Conference on Artificial Intelli- gence, pages 351-356, 2008.
- [Lukasiewycz et al., 2007] M. Lukasiewycz, M. Glaß, C. Haubelt, and Jürgen Teich. Solving multi-objective pseudo-boolean problems. In Int. Conf. on Theory and Applications of Satisfiability Testing, pages 56-69, 2007.
- [Mancinelli et al., 2006] F. Mancinelli, J. Boender, R. di Cosmo, J. Vouillon, B. Durak, X. Leroy, and R. Treinen. Managing the complexity of large free and open source package-based software distributions. In Int. Conf. Automated Soft. Engineering, pages 199-208, 2006.
- [Manquinho and Marques-Silva, 2004] V. Manquinho and J. Marques-Silva. Satisfiability-based algorithms for boolean optimization. Annals of Mathematics and Arti- ficial Intelligence, 40(3-4):353-372, 2004.
- [Marcotte et al., 2004] P. Marcotte, G. Savard, and F. Semet. A bilevel programming to the travelling salesman problem. Operations Research Letters, 21:240-248, 2004.
- [Meseguer et al., 2006] P. Meseguer, F. Rossi, and T. Schiex. Soft constraints. In Handbook of Constraint Program- ming, pages 281-328. 2006.
- [Rossi et al., 2008] F. Rossi, K. B. Venable, and T. Walsh. Preferences in constraint satisfaction and optimization. AI Magazine, 29(4), 2008.
- [Tucker et al., 2007] C. Tucker, D. Shuffelton, R. Jhala, and S. Lerner. OPIUM: Optimal package install/uninstall man- ager. In Int. Conf. Soft. Engineering, pages 178-188, 2007.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
Many real problems require an optimal solution rather than any solution. Whereas decision problems require a yes/no answer, optimization problems require the best solution, thus differentiating the possible solutions. In practice, there must be a classification scheme to determine how one solution compares with the others. Such classification may be seen as a way of establishing preferences that express cost or satisfaction.
A special case of combinatorial optimization problems may require a set of optimization criteria to be observed, for which is possible to define a hierarchy of importance. Not only you establish a hierarchy in your preferences, but also the preferences are defined in such a way that the set of potential solutions gets subsequently reduced. Such kind of problems are present not only in your daily life but also in many real applications.
∗The authors thank Nic Wilson and Jorge Orestes for insightful comments. This work is partially funded by European projects Mancoosi (FP7-ICT-214898) and Coconut (FP7-ICT-217069), and by FCT project Bsolo (PTDC/EIA/76572/2006).
Clearly, the problems we target can be encoded as a constraint optimization problem, making use of the available technology for dealing with preferences. Preference handling is a current hot topic in AI with active research lines in constraint satisfaction and optimization [Rossi et al., 2008]. Broadly, preferences over constraints may be expressed quantitatively or qualitatively. Soft constraints model quantitative preferences by associating a level of satisfaction with each of the solutions [Meseguer et al., 2006], whereas CP-nets model qualitative preferences by expressing preferential dependencies with pairwise comparisons [Boutilier et al., 2004]. Furthermore, preference-based search algorithms can be generalized to handle multi-criteria optimization [Junker, 2004].
A straightforward approach to solve a special case of a constraint optimization problem, for which there is a total ranking of the criteria, would be to establish a lexicographic ordering over variables and domains, such that optimal solutions would come first in the search tree [Freuder et al., In Press]. But this has the potential disadvantage of producing a thrashing behavior whenever assignments that are not supported by any solution are considered, as a result of decisions made at the first nodes of the search tree [Junker, 2004].
Maximum satisfiability (MaxSAT) naturally encodes a constraint optimization problem over Boolean variables where constraints are encoded as clauses. A solution to the MaxSAT problem maximizes the number of satisfied clauses. Weights may also be associated with clauses, in which case the sum of the weights of the satisfied clauses is to be maximized. The use of the weighted MaxSAT formalism allows to solve a set of hierarchically dependent optimization problems. Pseudo-Boolean (PB) optimization may also be used to solve this kind of problems, given that weighted MaxSAT problem instances can be translated to PB [Heras et al., 2008]. Each clause is extended with a relaxation variable that is then included in the cost function, jointly with the respective weight.
Boolean satisfiability (SAT) and PB have been extended in the past to handle preferences. For example, SAT-based planning has been extended to include conflicting preferences [Giunchiglia and Maratea, 2007], to which weights are associated, thus requiring the use of an objective function involving the preferences and their weights. In addition, algorithms for dealing with multi-objective PB problems have been developed [Lukasiewycz et al., 2007], in contrast to traditional algorithms that optimize a single linear function.
This paper is organized as follows. The next section describes the problem of package upgradeability in software systems. being developed. Section 3 introduces multilevel optimization and relates it with a variety of problems. Afterwards, specific multilevel optimization algorithms are proposed, being based on MaxSAT and PB. Experimental results show the effectiveness of the new algorithms.
2 A Practical Example
We have all been through a situation where the installation of a new piece of software turns out to be a nightmare. These kinds of problems may occur because there are constraints between the different pieces of software (called packages). Although these constraints are expected to be handled in a consistent and efficient way, current software distributions are developed by distinct individuals. This is opposed to traditional systems which have a centralized and closed development. Open systems also tend to be much more complex, and therefore some packages may become incompatible. In such circumstances, user preferences should be taken into account.
The constraints associated with each package can be defined by a tuple (p,D,C), where p is the package, D are the dependencies of p, and C are the conflicts of p. D is a set of dependency clauses, each dependency clause being a disjunction of packages. C is a set of packages conflicting with p. Previous work has applied SAT-based tools to ensure the consistency of both repositories and installations, as well as to upgrade consistently package installations. SATbased tools have first been used to support distribution editors [Mancinelli et al., 2006]. The developed tools are automatic and ensure completeness, which makes them more reliable than ad-hoc and manual tools. Recently, Max-SAT has been applied to solve the software package installation problem from the user point of view [Argelich and Lynce, 2008]. In addition, the OPIUM tool [Tucker et al., 2007] uses PB constraints and optimizes a user provided single objective function. One modeling example could be preferring smaller packages to larger ones.
The encoding of these constraints into SAT is straightforward: for each package pi there is a Boolean variable xi that is assigned to true iff package pi is installed, and clauses are either dependency clauses or conflict clauses (one clause for each pair of conflicting packages).
Example 1 Given a set of package constraints S = {(p1, {p2, p5 ∨ p6}, ∅), (p2, ∅, {p3}), (p3, {p4}, {p1}), (p4, ∅, {p5, p6})}, its encoded CNF instance is the following:
The problem described above is called software installability problem. The possibility of upgrading some of the packages (or introducing new packages) poses new challenges as existing packages may eventually be deleted. The goal of the software upgradeability problem is to find a solution that satisfies user preferences by minimizing the impact of introducing new packages in the current system, which is a reasonable assumption. Such preferences may be distinguished establishing the following hierarchy: (1) constraints on packages cannot be violated, (2) required packages should be installed, (3) packages that have been previously installed by the user should not be deleted, (4) the number of remaining packages installed (as a result of dependencies) should be minimized.
The software upgradeability problem can be naturally encoded as a weighted partial MaxSAT problem. In weighted MaxSAT, each clause is a pair (C,w) where C is a CNF clause and w is its corresponding weight. In weighted partial MaxSAT, hard clauses must be satisfied, in contrast to the remaining soft clauses that should be satisfied. Hard clauses are associated with a weight that is greater than the sum of the weights of the soft clauses. A solution to the weighted partial MaxSAT problem maximizes the sum of the weights of the satisfied clauses.
The following example shows a weighted partial MaxSAT formula for the upgradeability problem.
Example 2 Given a set of package constraints S = {(p1, {p2, p5}, {p4}), (p2, ∅, ∅), (p3, {p2 ∨ p4}, ∅), (p4, ∅, ∅), (p5, ∅, ∅)}, the set of packages the user wants to install I = {p1}, and the current set of installed packages in the system A = {p2}, its weighted partial MaxSAT instance is the following:
This example uses a weight distribution that gives priority to the user preferences over all the other packages, and also gives priority to the current installation profile over the remaining packages. The minimum weight (with value 1) is assigned to clauses encoding packages being installed as a result of dependencies, whose number should be minimized. A medium weight (with value 4, resulting from the sum of the weights of the previous clauses plus 1) is assigned to clauses encoding packages currently installed in our system, in order to minimize the number of removed packages. A maximum weight (with value 8) is assigned to the packages the user wants to install. Finally, we assign a hard weight (with value 16) to clauses encoding the dependencies and conflicts.
3 Multilevel Optimization
The software upgradeability problem described in the previous section can be viewed as a special case of the more general problem of Multilevel Optimization [Colson et al., 2007] 1 . Multilevel optimization can be traced back to the early 70s [Bracken and McGill, 1973], when researchers focused on mathematical programs with optimization problems in the constraints. Multilevel optimization represents a hierarchy of optimization problems, where the outer optimization problem is subject to the outcome of each of the enclosed optimization problems in order. In part motivated by the practical complexity of the multilevel optimization, most work in the recent past has addressed the special case of bilevel optimization [Colson et al., 2007]. Moreover, and for the special case of integer or Boolean variables, existing work is still preliminary [Denegre and Ralphs, 2009]. It should also be observed that the general problems of bilevel and multilevel optimization find a wide range of applications [Colson et al., 2007], examples of which can be represented with integer or Boolean variables [Marcotte et al., 2004].
1 This problem is also referred to as Multilevel Programming [Candler and Norton, 1977] and Hierarchical Optimization [Anandalingam and Friesz, 1992].
One can conclude that the software upgradeability problem can be viewed as a special case of multilevel optimization, where the constraints are clauses, and the variables have Boolean domain. The least constrained (or outer) optimization problem represents the problem of minimizing the number of newly installed packages due to dependencies, whereas the most constrained (or inner) optimization problem represents the problem of maximizing the installation of packages in the user preferences.
This paper focuses on the special case of multilevel optimization where the constraints are propositional clauses and the variables have Boolean domain. This problem will be referred to as Boolean Multilevel Optimization (BMO). For BMO, the hierarchy of optimization problems can be captured by associating suitable weights with the clauses, as illustrated for the package upgradeability problem.
More formally, consider a set of clauses C = C1 ∪ C2 ∪ . . . ∪ Cm, where C1,C2, . . . ,Cm form a partition of C. Moreover, consider the partition of C as a sequence of sets of clauses:
Where a weight is associated with each set of clauses:
As with MaxSAT, clauses Cm, each with weight wm, are required to be satisfied, and so are referred to as hard clauses. The associated optimization problem is to satisfy clauses in C1 ∪C2 ∪ . . . ∪Cm-1 such that the sum of the weights of the satisfied clauses is maximized.
Moreover, the hierarchy of optimization problems is captured by the condition:
The above condition ensures that the solution to the BMO problem can be split into a sequence of optimization problems, first solving the optimization problem for the soft clauses with the largest weight (i.e. wm-1), then for the next clause weight, and so on until all clause weights are considered. Building on this observation, the next section proposes dedicated algorithms for BMO.
4 Solving BooleanMultilevel Optimization
This section describes alternative solutions for BMO, in addition to the weight-based solution described earlier in the paper. The first solution is based on iteratively rescaling the weights of the MaxSAT formulation. The second formulation extends the standard encoding of weighted MaxSAT with PB constraints.
4.1 BMOwithMaxSAT
Consider the BMO problem specified by equations (1)-(3). We will now explain how solving a sequence 〈m - 1, . . . , 1〉 of MaxSAT subproblems can significantly reduce the weights associated with the clauses.
The first MaxSAT subproblem corresponds to subproblem m- 1 and is defined as follows:
Note that Cm corresponds to the set of hard clauses and the initial upper bound (UB) is given by the weight associated with the hard clauses 2 . In the worst case, the problem has no solution because at least one hard clause is unsatisfied.
For each MaxSAT subproblem following in the sequence, the weights of the clauses and the initial UB are rescaled, in such a way that the computed weights can be substantially smaller than the original weights.
For each subproblem i, let ui represent the minimum sum of weights of falsified clauses in Ci. In case the weights of the set of clauses in Ci is 1, ui corresponds to the minimum number of falsified clauses in Ci. Also, let pj be the weight associated with a set of clauses Cj in a subproblem. The remaining MaxSAT subproblems can be defined as follows, with m - 2 ≤ i ≤ 1:
Observe that the values of pj are refined for each iteration of the algorithm, as these values depend on the value of uj-1 and pj-1 computed by previous iterations, s.t. pj = (uj-1 + 1) · pj-1 with pi = 1. Note that uj-1 can be smaller than |Cj-1|, thus reducing the values of the computed weights.
Finally, the MaxSAT solution for the original problem is obtained as follows:
Proposition 1 The value obtained with (6), where the different ui values are obtained by the solution of the (4) and (5) MaxSAT problems, yields the correct solution to the BMO problem.
4.2 BMOwith PB
The efficacy of the rescaling method of the previous section is still bound by the weights used. Even though the rescaling method is effective at reducing the weights that need to be considered, for very large problem instances the challenge of large clause weights can still be an issue. An alternative approach is described in this section, which eliminates the need to handle large clauses weights. This approach is based on solving the BMO problem as a sequence of PB problems.
2 We are considering the MinUNSAT problem, instead of the equivalent MaxSAT problem.
Consider the BMO problem specified by equations (1), (2) and (3). Each set of clauses Ci can be modified by adding a relaxation variable to each clause. The resulting set of relaxed clauses is Cr i , and the set of relaxation variables used is denoted by Yi. For example, if cj ∈ Ci, the resulting clause is cj,r = cj ∪yj , and yj ∈ Yi. Solving MaxSAT by adding relaxation variables to clauses is a standard technique [Amgoud et al., 1996; Aloul et al., 2002].
The next step is to solve a sequence of PB problems. The first PB problem is defined as:
Let the optimum solution be vm-1. vm-1 represents the largest number of clauses with weight wm-1 that can be satisfied, independently of the other clause weights.
Moreover, the remaining PB problems can then be defined as follows:
With 1 ≤ i < m- 1, and where the optimum solution is vi. In this case, vi represents the largest number of clauses with weight wi that can be satisfied, taking into account that for larger weights, the number of satisfied clauses must be taken into account. The last problem to be considered corresponds to i = 1, for the clauses with the smallest weight.
Finally, given the definition of vi, the PB-based BMO solution is obtained as follows:
As can be concluded, the proposed PB-based approach can solve the BMO problem without directly manipulating any clause weights.
Proposition 2 The value obtained with (9), where the different vi values are obtained by the solution of the (7) and (8) PB problems, yields the correct solution to the BMO problem.
5 Experimental Evaluation
This section describes the experimental evaluation conducted to show the effectiveness of the new algorithms described above. With this purpose, we have generated a comprehensive set of problem instances of the software upgradeability problem. In a first step, a number of off-the-shelf MaxSAT and PB solvers have been run. In a second step, these MaxSAT and PB solvers have been adapted to perform BMO approaches. In what follows we will use BMOrsc to denote weight rescaling BMO with MaxSAT and BMOipb to denote BMO with iterative pseudo-Boolean optimization.
The problem instances of the upgradeability problem have been obtained from the Linux Debian distribution archive 3 , where Debian packages are daily archived. Each daily archive is a repository. Two repositories corresponding to a snapshot with a time gap of 6 months have been selected. From the first repository, the packages for a basic Debian installation have been picked, jointly with a set of other packages. From the second repository, a set of packages to be upgraded have been picked. This set of packages is a subset of the installed packages. Each problem instance is denoted as i<x>u<y> where x is the number of installed packages (apart from the 826 packages of the basic installation) and y is the number of packages to be upgraded. In the following experiments the number of x packages ranges from 0 to 4000 and the number of y packages is 98. The y packages correspond to the subset of packages of the basic installation that have been updated from one repository to the other.
The four MaxSAT solvers used for the evaluation are: IncWMaxSatz [Lin et al., 2008], MiniMaxSat [Heras et al., 2008], Sat4jMaxsat 4 and WMaxSatz [Argelich and Many`a, 2007]. The four PB solvers used for the evaluation are: Bsolo [Manquinho and Marques-Silva, 2004], Minisat+ [E´en and S¨orensson, 2006], PBS4 [Aloul et al., 2002] and Sat4jPB. Other solvers could have been used, even tough we believe that these ones are some of the most competitive and overall implement different techniques which affect performance differently. For each solver, a set of instances were run with the default solver and BMOrsc or BMOipb . In order to study the scalability as the number of packages to install increases, an additional number of instances has been run for the best performing solver.
The experiments were performed on an Intel Xeon 5160 server (3.0GHz, 1333Mhz FSB, 4MB cache) running Red Hat Enterprise Linux WS 4. JRE 1.6.0 0.07 was used for Sat4j. Each instance was given the timeout of 900 seconds.
Table 1 shows the CPU time required by MaxSAT solvers to solve a set of given problem instances. Column Default shows the results for the off-the-shelf solver and column BMOrsc shows the results for the weight rescaling approach specially designed for solving BMO problems with MaxSAT. For each instance the best result is highlighted in bold.
Clearly, IncWMaxSatz with BMOrsc is the best performing solver. Nonetheless, every other solver benefits from the use of BMOrsc . The only exception is Sat4jMaxsat because it spends around 8 seconds to read each instance and with BMOrsc the solver is called three times for the instances considered. Another advantage of using BMOrsc is that the solvers do not need to deal with the large integers representing the clause weights, which are used in the default encoding. This can be such a serious issue that for some solvers there are a few problem instances (designated with '-') that cannot be solved.
Table 2 shows the results for PB solvers on solving the same instances. BMOipb boosts the solvers performance, with Sat4jPB being the only exception (for some instances it improves, for some other it does not). For the remaining solvers, the improvements are significant: most of the instances aborted by the default solver are now solved with BMOipb . Although there is no dominating solver, in contrast to what happens with IncWMaxSatz in the MaxSAT solvers, Bsolo is the only solver able to solve all the instances with BMOipb . Also, despite an observable trend of increasing run times as the size of the instances increase, there are a few outliers. This also contrasts with MaxSAT solvers, but it is no surprise as additional variables can degrade the solvers performance in an unpredictable way.
3 http://snapshot.debian.net
4 http://www.sat4j.com
| IncWMaxSatz | MiniMaxSat | Sat4jMaxsat | WMaxSatz | |||||
|---|---|---|---|---|---|---|---|---|
| Instance | Default | BMOrsc | Default | BMOrsc | Default | BMOrsc | Default | BMOrsc |
| i0u98 | 3.90 | 3.29 | - | 89.96 | 10.74 | 29.78 | 275.50 | 13.15 |
| i10u98 | 3.58 | 3.63 | - | 90.06 | 10.60 | 25.88 | 276.32 | 13.19 |
| i20u98 | 4.72 | 3.67 | - | 90.24 | 10.77 | 25.94 | 348.13 | 13.28 |
| i30u98 | 4.33 | 3.81 | - | 90.39 | 10.80 | 26.02 | 316.93 | 14.87 |
| i40u98 | 4.13 | 3.58 | 254.21 | 92.20 | 10.37 | 26.67 | 265.45 | 14.67 |
| i50u98 | 4.57 | 3.37 | - | 91.65 | - | 27.53 | - | 18.67 |
| i100u98 | 7.50 | 3.97 | - | 99.79 | - | 26.54 | - | 100.98 |
| i200u98 | 16.22 | 5.64 | - | 95.89 | - | 27.57 | - | >900 |
| i500u98 | 22.98 | 4.82 | - | 126.97 | - | 46.51 | - | >900 |
| i1000u98 | 37.47 | 5.74 | - | 195.54 | - | >900 | - | >900 |
| i2000u98 | 45.69 | 7.39 | - | 223.81 | - | 685.17 | - | >900 |
| Bsolo | Minisat+ | PBS4 | Sat4jPB | |||||
|---|---|---|---|---|---|---|---|---|
| Instance | Default | BMOipb | Default | BMOipb | Default | BMOipb | Default | BMOipb |
| i0u98 | 5.38 | 23.81 | >900 | 5.97 | >900 | 116.45 | 3.97 | 11.72 |
| i10u98 | 25.33 | 23.63 | >900 | 5.91 | >900 | 46.26 | 3.63 | 11.67 |
| i20u98 | 91.13 | 23.37 | >900 | 7.77 | 735.54 | 59.11 | 18.05 | 13.82 |
| i30u98 | 104.18 | 23.25 | >900 | 7.83 | >900 | 78.88 | 19.10 | 13.74 |
| i40u98 | 92.27 | 23.13 | >900 | 22.52 | >900 | 111.40 | 48.42 | 26.48 |
| i50u98 | 103.73 | 23.00 | >900 | 25.91 | >900 | 64.49 | 48.35 | 25.98 |
| i100u98 | 321.46 | 22.40 | >900 | 19.22 | >900 | 78.81 | 41.09 | 54.86 |
| i200u98 | >900 | 22.19 | >900 | 39.78 | >900 | 70.86 | 69.53 | 116.05 |
| i500u98 | >900 | 23.61 | >900 | >900 | >900 | 91.17 | 158.52 | >900 |
| i1000u98 | >900 | 71.51 | >900 | >900 | >900 | >900 | >900 | >900 |
| i2000u98 | >900 | 90.15 | >900 | >900 | >900 | 242.10 | >900 | 40.54 |
Finally, we have further investigated IncWMaxSatz, which was the best performing solver. Figure 1 shows the scalability of the solver comparing the default performance of IncWMaxSatz with its performance using BMOrsc . (The plot includes results for additional instances, with each point corresponding to the average of 100 instances.) We should first note that the default IncWMaxSatz solver is by far more competitive than any other default MaxSAT or PB solver. Its performance is not even comparable with WMaxSatz, despite IncWMaxSatz being an extension of WMaxSatz. This is due to the features of IncWMaxSatz that make it particularly suitable for these instances, namely the incremental lower bound computation and the removal of inference rules that are particularly effective for solving random instances. Nonetheless, BMOrsc has been able to improve its performance and to reduce the impact of the size of the instance in the performance.

6 Conclusions
In many practical applications, one often needs to solve a hierarchy of optimization problems, where each optimization problem is specified in terms of a sequence of nested optimization problems. Examples in AI include specific optimization problems with preferences. Another concrete example is package management in software systems, where SAT, PB and MaxSAT find increasing application. It is possible to relate these optimization problems with multilevel (or hierarchical) optimization [Bracken and McGill, 1973; Candler and Norton, 1977; Colson et al., 2007], which finds a large number of practical applications.
This paper focus on Boolean Multilevel Optimization (BMO) and, by considering the concrete problem of package upgradeability in software systems, shows that existing solutions based on either MaxSAT or PB are in general inadequate. Moreover, the paper proposes two different algorithms, one that uses MaxSAT and another that uses PB, to show that dedicated algorithms for BMO can be orders of magnitude more efficient than the best off-the-shelf MaxSAT and PB solvers.
Despite the very promising results, a number of research directions can be outlined. One is to evaluate how the proposed algorithms scale for larger problem instances. Another one is to consider other computational problems in AI that can be cast as BMO, for example in the area of preferences and in the area of SAT-based optimization.
@inproceedings{ijcai2009p73,
title = {On Solving Boolean Multilevel Optimization Problemse},
author = {Argelich, Josep and Lynce, Inês and Silva, João P. Marques},
booktitle = {Proceedings of the Twenty-First International Joint Conference on
Artificial Intelligence, {IJCAI-09}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Craig Boutilier},
pages = {393--397},
year = {2009},
url = {https://ijcai.org/proceedings/2009/73},
}
TY - CPAPER TI - On Solving Boolean Multilevel Optimization Problemse AU - Argelich, Josep AU - Lynce, Inês AU - Silva, João P. Marques T2 - Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09 PB - International Joint Conferences on Artificial Intelligence PY - 2009 SP - 393 EP - 397 UR - https://ijcai.org/proceedings/2009/73 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: