Find optimal of function with 3D input

Hi,

I am currently working on an optimization problem, but I am not sure on how to proceed. I have computed a 3D array with scores (say 10x10x10). Now I want to find the optimal x (10x10x10) which consists of only 1's and 0's such that the sum of the individual elements of

scores .* x

is maximal.

The only constraint is that there can only be one 1 in every dimension of x. That is, the following must be satisfied:

all(sum(x, 1) <= 1)
all(sum(x, 2) <= 1)
all(sum(x, 3) <= 1)

I have been looking at applying fmincon, but I get the idea that it only works for x as a scalar, vector or matrix. I could flatten x to a vector, but then I am not certain if the constraining would still work.

Does anybody has some pointers for me? Any help is welcome.

Thank you.

Robert

Answer 1

[Matt J]

None of the solvers care what the dimensions of your unknown variable array x is. The problem with fmincon is that doesn't support binary constraints. You could use intlinprog, but the new problem-based optimization framework might make setting up the problem easier here.

 x=optimvar('x',[10,10,10],'LowerBound',0,'UpperBound',1,'Type','integer');

 prob=optimproblem('ObjectiveSense','max','Objective', scores(:).'*x(:));

     prob.Constraints.con1=sum(x,1)<=1;
     prob.Constraints.con2=sum(x,2)<=1;
     prob.Constraints.con3=sum(x,3)<=1;

 [sol,fval] = solve(prob);

[Robert Vullings]

Thank you for the comment. Having looked up the documentation, it seems to be a good solution to this problem. The only issue is that I only have access to 2016b and the functionality is added in 2017b.

Would using intlinprog work, like you suggested? The documentation claims that f, x, intcon, b, beq, lb, and ub should be vectors (https://nl.mathworks.com/help/optim/ug/intlinprog.html#outputarg_x).

[Matt J]

I've used prob2struct() to convert the optimproblem object to a struct compatible with intlinprog (see attached .mat file).

You can just do

intlinprog(s)

but first make the replacement s.f=scores.