MILP for similarity I have the following question and I'm not sure how to formulate it as a mixed integer linear programming problem (if possible):
I have a set of products i (1..n) where I'm searching a similar product j (1..m) for, where X(i,j) equals 1 when product i is matched to product j and 0 otherwise. Every product i should be matched to exactly 1 product j (but not necessarily the other way around).
Now, to define a product i similar to product j, we have a bunch of attributes. Let's define for simplicity just two attributes:
a(i,j) : abs difference in % wood used between product i and j
b(i,j) : abs difference in % metal used between product i and j
Note that these are all constants. Finally, we have our absolute difference of sales volumes:
e(i,j) : abs difference in sales volumes between product i and j
Now, I want to minimize the absolute differences of sales volume, meaning:
min AVG((X(i,j)*e(i,j))
BUT, I also want to decide (extra decision variables) the weights of the attributes (call them A and B), which refer to the above mentioned constants a(i,j) and b(i,j). The restriction is that, for every product i, I always choose the product j that has the minimum of:
a(i,j) * A + b(i,j) * B
meaning, the smallest combined distances. A and B should be independent of i and j.
An example dataset is:
i|j|a|b|e
A|X|10|200|4000
A|Y|8|240|3500
A|Z|4|230|800
B|X|20|100|1200
B|Y|70|120|2000
B|Z|80|180|2000
C|X|5|420|3000
C|Y|4|350|600
C|Z|12|300|700
So, if the weights of column a and b are both 0.5, I have differences for product A of:
(A,X) : 0.5*10+0.5*200 = 105
(A,Y) : 0.5*8+0.5*240 = 124
(A,Z) : 0.5*4+0.5*230 = 117
Hence, product A will be most similar to product X, where the sales volumes difference equals 4000.
Doing this for products B and C as well, equals:
Product B most similar to product X, with sales difference of 1200;
Product C most similar to product Z, with sales difference of 700.
Hence, the average sales difference is now (4000+1200+700)/3 = 1967.
This is the number I want to minimize, by choosing the right weights for the (in this case) two attributes, which in my example are set to 0.5 and 0.5.
The question is now: Which values to select for these weights, in order to minimize the average sales volume?
Thanks!
 A: Let binary variable $x_{i,j}$ indicate whether product $i$ is matched to product $j$, and let $d_{i,j} = a_{i,j} A + b_{i,j} B$.  If you require that $A$ and $B$ are nonnegative and sum to 1, then I find that $(A,B) = (0.86207, 0.13793)$ is optimal, yielding the following values:
i j  a   b    e x      d 
A X 10 200 4000 0 36.207 
A Y  8 240 3500 0 40.000 
A Z  4 230  800 1 35.172 
B X 20 100 1200 1 31.034 
B Y 70 120 2000 0 76.897 
B Z 80 180 2000 0 93.793 
C X  5 420 3000 0 62.241 
C Y  4 350  600 1 51.724 
C Z 12 300  700 0 51.724 

The resulting objective value is $2600/3 \approx 866.7$.
The formulation I used is as follows.  For all $i,j$, let $\underline{d}_{i,j} = \min(a_{i,j},b_{i,j})$ and $\overline{d}_{i,j} = \max(a_{i,j},b_{i,j})$.  The problem is to minimize $\frac{1}{n}\sum_{i,j} e_{i,j} x_{i,j}$ subject to:
\begin{align}
A + B &= 1 \\
\sum_j x_{i,j} &= 1 &&\text{for all $i$}\\
d_{i,j} &= a_{i,j} A + b_{i,j} B &&\text{for all $i,j$} \\
d_{i,j} - d_{i,k} &\le (\overline{d}_{i,j} - \underline{d}_{i,k})(1 - x_{i,j}) &&\text{for all $i,j,k \not= j$} \\
A,B &\ge 0 \\
x_{i,j} &\in \{0,1\} &&\text{for all $i,j$}
\end{align}
The "big-M" constraints enforce the logical implication $x_{i,j} = 1 \implies d_{i,j} \le d_{i,k}$ for all $k \not= j$.
