Suggestions for Matchmaking Algorithm 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.  

Edit:

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.
Although you might find a way to apply machine learning (ML) to this optimisation problem, it does not look necessary, and is probably a distraction. ML might help if the scoring system was complex or if you had incomplete data for most matches, and needed to compute matching score estimates from some more limited set of attributes.

Instead here you seem to have a combinatorial optimisation problem. A well known example of this is the Travelling Salesman Problem. 

There are many possible algorithms to attack these kinds of problem. Which to choose may depend on other traits of the data, such as how quickly you can calculate the scores - both for the whole set and for individual changes. If calculating for changes is fast enough, you can use optimisers that work from a complete (but not yet optimal) solution and make changes.

There is a free PDF/book called Clever Algorithms (Nature-Inspired Programming Recipes) covering selection choice amongst all the varied optimisers. This may allow you to find something optimal in terms of speed and reliability of algorithm.

Here's a simple thing you could try though


Create a "greedy" solution


Shuffle one set of items that need to be paired
For each item in turn, pair it with the best scoring partner
Calculate the score for this solution

Refine the solution


Sample some subset of pairs (e.g. 2, 3, 4, 5 pairs). You could do this deterministically for small enough dataset, or stochastically, or use some algorithm to filter to "at least has some chance of improving".
Find the best score amongst all permutations in this small subset (i.e. brute force all 24 pairings amongst 4 couples)
Put the best subset back into the solution
Repeat until no improvement found after some number of tests



This routine can be altered in various ways to take advantage of aspects of your problem. A nice thing in your case, making this easier that the Travelling Salesman Problem, is that you don't have any constraints on valid pairings. In TSP you care about making a single circuit, and not multiple separate loops which limits how you can make changes, whilst in your case each of your pairs is entirely separate.

One example of possible algorithm improvement: You could pre-calculate the scores for the top N matches for each person, and only search amongst those when considering local changes.