I run a heterosexual matching making service. I have my male clients and my female clients. I need to pair each of my clients with their "soul mate" based on several attributes (age, interests, personality types, race, height,horoscope, etc.)
After I create all my pairings, there will be some sort of score to grade the quality of my matches.
I can't match a man with multiple women or vice versa. I also want to minimize the number of unmatched clients.
What's the best algorithm to come up with a way to match my clients based on their attributes?
Again, this is a toy example. My actual use case is completely different.
The score is computed at the pair level and then summed. I can calculate how the score changes when I swap partners by looking at the new scores of two pairs. I do have access to the internals of the metric, but it's complicated. I don't have any constraints, other than I'd prefer it to be fast and simple for my own sanity.