Optimize and pairing

Hi,

I have a bunch of subjects that I need to pair them up in a group of 2, but some subjects cannot be paired with some of them, the relationships between them is attached: The cells "FAIL" means that they cannot be paired together, e.g.: No6 and No3 cannot be paired together.

The subjects cannot be repeated in multiple pairs, i.e. if No7 is paired with No9, No7 cannot be paired with No1, No2, etc...

Are there any ways to optimize the pairing with the maximum number of pairs as an outcome?

Thank you so much!

Dexter

The Solver tool (a standard add-in installed with Excel, but not activated) could be used for that.
If you are not familiar and don't have it installed (check far right part of Data Ribbon) start with: https://support.office.com/en-us/art...c-e24772f078ca

See how I did it in attached file.

I used A13:B17 as variables for the solver model.
Wrote there numbers from 1 to 10.
In solver I added condition, that the values in this range have to be all unique
Then in column C added checking if the pair in columns A and B is allowed (C13 and copy down):

Formula:

Please Login or Register  to view this content.

In C18 I added formula checking how many allowed pairs were selected:

Formula:

Please Login or Register  to view this content.

and set this cell as an aim for the solver (maximizing the value of C18).
Then I selected Solving method as Evolutionary (as the problem is of discrete nature) and run Solver

The conditions were not very tight (there are many allowed pairs), so very quickly Solver ended up with 5 pairs solution.

We could end up here as the task is done, but I added some bells and whistles like conditional formatting to show which pairs were selected in the original matrix. Selected B2:K11 and used conditional formatting with rule based on formula:

Formula:

Please Login or Register  to view this content.

formula in D13 copied down and right:

Formula:

Please Login or Register  to view this content.

And another conditional formatting - for range: D13:E17 based on formula:

Formula:

Please Login or Register  to view this content.

Write some starting numbers (like below) in A13:B17 and use Solver yourself. The solution will be probably different, but shall not be worse :-)
1 2
3 4
5 6
7 8
9 10