Calcite | Level 5

## Proc Optmodel, Pairwise selection of observations

Hi there,

I have an optimization problem where i need to select the observations in pairwise based on certain criteria. The problem is discussed in-detail as shown below:

for suppose we have following data:

property_code   state    value

53012            CA      500000

98432            FL      200000

32763            GA      300000

34534            CA      198000

12432            FL      650000

65851            MN     200000

85563            FL      499000

54632            CA      645000

65726            UT      100000

Using the optimization technique we have to select pair-wise records from above data, one property from CA and one property from FL such that the difference in their respective values is almost the same or below certain tolerance.

For suppose we want to take 2 pairs out of above data:

Optimizer has to output:

property_code   state    value

53012            CA      500000
85563            FL      499000
34534            CA      198000

98432            FL      200000

i.e It selected one from CA worth 500000 and then selected a near one from FL worth 499000, and similarly it pulled second pair as shown above.

Can anybody let me know how to put this as a constraint or a objective function.

Thank you for you help in advance!

6 REPLIES 6
Calcite | Level 5

## Re: Proc Optmodel, Pairwise selection of observations

I was able to select 2 records from each state using the state flag indicator. But could not do pair-selection such that the difference in the property values is min or within threshold.

SAS Super FREQ

## Re: Proc Optmodel, Pairwise selection of observations

For a given pair of states, your problem can be formulated as a linear assignment problem, where the cost of assigning record i from one state to record j from the other state is the absolute difference of the property values.  See the following usage note for how to solve a linear assignment problem using the LP solver in SAS/OR:

http://support.sas.com/kb/35/026.html

In SAS/OR 12.1, which will be released next month, there is also a linear assignment problem algorithm available in the new OPTNET procedure.

Note that without your threshold constraint, if there are n records for each of the two states, then just sorting the values for each state and matching them up in that order is optimal.  This property does not hold in general, but for your absolute difference cost, it is easy to show that any other matching will have higher cost.  (If two values are out of order, interchanging them will improve the cost.)

Calcite | Level 5

## Re: Proc Optmodel, Pairwise selection of observations

Thank you Rob, It worked. Thank you very much !

Calcite | Level 5

## Re: Proc Optmodel, Pairwise selection of observations

Rob, This was helpful but has a big limitation when applied to my example. I need to pick up pairs with lowest individual cost (limited number).

This model picks up in such a way that it minimizes the cost for the whole matrix.

Is there a way i can select the costs (limited number) such that each individual cost is small out of the whole nXn cost matrix.

Like if i am interested in picking up only 10 pairs of the 200, the output should be something like this:

 CA FL prop_val prop_val Error 40491.01228 40627.76096 136.7486725 74185.43779 74439.91526 254.4774759 52112.67672 51757.37807 355.2986575 92344.59878 92861.84872 517.2499386 149438.711 150428.7754 990.064358 161100.0464 162322.5791 1222.532687 45977.42362 44745.24589 1232.177735 52993.13839 54359.262 1366.123614 108280.265 113204.0449 4923.7799

The solution from Proc optmodel LP solver was not trying to give me the minimum error values since it was trying to balance total cost (i mean minimize)

SAS Super FREQ

## Re: Proc Optmodel, Pairwise selection of observations

For your "cardinality-constrained" assignment problem, you can modify both sets of = 1 constraints to <= 1 and then include a new constraint that forces the desired number of assignments:

con cardinality: sum{i in NSET, j in NSET} x[i,j] = 10;

In that case, you should also declare x as binary and use the MILP solver.

Calcite | Level 5

## Re: Proc Optmodel, Pairwise selection of observations

That's simply awesome!  I owe you a treat . Thank you very much Rob. Have a nice day!

Discussion stats
• 6 replies
• 1513 views
• 3 likes
• 2 in conversation