Formulating an optimization based on rank

Question

I originally posted this question here on the SuperUser network as I'd seen suggestions that was the best place for MatLab questions, but it's not getting a lot of traction there. Independent of MatLab, if anyone here has some guidance on the general formulation of the problem, I can work the MatLab implementation. Hopefully this isn't "cross-posting"....

This is a problem that I have previously addressed in Excel, but would like to move to MatLab for better quality solutions.

Where I work, there is a semiannual process to rank new initiatives. They are scored against a number of criteria and assigned a criteria score in the range [0,1]. Each criteria has a weight assigned to it, and these weight are normalized such that they sum to 1. The total score for a given initiative is then the sum of the products of each criteria score and its weight.

Executing this process generates scores for each initiative under consideration, and the initiatives can thus be ranked 1-n based on their scores. So far so good...

But this list is then provided to a managerial decision body that "applies judgement" and shuffles this ranking based on their own deliberations. They don't assign a new score (if I had that I would know what to do) they just change the relative rankings of the initiatives.

What I would like to do is to investigate whether there is a set of criteria weights that produces a 1-n list closer to the final product of the deliberations. In the past I have done this in Excel, where I can use the rank() function as part of my calculation. I set it up something like this

In this case I tell Excel solver to change the values in red, subject to the constraints that they are [0,1] and sum to 1, in order to minimize the sum in green.

The idea is to highlight issues along the lines of "You say criteria X is the most important, but your application of judgement seems to show that Y is actually more of a determinant."

I really don't know how to approach formulating this for fmincon (or any other non-Excel solver for that matter) and would appreciate any guidance. My recent experience with Excel has been that a) as the number of initiative increases the runtimes become quite long and b) I can run the same optimization 10 times and get 10 very different solutions...

Answer 1

So the answer is to introduce slack variables, add constraints that force things into the post-judgement ranks, and then minimize the sum of the slack variables.

So for example, the top alternative after judgement scored 0.8, 1, 1, and 1 on the four measures. It's total score would thus be 0.8W1 + W2 + W3 + W4 where the W's are the criteria weights.

The second alternative scored 0.8, 1, 0.8, and 1, so it's total score would be 0.8W1 + W2 + 0.8W3 + W4.

The next alternative scored 0.8, 1, 0.8, and 1 again, so it's total score would be 0.8W1 + W2 + 0.8W3 + W4.

The first two constraints in the model are thus

0.8W1 + W2 + W3 + W4 + S1 >= 0.8W1 + W2 + 0.8W3 + W4 + S2
0.8W1 + W2 + 0.8W3 + W4 + S2 >= 0.8W1 + W2 + 0.8W3 + W4 + S3

I could have expressed them like this in MatLab, but I went ahead and pulled the like terms together, so the first two constraints become

0W1 + 0W2 + 0.2W3 + 0W4 + S1 - S2 >= 0
0W1 + 0W2 + 0W3   + 0W4 + S2 - S3 >= 0

etc

For a trial run from a year where there were only 25 alternatives under consideration, my solution in MatLab looked like this. (Any suggestions to improve are appreciated)

A=[0  0  .2    0   1 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0;
   0  0   0    0   0  1 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0;
   0  .2  -.2  0   0  0  1 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0;
   0  0   0    0   0  0  0  1 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0;
   0  0   0    0   0  0  0  0  1 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0;
   0  0   .2   0   0  0  0  0  0  1 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0;
   .3 -.2 0    0   0  0  0  0  0  0  1 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0;
   0  0   -.2  .2  0  0  0  0  0  0  0  1 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0;
   0  .2  0    -.2 0  0  0  0  0  0  0  0  1 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0;
  -.3 .3  0    0   0  0  0  0  0  0  0  0  0  1 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0;
   .3 -.3 0    0   0  0  0  0  0  0  0  0  0  0  1 -1  0  0  0  0  0  0  0  0  0  0  0  0  0;
  -.3 0   0    .5  0  0  0  0  0  0  0  0  0  0  0  1 -1  0  0  0  0  0  0  0  0  0  0  0  0;
   .3 0   .2   -.5 0  0  0  0  0  0  0  0  0  0  0  0  1 -1  0  0  0  0  0  0  0  0  0  0  0;
  -.3 0   0    .5  0  0  0  0  0  0  0  0  0  0  0  0  0  1 -1  0  0  0  0  0  0  0  0  0  0;
   .3 0   -.2  0   0  0  0  0  0  0  0  0  0  0  0  0  0  0  1 -1  0  0  0  0  0  0  0  0  0;
   0  0   0    0   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1 -1  0  0  0  0  0  0  0  0;
   0  -.2 .8   -.3 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1 -1  0  0  0  0  0  0  0;
   0  .5  -.6  .3  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1 -1  0  0  0  0  0  0;
   0  .3  -.2  0   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1 -1  0  0  0  0  0;
   0 -.3   .5  0   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1 -1  0  0  0  0;
   0   0    0  0   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1 -1  0  0  0;
   0  .3    0  0   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1 -1  0  0;
   0   0    0  0   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1 -1  0;
   .3  0   .3  0   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1 -1];

b = zeros(1,24);

Aeq = zeros(1,29);
Aeq(1:4)=[1 1 1 1];    %sum of the first four variables (the weights) must = beq = 1

beq = 1;

f = ones(1,29);       %objective function is to minimize sum of the slack variables
f(1:4) = [0 0 0 0];   %weights not part of objective function

lb = zeros(1,29);     %no negative values, otherwise minimization is unbounded
ub = [1 1 1 1];       %weights cannot exceed 1

[x,fval]=linprog(f,A,b,Aeq,beq,lb,ub)

This seems to be working so far, and providing the interesting insight that the movement from the model to the post-judgement list is minimized if you just put all the weight on the first criteria.

Thanks to @DonThousand for getting me to think about this differently!