The MATCHD.lng Model

Matching Model

Here, we introduce the use of a sparse derived set with a membership filter. Using a membership filter is the third method for difining a derived set. When you define a set using this method, you specify a logical condition each member of the set must satisfy. This condition is used to filter out members that don't satisfy the membership condition.

For our example, we will formulate a matching problem. In a matching problem, there are N objects we want to match into pairs at minimum cost. The pair (I,J) is indistiguishable from the pair (J,I). Therefore, we arbitrarily require I to be less than J in the pair. Formally, we require I and J make a set of ordered pairs. In other words, we do not wish to generate redundant ordered pairs of I and J, but only those with I less than J. This requirement that I be less than J will form our membership filter.

In this example, suppose you manage your company's strategic planning department. You have a total of eight analysts in the department. Furthermore, you department is about to move into a new suite of offices. There are a total of four offices in the new suite and you need to match up your analysts into 4 pairs, so each pair can be assigned to one of the new offices. Based on past observations you know some of the analysts work better together than they do with others. In the interest of departmental peace, you would like to come up with a pairing of analysts that results in minimal potential conflicts. To this goal, you have come up with a rating system for pairing you analysts. The scale runs from 1 to 10, with a 1 rating of a pair meaning the two get along fantastically. Whereas, a rating of 10 means all sharp objects should be removed from the pair's office in anticipation of mayhem. The problem is to find the pairings of analysts that minimizes the sum of the incompatibility ratings of the paired analysts.

Keywords:

Matching |