How can I model a submatrix with decision variables as indices ?

[Fleming]

Hi, guys.

I'm currently working on an optimization problem and I'm now having trouble in model a matrix with decision variables as indices.

Here are the details: both a and b are decision variables, M is a matrix with certainty, My questions is how can I define variables a and b and how can I model the submatrix M[(a:b), (a:b)].

Thanks for stopping by and I'm appreciated for your help!

[Johan Löfberg]

That's simply impossible, you cannot have variable length

You will have to formulate it another way. sum(x(a:b)) can for instance be defined as y being binary and y'*x, and then you use logic using implies to control that the elements of y are set to zero or 1 accordingly

[Johan Löfberg]

[Fleming]

Dear Johan, thank you for your reply. But I'm still confused about 'logic using implies' as you mentioned. Could you be a little more specific, an example if possible?

Many thanks in advance. 

[Johan Löfberg]

Here's an example. This is not necessarily the best way to model/solve the problem addressed here, but a direct simple binary model

% Select a range of numbers from x, to maximize sum(x(a:b))

n = 5;

x = randn(n,1);

intvar a b

y = binvar(n,1); % y(a:b) = 1, 0 otherwise

the_sum = x'*y;

a_i = binvar(n,1); % a_i(i) == 1 implies a = i

b_i = binvar(n,1); % b_i(i) == 1 implies b = i

Model = [sum(a_i)==1,sum(b_i)==1];

for i = 1:n    

Model = [Model, implies(a_i(i), a == i),

                implies(b_i(i), b == i)];

end

% If a = i, then y(i) = 1 and y(1:i-1)=0, if b=i, y(i) = 1, y(i+1:end)=0

for i = 1:n

Model = [Model,  

         implies(a_i(i), [y(i) == 1,y(1:i-1)==0]), 

         implies(b_i(i), [y(i) == 1,y(i+1:end)==0])]

end

% Some more stuff we know or must add

Model = [Model, sum(y) == b - a + 1, 1 <= a, a <= b, b <= n, y >= a_i,y >= b_i]  

optimize(Model,-the_sum)

value([a b])

value([a_i b_i y])

x

[Fleming]

Thanks Johan! One last tiny question: Are 'y >= a_i' and 'y >= b_i' compulsory? What's the purpose for mentioning them explicitly?

[Johan Löfberg]

in integer programming , one should add as much information as impossible about the integer variables, even if it is redundant

[Fleming]

Thanks Johan, your solution is very helpful~