How to choose one value for each row and column in a matrix so that the sum of values in the matrix is minimized

I am trying to develop an algorithim to automate a site selection process. Each column of the matrix represents a site of interest and each row represents a monitor collecting data within an acceptable buffer distance from each site and the numeric value represents the distance from the monitor to the site of interest. Since I want to obtain the largest data set possible I first want to maximize the number of sites with monitoring data and then minimize the total distance, or the sum of the selected numbers. Essentially only one value can be selected for each row and column in the matrix. The algorithim should select the starred values in the examples below.

d1 =

    0.00000   22.61630   12.02885    0.00000   *14.99793*
    0.00000    0.00000    0.00000    0.00000    0.00000
    0.00000    0.00000    0.00000    *7.40015*  0.00000
    0.00000    0.00000    0.00000    0.00000    0.00000
    0.00000    0.00000   *28.56141*   10.98434   0.00000

d1 =

    0.00000   22.61630   14.9980    *12.3234*     0.00000
    *23.0000*   0.00000   0.00000      21         0.00000
    0.00000    0.00000    0.00000    0.00000     *7.40032*
    0.00000    0.00000    0.00000    0.00000      0.00000
    0.00000    0.00000    0.00000    0.00000      10.98434

[Rachel]

Hi Matt, Thanks for your question. You can only make one selection per row, so once a selection has been made in a row none of the other values in that row can be counted (in the context of this study this is because we don't want to double count data by using data from the same monitor at two different sites). Another valid selection for that example would have been to select the 21 and the 14.9980 but if you sum these values the total distance would be slightly larger. The other caveat is that we are trying to get data for as many sites as possible by selecting from as many columns as possible. In the first example only the first row has data for sites two and five, and since column three had other data available the 14 was selected from row 1 instead of the 12. If the 12 was selected only 2 sites would have completed data sets. I hope this helps!

Answer 1

[Matt J]

You could pose this as a binary integer program and use bintprog from the Optimization Toolbox to solve it. The problem would be formulated by assigning binary variables x(i) to the non-zero entries of your d1 matrix. Taking your first example d1, this would be

    0.00000   x1           x2        0.00000     x6
    0.00000    0.00000    0.00000    0.00000    0.00000
    0.00000    0.00000    0.00000    x4         0.00000
    0.00000    0.00000    0.00000    0.00000    0.00000
    0.00000    0.00000     x3        x5         0.00000

The idea is now to decide which x(i) are assigned 1 and which will be assigned 0, where an assignment of 1 would mean you decide to include that entry. This is subject to the constraint that no column or row contains more than 1 selection, which can be expressed using linear constraints as follows,

   x1+x2+x6<=1
         x4<=1
       x3+x5<=1

     x1<=1
  x2+x3<=1
  x4+x5<=1
  x6<=1

To maximize first with respect to the number of sites, run bintprog with the objective function vector

    f=-ones(1,nnz(d1))

which will lead to an optimum value -fmax where fmax will be the maximum possible number of sites. Then, to minimize among the possible total distances, re-solve the problem adding the linear equality constraint

   x1+...+x6 = fmax

and using the objective function vector

   f=nonzeros(d1)

[Rachel]

Thanks so much! Would it be possible to automate the definition of the linear constraints since the position of the binary variables changes each time?

[Matt J]

Yes, it's possible. I do so in the code below, which solves the entire problem for a given d1.

    %%build constraint data

        n=nnz(d1); 
       [I,J]=find(d1);  

       A=[sparse(I,1:n,1);sparse(J,1:n,1)]; 
          A=A(any(A,2),:); %get rid of trivial rows

       b=ones(size(A,1),1);

   %%maximize sites chosen (columns of d1)

       f0=-ones(1,n);

       [x0,minf0]=bintprog(f0,A,b);

    %%minimize distance subject to maximum number of sites

        x=bintprog(nonzeros(d1),A,b,f0,minf0,x0);

    %%display the solution in matrix form

        mask=logical(d1);
         mask(mask)=x;

        d_chosen = d1.*mask  %show resulting choices