The Exponentiated Subgradient Algorithm for Heuristic Boolean Programming
Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence. Pages 334-340.
© 2001 International Joint Conferences on Artificial Intelligence
Abstract
Boolean linear programs (BLPs) are ubiquitous in AI. Satisfiability testing, planning with resource constraints, and winner determination in combinatorial auctions are all examples of this type of problem. Although increasingly well-informed by work in OR, current AI research has tended to focus on specialized algorithms for each type of BLP task and has only loosely patterned new algorithms on effective methods from other tasks. In this paper we introduce a single general-purpose local search procedure that can be simultaneously applied to the entire range of BLP problems, without modification. Although one might suspect that a general-purpose algorithm might not perform as well as specialized algorithms, we find that this is not the case here. Our experiments show that our generic algorithm simultaneously achieves performance comparable with the state of the art in satisfiability search and winner determination in combinatorial auctions— two very different BLP problems. Our algorithm is simple, and combines an old idea from OR with recent ideas from AI.
- [Andersson et al., 2000] A. Andersson, M. Tenhunen, and F. Ygge. Integer programming for combinatorial auction winner determination. In Proceedings ICMAS-00, 2000.
- [Beacham et al., 2001] A. Beacham, X. Chen, J. Sillito, and P. van Beek. Constraint programming lessons learned from crossword puzzles. In Proc. Canadian AI Conf., 2001.
- [Bertsekas, 1995] D. Bertsekas. Nonlinear Optimization. Athena Scientific, 1995.
- [Davenport et al., 1994] A. Davenport, E. Tsang, C. Wang, and K. Zhu. GENET: A connectionist architecture for solving constraint satisfaction problems. In Proceedings AAAI-94, pages 325-330, 1994.
- [Everett, 1963] H. Everett. Generalized Lagrange multiplier method for solving problems of the optimal allocation of resources. Operations Res., 11:399-417, 1963.
- [Fisher, 1981] M. Fisher. The Lagrangian relaxation method for solving integer programming problems. Management Sci., 27:1-18, 1981.
- [Frank, 1997] J. Frank. Learning short-tem weights for GSAT. In Proceedings IJCAI-97, pages 384-391, 1997.
- [Fujishima et al., 1999] Y. Fujishima, K. Leyton-Brown, and Y. Shoham. Taming the computational complexity of com- binatorial auctions: optimal and approximate approaches. In Proceedings IJCAI-99, pages 548-553, 1999. IJCAI
- [Glover, 1989] F. Glover. Tabu search Part 1. ORSA Journal on Computing, 1(3):190-206, 1989.
- [Gomes, 2000] C. Gomes. Structure, duality, and random- ization: Common themes in AI and OR. In Proceedings AAAI-00, pages 1152-1158, 2000.
- [Held and Karp, 1970] M. Held and R. Karp. The travelling salesman problem and minimum spanning trees. Opera- tions Res., 18:1138-1162, 1970.
- [Holte, 2001] R. Holte. Combinatorial auctions, knapsack problems, and hill-climbing search. In Proceedings Cana- dian AI Conference, 2001.
- [Hooker et al., 1999] J. Hooker, G. Ottosson, E. Thorsteins- son, and H.-K. Kim. On integrating constraint propaga- tion and linear programming for combinatorial optimiza- tion. Proceedings AAAI-99, pages 136-141, 1999.
- [Hoos and Boutilier, 2000] H. Hoos and C. Boutilier. Solv- ing combinatorial auctions using stochastic local search. In Proceedings AAAI-00, pages 22-29, 2000.
- [Hoos and Stützle, 2000] H. Hoos and T. Stützle. Local search algorithms for SAT: An empirical evaluation. J. Automat. Reas., 24:421-481, 2000.
- [Hoos, 1999] H. Hoos. On the run-time behavior of stochas- tic local search algorithms for SAT. In Proceedings AAAI- 99, pages 661-666, 1999.
- [Kautz and Selman, 1996] H. Kautz and B. Selman. Pushing the envelope: Planning, propositional logic, and stochastic search. In Proceedings AAAI-96, pages 1194-1201, 1996.
- [Kautz and Walser, 1999] H. Kautz and J. Walser. State- space planning by integer optimization. Proceedings AAAI-99, pages 526-533, 1999.
- [Kivinen and Warmuth, 1997] J. Kivinen and M. Warmuth. Exponentiated gradient versus gradient descent for linear predictors. Infor. Comput., 132:1-63, 1997.
- [Larsson et al., 1996] T. Larsson, M. Patriksson, and A.-B. Stromberg. Conditional subgradient optimization-theory and applications. Euro. J. Oper. Res., 88:382-403, 1996.
- [Lau et al., 2000] H. Lau, A. Lim, and Q. Liu. Solving a supply chain optimization problem collaboratively. Pro- ceedings AAAI-00, pages 780-785, 2000.
- [Leyton-Brown et al., 2000] K. Leyton-Brown, M. Pearson, and Y. Shoham. Towards a universal test suite for combi- natorial auction algorithms. In Proc. EC-00, 2000.
- [Magazine and Oguz, 1984] M. Magazine and O. Oguz. A heuristic algorithm for the multidimensional knapsack problem. Euro. J. Oper. Res., 16:319-326, 1984.
- [Martin, 1999] R. Martin. Large Scale Linear and Integer Optimization. Kluwer, 1999.
- [McAllester et al., 1997] D. McAllester, B. Selman, and H. Kautz. Evidence for invariants in local search. In Pro- ceedings AAAI-97, pages 321-326, 1997.
- [Parkes and Walser, 1996] A. Parkes and J. Walser. Tuning local search for satisfiability testing. In Proceedings AAAI- 96, pages 356-362, 1996.
- [Resende and Feo, 1996] M. Resende and T. Feo. A GRASP for satisfiability. In Cliques, Coloring, and Satisfiability, DIMACS series v.26, pages 499-520. AMS, 1996.
- [Sandholm, 1999] T. Sandholm. An algorithm for optimal winner determination in combinatorial auctions. In Pro- ceedings IJCAI-99, pages 542-547, 1999. IJCAI
- [Schuurmans and Southey, 2000] D. Schuurmans and F. Southey. Local search characteristics of incomplete SAT procedures. In Proc. AAAI-00, pages 297-302, 2000.
- [Selman et al., 1994] B. Selman, H. Kautz, and B. Cohen. Noise strategies for improving local search. In Proceed- ings AAAI-94, pages 337-343, 1994.
- [Thornton and Sattar, 1999] J. Thornton and A. Sattar. On the behavior and application of constraint weighting. In Proceedings CP-99, pages 446-460, 1999.
- [Vossen et al., 1999] T. Vossen, M. Ball, A. Lotem, and D. Nau. On the use of integer programming models in AI planning. Proceedings IJCAI-99, pages 304-309, 1999. IJCAI
- [Voudouris and Tsang, 1996] C. Voudouris and E. Tsang. Partial constraint satisfaction problems and guided local search. In Proceedings PACT-96, pages 337-356, 1996.
- [Walser, 1999] J. Walser. Integer Optimization by Local Search. Springer-Verlag, 1999.
- [Wu and Wah, 2000] Z. Wu and W. Wah. An efficient global- search strategy in discrete Lagrangian methods for solv- ing hard satisfiability problems. In Proceedings AAAI-00, pages 310-315, 2000.
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
A Boolean linear program is a constrained optimization problem where one must choose a set of binary assignments to variables DC BD BN BMBMBMBN DC D2 to satisfy a given set of D1 linear inequalities CR BD A1 DC AK CQ BD BN BMBMBMBN CR D1 A1 DC AK CQ D1 while simultaneously optimizing a linear side objective CP A1 DC. Specifically, we consider BLP problems of the canonical form
Clearly this is just a special case of integer linear programming (ILP) commonly referred to as 0-1 integer programming. 1 Many important problems in AI can be naturally expressed as BLP problems; for example: finding a satisfying truth assignment for CNF propositional formulae (SAT)
A3 Work performed while at the University of Ottawa.
1 Although one could alternatively restrict the choice of values to CUBCBN BDCV we often find it more convenient to use CUA0BDBN B7BDCV.
Robert C. Holte A3
Department of Computing Science University of Alberta holte@cs.ualberta.ca
[Kautz and Selman, 1996], winner determination in combinatorial auctions (CA) [Sandholm, 1999; Fujishima et al., 1999], planning with resource constraints [Kautz and Walser, 1999; Vossen et al., 1999], and scheduling and configuration problems [Walser, 1999; Lau et al., 2000]. The two specific problems we will investigate in detail below are SAT and CA.
In general, BLP problems are hard in the worst case (NP-hard as optimization problems, NP-complete as decision problems). Nevertheless, they remain important problems and extensive research has been invested in improving the exponential running times of algorithms that guarantee optimal answers, developing heuristic methods that approximate optimal answers, and identifying tractable subcases and efficient algorithms for these subcases. There is a fundamental distinction between complete methods, which are guaranteed to terminate and produce an optimal solution to the problem, and incomplete methods, which make no such guarantees but nevertheless often produce good answers reasonably quickly. Most complete methods conduct a systematic search through the variable assignment space and use pruning rules and ordering heuristics to reduce the number of assignments visitedwhile preserving correctness. Incompletemethods on the other hand typically employ local search strategies that investigate a small neighborhood of a current variable assignment (by flipping one or a small number of assignments) and take greedy steps by evaluating neighbors under a heuristic evaluation function. Although complete methods might appear to be more principled, incomplete search methods have proven to be surprisingly effective in many domains, and have led to significant progress in some fields of research (most notably on SAT problems [Kautz and Selman, 1996] but more recently on CA problems as well [Hoos and Boutilier, 2000]).
In this paper we investigate incomplete local search methods for general BLP problems. Although impressive, most of the recent breakthroughs in incomplete local search have been achieved by tailoring methods to a reduced class of BLP problems. A good illustration of this point is the CA system of Hoos and Boutilier [2000] (Casanova) which is based on the SAT system of [Hoos, 1999; McAllester et al., 1997] (Novelty+), but is not the same algorithm (neither of these algorithms can be directly applied to the opposing problem). Another example is the WSAT(OIP) system of Walser [1999] which is an extension of WSAT [Selman et al., 1994] and achieves impressive results on general ILP problems, but nevertheless requires soft constraints to be manually created to replace a given optimization objective.
Our main contribution is the following: Although a variety of research communities in AI have investigated BLP problems and developed effective methods for certain cases, the current level of specialization might not be yielding the benefits that one might presume. To support this observation we introduce a generic local search algorithm that when applied to specialized forms of BLP (specifically SAT and CA) achieves performance that competes with the state of the art on these problems. Our algorithm is based on combining a simple idea from OR (subgradient optimization for Lagrangian relaxation) with a recent idea from AI, specifically from machine learning theory (multiplicative updates and exponentiated gradients). The conclusion we draw is that research on general purpose methods might still prove fruitful, and that known ideas in OR might still yield additional benefits in AI problems beyond those already acknowledged.
2 Background
Research on constrained optimization in AI has become increasingly well informed by extensive foundational work in OR [Gomes, 2000]. OR has investigated the specific task of ILP in greater depth than AI, and has tended to place more emphasis on developing general purpose methods applicable across the entire range of ILP problems. Complete methods in OR typically employ techniques such as branch and bound (using linear programming or Lagrangian relaxation), cutting planes, and branch and cut to prune away large portions of the assignment space in a systematic search [Martin, 1999]. This research has yielded sophisticated and highly optimized ILP solvers, such as the commercial CPLEX system, which although general purpose, performs very well on the specialized problems investigated in AI. In fact, it is still often unclear whether specialized AI algorithms perform better [Andersson et al., 2000].
Perhaps less well known to AI researchers is that beyond systematic search with branch and bound, the OR literature also contains a significant body of work on incomplete (heuristic) local search methods for approximately solving ILP problems; see for example [Magazine and Oguz, 1984; Larsson et al., 1996]. The simplest and most widespread of these ideas is to use subgradient optimization (which we describe below).
Our algorithm arises from the observation that the most recent strategies developed for the SAT problem have begun to use an analog of subgradient optimization as their core search strategy; in particular the DLM system of [Wu and Wah, 2000] and the SDF system of [Schuurmans and Southey, 2000] (see also [Thornton and Sattar, 1999; Frank, 1997; Davenport et al., 1994]). Interestingly, these are among the most effective methods for finding satisfying assignments for CNF formulae, and yet they appear to be recapitulating a forty year old idea in OR going back to [Everett, 1963]. Below we show that, indeed, a straightforward subgradient optimization approach (with just three basic improvements from AI) yields a state of the art SAT search strategy that competes with DLM (arguably the fastest SAT search procedure currently known).
Interestingly, the method we develop is not specialized to SAT problems in any way. In fact, the algorithm is a general purpose BLP search technique that can in principle be applied to any problem in this class. To demonstrate this point we apply the method without modification (beyond parameter setting) to CA problems and find that the method still performs well relative to the state of the art (although somewhat less impressively than on SAT problems). In this case we also find that the commercial CPLEX system performs very well and is perhaps the best of the methods that we investigated. Our results give us renewed interest in investigating general purpose algorithms for BLP that combine well understoodmethods fromOR with recent ideas fromAI.
3 The exponentiated subgradient algorithm
To explain our approach we first need to recap some basic concepts from constrained optimization theory. Consider the canonical BLP (1). For any constrained optimization problem of this form the Lagrangian is defined to be
where CR CX is the CXth row vector of the constraint matrix BV and DD CX is the real valued Lagrange multiplier associated with constraint CR CX . One can think of the multipliers DD CX simply as weights on the constraint violations DA CX BG BP CR CX A1 DC A0 CQ CX . Thus the Lagrangian can be thought of as a penalized objective function where for a given vector of constraint violation weights one could imagine minimizing the penalized objective B4DCBN DDB5. In this way, the Lagrangian turns a constrained optimization problem into an unconstrained optimization problem. In fact, the solutions of these unconstrained optimizations are used to define the dual function
The dual problem for (1) is then defined to be
Let BW A3 denote the maximum value of (4) and let A3 denote the minimum value of (1). Note that these are all just definitions. The reason that (4) can be considered to be a dual to (1) is given by the weak duality theorem, which asserts that BW A3 AK A3 [Bertsekas, 1995; Martin, 1999] (see Appendix A). Therefore, solving D1CXD2 DCBECUA0BDBNB7BDCV D2 B4DCBN DDB5 for any Lagrange multiplier vector DD AL BC gives a lower bound on the optimum value of the original problem (1). The best achievable lower bound is achieved by solving the dual problem of maximizing BWB4DDB5 subject to DD AL BC, yielding the optimal value BW A3 . The difference A3 A0BW A3 is called the duality gap. A fundamental theorem asserts that there is no duality gap for linear (or convex) programs with real valued variables [Bertsekas, 1995], so in principle these problems can be solved by dual methods alone. However, this is no longer the case once the variables are constrained to be integer or CUA0BDBN B7BDCV valued.
Although the dual problem cannot be used to directly solve (1) because of the existence of a possible duality gap, obtaining lower bounds on the optimal achievable value can still prove very useful in various search strategies, ranging from branch and bound to local search. Obviously there is a natural desire to maximize BWB4DDB5 by searching through Lagrange multiplier vectors for larger values. A natural way to proceed would be to start with a vector DD B4BCB5 , solve the unconstrained minimization problem (3), and then update DD B4BCB5 to obtain a better weight vector DD B4BDB5 , and so on. The issue is knowing how to update the weight vector DD B4BCB5 . This question is complicated by the fact that BWB4DDB5 is typically nondifferentiable, which leads to the last technical development we will consider: subgradient optimization.

Since BWB4DDB5 is always known to be concave [Bertsekas, 1995], a subgradient of BW (at a point DD) is given by any direction vector D9 such that BWB4DEB5 AK BWB4DDB5 B7 B4DE A0 DDB5 BQ D9 for all DE BE CA D1 . (Intuitively, a subgradient vector D9 gives the increasing direction of a plane that sits above BW but touches BW at DD, and hence can serve as a plausible search direction if one wishes to increase BW; see Figure 1.) Therefore, to update DD, all we need to do is find a subgradient direction. Here we can exploit an extremely useful fact: after minimizing B4DCBN DDB5 to obtain DC DD BP CPD6CVD1CXD2 DCBECUA0BDBNB7BDCV D2 CP A1 DC B7 DD BQ B4BVDC A0 CQB5 the resulting vector of residual constraint violation values DA DD BP BVDC DD A0CQ is always a subgradient of BW at DD [Bertsekas, 1995; Martin, 1999] (see Appendix B). So, in the end, despite the overbearing terminology, subgradient optimization is a fundamentally simple procedure:
Subgradient optimization: To improve the lower bound BWB4DDB5 on the optimal solution of the original problem, take a given vector of Lagrange multipliers DD, solve for a primal vector DC BE CUA0BDBNB7BDCV D2 that minimizes the Lagrangian B4DCBN DDB5, and update DD by adding a proportional amount of the residual constraint violations DA DD BP BVDC DD A0 CQ to DD (maintaining DD AL BC); i.e. use the rule DD BC BP DDB7ABDA DD . Note that this has the intuitive effect of increasing the weights on the violated constraints while decreasing weights on satisfied constraints. Although this update is not guaranteed to increase the value of BWB4DDB5 at every iteration, it is guaranteed to move DD closer to DD A3 BP CPD6CVD1CPDC DDALBC BWB4DDB5 for sufficiently small step-sizes AB [Bertsekas, 1995].
These ideas go back at least to [Everett, 1963], and have been applied with great success by Held and Karp [1970] and many since. Typically, subgradient optimization has been used as a technique for generating good lower bounds for branch and bound methods (where it is known as Lagrangian relaxation [Fisher, 1981]). However, subgradient optimization can also be used as a heuristic search method for approximately solving (1) in a very straightforwardway: at each iteration simply check if DC DD is feasible (i.e. satisfies BVDC DD AK CQ), and, if so, report CP A1 DC DD as a feasible objective value (keeping it if it is the best value reported so far); see for example [Magazine and Oguz, 1984; Larsson et al., 1996].
Interestingly, in the last few years this procedure has been inadvertently rediscovered in the AI literature. Specifically, in the field of incomplete local search methods for SAT, clause weighting schemes turn out to be using a form of subgradient optimization as their main control loop. These procedures work by fixing a profile of clause weights (Lagrange multipliers), greedily searching through variable assignment space for an assignment that minimizes a weighted score of clause violations (the Lagrangian), and then updating the clause weights by increasing them on unsatisfied clauses-all of which comprises a single subgradient optimization step. However, there are subtle differences between recent SAT procedures and the basic subgradient optimization approach outlined above. The DLM system of [Wu and Wah, 2000] explicitly uses a Lagrangian, but the multiplier updates follow a complex system of ad hoc calculations. 2 The SDF system of [Schuurmans and Southey, 2000] is simpler (albeit slower), but includes several details of uncertain significance. Nevertheless, the simplicity of this latter approach offers useful hypotheses for our current investigation.
Given the clear connection between recent SAT procedures and the traditional subgradient optimization technique in OR, we conduct a study of the deviations from the basic OR method so that we can identify the deviations which are truly beneficial. Our intent is to validate (or refute) the significance of some of the most recent ideas in the AI SAT literature.
Linear versus nonlinear penalties: One difference between recent SAT methods and subgradient optimization is that the SAT methods only penalize constraints with positive violations (by increasing the weight on these constraints), whereas standard subgradient optimization also rewards satisfied constraints (by reducing their weight proportionally to the degree of negative violation). To express this difference, consider an augmented Lagrangian which extends (2) by introducing a penalty function AI on constraint violations
The penalty functions we consider are the traditional linear penalty AIB4DAB5 BP DA and the "hinge" penalty
(Note that DA is an integer.) DLM and SDF can be interpreted as implicitly using a hinge penalty for dual updates on SAT problems. (However, SDF uses a different penalty for its primal search.) Intuitively, the hinge penalty has advantages because it does not favor increasing the satisfaction level of satisfied constraints above reducing the violations of unsatisfied constraints. Below we observe that the traditional linear penalty leads to poor performance on constraint satisfaction tasks and the AI methods have an advantage in this respect.
2 The Lagrangian used in [Wu and Wah, 2000] is also quite different from (2) because it includes a redundant copy of the constraint violations in the minimization objective. This prevents their Lagrangian from being easily generalized beyond SAT.
Unfortunately, the consequence of choosing a nonlinear penalty function is that finding a variable assignment DC which minimizes AI B4DCBN DDB5 is no longer tractable. To cope with this difficulty AI SAT solvers replace the global optimization process with a greedy local search (augmented with randomization). Therefore, they only follow a local subgradient direction in DD at each update. However, despite the locally optimal nature of the dual updates, the hinge penalty appears to retain an advantage over the linear penalty.
Multiplicative versus additive updates: The SDF procedure updates DD multiplicatively rather than additively, in an analogy to the work on multiplicative updates in machine learning theory [Kivinen and Warmuth, 1997]. A multiplicative update is naturally interpreted as following an exponentiated version of the subgradient; that is, instead of using the traditional additive update DD BC BP DDB7ABAIB4DAB5 one uses DD BC BP DDAB AIB4DAB5 , AB BQ BD, given the vector of penalized violation values AIB4DAB5. Below we compare both types of update and find that the multiplicative approach typically works better.
Weight smoothing: [Schuurmans and Southey, 2000] also introduce the idea of weight smoothing: after each update DD BC BP DDAB AIB4DAB5 the constraint weights are pulled back toward the population average DD BC BP BD D1 D1 CXBPBD DD BC CX using the rule DD BCBC BP AQDD BC B7 B4BD A0 AQB5DD BC , BC BO AQ AK BD. This has the effect of increasing the weights of frequently satisfied constraints without requiring them to be explicitly violated (which led to a noticeable improvement in SDF's performance).
Exponentiated subgradient optimization (ESG): The final procedure we propose follows a standard subgradient optimization search with three main augmentations: (1) we use the augmented Lagrangian AI with a hinge penalty rather than a linear penalty, (2) we use multiplicative rather than additive updates, and (3) we use weight smoothing to uniformize weights without requiring constraints to be explicitly violated. The parameters of the final procedure are AB, AQ, and a noise parameter AH (see Figure 2). 3 Below we compare four variants of the basic method: ESG CW , ESG CO (multiplicative updates with hinge and linear penalties respectively), and ASG CW , ASG CO (additive updates with each penalty). 4
The final ESG procedure differs from the SDF system of [Schuurmans and Southey, 2000] in many respects. The most important difference is that ESG can be applied to arbitrary BLP tasks, whereas SDF is applicable only to SAT problems. However, even if a generalized form of SDF could be devised, there would still remain minor differences: First, ESG uses a constant multiplier AB for dual updates, whereas SDF uses an adaptive multiplier that obtains a minimum difference Æ in B4DCBN DDB5 for some primal search direction. Second, SDF uses a different penalty in its primal and dual phases (exponential ESG AI B4ABBN AQBN AHB5 procedure Initialize DD BMBP BD and DC BMBP random CUA0BDBN B7BDCV D2 while solution not found and restart not reached Primal search: Use greedy local search from DC to find DC BC that locallyminimizes AI B4DC BC BN DDB5 (iff stuck, with probability AH take a randommove and continue); DA BC BMBP BVDC BC A0 CQ. BC B5 ; DD BCBC BMBP AQDD BC B7 B4BDA0 AQB5DD BC .
3 Software available at http://ai.uwaterloo.ca/AOdale/software/esg/.
4 Note that when using a linear penalty we employ an optimal primal search, but when using a hinge penalty we must resort to a greedy local search to approximately minimize B4DCBN DDB5.
Figure 2: ESG procedure
versus hinge) whereas ESG uses the same hinge penalty in both phases. Third, ESG smooths all of the weights, whereas SDF only smooths weights on satisfied constraints. Finally, ESG includes a small probability of stepping out of local minima during its primal search, whereas SDF employs a deterministic primal search. Overall, these simplifications allow for a more streamlined implementation for ESG that yields a significant reduction in CPU overhead per step, while simultaneously allowing application to more general tasks.
4 SAT experiments
We consider applying the BLP techniques to SAT problems. An instance of SAT is specified by a set of clauses CR BP CUCR CX CV D1 CXBPBD , where each clause CR CX is a disjunction of CZ CX literals, and each literal denotes whether an assignment of "true" or "false" is required of a variable DC CY . The goal is to find an assignment of truth values to variables such that every clause is satisfied on at least one literal. In our framework, an instance of SAT can be equivalently represented by the BLP
where BC and BE are vectors of zeros and twos respectively, and
An assignment of B7BD to variable DC CY denotes "true", and an assignment of A0BD denotes "false". The idea behind this representation is that a clause CR CX is encoded by a row vector CR CX in BV which has CZ CX nonzero entries corresponding to the variables occurring in CR CX , along with their signs. A constraint is violated only when the CUA0BDBN B7BDCV assignment to DC agrees with the coefficients in CR CX on every nonzero entry, yielding a row sum of CR CX A1DC BP CZ CX . If a single sign is flipped then the row sum drops by 2 and the constraint becomes satisfied.
Note that the zero vector means that the minimization component of this problem is trivialized. Nevertheless it remains a hard constraint satisfaction problem. The trivialized objective causes no undue difficulty to the methods introduced above, and therefore the BLP formulation allows us to accommodate both constraint satisfaction and constrained optimization problems in a common framework (albeit in a more restricted way than [Hooker et al., 1999]).
For this problem we compared the subgradient optimization techniques ESG/ASG against state of the art local search methods: DLM, SDF, Novelty+, Novelty, WSAT, GSAT and HSAT. However, for reasons of space we report results only for DLM, SDF, and Novelty+, which represent the best of the last two generations of local search methods for SAT. 5 We ran these systems on a collection of (satisfiable) benchmark problems from the SATLIB repository. 6 Here the SAT solvers were run on their standard CNF input representations whereas the BLP solvers were run on BLP transformed versions of the SAT problems, as given above. (Although alternative encodings of SAT problems could affect the performance of BLP solvers [Beacham et al., 2001] we find that the simple transformation described above yields reasonable results.)
| Avg. Steps | Est. Opt. Steps | Fail % | Opt. sec | |
|---|---|---|---|---|
| uf50 | (100 problems) | |||
| CPLEX (10 probs) | 49 | na | 0 | .186 |
| ASG CO B4BMBDBEBN BCBN BMBCBEB5 | 500,000 | na | 100 | na |
| ESG CO B4BEBMBCBN BMBCBHBN BMBDBEBHB5 | 178,900 | 143,030 | 25 | 43.3 |
| ASG CW B4BMBDBEBN BCBN BMBCBEB5 | 1,194 | 359 | 0.3 | .027 |
| ESG CW B4BDBMBEBN BMBLBLBN BMBCBCBCBHB5 | 215 | 187 | 0 | .0009 |
| uf100 | (1000 problems) | |||
| CPLEX (10 probs) | 727 | na | 0 | 6.68 |
| ASG CW B4BMBEBN BCBN BMBCBEB5 | 3,670 | 2,170 | 1.3 | 0.26 |
| ESG CW B4BDBMBDBHBN BMBCBDBN BMBCBCBEB5 | 952 | 839 | 0 | .004 |
| uf150 | (100 problems) | |||
| CPLEX (10 probs) | 13,808 | na | 0 | 275.2 |
| ASG CW B4BMBHBN BCBN BMBCBEB5 | 14,290 | 6,975 | 1.1 | .071 |
| ESG CW B4BDBMBDBHBN BMBCBDBN BMBCBCBDB5 | 2,625 | 2,221 | 0 | .011 |
To measure the performance of these systems we recorded wall clock time on a PIII 750MHz processor, average number of primal search steps ("flips") needed to reach a solution, and the proportion of problems not solved within 500K steps (5M on bw large.c). To avoid the need to tune every method for a restart threshold we employed the strategy of [Schuurmans and Southey, 2000] and ran each method 100 times on every problem to record the distribution of solution times, and used this to estimate the minimum expected number of search steps required under an optimal restart scheme for the distribution [Parkes and Walser, 1996]. The remaining parameters of each method were manually tuned for every problem set. The parameters considered were: Novelty+(walk, noise), DLM(16 tunable parameters), SDFB4ÆBN BDA0AQB5, ESG AI B4ABBN BDA0AQBN AHB5 and ASG AI B4ABBN BDA0AQBN AHB5. 7
5 Implementations of these methods are available at ai.uwaterloo.ca/AOdale, www.satlib.org, and manip.crhc.uiuc.edu.
6 SATLIB is at www.satlib.org. We used three classes of problems in our experiments. The uf problems are randomly generated 3CNF formulae that are generated at the phase transition ratio of 4.3 clauses to variables. (These formulae have roughly a 50% chance of being satisfiable, but uf contains only verified satisfiable instances.) The flat problems are SAT encoded instances of hard random graph coloring problems. The remaining problems are derived from AI planning problems and the "all interval series" problem.
7 For the large random collections (Tables 1 and 2: flat100uf250) the methods were tuned by running on 10 arbitrary problems. Performance was then measured on the complete collection. Novelty+ parameters were tuned from the published values of [Hoos and St¨utzle, 2000]. DLMwas tuned by running each of the 5 default parameter sets available at manip.crhc.uiuc.edu and choosing the best.
| Avg. | Est. Opt. | Fail | Opt. | |
|---|---|---|---|---|
| Steps % sec | ||||
| ais8 | Steps | (1 problem) | ||
| Novelty+B4BMBGBN BMBCBDB5 | 183,585 | 20,900 | 9 | .078 |
| SDFB4BMBCBCBCBGBN BMBCBCBHB5 | 4,490 | 4,419 | 0 | .083 |
| DLMB4pars1B5 | 4,678 | 4,460 | 0 | .044 |
| ESG CW B4BDBMBLBN BMBCBCBDBN BMBCBCBCBIB5 | 4,956 | 4,039 | 0 | .043 |
| ais10 | (1 problem) | |||
| Novelty+B4BMBFBN BMBCBDB5 | 434,469 | 340,700 | 79 | 1.64 |
| SDFB4BMBCBCBCBDBFBN BMBCBCBHB5 | 15,000 | 13,941 | 0 | .40 |
| DLMB4pars4B5 | 18,420 | 14,306 | 0 | .11 |
| ESG CW B4BDBMBLBN BMBCBCBDBN BMBCBCBCBGB5 | 15,732 | 15,182 | 0 | .23 |
| ais12 | (1 problem) | |||
| Novelty+B4BMBHBN BMBCBDB5 | 496,536 | 496,536 | 99 | 3.0 |
| SDFB4BMBCBCBCBDBN BMBCBCBHB5 | 132,021 | 97,600 | 1 | 3.6 |
| DLMB4pars1B5 | 165,904 | 165,904 | 3 | 2.5 |
| ESG CW B4BDBMBKBN BMBCBCBDBN BMBCBCBCBHB5 | 115,836 | 85,252 | 10 | 1.7 |
| bw large.a | (1 problem) | |||
| Novelty+B4BMBGBN BMBCBDB5 | 9,945 | 8,366 | 0 | .025 |
| SDFB4BMBCBCBCBDBN BMBCBCBHB5 | 3,012 | 3,012 | 0 | .057 |
| DLMB4pars4B5 | 3,712 | 3,701 | 0 | .028 |
| ESG CW B4BFBN BMBCBCBHBN BMBCBCBDBHB5 | 2,594 | 2,556 | 0 | .022 |
| bw large.b | (1 problem) | |||
| Novelty+B4BMBGBN BMBCBDB5 | 210,206 | 210,206 | 12 | .82 |
| SDFB4BMBCBCBCBCBHBN BMBCBCBHB5 | 33,442 | 33,255 | 0 | 1.30 |
| DLMB4pars4B5 | 44,361 | 39,216 | 0 | .34 |
| ESG CW B4BDBMBGBN BMBCBDBN BMBCBCBCBHB5 | 33,750 | 26,159 | 0 | .40 |
| bw large.c | (1 problem) | |||
| Novelty+B4BMBEBN BMBCBDB5 | 3,472,770 | 1,350,620 | 52 | 7 |
| SDFB4BMBCBCBCBCBEBN BMBCBCBHB5 | 3,478,770 | 3,478,770 | 48 | 313 |
| DLMB4pars4B5 | 3,129,450 | 2,282,900 | 32 | 41 |
| ESG CW B4BDBMBGBN BMBCBDBN BMBCBCBCBHB5 | 1,386,050 | 875,104 | 5 | 39 |
| logistics.c | (1 problem) | |||
| Novelty+B4BMBGBN BMBCBDB5 | 127,049 | 126,795 | 1 | .38 |
| SDFB4BMBCBCBCBCBCBLBN BMBCBCBHB5 | 15,939 | 15,939 | 0 | 1.40 |
| DLMB4pars4B5 | 12,101 | 11,805 | 0 | .13 |
| ESG CW B4BEBMBEBN BMBCBDBN BMBCBCBEBHB5 | 8,962 | 8,920 | 0 | .15 |
| flat100 | (100 problems) | |||
| Novelty+B4BMBIBN BMBCBDB5 | 17,266 | 12,914 | .03 | .019 |
| SDFB4BMBCBCBCBEBN BMBCBCBHB5 | 7,207 | 6,478 | 0 | .074 |
| DLMB4pars4B5 | 9,571 | 8,314 | 0 | .022 |
| ESG CW B4BDBMBDBN BMBCBDBN BMBCBCBDBHB5 | 7,709 | 6,779 | 0 | .022 |
| flat200 | (100 problems) | |||
| Novelty+B4BMBIBN BMBCBDB5 | 238,663 | 218,274 | 27 | .34 |
| SDFB4BMBCBCBCBDBN BMBCBCBHB5 | 142,277 | 115,440 | 7 | 1.56 |
| DLMB4pars4B5 | 280,401 | 242,439 | 31 | .77 |
| ESG CW B4BDBMBCBDBN BMBCBDBN BMBCBCBEBHB5 | 175,721 | 134,367 | 14 | .47 |
| uf150 | (100 problems) | |||
| Novelty+B4BMBIBN BMBCBDB5 | 6,042 | 3,970 | 0 | .008 |
| SDFB4BMBCBCBCBIBHBN BMBCBCBHB5 | 3,151 | 2,262 | 0 | .023 |
| DLMB4pars4B5 | 3,263 | 2,455 | 0 | .008 |
| ESG CW B4BDBMBDBHBN BMBCBDBN BMBCBCBDB5 | 2,625 | 2,221 | 0 | .011 |
| uf200 | (100 problems) | |||
| Novelty+B4BMBIBN BMBCBDB5 | 25,917 | 22,214 | 1.8 | .048 |
| SDFB4BMBCBCBCBFBN BMBCBCBHB5 | 14,484 | 11,304 | .4 | .134 |
| DLMB4pars4B5 | 13,316 | 9,020 | .1 | .030 |
| ESG CW B4BDBMBEBFBN BMBCBDBN BMBCBCBFB5 | 10,583 | 7,936 | .2 | .039 |
| uf250 | (100 problems) | |||
| Novelty+B4BMBIBN BMBCBDB5 | 27,730 | 24,795 | 1.8 | .055 |
| SDFB4BMBCBCBCBEBN BMBCBCBHB5 | 18,404 | 13,626 | .1 | .177 |
| DLMB4pars4B5 | 22,686 | 12,387 | .2 | .042 |
| ESG CW B4BDBMBDBHBN BMBCBDBN BMBCBCBFB5 | 13,486 | 10,648 | .1 | .054 |
Table 1 compares the different BLP procedures on random problems from SATLIB. The most salient feature of these results is that the linear penalty performs poorly (as anticipated). Here, the traditional ASG CO method was unable to solve any problems in the allotted steps. Table 1 also shows that multiplicative updates (ESG) were generally superior to additive updates (ASG) regardless of the penalty function used (at least on random SAT problems). Although details are omitted, we have also found that some smoothing (BD A0 AQ AK BCBMBCBD) usually improves the performance of ESG but is generally less beneficial for ASG. CPLEX generally performs poorly in these experiments.
Table 2 shows the results of a larger scale comparison between ESG CW and state of the art local search methods for SAT. These results show that ESG CW tends to finds solutions in fewer primal search steps (flips) than other procedures. However, ESG CW 's time per flip is about 1.5 to 2 times higher than DLM and about 2 to 4 times higher than Novelty+, which means that its overall run time is only comparable to these methods. Nevertheless, ESG CW , DLM and SDF obtain a large reduction in search steps over Novelty+ on the structured ais and planning problems (with the notable exception of bw large.c). As a result, DLM and ESG CW both tend to demonstrate better run times than Novelty+ on these problems. All three methods (Novelty+, DLM and ESG CW ) demonstrate similar run times on the random uf and flat problems.
Note that none of these SAT procedures (other than ESG/ASG and CPLEX) can be applied to general BLP problems without modification.
5 CA experiments
The second problem we considered is optimal winner determination in combinatorial auctions (CA). This problem introduces a nontrivial optimization objective that is not present in SAT. However, the subgradient optimization approach remains applicable, and we can apply the same ESG/ASG methods to this task without modifying them in any way. (Nevertheless, we did conduct some implementation specializations to gain improvements in CPU times on SAT problems.) The CA problem has been much less studied in the AI literature, but interest in the problem is growing rapidly.
An instance of the optimal winner determination problem in combinatorial auctions (CA) is given by a set of items CR BP CUCR CX CV D1 CXBPBD with available quantities D5 BP CUD5 CX CV D1 CXBPBD , and a set of bids DE BP CUDE CY CV D2 CYBPBD which offer amounts DA BP CUDA CY CV D2 CYBPBD for a specified subset of items. We can represent the bid requests in a constraint matrix BV where
The problem then is to find a set of bids that maximizes the total revenue subject to the constraint that none of the item quantities are exceeded. If DE CY BE CUBCBN BDCV this problem can be expressed as the BLP
However it is not in our canonical CUA0BDBNB7BDCV form. To transform it to the canonical form we use the substitutions DC BP
BEDE A0 BD, CP BP A0DABPBE and CQ BP BED5 A0 BVBD. The minimum solution to the transformed version of this problem can then be converted back to a maximum solution of the original CA.
For this task we compared the ESG/ASG algorithms to CPLEX and Casanova [Hoos and Boutilier, 2000], a local search method loosely based on Novelty+. 8 The problems we tested on were generated by the CATS suite of CA problem generators [Leyton-Brown et al., 2000], which are intended to model realistic problems. However, our results indicate that these tend to be systematically easy problems for all the methods we tested, so we also tested on earlier artificial problem generators from the literature [Sandholm, 1999; Fujishima et al., 1999]. Some of these earlier generators were shown to be vulnerable to trivial algorithms [Andersson et al., 2000] but some still appear to generate hard problems. However, to push the envelope of difficulty further, we also encoded several hard SAT problems as combinatorial auctions by using an efficient polynomial (quadratic) reduction from SAT to CA. Unfortunately, space limitations preclude a detailed description of this reduction, but our results show that these converted SAT problems are by far the most difficult available at a given problem size.
To measure the performance of the various methods, we first solved all of the problems using CPLEX and then ran the local search methods until they found an optimal solution or timed out. Although we acknowledge that this method of reporting ignores the anytime performance of the various methods, it seems sufficient for our purposes. To give some indication of anytime behavior, we recorded the fraction of optimality achieved by the local search methods in cases where they failed to solve the problem within the allotted time.
Table 3 shows a comparison of the different subgradient optimization procedures on one of the CATS problem classes. These results show that the linear penalty is once again weaker than the hinge (but to a lesser extent than on SAT problems). Interestingly, additive updates appear to work as well as multiplicative updates on these problems (although the performance of ASG begins to weaken on harder constraint systems such as those encountered in Table 5).
Table 4 shows the results of a larger comparison between ESG/ASG, Casanova and CPLEX on the CATS problems and an artificial problem. These results show that there is very little reason not to use CPLEX to solve these problems in practice. 9 CPLEX, of course, also proves that its answers are optimal, unlike local search. Nevertheless, the results show that ESG CW and ASG CW are roughly competitive with Casanova, which is a specialized local search technique for this task.
8 Casanova is specialized to single unit CA problems (D5 BP BD), so we restrict attention to this class. However, ESG/ASG and CPLEX can be applied to multi-unit CA problems without modification, and hence are more general. CPLEX was run with the parameter settings reported in [Andersson et al., 2000]. Casanova uses the same parameters as Novelty+, walk and noise.
9 The CPLEX timings show time to first discover the optimum, not prove that it is indeed optimal. Also note that even though "steps" are recorded for each of the methods, they are incomparable numbers. Each method uses very different types of steps (unlike the previous SAT comparison in terms of "flips") and are reported only to show method-specific difficulty.
Note that the large score proportions obtained by all methods when they fail to find the optimal solution follows from the fact that even simple hill-climbing strategies tend to find near optimal solutions in a single pass [Holte, 2001]. It appears that most of the difficulty in solving these problems is in gaining the last percentage point of optimality.
Finally, Table 5 shows that Casanova demonstrates inferior performance on the more difficult SATAXCA encoded problems. Nevertheless all methods appear to be challenged by these problems. Interestingly, CPLEX slows down by a factor of 400 when transforming from the direct SAT encoding of Section 4 to the SATAXCA encoding used here. By comparison the ESG method slows down by a factor of 20K.
6 Conclusion
Although we do not claim that the methods we have introduced exhibit the absolute best performance on SAT or CA problems, they nevertheless compete very well with the state of the art techniques on both types of problem. Therefore, we feel that the simple Lagrangian approach introduced here might offer a useful starting point for future investigation beyond the myriad WalkSAT variants currently being pursued in AI. Among several directions for future work are to investigate other general search ideas from the OR literature, such as tabu search [Glover, 1989], and compare to other local search methods for ILP problems [Resende and Feo, 1996; Voudouris and Tsang, 1996] (which do not appear to be competitive on SAT problems, but still offer interesting perspectives on ILP problems in general).
A Weak duality
It is insightful to see why BWB4DDB5 AK A3 for all DD AL BC. In fact, it is almost immediately obvious: Note that for any DD AL BC we have
and hence BWB4DDB5 AK A3 . From this one can see that the constraint DD AL BC is imposed precisely to ensure a lower bound on A3 .
B Subgradient direction
It is also easy to see that the vector of constraint violation values DA DD BP BVDC DD A0 CQ (where DC DD BP CPD6CV D1CXD2 DCBECUA0BDBNB7BDCV D2 B4DCBN DDB5) must yield a subgradient of BW at DD:
Acknowledgments
Research supported by NSERC and CITO. Thanks to Holger Hoos and Craig Boutilier for helpful comments and providing access to Casanova. Thanks also to Peter van Beek and the anonymous referees for many helpful suggestions. The assistance of Istv´an Hern´adv¨olgyi is also warmly appreciated.
| Avg. sec | Avg. Steps | Fail % | % Opt. | |
|---|---|---|---|---|
| CATS-regions | (100 problems) | |||
| ESG CW B4BDBMBLBN BMBDBN BMBCBDB5 | 7.2 | 1416 | 4.1 | 99.93 |
| ASG CW B4BMBCBGBHBN BCBN BMBCBDB5 | 12.7 | 2457 | 7.9 | 99.86 |
| ESG CO B4BDBMBFBN BMBLBN BMBCBDB5 | 64.7 | 7948 | 77 | 88.11 |
| ASG CO B4BMBCBDBN BCBN BMBCBDB5 | 48.1 | 9305 | 90 | 93.96 |
| Avg. sec | Avg. Steps | Fail % | % Opt. | |
|---|---|---|---|---|
| CATS-regions | (100 problems) | |||
| CPLEX | 6.7 | 64117 | 0 | 100 |
| CasanovaB4BMBHBN BMBDBJB5 | 4.2 | 1404 | 3.4 | 99.95 |
| ESG CW B4BDBMBLBN BMBDBN BMBCBDB5 | 7.2 | 1416 | 4.1 | 99.93 |
| ASG CW B4BMBCBGBHBN BCBN BMBCBDB5 | 12.7 | 2457 | 7.9 | 99.86 |
| CATS-arbitrary | (100 problems) | |||
| CPLEX | 22 | 9510 | 0 | 100 |
| CasanovaB4BMBCBGBN BMBDBEB5 | 9 | 2902 | 0.47 | 99.98 |
| ESG CW B4BEBMBDBN BMBCBHBN BMBHB5 | 33 | 7506 | 4.21 | 99.95 |
| ASG CW B4BMBCBGBN BCBN BMBCBDB5 | 30 | 6492 | 4.87 | 99.87 |
| CATS-matching | (100 problems) | |||
| CPLEX | 1.30 | 499 | 0 | 100 |
| CasanovaB4BMBFBN BMBDBJB5 | .17 | 109 | 0 | 100 |
| ESG CW B4BDBMBJBN BMBCBHBN BCB5 | .16 | 215 | 0 | 100 |
| ASG CW B4BMBLBN BCBN BMBKB5 | .73 | 1248 | 0 | 100 |
| CATS-paths | (100 problems) | |||
| CPLEX | 25 | 1 | 0 | 100 |
| CasanovaB4BMBHBN BMBDBHB5 | 26 | 49 | 0 | 100 |
| ESG CW B4BDBMBFBN BMBCBHBN BMBGB5 | 28 | 2679 | 2.5 | 99.99 |
| ASG CW B4BMBCBDBN BCBN BMBDBHB5 | 75 | 5501 | 6.8 | 99.96 |
| CATS-scheduling | (100 problems) | |||
| CPLEX | 15 | 1426 | 0 | 100 |
| CasanovaB4BMBHBN BMBCBGB5 | 44 | 7017 | 19.9 | 99.87 |
| ESG CW B4BDBMBFBHBN BMBCBHBN BMBCBDBHB5 | 65 | 11737 | 41 | 99.68 |
| ASG CW B4BMBCBDBHBN BCBN BMBDBEBHB5 | 58 | 12925 | 44.2 | 99.51 |
| Decay-200-200-.75 | (100 problems) | |||
| CPLEX | 1.1 | 2014 | 0 | 100 |
| CasanovaB4BMBHBN BMBDBJB5 | 0.5 | 2899 | 2 | 99.97 |
| ESG CW B4BDBGBMBHBN BMBCBGBHBN BMBGBHB5 | 1.8 | 24466 | 96.3 | 96.91 |
| ASG CW B4BMBCBGBN BCBN BMBHB5 | 1.7 | 24939 | 99.6 | 91.49 |
| Avg. sec | Avg. Steps | Fail % | % Opt. | |
|---|---|---|---|---|
| SAT(uf50)AXCA | (10 problems) | |||
| CPLEX | 42 | 754 | 0 | 100 |
| CasanovaB4BMBHBN BMBDBDB5 | 468 | 9.6A2BDBC BI | 90 | 99.36 |
| ESG CW B4BFBCBN BMBCBHBN BMBDB5 | 31 | 1.7A2BDBC BI | 10 | 99.95 |
| ASG CW B4BHBN BCBN BMBHB5 | 173 | 8.6A2BDBC BI | 80 | 99.40 |
| SAT(uf75)AXCA | (10 problems) | |||
| CPLEX | 666 | 5614 | 0 | 100 |
| CasanovaB4BMBHBN BMBDBDB5 | 800 | 1.0A2BDBC BJ | 100 | 98.46 |
| ESG CW B4BGBDBN BMBCBHBN BMBDB5 | 165 | 6.2A2BDBC BI | 60 | 99.81 |
| ASG CW B4BDBCBN BCBN BMBHB5 | 291 | 1.0A2BDBC BJ | 100 | 99.17 |
@inproceedings{ijcai2001p48,
title = {The Exponentiated Subgradient Algorithm for Heuristic Boolean Programming},
author = {Schuurmans, Dale and Southey, Finnegan and Holte, Robert C.},
booktitle = {Proceedings of the Seventeenth International Joint Conference on
Artificial Intelligence, {IJCAI-01}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Bernhard Nebel},
pages = {334--340},
year = {2001},
url = {https://ijcai.org/proceedings/2001/48},
}
TY - CPAPER TI - The Exponentiated Subgradient Algorithm for Heuristic Boolean Programming AU - Schuurmans, Dale AU - Southey, Finnegan AU - Holte, Robert C. T2 - Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI-01 PB - International Joint Conferences on Artificial Intelligence PY - 2001 SP - 334 EP - 340 UR - https://ijcai.org/proceedings/2001/48 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: