Minimize sum of array elements subject to conditions

Question

I have array where each point at different times are shown parameters

m = {{2.45, 3.24, 3.87, 3.90}, 
     {4.12, 2.15, 3.11, 3.51}, 
     {3.32, 3.11, 4.21, 3.64}, 
     {2.78, 4.01, 3.69, 1.57}, 
     {2.69, 2.22, 3.59, 1.98}, 
     {2.15, 1.98, 2.54, 1.78}, 
     {1.99, 1.87, 5.11, 2.01}}

After addition of the header

rows = {"1200", "1210", "1220", "1230", "1240", "1250", "1300"};
TableForm[m, TableHeadings -> {rows, {"P1", "P2", "P3", "P4"}}, TableAlignments -> Center]

Summing can be done only by adding one element of the column and row.

Important is the combination of the aggregation of the selected elements: please add up all combinations "below" the main diagonal of the matrix. I found 35 in my table $m$.

Described in table times and points to simulate the passage of the vehicle (by optimization of parameters in a specified place and time), so there is no potentiality in specified time appearance on all points, or back.

Sorted (from min to max) results (sum) should determine the hours to pass through the points. The smallest sum will be at 1200 P2 reach about 1210, P3 1250 and the end of P4 at 1300.

The objective is to seek a minimum sum of the numbers for moving the vehicle to the fixed route. Tables of data will be significantly greater than in this example.

How to force Mathematica to count different combinations of diagonals and then determine the origin of the smallest sum?

The example generated in Excel below may help clarify the problem.

Answer 1

It seems to me that generating only the valid combinations might be labor-intensive. Instead I first generate all possible combinations of elements, one from each column, labeling them with the indices of the rows from which each element was picked, and calculating the total you want to have minimized:

allcombos = MapThread[
   {#1, Total@#2} &,
   {
    Tuples[Range[Dimensions[m][[1]]], {Dimensions[m][[2]]}],
    Tuples[Transpose@m]
    }
   ];

I then select only those combinations that fulfill your requirements: a) only one element should be picked from each row (DuplicateFreeQ condition) and b) the elements should be ordered by increasing time, which is equivalent to requesting that they be picked from rows with increasing indices (OrderedQ condition):

validcombos = Select[allcombos, DuplicateFreeQ[#[[1]]] && OrderedQ[#[[1]]] &];

Finally, the best choice is the one with the lowest total, so I sort the valid combinations by their corresponding total, and then I pick the first one, i.e. the one with the lowest total:

SortBy[Last][validcombos][[1]]

(* Out: {{1, 2, 6, 7}, 9.15} *)

This is the same result you obtained.

The code above makes no assumptions on the size and shape of the matrix m, so it should work for larger matrices as well, as long as you have enough memory to generate the Tuples.