FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:   || 2 |

«Abstract. We propose to enable branch-and-propagate constraint solvers to publish their search frontiers. This is quite straightforward to implement, ...»

-- [ Page 1 ] --

Towards Component-Based Cooperative

Constraint Solving

Peter Zoeteweij

Delft University of Technology, fac. EEMCS,

P.O. Box 5031, 2600 GA Delft, The Netherlands

e-mail: p.zoeteweij@ewi.tudelft.nl

Abstract. We propose to enable branch-and-propagate constraint solvers to publish their search frontiers. This is quite straightforward to

implement, and transforms an otherwise closed system into a versatile

software component, opening up new possibilities for realizing cooperative constraint solving. With the proposed mechanism, several solver cooperation schemes that would otherwise require re-engineering solvers, leading to ad-hoc solutions, become a matter of component-based software engineering, leading to reusable solutions instead. We report our experience with using this technique for implementing parallel search.

Being a homogeneous cooperation scheme, this is of limited relevance from a solver cooperation perspective, but being aimed solely at reducing the turn-around time of constraint solving, it is ideal for demonstrating that our approach leads to efficient solvers. Departing from this starting point, we discuss the perspectives for implementing more interesting cooperation schemes, some of which can be classified as hybrid solvers.

1 Introduction Solver cooperation is a key technique for the efficient solving of constraint satisfaction problems that model combinatorial (optimization) problems that occur in practice. For this reason, many existing constraint solving tools apply solving procedures that can be characterized as solver cooperations, but usually, these procedures are hard-wired in the implementation. Consequently, the possibilities for experimenting with alternative cooperation schemes are limited: it is generally not possible to plug in additional or different solvers, or to change the cooperation without re-engineering the tools.

To overcome this limitation, several frameworks for solver cooperation have been developed, see e.g. [2, 3]. Such frameworks typically allow that solvers can be combined according to arbitrary cooperation schemes, but another problem is that existing constraint solvers do not lend themselves easily for cooperation with other solvers. This is the problem that we address in this paper. We propose a simple extension of the functionality of branch-and-propagate constraint solvers, namely publishing the search frontier, which will improve the ability of such solvers to cooperate with other solvers. Our approach is complementary to that of developing cooperation frameworks: for solver cooperation we need both the enabling framework and the solvers that can be used inside those frameworks.

We implemented the idea of publishing the search frontier in OpenSolver [7], a configurable branch-and-propagate tree search engine, where it is used for parallel search [8]. In this particular application, the search frontier is published by the parallel solvers when a time-out elapses before the search finishes. Then the nodes are re-distributed among the solvers in a master–slave fashion. The time-out mechanism allows us to tune the communication overhead, and provides an implicit load-balancing. The first of these two concerns, the amount of work that is done in between (expensive) communication operations, is also relevant for implementing solver cooperation: if the cooperating solvers spend most of their time waiting for I/O operations, the cooperation may become inefficient. This is particularly relevant if instead of a hard-wired solution, we are using a cooperation framework, or aim for a component-based implementation otherwise.

While parallel search is of limited interest from a solver cooperation point of view, it is a very demanding application from an efficiency perspective. Since we have been able to construct an efficient parallel solver based on publishing the search frontier, we expect that it also allows for the efficient implementation of more interesting solver cooperation schemes. In addition, such implementations can be highly modular: our parallel solver is a network of processes that communicate subproblems, based on a textual representation, via standard I/O primitives. This “flow of subproblems” view suggests a component-based implementation of solver cooperations, where new solvers can easily be inserted the network of cooperating solvers.

The remainder of this paper is organized as follows. In Sect. 2 we introduce OpenSolver, and in Sect. 3 we describe our experiments with parallel search.

Section 4 is the heart of the paper. Here we discuss the possibilities for implementing proper solver cooperation schemes based on exposing the search frontier of a branch-and-propagate constraint solver. In addition to enabling solver cooperation, the proposed mechanism has further possibilities. Two of these are discussed in Sect. 5. We conclude in Sect. 6.

2 OpenSolver

OpenSolver [7] is a configurable branch-and-propagate tree search engine, implemented as an autonomous application, whose functionality is determined by software plug-ins. These plug-ins come in a number of categories, corresponding

to various aspects of branch-and-propagate constraint solving:

domain types that implement the domains of variables, – reduction operators that reduce and split these domains, – schedulers of reduction operators, – containers of nodes of the search tree, – selectors that make a selection among the nodes stored in containers, – – annotations that decorate the nodes of the search tree with extra information, to be used by plug-ins in some of the other categories, – evaluators of nodes of the search tree; these determine whether a node of the search tree is a solution, failure, or internal node.

OpenSolver is configured for solving a particular CSP through a script in a simple configuration language, and example of which is shown in Figure 1. Configuration VARIABLE x IS IntegerInterval {1..100000};

VARIABLE y IS IntegerInterval {1..100000};

VARIABLE z IS IntegerInterval {1..100000};

VARIABLE obj IS IntegerInterval {};

AUX aux_x3 IS IntegerInterval {};

AUX aux_y2 IS IntegerInterval {};

AUX aux_z3 IS IntegerInterval {};

AUX aux_x1y1 IS IntegerInterval {};

DRF IIARule { aux_x3^1 * (1) = x^3 };

DRF IIARule { aux_y2^1 * (1) = y^2 };

DRF IIARule { aux_z3^1 * (1) = z^3 };

DRF IIARule { aux_x1y1^1 * (1) = y * x };

DRF IIARule { x^3 * (1) = aux_x3 };

DRF IIARule { y^2 * (1) = aux_y2 };

DRF IIARule { z^3 * (1) = aux_z3 };

DRF IIARule { y^1 * (x) = aux_x1y1 };

DRF IIARule { x^1 * (y) = aux_x1y1 };

DRF IIARule { aux_x3^1 * (1) = -1*aux_y2 + 1*aux_z3 };

DRF IIARule { aux_y2^1 * (1) = -1*aux_x3 + 1*aux_z3 };

DRF IIARule { aux_z3^1 * (-1) = -1*aux_x3 + -1*aux_y2 };

DRF IIARule { obj^1 * (1) = 2*aux_x1y1 + -1*z };

DRF IIARule { aux_x1y1^1 * (-2) = -1*obj + -1*z };

DRF IIARule { z^1 * (1) = -1*obj + 2*aux_x1y1 };

DRF Optimize { +obj };

DRF RoundRobin { 0, x, y, z, obj };

SCHEDULER ChangeScheduler { schedule = { 1,2,9,4,0,2,10,5,0,1,11,6,3,12,13,7,8,3,14,15 } };

Fig. 1. Example of an OpenSolver configuration script

scripts contain commands for activating plug-ins. This way, they specify both a CSP, and the solver for solving it: the VARIABLE (and AUX) commands in Figure 1 introduce the variables and their domains. The DRF commands introduce the reduction operators (including branching operators, here RoundRobin) that enforce the constraints. These are the only commands that add plug-in instances.

The other commands replace currently active plug-ins. In the example we replace the default scheduler with one that takes the hierarchical dependencies between the reduction operators (instances of IIARule, for integer interval arithmetic rule) into account.

The state of OpenSolver consists of three sets of nodes of the search tree, implemented by container plug-ins (see Figure 2, and Sect. 4.3). The leftmost of these three sets is the search frontier [5], i.e., the set of nodes of the search tree that require further exploration by constraint propagation and branching.

–  –  –

In addition to the seven categories of plug-ins enumerated at the beginning of this section, there is a special, eighth category of coordination-layer plug-ins that steer the execution of the solving algorithms, and allow for communication with the environment (it allows for various forms of exogenous, or external, coordination of the solver, see [8]). There is always exactly one coordination layer plug-in active. OpenSolver executes a command loop, where it continually asks this plug-in what to do next. Examples of commands that can be given are – interpret a configuration script, – apply the scheduler of reduction operators to perform constraint propagation in each of the nodes of the search tree in the middle set of Figure 2, – flush the nodes of the search tree: this generates a configuration script for every subproblem that still must be explored, and for all solutions that have been found so far. The data structures for these nodes are deallocated.

The latter command is important for implementing the time-out mechanism that forms the basis of the parallel solver of the next section.

3 Parallel Search For parallel search, we implemented a special coordination layer plug-in that reads configuration scripts from standard input. Then it issues the sequence of commands that makes the solver perform a regular branch-and-propagate search, but instead of an exhaustive exploration, the coordination layer plug-in aborts the search when a specified time-out elapses. At that point it issues the command to flush the nodes of the search tree, and generates a configuration script for every solution that has been found so far, and one for every subproblem that must still be explored. These scripts are written to standard output, the last one followed by some character-encoded token τ, and the solver restarts and reads a new configuration script from standard input.

The idea is that we are able to tune the time-out value such that it is both sufficiently small to ensure that enough subproblems are available to keep all solvers busy, and sufficiently large to ensure that the overhead of communicating the subproblems is negligible.

Figure 3 shows how a (3-way) parallel solver can be constructed from three OpenSolver instances (labeled Solt ) that are equipped with this coordination layer plug-in, and a small number of special-purpose processes. The processes in this figure communicate through directed channels. The “resistors” depict filters, that recognize solutions: node b replicates all subproblems written to it on both filters. The filter from node b to node c forwards only solutions, and discards all other subproblems. The other filter forwards only internal nodes of the search tree, that re-enter the loop through process T.

–  –  –

Process T implements termination detection. Initially, it reads a problem from its left-hand side input port. All configuration scripts entering T, through either input port, are forwarded immediately through its right-hand side output port to the Store. Also T counts the number of problems forwarded to the Store, and the number of tokens τ received through its bottom port (from node b).

While these numbers do not match, the parallel solver is busy, and T will accept new (sub)problems from its bottom input port (connected to node b) only. As soon as the number of problems is canceled out by the number of tokens, T sends a token τ through its top port (to node c), indicating that the parallel solver has finished working on its current problem. Then it will return to its initial state, and accept a new problem from its left-hand side input port.

Process R3 is a 3-ary exclusive router. Every subproblem on its input port is forwarded on exactly one of its output ports. If none of the channels connected to the output ports is able to forward a data item, the router blocks. If a data item item can be forwarded on more than one output port, a non-deterministic choice is made.

The Store process buffers incoming problems, and interprets these problems to determine the level (depth) of the corresponding node of the search tree (this information is generated by the solvers, and maintained using annotation plugins). The level data is used to enforce a global traversal strategy, to control the number of subproblems residing in the Store: When R3 is ready to accept data, i.e., when one of the load-balancing solvers has become idle, it forwards a

problem according to the following strategy:

– If the number of problems residing in the Store is small, it selects a node that has the shallowest level in the search tree. These are least likely to be solved within the time-out period, and this effectively generates more subproblems.

Having a sufficiently large repository of subproblems prevents that solvers become idle, and thus ensures a good load balance.

– If the size of the Store becomes too large, it selects a subproblem that has the deepest level. This effectively drains the Store.

We implemented the parallel solver using MPI and UNIX pipes for communicating subproblems, and evaluated the efficiency on three benchmark problems:

counting the number of solutions to the 15-queens problem, proving satisfiability of the par16-2-c SAT problem, and proving that no 9-coloring exists for the DSJC125.5 graph. In all three cases we perform an exhaustive search to avoid speedup anomalies due to a different exploration order. The performance on 2 to 16 nodes of a Beowulf cluster of 1200 MHz AMD Athlon nodes are shown in Fig. 4. The speedup figures reported there are averages of 10 repeated runs, and are obtained by comparing with a sequential run, without the time-out mechanism. The first column shows the results for a “parallel” run on one processor.

–  –  –

On our hardware, these test problems involve 7 to 25 minutes of CPU time.

Pages:   || 2 |

Similar works:

«Technische Universität München Wissenschaftszentrum Weihenstephan für Ernährung, Landnutzung und Umwelt Lehrstuhl für Pflanzenernährung Tillering response to salinity in contrasting wheat cultivars Yuefeng Ruan Vollständiger Abdruck der von der Fakultät Wissenschaftszentrum Weihenstephan für Ernährung, Landnutzung und Umwelt der Technischen Universität München zur Erlangung des akademischen Grades eines Doktors der Naturwissenschaften (Dr. rer.nat.) genehmigten Dissertation....»

«66 INDUSTRIAL UTILIZATION OF SINGLE-IMAGE PHOTOGRAMMETRY VYUŽITÍ JEDNOSNÍMKOVÉ FOTOGRAMMETRIE V PRŮMYSLU Lucie STAVAŘOVÁ Ing., Institute of geodesy and mine surveying, Faculty of Mining and Geology, VŠB – Technical University of Ostrava, 17.listopadu 15, 708 33 OstravaPoruba, tel. (+420) 59 732 5271 e-mail: lucie.stavarova.st@vsb.cz Abstract Single-image photogrammetry is today only a marginally used surveying method. In the project of diagnostics of rotary kilns a non-contact method...»

«Chapter 2 Anisotropy of Magnetic Susceptibility Abstract Anisotropy of magnetic susceptibility is an important technique which depicts preferred orientation of magnetic minerals in a rock or unconsolidated sediments. Hence the property is used for study of primary structures and rock fabric. The technique is non-destructive and can be used in nearly all types of rocks because it does not need a rock to contain specific strain markers like deformed fossils, reduction spots, ooids, etc. The...»

«VALIDATING CRITERION-REFERENCED READING TESTS a Daniel S. Sheehan and Mary Marcus Dallas Independent School District Abstract. Validation is an important step in the developmental process of any reading test. Yet traditional approaches to reliability and validity assessment are not relevant for criterion-referenced reading tests. A more relevant approach defines reliability in terms of the consistency of decision-making across repeated test administrations and validity in terms of the accuracy...»

«BRAND PROTECTION Technical Manual on Brand Protection © IOC ALL RIGHTS RESERVED As part of the IOC initiative to update and standardise the technical manuals provided to OCOGs, this manual is using a new title for a version already in use. Please note that the content of this manual has not changed and the previous title may be used throughout this document. As it is referenced in the IOC Host City Contract, this manual should be considered part of said Contract. The previous title was the...»

«DEPARTMENT OF THE NAVY Headquarters United States Marine Corps Washington, D.C. 20380-1775 30 July 1997 FOREWORD This publication is about winning in combat. Winning requires many things: excellence in techniques, an appreciation of the enemy, exemplary leadership, battlefield judgment, and focused combat power. Yet these factors by themselves do not ensure success in battle. Many armies, both winners and losers, have possessed many or all of these attributes. When we examine closely the...»

«Corporate & Continuing Education Greetings, and welcome to Fayetteville Technical Community College! The selection of classes presented in this spring tabloid present a number of outstanding opportunities to begin a new year in a positive way—through education! Learning something new is a great way to add enthusiasm to life, and participating in learning opportunities during the winter months adds a warm spark of excitement to life. No matter where your interest lies, you’ll find that FTCC...»

«Save As Animal Farm Chapter 7 Answers with easy. Then You can Read eBook Animal Farm Chapter 7 Answers file for free ANIMAL FARM CHAPTER 7 ANSWERS PDF Download: ANIMAL FARM CHAPTER 7 ANSWERS PDF Digital document ANIMAL FARM CHAPTER 7 ANSWERS File update. So you are person who likes to download animal farm chapter 7 answers Pdf to any kind of device,whether its your laptop, Kindle or iPhone, there are more options now than ever before. Perhaps because of the growing popularity of Algebra...»

«STARFACE ADMINISTRATIONSHANDBUCH STARFACE Administrationshandbuch 3.0 Stand November 2011 Die in diesem Buch enthaltenen Angaben und Daten können ohne vorherige Ankündigung geändert werden. Ohne ausdrückliche schriftliche Genehmigung der STARFACE GmbH darf kein Teil dieses Dokumentes vervielfältigt oder übertragen werden, unabhängig davon, auf welche Art und Weise oder mit welchen Mitteln, elektronisch oder mechanisch, dies geschieht. ©2011 STARFACE GmbH. Alle Rechte vorbehalten....»

«The African National Anthem, Nkosi Sikelel' iAfrika A Pragmatic Linguistic Analysis By Abdul Karim Bangura Included in this preview: • Copyright Page • Table of Contents • Excerpt of Chapter 1 For additional information on adopting this book for your class, please contact us at 800.200.3908 x501 or via e-mail at info@cognella.com THE AFRICAN NATIONAL ANTHEM, “NKOSI SIKELEL’ IAFRIKA” A PRAGMATIC LINGUISTIC ANALYSIS BY ABDUL KARIM BANGURA Copyright © 2011 by Abdul Karim Bangura. All...»

«DESIGN EDUCATION VIA WEB-BASED VIRTUAL ENVIRONMENTS Simeon J. Simoff and Mary Lou Maher1 Abstract The concept of a virtual environment has emerged from advances in computer networking, image processing, modeling, simulation and multimedia data representation. During the past few years the concept has been intensively employed in Virtual Design Studios (VDSs) for teaching students both design and Internet technology issues. This paper presents the Web-based VDS as an environment for computer...»

«Simulationsgestützte Abschätzung der Genauigkeit von Messungen mit Röntgen-Computertomographie Der Technischen Fakultät der Universität Erlangen-Nürnberg zur Erlangung des Grades DOKTOR-INGENIEUR vorgelegt von Philipp Martin Krämer Erlangen – 2012 Als Dissertation genehmigt von der Technischen Fakultät der Universität Erlangen-Nürnberg Tag der Einreichung: 25.11.2011 Tag der Promotion: 16.03.2012 Dekanin: Prof. Dr.-Ing. habil. Marion Merklein Berichterstatter: Prof. Dr.-Ing. Prof....»

<<  HOME   |    CONTACTS
2016 www.abstract.xlibx.info - Free e-library - Abstract, dissertation, book

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.