Optimizing a matrix with cplexlp?

2019 6 3
3 个回答
回答已采纳
更新时间：2019 6 7
4 次查看（30 天）

0 个投票

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.

7 个评论
显示 5更早的评论 隐藏 5更早的评论

KSSV
KSSV 2019-6-6
What do you mean by optimum match no. beetween column numbers?
Raghunandan V
Raghunandan V 2019-6-6
You lost me here -
Optimum value is = 2 match.
are you explaning the matrix or the your algorithm in this line?
Berkay Sen
Berkay Sen 2019-6-6
编辑：Berkay Sen 2019-6-6
Hi KSSV,
I mean, how many matches can be made in this matrix?
In that example: optimum match number is 2 match
Thank you for your interest.
Berkay Sen
Berkay Sen 2019-6-6
编辑：Berkay Sen 2019-6-6
Hi Raghunandan,
I'm explaining algorithm in that line.
Any algorithm can suggest me these;
0 match
1 match with NO2-NO1
1 match with NO2 - NO3
1 match with NO4 - NO9
2 match with NO2 - NO3 and NO4- NO9
2 match with NO2 - NO1 and NO4- NO9
If algorithm is working perfectly(I mean algorithm can find optimum value, it must suggest me 2 match.
Thanks for your interest
Greg Heath
Greg Heath 2019-6-6
Sorry, cannot help.
Greg
Walter Roberson
Walter Roberson 2019-6-6
CPLEXLP is a third party product that is outside my experience.
Berkay Sen
Berkay Sen 2019-6-6
Hi Greg,
thank you anyway;
Hi Walter,
There is no restraction with solution way, its just a suggestion for solver. I can use MILP or any function, solver.
Thank you

请先登录，再进行评论。

请先登录，再回答此问题。

 采纳的回答

Stephan
Stephan 2019-6-6
编辑：Stephan 2019-6-6

1 个投票

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

1 个评论
显示 -1更早的评论 隐藏 -1更早的评论

Stephan
Stephan 2019-6-6
编辑：Stephan 2019-6-6
Note that the node numbers in the reduced graph have changed - you can fix this by naming the nodes. see documentation for more details.

请先登录，再进行评论。

更多回答（2 个）

Alan Weiss
Alan Weiss 2019-6-6

1 个投票

I really don't know, but it is possible that the matchpairs function might be applicable.
Alan Weiss
MATLAB mathematical toolbox documentation

3 个评论
显示 1更早的评论 隐藏 1更早的评论

Berkay Sen
Berkay Sen 2019-6-6
Hi Alan,
thank you for your great suggest.
But matchpairs doesn't working for me because matchpairs lookin rows(1. row, 2.row, 3.row...) and choosing best choise.
Imagine that,
No1 can match with No4,No5,No6;
But No2 can only match with No4,
And No3 can only match with No5
If matchpairs choose no4 because placement, then No2 can no longer match with anyone.
Same for no3-no5.
So algorithm must know this and choose NO6 for NO1.
I hope i could explain that :)
Christine Tobler
Christine Tobler 2019-6-6
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.
Berkay Sen
Berkay Sen 2019-6-6
Hi Christine, That's completely true, have you got any idea? Thank you for your comment

请先登录，再进行评论。

Christine Tobler
Christine Tobler 2019-6-6

1 个投票

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)
This code is inspired by this Sudoku solver example.

4 个评论
显示 2更早的评论 隐藏 2更早的评论

Berkay Sen
Berkay Sen 2019-6-6
Christine, you are awesome! I'm away from my computer right now. I'm dying to try this solution! Thanks also for your explanations!
Berkay Sen
Berkay Sen 2019-6-6
Christine,
I don't know how to thank you. Algorithm is running smoothly. You're superb!
Thank you to all who spent their time!
I'm gonna share the project(cross kidney transplant algorithm) when i finish it.
Christine Tobler
Christine Tobler 2019-6-6
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.
Berkay Sen
Berkay Sen 2019-6-7
Thanks but i've already adjust that. My matrix's diagonal is full of 0. It's working perfectly ?

请先登录，再进行评论。

类别

在 帮助中心 和 File Exchange 中查找有关 Solver Outputs and Iterative Display 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by