How to Solve Optimization Problems with Azure Quantum QIO (Part 4)
Learn how to submit your cost function (QUBO or Ising) to an optimization solver.
This is part 4 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 this article learn how to convert the cost function into code that can be submitted to an Azure Quantum optimization solver.
You can find the complete sourcecode of the overall solution on GitHub: https://github.com/hsirtl/aq-qio-samples/tree/main/soccer-teams.
Prepare the Environment in Azure
We’ll implement the cost function as Azure Quantum jobs in Python and will submit the job to an Azure Quantum workspace. Perform following steps to setup your environment:
- Get an Azure Account
- Install the Azure Command Line Interface (CLI)
- Create an Azure Quantum workspace
- Install the
azure-quantumPython package
After the quantum workspace is generated take note of following information as we need it for authenticating at the workspace:
- Subscription ID (format similar to
XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXX) - Resource group name
- Name of the workspace
- Location of the workspace (e.g.,
eastus)
In your project directory create a file called appsettings.json containing following JSON-code and replace the placeholders with your values.
{
"workspace" : {
"subscription_id": "<YOUR_SUBSCRIPTION_ID>",
"resource_group": "<YOUR_RESOURCE_GROUP_NAME>",
"name": "<YOUR_WORKSPACE_NAME>",
"location": "<YOUR_WORKSPACE_REGION>"
}
}
Template for your appsettings.json-config file containing authentication information
Implement the Cost Function as a Azure QIO Job
So far, we have created a binary quadratic model (BQM) for our business problem, the assignment of soccer players to teams. Objective was to get teams of equal strength. Constraints were that a given player can only be assigned to one team and each team can only have one goalkeeper.
For getting a solution for this optimization challenge, we need a Python program that performs following steps:
- Read the problem specification from a file
- Create the cost function as a list of
terms - Submit the cost function as an optimization job to an Azure Quantum optimization solver
- Get the job result
- Extract the solution from the result object
The sample-GitHub-repo contains a template file template.py that contains already empty methods that we’ll fill with necessary code in following sections.
Read the problem specification from a file
First, let’s create a file that contains our problem specification as a JSON-object. The file should look like the following:
{
"problem": {
"type": "soccer-teams",
"data": {
"teams": ["Alpha", "Beta"],
"players" : [
{ "id": 1, "name": "Alice", "strength": 5, "isGoalkeeper": "False" },
{ "id": 2, "name": "Bob", "strength": 6, "isGoalkeeper": "True" },
{ "id": 3, "name": "Claire", "strength": 8, "isGoalkeeper": "True" },
{ "id": 4, "name": "Danny", "strength": 4, "isGoalkeeper": "False" },
{ "id": 5, "name": "Eve", "strength": 6, "isGoalkeeper": "False" },
{ "id": 6, "name": "Frank", "strength": 9, "isGoalkeeper": "False" }
]
}
}
}
The problem specification as a JSON-object
Name that file problem.json. It contains a list of teams and a list of player objects. Players are described with ids, names, strengths and a boolean value indicating, if the respective player is a goalkeeper. The template.py script already contains a function that imports this problem spec and stores it in a variable called problemData.
def getProblemData():
with open('problem.json') as f:
problemJson = json.load(f)
problemData = problemJson.get("problem").get("data")
return problemData
Function for reading the problem specification
Create Cost Function Terms for the Problem
Let’s repeat what we learned about the general form of a BQM:
$$ min \left( \sum_{i}\sum_{j>i} a_{ij} x_i x_j + \sum_{i} b_i x_i + c \right) $$
So, at the end, a BQM is a big sum of products. Some of these products have a coefficient and two binary variables (\(a_{ij} x_i x_j\)), some have one coefficient and one binary variable (\(b_i x_i\)) and some have only the coefficient (which can be aggregated to one constant \(c\)). When implementing these in Python, each product is represented by a Term-object. This object has two arguments: a coefficient (a Float) and a list of indices (each an Integer).
Example: The term \(5 x_0 x_1)\) will be implemented as Term(c = 5, indices [0,1]).
Our cost function will then be implemented as a list of Term-objects, i.e. costFunction: List[Term].
Create Terms for the Objective
def getObjectiveTerms(problemData) -> List[Term]:
terms: List[Term] = []
players = problemData.get("players")
numberOfTeams = len(problemData.get("teams"))
numberOfPlayers = len(problemData.get("players"))
strengths = [player.get("strength") for player in players]
for team in range(numberOfTeams):
teamTerms = getHamiltonianForSumOfWeights([i for i in range(team * numberOfPlayers, team * numberOfPlayers + numberOfPlayers)], strengths, sum(strengths) / numberOfTeams)
terms.extend(teamTerms)
return terms
Function for creating Terms for the objective
def getHamiltonianForSumOfWeights(listOfIndices, listOfWeights, sumOfWeights) -> List[Term]:
numOfIndices = len(listOfIndices)
terms: List[Term] = []
for i in range(numOfIndices):
terms.append(Term(c = 2 * listOfWeights[i] * listOfWeights[i], indices = [listOfIndices[i], listOfIndices[i]]))
for i in range(numOfIndices-1):
for j in range(i+1, numOfIndices):
terms.append(Term(c = 2 * listOfWeights[i] * listOfWeights[j], indices = [listOfIndices[i], listOfIndices[j]]))
for i in range(numOfIndices):
terms.append(Term(c = - 2 * sumOfWeights * listOfWeights[i] - 2 * listOfWeights[i] * listOfWeights[i], indices = [listOfIndices[i]]))
return terms
Function for creating Terms minimizing variance of a sum from a certain value
Create Terms for the Constraints
Let’s first introduce a helper function that returns Terms for ensuring that at max only one of two indices can be \(1\).
def getMaxOneOutOfTwoTerms(i, j, penalty):
terms = []
terms.append ( Term ( c = penalty, indices = [ i , j ] ) )
return terms
Function for creating Terms ensuring that from two indices only one can be 1
This function is useful for our next function. getOnePlayerInOneTeamConstraintTerms creates Term-objects that ensure that all players are only assigned to one team each.
def getOnePlayerInOneTeamConstraintTerms(problemData):
terms = []
players = problemData.get("players")
numberOfTeams = len(problemData.get("teams"))
numberOfPlayers = len(players)
penalty = 100
for i in range(numberOfPlayers):
for j in range(numberOfTeams - 1):
for k in range(j + 1, numberOfTeams):
idx1 = j * numberOfPlayers + i
idx2 = k * numberOfPlayers + i
terms.extend(getMaxOneOutOfTwoTerms(idx1, idx2, penalty))
return terms
Function for creating Terms ensuring that a player is only assigned to one team
Now to the second constraint: following function creates Term-objects indicating that a team can have only one goalkeeper. Let’s keep the function as general as possible, so let’s not just focus on the special case of two goalkeepers but let the function find out, who the goalkeepers are and keep them separated from each other.
def getOneGoalkeeperPerTeamTerms(problemData):
terms = []
players = problemData.get("players")
numberOfTeams = len(problemData.get("teams"))
numberOfPlayers = len(players)
goalkeeperIndices = []
penalty = 100
for i in range(numberOfPlayers):
if players[i].get("isGoalkeeper") == "True":
goalkeeperIndices.append(i)
for team in range(numberOfTeams):
for i in range(len(goalkeeperIndices) - 1):
for j in range(i + 1, len(goalkeeperIndices)):
idx1 = team * numberOfPlayers + goalkeeperIndices[i]
idx2 = team * numberOfPlayers + goalkeeperIndices[j]
terms.extend(getMaxOneOutOfTwoTerms(idx1, idx2, penalty))
return terms
Function for creating Terms ensuring that a team has only one goalkeeper
Now, we can finally implement the cost function by subsequently calling the functions above to create a longer list of Term-objects.
def createCostFunction(problemData):
terms = []
objectiveTerms = getObjectiveTerms(problemData)
terms.extend(objectiveTerms)
constraintTerms = getOnePlayerInOneTeamConstraintTerms(problemData)
terms.extend(constraintTerms)
constraintTerms = getOneGoalkeeperPerTeamTerms(problemData)
terms.extend(constraintTerms)
return terms
Function for assembling the cost function Terms
With that, we have completed the most difficult task on our side: creating a list of Terms representing our cost function. Now, we just need to send this to the Azure Quantum service for assigning values to the binary variables so that the overall function has its minimum value.
Submit the Job
For submitting our problem to Azure Quantum, we need two instantiate objects:
- A
Problem-object, containing the name of the optimization job, the problem type (QUBO or Ising) and the cost function (the list ofTerm-objects we created above). - A
Solver-object, specifying the optimization solver to use with some initialization parameters.
Following code creates these two objects and submits the problem to the chosen optimization solver. Here, a Simulated Annealing solver running in an FPGA-environment is used. Other solvers are available.
problem = Problem(name="problem", problem_type=ProblemType.pubo, terms=terms)
solver = SimulatedAnnealing(workspace, platform=HardwarePlatform.FPGA, timeout=5)
job = solver.submit(problem)
job.refresh()
Job submission code
The last line makes the Python-script wait for the job completion.
Retreive the Job Result
The next step is easy: after the job completes, we can retrieve the optimization result as follows.
result = job.get_results()
Retreiving the optimization result
Unfortunately, the result is not in a format that directly maps to our business problem. In fact, the result object only contains a couple of technical metrics and a configuration-object. That object is the interesting part: it is a series of \(0\) and \(1\) values telling us, which binary variable should be assigned the value \(0\) (or \(1\) respectively) for getting the minimum value of our cost function.
{
"version": "1.0",
"configuration": {
"0": 1,"1": 0,"2": 1,"3": 0,"4": 1,"5": 0,"6": 0,"7": 1,"8": 0,"9": 1,"10": 0,"11": 1
},
"cost": -980.0,
"parameters": {
"beta_start": 0.000776,
"beta_stop": 0.498733,
"restarts": 216,
"sweeps": 100
},
"solutions": [
{
"configuration": {
"0": 1,"1": 0,"2": 1,"3": 0,"4": 1,"5": 0,"6": 0,"7": 1,"8": 0,"9": 1,"10": 0,"11": 1
},
"cost": -980.0
}
]
}
Optimization result
So, the solver will not directly tell you, what player to assign to which team. Reason for this is, that the solver has no understanding of the business problem, or concepts like ’teams’, ‘players’, ‘strengths’, ‘goalkeepers’. We encoded these concepts in a list of Term-objects, and this is the only thing, the optimizer cares about. And that’s the only thing we actually send to Azure Quantum.
For our cost function this means that we now have the variable assignments derived from the configuration-object in the Result:
$$ x_0=1, x_1=0, x_2=1, x_3=0, x_4=1, x_5=0, x_6=0,\ … $$
These variable assignments lead to a minimum value of \(-980.0\) for our cost function.
In part 5 of this blog series, we’ll convert this result into a format that maps to our business problem. I.e., we’ll finally get the answer to our question of what player to assign to which team.
Recommended Resources
For diving deeper into this topic, I’d recommend following resources: