topic Re: Proc Optmodel, Pairwise selection of observations in Mathematical Optimization, Discrete-Event Simulation, and OR

Proc Optmodel, Pairwise selection of observations

khchaitanya — Thu, 19 Jul 2012 20:04:49 GMT

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!

Re: Proc Optmodel, Pairwise selection of observations

khchaitanya — Fri, 20 Jul 2012 15:09:10 GMT

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.

Re: Proc Optmodel, Pairwise selection of observations

RobPratt — Tue, 24 Jul 2012 13:19:27 GMT

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

Re: Proc Optmodel, Pairwise selection of observations

khchaitanya — Tue, 24 Jul 2012 22:12:51 GMT

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

Re: Proc Optmodel, Pairwise selection of observations

khchaitanya — Thu, 26 Jul 2012 23:12:40 GMT

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)

Re: Proc Optmodel, Pairwise selection of observations

RobPratt — Fri, 27 Jul 2012 14:35:27 GMT

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.

Re: Proc Optmodel, Pairwise selection of observations

khchaitanya — Fri, 27 Jul 2012 15:37:42 GMT

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