BookmarkSubscribeRSS Feed
khchaitanya
Calcite | Level 5

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
khchaitanya
Calcite | Level 5

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
SAS Super FREQ

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
Calcite | Level 5

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

khchaitanya
Calcite | Level 5

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:


CAFL
prop_valprop_valError
40491.0122840627.76096136.7486725
74185.4377974439.91526254.4774759
52112.6767251757.37807355.2986575
92344.5987892861.84872517.2499386
149438.711150428.7754990.064358
161100.0464162322.57911222.532687
45977.4236244745.245891232.177735
52993.1383954359.2621366.123614
108280.265113204.04494923.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
SAS Super FREQ

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
Calcite | Level 5

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

sas-innovate-2024.png

Join us for SAS Innovate April 16-19 at the Aria in Las Vegas. Bring the team and save big with our group pricing for a limited time only.

Pre-conference courses and tutorials are filling up fast and are always a sellout. Register today to reserve your seat.

 

Register now!

Multiple Linear Regression in SAS

Learn how to run multiple linear regression models with and without interactions, presented by SAS user Alex Chaplin.

Find more tutorials on the SAS Users YouTube channel.

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