The QuBlog

Introduction

This is part 5 of a 5-part-series explaining how to solve optimization problems with the quantum-inspired optimization path in Azure Quantum. In part 1 you learned about the overall process for preparing, submitting, and post-processing optimization jobs. In part 2 we introduced Binary Quadratic Models (BQM), which are the tool to express cost functions representing the objective (the metric to be minimized) and constraints. In part 3 you learned how to write the cost functions for the business problem introduced in part 2. In part 4 you learned how to convert the cost function into code that could be submitted to an Azure Quantum optimization solver. In this article, we’ll bring everything together and convert the result returned by the optimization solver into a business representation.

You can find the complete sourcecode of the overall solution on GitHub: https://github.com/hsirtl/aq-qio-samples/tree/main/soccer-teams.

Recap

Let’s have a look on what we have so far.

The business problem

We started with a problem description consisting of a list of soccer players, and the challenge of assigning them to two teams of equal strength while ensuring that each team had one goalkeeper.

The list of players was specified as follows:

Table 1: the players

The Binary Quadratic Model and Cost Function

Basis for our BQM was following truth matrix indicating what player gets assigned to which team. E.g., \(x_0 = 1\) meant that Alice would be assigned to Team A etc.:

Table 2: truth table of player assignments

Based on the objective (teams of equal strength) and the constraints (each player in only one team; each team with one goalkeeper), we created following cost function:

$$ C = [\sum_{i \in [0,5]} (strength_i x_i) - EqualDist]^2 + [\sum_{i \in [6,11]} (strength_i x_i) - EqualDist]^2 + P(x_0x_6) + … $$

Implementation in Python

Then we implemented this cost function as a list of Term-objects in Python, submitted this list embedded in a Problem-object to Azure Quantum and got back a Result-object. The Configuration-object contained a series of \(0\)s and \(1\)s indicating value assignments to the variables in Table 2.

Interpreting the Result

Even though we have the optimization result, it is not immediately visible how this relates to the business scenario. Especially with more players and more than two teams it becomes hard to tell, which player gets assigned to which team. So, in a final step let’s decode the Configuration-object. Following code does exactly that:

def extractSolution(problemData, result):
    config = result.get("configuration")
    players = problemData.get("players")
    teams = problemData.get("teams")
    numberOfPlayers = len(players)
    numberOfTeams = len(problemData.get("teams"))
    solution = {}
    solution["teams"] = []

    for teamidx in range(numberOfTeams):
        team = {}
        team["name"] = teams[teamidx]
        teamplayers = []
        teamstrength = 0
        for playeridx in range(numberOfPlayers):
            if (config[str(playeridx + teamidx * numberOfPlayers)] == 1):
                teamplayers.append(players[playeridx])
                teamstrength = teamstrength + players[playeridx].get("strength")
        team["players"] = teamplayers
        team["strength"] = teamstrength
        solution["teams"].append(team)

    return solution

Decoding the Configuration-object

This function returns a JSON-object that contains the optimization solution in a more readable format.

{
  "teams": [
    {
      "name": "Alpha",
      "players": [
        { "id": 1, "name": "Alice",  "strength": 5, "isGoalkeeper": "False" },
        { "id": 3, "name": "Claire", "strength": 8, "isGoalkeeper": "True"  },
        { "id": 5, "name": "Eve",    "strength": 6, "isGoalkeeper": "False" }
      ],
      "strength": 19
    },
    {
      "name": "Beta",
      "players": [
        { "id": 2, "name": "Bob",   "strength": 6, "isGoalkeeper": "True"  },
        { "id": 4, "name": "Danny", "strength": 4, "isGoalkeeper": "False" },
        { "id": 6, "name": "Frank", "strength": 9, "isGoalkeeper": "False" }
      ],
      "strength": 19
    }
  ]
}

The optimization solution in a domain specific represenation

This representation makes it easy to tell what player gets assigned to which team, what overall strength each team has with the given player assignments. It also shows that each team has exactly one goalkeeper. With the objective achieved and all constraints satisfied we have a solution for our optimization problem.

Conclusion

With that, we have our goal achieved: an optimum soltution for our business challenge. The actual scenario was fairly simple. With only six players and two teams you could have easily solved this problem classically (or even with just a pen and a piece of paper). But imagine, you have 100 players and 10 teams. In such a scenario the number of assignments combinations is of magnitudes higher. Yet still an easy task to complete with an Azure Quantum optimization solver.

You’ll find the complete solution on GitHub. Just clone that repo and play around with larger sets of players and teams. Just change the content of the problem.json-file accordingly (e.g., add players, enter more teams, etc.) and execute the soccer-teams.py-script.