23 views (last 30 days)

Hi to all,

I'm working on my graduating thesis what about cross kidney transplants matching algorithms.

I've a solution with genetic algorithm but i want to know 'what is the optimum?' (of course GA is %90-99 interval, not %100-optimum-)

So;

I have a binary matrix(also symetric)

for example=

1 2 3 4 5 6 7 8 9 10

1 [0 1 0 0 0 0 0 0 0 0

2 1 0 1 0 0 0 0 0 0 0

3 0 1 0 0 0 0 0 0 0 0

4 0 0 0 0 0 0 0 0 1 0

5 0 0 0 0 0 0 0 0 0 0

6 0 0 0 0 0 0 0 0 0 0

7 0 0 0 0 0 0 0 0 0 0

8 0 0 0 0 0 0 0 0 0 0

9 0 0 0 1 0 0 0 0 0 0

10 0 0 0 0 0 0 0 0 0 0]

I want to find optimum match number beetween column numbers. (How many matches can be made in this matrix?)

In this case; Possible matches are:

NO2 - NO1

NO2 - NO3

NO 4- NO9

But when NO2 was matched with NO1, it can no longer match with NO1. Its kinda monogamy.(If patient and donor NO2 exchanges kidneys with p and d NO1, of course NO2 can not exchange with NO3)

In this example, optimum match value is = 2.

Let's think about 1000*1000 matrix.

When i solve this matrix with genetic algortihm, i had 410 as a result. ( theoretical match number is 500 ((1000/2)), of course impossible.)

HOW CAN I SOLVE THIS MATRIX USING CPLEXLP OR MILP?(or something else solver)

I will be very pleased if anybody help,

Yours truly.

Stephan
on 6 Jun 2019

Edited: Stephan
on 6 Jun 2019

Hi,

you could think about using graphs for this job:

% your matrix

A = [0 1 0 0 0 0 0 0 0 0;

1 0 1 0 0 0 0 0 0 0;

0 1 0 0 0 0 0 0 0 0;

0 0 0 0 0 0 0 0 1 0;

0 0 0 0 0 0 0 0 0 0;

0 0 0 0 0 0 0 0 0 0;

0 0 0 0 0 0 0 0 0 0;

0 0 0 0 0 0 0 0 0 0;

0 0 0 1 0 0 0 0 0 0;

0 0 0 0 0 0 0 0 0 0];

% create a graph object

g = graph(A);

% plot graph

plot(g);

% remove nodes who have no matches / are unconnected

g = rmnode(g,find(degree(g)==0));

% count the number of different matches

result = numel(unique(conncomp(g)));

% plot resulting graph

hold on

plot(g)

hold off

Stephan
on 6 Jun 2019

Sign in to comment.

Alan Weiss
on 6 Jun 2019

Alan Weiss

MATLAB mathematical toolbox documentation

Christine Tobler
on 6 Jun 2019

Thank you for thinking of matchpairs, Alan. Unfortunately it wouldn't work for this case: Matchpairs will match rows of A to columns, but it doesn't have an understanding that if row i of A is matched, then column i of A is also unavailable for another match.

Basically, in matchpairs the rows and columns represent two different sets of resources to be matched up, while in this problem both rows and columns represent the same set of resources.

Sign in to comment.

Christine Tobler
on 6 Jun 2019

You can solve this using intlinprog. This is probably not the most efficient way of solving the problem, but reliable

A = [0 1 0 0 0 0 0 0 0 0;

1 0 1 0 0 0 0 0 0 0;

0 1 0 0 0 0 0 0 0 0;

0 0 0 0 0 0 0 0 1 0;

0 0 0 0 0 0 0 0 0 0;

0 0 0 0 0 0 0 0 0 0;

0 0 0 0 0 0 0 0 0 0;

0 0 0 0 0 0 0 0 0 0;

0 0 0 1 0 0 0 0 0 0;

0 0 0 0 0 0 0 0 0 0];

% Define an optimization variable: x(i,j) == 1 if (i, j) are matched, otherwise x(i, j) == 0

x = optimvar("x", size(A), "Type", "integer", "LowerBound", 0, "UpperBound", 1);

% Define an optimization problem

problem = optimproblem;

% Maximize the number of indices (i, j) for which A(i, j) == 1 and x(i, j) == 1

% (change sign because Objective is minimized in solve)

problem.Objective = -sum(sum(x.*A));

% Every column of x can only contain 1 non-zero (otherwise that column is matched to more than one row)

problem.Constraints.noDuplicates = sum(x, 1) == 1;

% Require x(i, j) == x(j, i)

problem.Constraints.symmetric = x == x';

% Solve the problem

s = solve(problem);

% Find indices i, j for which A(i, j) == 1 and s.x(i, j) == 1

[i, j] = find(triu(A & s.x))

% This returns i = [2; 4] and j = [3; 9], so two pairs (2, 3) and (4, 9)

Christine Tobler
on 6 Jun 2019

You're very welcome. I just realized you probably need an additional constraint:

% Require x(i, i) == 0

n = size(x, 1);

problem.Constraints.NonDiagonal = x(1:n+1:end) == 0;

This will prevent the solver from matching an index with itself.

Sign in to comment.

Sign in to answer this question.

Opportunities for recent engineering grads.

Apply Today
## 7 Comments

## Direct link to this comment

https://in.mathworks.com/matlabcentral/answers/465250-optimizing-a-matrix-with-cplexlp#comment_712051

⋮## Direct link to this comment

https://in.mathworks.com/matlabcentral/answers/465250-optimizing-a-matrix-with-cplexlp#comment_712051

## Direct link to this comment

https://in.mathworks.com/matlabcentral/answers/465250-optimizing-a-matrix-with-cplexlp#comment_712055

⋮## Direct link to this comment

https://in.mathworks.com/matlabcentral/answers/465250-optimizing-a-matrix-with-cplexlp#comment_712055

## Direct link to this comment

https://in.mathworks.com/matlabcentral/answers/465250-optimizing-a-matrix-with-cplexlp#comment_712056

⋮## Direct link to this comment

https://in.mathworks.com/matlabcentral/answers/465250-optimizing-a-matrix-with-cplexlp#comment_712056

## Direct link to this comment

https://in.mathworks.com/matlabcentral/answers/465250-optimizing-a-matrix-with-cplexlp#comment_712059

⋮## Direct link to this comment

https://in.mathworks.com/matlabcentral/answers/465250-optimizing-a-matrix-with-cplexlp#comment_712059

## Direct link to this comment

https://in.mathworks.com/matlabcentral/answers/465250-optimizing-a-matrix-with-cplexlp#comment_712100

⋮## Direct link to this comment

https://in.mathworks.com/matlabcentral/answers/465250-optimizing-a-matrix-with-cplexlp#comment_712100

## Direct link to this comment

https://in.mathworks.com/matlabcentral/answers/465250-optimizing-a-matrix-with-cplexlp#comment_712108

⋮## Direct link to this comment

https://in.mathworks.com/matlabcentral/answers/465250-optimizing-a-matrix-with-cplexlp#comment_712108

## Direct link to this comment

https://in.mathworks.com/matlabcentral/answers/465250-optimizing-a-matrix-with-cplexlp#comment_712317

⋮## Direct link to this comment

https://in.mathworks.com/matlabcentral/answers/465250-optimizing-a-matrix-with-cplexlp#comment_712317

Sign in to comment.