Optimization/Dynamic Programming to Find Least Sum from Elements of Two Arrays

Given the following optimization problem,

Find the least sum (globally optimized) from elements of two arrays A and B such that

• Only one element is selected from A or B at each index, i.e., when A(1) is selected, B(1) cannot be selected
• Total sum of elements selected from array B should be <= 57
• Atleast one element should be selected at each index

A = [10, 15, 17, 30, 45]

B= [7, 10, 15, 26, 31]

Basically, elements of B will always be less than elements of A at every index. However, there is a limit on the maximum sum of elements that can be used from B.

[John D'Errico]

But now, having shown two simple vectors A and B, what would the solution be that you want to see? As far as I can see, the least sum there is gained by taking no elements at all.

Or perhaps, the least sum is gained from just B(1).

Must your solution have a total of 5 elements chosen? So the choice is simply whether you choose from vectors A or B for each index?

[Neeraj Rama]

How do I set this problem by using binary integer linear program for the attached arrays? New conditions,

• Elements of A, B are real numbers
• Sum of elements selected from array B <= 1165.208

Answer 1

[John D'Errico]

If I had to guess, you want to select 5 elements, from either A, OR B, but you need to select exactly 5 elements, and you cannot select the same index from the two vectors.

A = [10, 15, 17, 30, 45];
B = [7, 10, 15, 26, 31];

For vectors of length 5, why are you bothering to do this at all? The solution is trivial, since there are only 2^5 possible combinations. Just check all 32 possible choices and be done with it. Yes, that really is trivial to write.

n = numel(A);
XA = dec2bin(0:2^n-1) - '0';
XB = 1-XA;
% discard the combinations where the sum of B exceeds 57.

Bfail = (XB*B' > 57);
XB(Bfail,:) = [];
XA(Bfail,:) = [];

So the possible sums are

S = XA*A' + XB*B'
S =
   107
   105
    95
   109
   108
    98
   112
   110
   100
   114
   106
    96
   110
   108
    98
   112
   111
   101
   115
    99
   113
   103
   117

The globally minimal sum is:

[minsum ,minind] = min(S)
minsum =
    95
minind =
     3

XA(minind,:)
ans =
     0     0     1     1     0

XB(minind,:)
ans =
     1     1     0     0     1

For significantly larger vectors, you can do all of this as a binary integer linear program. Just set it up for intlinprog.

[John D'Errico]

Why not try it yourself? You won't learn anything unless you do.

First, this claim of yours is clearly false, by your own construction:

"Basically, elements of B will always be less than elements of A at every index. "

Clearly that is incorrect, if we look at the difference of the vectors, thus A-B. If A-B is ever negative, then your statement is false.

   Min     -1.837
  1.0%    -0.8335
  5.0%    -0.3561
 10.0%    -0.2198
 25.0%   -0.04252
 50.0%    0.03591
 75.0%       1.22
 90.0%      3.574
 95.0%      4.333
 99.0%      5.621
   Max      36.98

Mean     0.8588
 Std       1.67
 Rms      1.878
Range      38.82

So more than 25% of the elements of A and B fail to satisfy your claim at some set of indices.

I suppose nothing really hinges on that claim though.

That neither A or B is integer is irrelevant. However, as usual, someone posts a question with a tiny example, then wants us to solve an immense problem, and expects the algorithm suggested to be satisfactory.

The search space for the problem is a space of dimension 10000. It may easily be far too large for intlinprog to solve in a reasonable amount of time. GA might be another option, but I fear that may have problems too.

Regardless, how might you formulate this problem for a reasonably sized A and B? I'll try this one, and see how fast it goes.

N = numel(A);
blimit = 1165.208;
f = A-B;
intcon = 1:N;

% Constraint on the sum of the components that live in b is:
% -B'*x <= blimit - sum(B)
Aineq = -B';
bineq = blimit - sum(B);
lb = zeros(1,N);
ub = ones(1,N);

Aeq = [];
beq = [];

tic
[X,FVAL,EXITFLAG]=intlinprog( ...
   f,intcon,Aineq,bineq,Aeq,beq,lb,ub);
toc

LP:                Optimal objective value is -433.320677.                                          

Cut Generation:    Applied 1 Gomory cut,                                                            
                   and 1 strong CG cut.                                                             
                   Lower bound is -433.320148.                                                      

Heuristics:        Found 1 solution using rounding.                                                 
                   Upper bound is -433.255129.                                                      
                   Relative gap is 0.00%.                                                          

Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.RelativeGapTolerance = 0.0001 (the default value). The intcon
variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the default value).

Elapsed time is 0.197694 seconds.

sum(X)
ans =
        4878

INTLINPROG was surprisingly fast. I'll let you figure out what X means, and how it gives you the solution.