Finding the minimum cost of a matrix

Suppose i have cost matrix M= [ 100 250 300 400

600 900 400 300

250 300 160 190].

The size of matrix 3x4. Let column represent machines and row represent worker.I want to minimize cost Matrix M. Each column should have only one cost. I didn't want to use matchpair function.

How can i use intlinprog function of Matlab for minimization cost?

[Danish Nasir]

I tried to run on a balanced matrix M=[ 600 670 960 560

900 280 970 540

310 350 950 820

325 290 600 540 ]

f = M(:)' ;

T=size(M,1)

y=eye(T);

Aeq=[y y y y];

d=length(Aeq)

beq = ones(T,1);

[x ,fval]=intlinprog(f,1:d,[],[],Aeq,beq,zeros(d,1),inf(d,1));

find(x);

But the code gives answer x is 3 6 8 13 and fval=1440 which is incorrect.

The correct answer is x=3 6 12 13 and fval=1750.

Can you suggest the error in code?

Note: the above matrix M given as example in Matchpair function in Matlab

[Abolfazl Chaman Motlagh]

your constraints are wrong for this problem. as you can see in the solutions 6 and 8 means worker 2 and 4 are simultaneusly work on machine 2. in a symmetric model as you mentioned balanced the other constraint should be added :

which means just 1 worker can work on every machine. including this you have 4+4 constraints (4 before):

you can create these 4 constraints by :

Aeq = [ ones(1,4) zeros(1,12);
    zeros(1,4) ones(1,4) zeros(1,8);
    zeros(1,8) ones(1,4) zeros(1,4);
    zeros(1,12) ones(1,4);
    1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0;
    0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0;
    0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0;
    0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1];

if you get the solution, you can easily create 4 first row with this:

kron(eye(4),ones(1,4))

ans = 4×16

1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1

and 4 second row with this:

kron(ones(1,4),eye(4))

ans = 4×16

1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1

[Danish Nasir]

I want to generalize the code i.e. a) when machine and worker are equal and each worker can work on only one machine b) when workers are more than machine ,hence some workers remain idle c) when workers are less than machines , hence some machines remain idle.

Can you provide single code which caters to all 3 scenarios?

Note: case a is a balanced matrix , case b unbalanced with rows>columns , case c unbalanced with rows<columns.

[Abolfazl Chaman Motlagh]

sure, i add generall method in comment of Accepted answer. give me some time to write it clear and properly.

[Danish Nasir]

Thanx for the help.

Please remember that output of the code (minimize cost) will be such that "any size matrix can be given as an input to the code".

Answer 1

[Abolfazl Chaman Motlagh]

If i get that right, you have an assignment task.

so you want to solve this :

your constraint should be :

which i represent machines, and j represent workers. you have 3 workers and 4 machines. hence the constraints are not symmetric.

you also need boundery conditions.

i am going to linearize 2d index of x_i,j to a vector so we have

finally :

M= [ 100 250 300 400;
     600 900 400 300;
     250 300 160 190];
f = M(:)' ;
Aeq = [ 1 0 0 1 0 0 1 0 0 1 0 0;
        0 1 0 0 1 0 0 1 0 0 1 0;
        0 0 1 0 0 1 0 0 1 0 0 1];
beq = ones(3,1);
x = intlinprog(f,1:12,[],[],Aeq,beq,zeros(12,1),inf(12,1));

LP:                Optimal objective value is 560.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).

find(x)

ans = 3×1

1 9 11

which means X11 = 1, X33=1, X42=1.

and that means : the worker 1 assign to machie 1, worker 2 assign to machine 4, and worker 3 assign to machine 3.

[Abolfazl Chaman Motlagh]

General Solution : Given mxn Matrix of Cost Coefficients.

m represent number of workers. and index i represent i-th worker.

n represent number of machines. and index j represent j-th machine.

3 different situation could happend:

• m=n . workers are equal to machines.

in this case we need both constraints for limit workers to work somewhere and workers to work exactly on one machine :

Aeq = [ kron(eye(m),ones(1,m)); 
    kron(ones(1,m),eye(m))];
beq = ones(2*m,1);      % m=n , so m+n is 2m

• m<n . workers are less than machines.

in this case we need a set of constraints to limit workers to work exactly on one machine. ( so n-m machine remain without any worker):

Aeq = kron(ones(1,n),eye(m));
beq = ones(m,1);

• m>n. workers are more than machines.

in this case, similar to previous we need a set of constraints to limit machines to have exactly one worker. ( so m-n workers won't do anything):

Aeq = kron(eye(n),ones(1,m));
beq = ones(n,1);

Hence :

f = M(:)';
x = intlinprog(f,1:m*n,[],[],Aeq,beq,zeros(m*n,1),inf(m*n,1));
ind = find(x);

you can find index of worker and machine by using :

[worker_index machine_index] = ind2sun([m n],ind);

means worker_index(k) are working on machine_index(k) for all k.

for formulation of problem see accepted answer and comments below the original question.

[Danish Nasir]

Suppose M= [30187 18877 45543 43822

31457 19802 46460 45501

33977 21638 48279 48831

35815 22274 50330 52160

36817 23199 54771 52584 ]

In this case m=5,n=4

The code is

T1=size(M,1)

T2=size(M,2)

if T1==T2

Aeq = [ kron(eye(T1),ones(1,T1));

kron(ones(1,T1),eye(T1))];

beq = ones(2*T1,1); % m=n , so m+n is 2m

elseif T1<T2

Aeq = kron(ones(1,T2),eye(T1));

beq = ones(T1,1);

elseif T1>T2

Aeq = kron(eye(T2),ones(1,T1));

beq = ones(T2,1);

end

f = M(:)';

[x,fval] = intlinprog(f,1:T1*T2,[],[],Aeq,beq,zeros(T1*T2,1),inf(T1*T2,1));

ind = find(x);

[worker_index machine_index] = ind2sub([T1 T2],ind)

When i run the code,the worker_index coming out as 1 1 1 1 and machine_index=1 2 3 4.

Pls check why the error coming in index when m>n?

[Danish Nasir]

M=[1 2 3 5 6 ; 13 3 5 6 4 ; 2 3 15 4 3; 1 3 15 13 3;13 14 23 2 3 ;2 14 13 12 3]

The code gives results as worker_index =4 1 1 5 6 & machine_index= 1 2 3 4 5

As can be seen worker 1 assigned to two machines.

Pls check.

[Abolfazl Chaman Motlagh]

yes, i'am sorry. i forgot to include constraints for ensure than workers are not having more than one job, and machines have more than one workers. here is complete solution. i hope it doesn't have any problem:

M= [30187,18877,45543,43822;
31457,19802,46460,45501;
33977,21638,48279,48831;
35815,22274,50330,52160;
36817,23199,54771,52584]; % for example

[m n] = size(M);
f = M(:)';
if m==n
    Aeq = [ kron(eye(m),ones(1,m)); 
            kron(ones(1,m),eye(m))];
    beq = ones(2*m,1);
    x = intlinprog(f,1:m*n,[],[],Aeq,beq,zeros(m*n,1),ones(m*n,1));
elseif m>n
    Aeq = kron(eye(n),ones(1,m));
    beq = ones(n,1);
    A = kron(ones(1,n),eye(m));
    b = ones(m,1);
    x = intlinprog(f,1:m*n,A,b,Aeq,beq,zeros(m*n,1),ones(m*n,1));
else  %(m<n)
    Aeq = kron(ones(1,n),eye(m));
    beq = ones(m,1);
    A = kron(eye(n),ones(1,m));
    b = ones(n,1);
    x = intlinprog(f,1:m*n,A,b,Aeq,beq,zeros(m*n,1),ones(m*n,1));
end
ind = find(x);
[worker_index machine_index] = ind2sub([m n],ind);

in 2rd and 3rd cases i add an inequality to make sum of machines for each worker be less than 1(m>n), and some of worker on each machine be less than 1(m<n).

[Danish Nasir]

Thanx for the help. The code is working.