Proc Optmodel, Pairwise selection of observations

[khchaitanya]

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!

[khchaitanya]

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.

[RobPratt]

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.)

[khchaitanya]

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

[khchaitanya]

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)

[RobPratt]

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.

[khchaitanya]

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