Geeks With Blogs

News
Charles Young

This supplementary article should be read in conjunction with the main article comparing Windows Workflow Foundation (WF) with the Microsoft Business Rules Engine (MS BRE).  MS BRE is a data-driven inferencing engine. To illustrate more clearly how its forward chaining offers greater power than WF, let’s take a simple inferencing example.  We will study a design for some MS BRE rules for solving the 'travelling salesperson' problem.   In the following example, we will begin with a collection of 'Location' facts.   One location is marked as the 'start' location.   Other locations represent sites that will be visited by our mythical salesperson.  The goal is to determine a single itinerary that will allow one salesperson to visit all the sites just once, starting and finishing at the 'start' location, and taking the shortest overall route possible.   Some readers may recognise this as a classic 'Hamiltonian tour' decision problem.

For this example, we will assume that the following 'fact' classes have been created.

Location

      .ctor Location ( int x, int y, bool isStart )
      int X
      int Y
      int ID
      bool IsStart ( )

Itinerary

      .ctor Itinerary ( Location loc )
      double Distance
      void Add ( Location loc )
      bool IsComplete ( )
      bool CanAddLocation ( Location loc )
      void PrintItinerary ( )

Context

      static int LocationCount
      static int CandidateItineraryCount
      static int CandidateItineraryCreationCount
      static Itinerary CreateNewItinerary ( Location loc )
      static Itinerary SelectedItinerary

Our approach to determining the solution will be a simple 'brute force' approach.   We will test every possible combination of locations and select one which has the shortest distance overall.   There may be several candidate itineraries which have equally short overall distances, but we will let the engine select one arbitrarily.  This is a terrible way to solve this problem (the Christofides algorithm offers a much better approach, although it provides only an approximate solution where the selected itinerary may be up to 50% longer than the correct solution), and is only suitable for very small numbers of locations, because the number of combinations increases very rapidly as the number of locations increases, and the number of comparisons of these combinations increases even faster.  Some readers will understand when I say that this is a well-known NP-complete problem.

Locations     

Combinations 

Potential Comparisons*

1

0

0

2

1

0

3

2

1

4

6

30

5

24

552

6

120

14,280

7

720

517,680

8

5,040

25,396,560

9

40,320

1,625,662,080

10

362,880

131,681,531,520

11

3,628,800

13,168,185,811,200

12

39,916,800

1,593,350,882,323,200

* In reality, MS BRE will not need to carry out so many comparisons of the various combinations, because it discards combinations (i.e., candidate Itineraries) as quickly as possible, thanks to the high priority of rule 3 below.

Although highly impractical, the approach taken in this example will suit our purposes for demonstrating the way rules in MS BRE can undertake highly combinatorial processing.  Using location sets greater than about 6 or 7 will take significantly amounts of time to run.

We will start by asserting a collection of Location objects and a single 'Context' object (MS BRE insists that an instance of Context is asserted, even though we will only use its static members).  One Location object will represent the start location, and its IsStart method will return 'true'.   All other Locations will return 'false'.   The Context class will be initialised with the number of Locations.   Its CandidateItineraryCount property will return the number of candidate Itineraries, which is calculated as (LocationCount - 1)!.   When MS BRE has completed its processing of the ruleset, the selected Itinerary will be provided via the SelectedItinerary property.

Rule 1: create_candidate_itineraries (priority = 5)

      IF
         Context.CandidateItineraryCreationCount <  Context.CandidateItineraryCount
         AND Location.IsStart ( );
      THEN
         // Increment
Context.CandidateItineraryCreationCount
         Assert Context.CreateNewItinerary ( Location );
         // The following assert causes Rule 1 to be matched 
         // repeatedly until all candidate Itineraries are created 
         Assert Context; 

Rule 2: add_locations  (priority = 0)

      IF
         // The logic in the CanAddLocation method ensures that all
         // combinations are built
         Itinerary.CanAddLocation ( Location ) 
      THEN
         Itinerary.Add ( Location );
         // This assert causes Rule 2 to be matched repeatedly until
         // all candidate Itineraries are built
         Assert Itinerary; 

Rule 3: filter_itineraries  (priority = 10)

      IF
         Itinerary(1).IsComplete ( )
         AND Itinerary(2).IsComplete ( )
         AND Itinerary(1).Distance <= Itinerary(2).Distance;
      THEN
         // Select the Itinerary with the least distance
         Context.SelectedItinerary = Itinerary(1);
         // Discard the Itinerary with the greatest distance
         Retract Itinerary(2);

Rules 1 and 2 are used to create candidate Itinerary objects and to populate them with combinations of Locations.   They depend on some logic within the Location and Context classes that controls the population and ensures that every possible Location combination is represented.   The CanAddLocation() method, in particular, is implemented to determine if a location is eligible to be added to the Itinerary.   Splitting logic between rules and custom code in this way is a normal pattern in MS BRE, but we could consider pushing the logic of the first two rules back entirely into custom code, and then just asserting the pre-populated Itinerary objects, rather than the Location objects.

Rule 3 uses forward chaining to implement a process of elimination.   The numbers contained in parenthesis after each reference to Itinerary are 'instance' numbers.   The condition in Rule 3 tests every combination of two Itineraries and discards instance (2) if its total distance (calculated internally within the Itinerary object) is less than the total distance for instance 1.   The engine will perform forward chaining cycles repeatedly until the working memory contains only those Itineraries which have an equally shortest total distance.   One of these will have been assigned to the Context.Itinerary property, and this is the 'winner'.

Note that the priority of Rule 3 is higher than the other two rules.   This ensures that Itineraries are retracted from memory as quickly as possible, reducing the number of times Rule 2 and Rule 3 are selected onto the agenda.  This significantly optimises the ruleset.

By elaborating Rule 3, and adding additional rules, this basic foundation could be used to select an Itinerary based on additional criteria, such as agreed times for site visits, salesperson knowledge, etc.   Of course, as I stated before, the example I have provided is a really, really bad way to solve the 'travelling salesperson' problem.  There are much more efficient heuristic algorithms available, and these could be implemented in a straightforward manner using MS BRE rules.   The point of this example is simply to show the ability of MS BRE to solve highly combinatorial problems using pattern matching.   A single rule can be matched to large number of combinations of facts, and perform chaining in order to infer a solution.

Posted on Sunday, October 9, 2005 10:21 PM | Back to top


Comments on this post: Business Rules Framework: 'Travelling SalesPerson' example

No comments posted yet.
Your comment:
 (will show your gravatar)


Copyright © Charles Young | Powered by: GeeksWithBlogs.net