optimal solution of a matrix

Hey everyone, Im working on my thesis and need to find the min. cost solution within my project. However, I got stuck! Hope you can help me!

    1.1095    1.1112         0         0    1.1120    1.1122         0
    1.2292    1.2275         0         0    1.2286    1.2295         0
         0         0    1.1567         0         0    1.1590         0
         0         0         0    1.0988         0         0    1.1008
    1.1369    1.1355         0         0    1.1345         0         0
    1.0695    1.0688    1.0690         0         0    1.0668         0
         0         0         0    1.1082         0         0    1.1062

The previous matrix is my output. Rows are defined as j, Colums are defines as i. I need to min. cost at i, while providing producst to every j. Example: i = 1 could provide for j = {1,2,5,6}, i = 3 could provide for j = 3 (it is possible to provide for yourself) and i =4 could provide for j= {4,7}. What i need matlab to do is calculate all the different options (only 1 i is allowed for each j, but 1 i can supply multiple j's) and to give me the lowest cost and the i,j combinations that correspont with this.

I hope someone can help me! It's the last part I need to do to graduate, but matlab is very new to me, so would appreciate the help!

Thanks, Arjan

Answer 1

[Roger Stafford]

It isn't entirely clear what you are asking. If it is allowed to select only a portion of the non-zero values in a column, then the problem is easy. For each row select the minimum non-zero value in it. Let your 7 x 7 matrix be called M.

   ji = zeros(7,2);
   s = 0;
   for j = 1:7
     p = find(M(j,:)>0);
     [c,q] = min(M(j,p));
     s = s + c;
     ji(j,:) = [j,p(q)];
   end

Then ji contains the seven j,i index pairs of the optimum selection and s is the sum of their total "costs" in M.

(I can see without even using matlab that the solution for your particular example happens to be the pairs along the main diagonal of M.)

Answer 2

[A]

Thanks for answering! Sorry for not being 100% clear, I tried my best but I’ll try to clarify!

I need the model to check all possible combinations (in this case indeed the cheapest would be the diagonal, this is because some of the values are the same now, but this can change in time, and the answer could change with that).

This morning I noticed a mistake which is actually a bigger problem for me to fix.

Like I said, one i (column) can supply multiple j’s (rows). When an i is chosen to supply one or more j’s, a one-time fixed cost should be added (the cost to “open” this i). right now, all my solutions get this fixed cost added to them. What this gives me is, worst case scenario, one i that provides all j’s and increases my final answer with 7 times the fixed costs (This should of course only be one time).

So what I need is the model to check all options that will satisfy all the j’s (all j’s need supply, no matter which i) and then, when lets say the answer is that i,j = {1,1;1,2;1,5;1,6;3,3;7,4;4,7} that the fixed cost of 1,3 and 4 will be added to the total of the sum of costs i,j (one time!). this will be the new lower bound. Example (see previously chosen i,j): 1.1095+1.2292+ 1.1369+1.0695+1.1567+1.1008+1.1082= 7,9108. The fixed cost are 2 for i =1, 3 for i=3 and 0,5 for i=4. So it would be 7,9108+2+3+0,5=13,4108. Then he will pick another option that satisfies all j’s and do the same and see if this option is lower or higher than the previous cost. If it’s lower than a new Lower Bound will be defined. The model has to do this for all possible combinations and then print the lowest bound he found, with the corresponding arcs.

So the main problems are: how to make the model run all the different options, and how to make sure that when an option is chosen, the fixed costs will only be added one time.

It’s very difficult to explain it on paper, so please tell me if things are unclear, then I’ll try to rephrase them. It's alot of reading, sorry for that. Thanks a lot for the help!

[Roger Stafford]

Your explanation is still somewhat unclear to me. Here are some of my uncertainties:

1) The phrase "one-time fixed cost" is confusing me because it seems to hint that your other costs could occur many times. Or to put it another way, is the quantity 13.4108 in your example the actual amount you wish to minimize, or do the costs in the 7.9108 figure apply multiple times? It is important to be precise in defining what it is you wish to minimize. Changes in this definition can seriously affect the algorithm needed for the problem.

2) There was no mention of the "fixed cost" aspect in your original description. Do you have a list of all these amounts? You mention three of them in your example: 2, 3, and 0.5. What are the others? Is there a fixed list of them for each optimization?

3) In your example, {1,1;1,2;1,5;1,6;3,3;7,4;4,7}, there occurs the pair i = 7, j = 4, and in the matrix the corresponding cost would be 1.1008 which you included in the figure 7.9108. However, you did not list a corresponding one-time fixed cost amount for this i = 7 case. Was that a mistake on your part, or is this something further that I don't understand about your problem?