How to Solve Optimization Problems with Azure Quantum QIO (Part 2)

Learn how to identify objectives and constraints for an optimization scenario.

This is part 2 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 this part we’ll introduce Binary Quadratic Models (BQM), which are the tool to express cost functions representing the objective (the metric to be minimized) and constraints.

Introduction

As already stated in part 1, you cannot simply submit a business problem to Azure Quantum. You need to translate it first into a form that the optimization solvers can understand. This form is a Binary Quadratic Model (BQM).

Binary Quadratic Models (BQM)

But what is a BQM? Well, it’s a mathematical expression that is binary and quadratic. Binary means that all variables in that expression are binary (i.e. can only have one of two values). Quadratic means that each addend can only have two variables at max.

There are two types of BQM:

  • QUBO (quadratic unconstrained binary optimization) models: here, all variables \( x_i \in \lbrace 0, 1 \rbrace \)
  • Ising models: here, all variables \( x_i \in \lbrace -1, +1 \rbrace \)

Don’t worry too much about the difference of these two types. In fact, one can easily be converted into the other.

General Form of BQMs

Following is 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) $$

where \( a_{ij}, b_i, c \in \mathbb{Z} \) and \( x_i, x_j \in \lbrace 0, 1 \rbrace \) for QUBO and \( x_i, x_j \in \lbrace -1, 1 \rbrace \) for Ising. It has three parts: a quadratic part (the first addend), a linear part (the second) and a constant. The constant is often omitted because for finding the minimum it is irrelevant.

Sounds a bit abstract? Let’s have a look at an example:

$$ C = -9 x_0 -3 x_0 x_1 + 5 x_0 x_2 $$

This is a valid BQM. It’s a cost function that should be minimized. For Ising we’d like to assign the values \( \lbrace -1, 1 \rbrace \) to the variables \( x_0, x_1, \) and \( x_2 \) such that \( C \) becomes minimal, i.e., no other variable assignment would lead to a lower value for \( C \). For this example, the task is easy, and you probably have found the solution by just trying all combinations of variable assignments. Here it is:

$$ x_0 = 1, x_1 = 1, x_2 = -1 \Rightarrow C = -9 \cdot 1 -3 \cdot 1 \cdot 1 + 5 \cdot 1 \cdot -1 = -9 -3 -5 = -17 $$

For larger problems with 100.000 variables the task is no longer trivial. But that’s exactly the scenario, the Quantum Solvers in Azure Quantum are built for: you give them a potentially large equation and they will return a configuration representing the variable assignments.

Process for Defining a BQM

Let’s have a look at how to derive a BQM from a given problem statement taken from a sample scenario. We’ll conduct all necessary steps using that scenario.

Sample Scenario: Creating Soccer Teams

Imagine the following scenario. You are a soccer coach coaching 6 players. You know the strengths of each player and want to split the group into two teams with both having equal or as similar overall strength (i.e. sum of player’s strengths) as possible. In addition, two of the players are goalkeepers, i.e. they cannot be assigned to the same team (and, if we had to create more teams, each team would have to have one goalkeeper). Following table gives an overview of the players.

Player Strength Goalkeeper
Alice 5 no
Bob 6 yes
Claire 8 yes
Danny 4 no
Eve 6 no
Frank 9 no

Identify Objectives and Constraints

The first step for deriving a BQM is to get a clear picture of what the objective and constraints are. The objective is the metric that must be minimized. Constraints define conditions a solution must satisfy.

Let’s start with the objective. That’s pretty easy, as it is already stated in the scenario description: Both teams should be of equal (or similar) strength. So, the difference in overall strength should be minimized. That’s our metric.

In some cases, that’s it, and you can start by creating mathematical expressions for the BQM without any further constraints. Let’s see, if this is the case here. What about following two solutions:

Sample Solution 1:
Team A: Alice, Bob, Claire, Danny, Eve, Frank (overall strength: 38)
Team B: Alice, Bob, Claire, Danny, Eve, Frank (overall strength: 38)
Strength difference: 0

or

Sample Solution 2:
Team A: - (overall strength: 0)
Team B: - (overall strength: 0)
Strength difference: 0

If we had only our objective, both would be great solutions as the strength difference is 0. However, for sure you’ve noticed the problem of both: in solution 1, all players are assigned to both teams. In solution 2, no player is assigned. To avoid this, we need to add formal constraints. A first one would be: A player gets assigned to not more than one team.

Now, what about following solution?

Sample Solution 3:
Team A: Alice, Bob, Claire (overall strength: 19)
Team B: Danny, Eve, Frank (overall strength: 19)
Strength difference: 0

Our objective is achieved (no difference in overall strength) and the constraint is satisfied (each player is assigned to only one team). However, both goalkeepers - Bob and Claire - are assigned to team A. That’s not desired. So, we need another constraint: Each team must have exactly one goalkeeper.

With this, our scenario should be fully covered. You can write down the objective and final set of constraints as follows:

  • Objective: Minimize the difference of overall strength of both teams
  • Constraints:
    • A player gets assigned to not more than one team.
    • A team must have exactly one goalkeeper.

You could add another constraint for getting teams of equal size (both teams with 3 players). However, in real life you might have a super-skilled player in one team, requiring more players in the other team to get same overall strength of both teams.

In part 3 of this blog series, we’ll continue our effort by converting the objectives and constraints into binary math expressions. Ultimately, these will then be the components of the BQM.

For diving deeper into this topic, I’d recommend following resources:

Web Resources

Whitepapers