create matrix of integers with specified sum in column and row

I want to create a 4x4 matrix of integers such that:-

Say, M=[ A B C D ; E F G H ; I J K L ; M N O P ]

A+B+C+D>=value from user

A+B+C+D<=value from user

A+E+I+M>=value from user

A+E+I+M<=value from user

and likewise for all columns and rows.

[Rik]

What have you tried?

Also, don't forget that this might not be possible for some values provided by the user.

Answer 1

[Matt J]

You can try to formulate it as an integer program.

M=optimvar('M',[4,4],'type','integer');

Constraints.columns=sum(M,1)<=colvalues;
Constraints.rows=sum(M,2)<=rowvalues;

prob=optimproblem('Objective', 0,'Constraints',Constraints );

sol=solve(prob)

[Zaid Ali Basharat]

I have tried this:-

M=optimvar('M',[4,4],'type','integer');
colvalues=[21 24 34 28];
rowvalues=[7 6 9 11]';
Constraints.columns=sum(M,1)<=colvalues;
Constraints.rows=sum(M,2)<=rowvalues;
prob=optimproblem('Objective', 0,'Constraints',Constraints );
sol=solve(prob)

And got this output:-

>> test
LP:                Optimal objective value is 0.000000.                                             
Optimal solution found.
Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value,
options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance,
options.IntegerTolerance = 1e-05 (the default value).
sol = 
  struct with fields:
    M: [4×4 double]

I could not find the output Matrix. I opened struct M but it is filled with 'inf' values.

[Matt J]

You also need lower bounds, don't you?

Constraints.columns=[sum(M,1)<=upper_colvalues;  sum(M,1)>=lower_colvalues]

and similarly for the rows.

[Zaid Ali Basharat]

clc;
clear;
clear all;
M=optimvar('M',[4,4],'type','integer');
upper_colvalues=[12 12 12 12];
lower_colvalues=[6 6 6 6];
upper_rowvalues=[40 40 40 40]';
lower_rowvalues=[20 20 20 20]';
Constraints.columns=[sum(M,1)<=upper_colvalues; sum(M,1)>=lower_colvalues];
Constraints.rows=[sum(M,2)<=upper_rowvalues; sum(M,2)>=lower_rowvalues];
prob=optimproblem('Objective', 0,'Constraints',Constraints );
sol=solve(prob);

Please check if this is the write code. I have also tried:-

Constraints.columns=sum(M,1)<=upper_colvalues; 
Constraints.columns=sum(M,1)>=lower_colvalues;

But then it gives upper_colvalues and lower_colvalues with 'inf' entries.

[Rik]

This time I edited your post for you. Next time, please use the tools explained on this page to make your posts more readable.

Also, you should not be using clear all. clear will already clear all normal variables.

[Matt J]

Here's what I get,

M=optimvar('M',[4,4],'type','integer');
upper_colvalues=[12 12 12 12];
lower_colvalues=[6 6 6 6];
upper_rowvalues=[40 40 40 40]';
lower_rowvalues=[20 20 20 20]';
Constraints.columnsUB= sum(M,1)<=upper_colvalues;
Constraints.columnsLB= sum(M,1)>=lower_colvalues;
Constraints.rowsUB = sum(M,2)<=upper_rowvalues;
Constraints.rowsLB = sum(M,2)>=lower_rowvalues;
prob=optimproblem('Objective', 0,'Constraints',Constraints );
sol=solve(prob)

Solving problem using intlinprog.

No feasible solution found.

Intlinprog stopped because no point satisfies the constraints.

sol = struct with fields:
    M: []

But if we enlarge upper_colvalues,

Constraints.columnsUB = sum(M,1)<=[12 12 12 12]*4;

>> sol.M

ans =

     0     0     0    20
     0     0     0    20
     0     0    20     0
     6     6     0     8

[Zaid Ali Basharat]

UPDATE: I can have float values as well. Integer is not necessary. Can we have solution without enlarging values?

[Matt J]

You can try removing the integer constraint and see what you get.

[Zaid Ali Basharat]

I made these changes and got this:-

M=optimvar('M',[4,4],'type','continuous');
upper_colvalues=[12 12 12 12]*4;

>> sol.M

ans =

    20     0     0     0
     0     0     0    20
     0     0     0    20
     0     6     6     8

[Matt J]

problem solved?

[Zaid Ali Basharat]

No. I am getting more zero values and also these are again integers. I mean this is not the optimal solution

[Zaid Ali Basharat]

Let me restate the question:-

User will input lower and upper bound values for each row and column in a 4x2 matrix each.

I need to create a 4x4 matrix such that the sum of each row is inside the range defined by the user and likewise for each column.

[Matt J]

No. I am getting more zero values and also these are again integers. I mean this is not the optimal solution.

Integers are not forbidden and zeros are not forbidden, based on what you've told us. What is sub-optimal about the solution?

[Zaid Ali Basharat]

OUTPUT USER INPUTS

2 7 9 6 = 26 20-30

8 9 10 11 = 38 30-40

3 5 1 0 = 9 5-15

4 8 2 4 = 18 15-20

= = = =

17 29 22 21

10-25 8-30 22-40 15-30

This is the kind of output I want for given input ranges.

[Matt J]

Your example doesn't clarify what you see as wrong with the solution given by solve(). Are you saying you don't believe the input ranges were satisfied. That is fairly easy to test.

M=optimvar('M',[4,4]);

upper_colvalues=[12 12 12 12]*4;
lower_colvalues=[6 6 6 6];
upper_rowvalues=[40 40 40 40]';
lower_rowvalues=[20 20 20 20]';

Constraints.columnsUB= sum(M,1)<=upper_colvalues;
Constraints.columnsLB= sum(M,1)>=lower_colvalues;
Constraints.rowsUB = sum(M,2)<=upper_rowvalues;
Constraints.rowsLB = sum(M,2)>=lower_rowvalues;

prob=optimproblem('Objective', 0,'Constraints',Constraints );
sol=solve(prob); sol.M,

Solving problem using linprog.

Optimal solution found.

ans = 4×4

20 0 0 0 0 0 0 20 0 0 0 20 0 6 6 8

The bounds look well-satisfied to me:

column_check =[lower_colvalues;sum(sol.M,1); upper_colvalues],

column_check = 3×4

6 6 6 6 20 6 6 48 48 48 48 48

row_check =[lower_rowvalues,sum(sol.M,2), upper_rowvalues].'

row_check = 3×4

20 20 20 20 20 20 20 20 40 40 40 40

[Zaid Ali Basharat]

Ok now I got what I wanted but is there anyway we can do it without exapnding the upper column values?

[Matt J]

The solver will tell you if it is possible for the given set of input ranges. If it returns. sol.M=[], then it is not possible.