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

Learn how to convert objectives and constraints into binary math expressions.

This is part 3 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 this article learn how to write the cost functions for the business problem introduced in part 2.

Convert Objectives and Constraints into Binary Math Expressions

Define the Meaning of the Binary Variables

As stated above, a BQM contains binary variables \( x_0, x_1, … \in \lbrace 0, 1 \rbrace \) (for QUBO). We now need to define what these variables represent in the scenario context. I.e., what does it mean, if \( x_i = 0 \) vs. \( x_i = 1 \)?

For our scenario we could use following matrix for support:

Player Team A Team B
Alice \( x_0 \) \( x_6 \)
Bob \( x_1 \) \( x_7 \)
Claire \( x_2 \) \( x_8 \)
Danny \( x_3 \) \( x_9 \)
Eve \( x_4 \) \( x_{10} \)
Frank \( x_5 \) \( x_{11} \)

To give an answer to the question: \( x_i = 1 \) means that the player of the respective row is assigned to the team indicated by the column, \( x_i = 0 \) otherwise. E.g., \( x_0 = 1 \) means that Alice is assigned to team A.

With the objective, relevant constraints, and an understanding of what the binary variables represent, we have everything prepared for formulating actual math expressions. These expressions then will lead us to a mathematical representation of the BQM.

Formulate the Objective Function

Let’s start with the objective function. If we were focusing on just creating two teams, we could use a function like this:

$$ Objective = [ ( overall\ strength\ team\ A ) - ( overall\ strength\ team\ B ) ]^2 $$

It represents our goal of minimizing the strength difference of both teams. We need to square the expression because without it a solver could assign all players to team B for getting a low value for \( Objective \) (a large negative number). So, \( Objective \) only becomes \( 0 \), if both teams are of equal strength. However, we’d like to create a more general solution that supports the creation of more than two teams. In this case we need to look at each team and aim for minimizing its variance from \(EqualDist\). \(EqualDist\) is the overall strength of all players divided by the number of teams.

$$ Objective = \sum_{i} ( {overall\ strength\ of\ team\ i} - {EqualDist} )^2 $$

In case of two teams we get…

$$ Objective = O_0 + O_1 $$

with

$$ O_0 = [\sum_{i \in [0,5]} (strength_i x_i) - EqualDist]^2 = [ ( 5x_0 + 6x_1 + 8x_2 + 4x_3 + 6x_4 + 9x_5 ) - EqualDist ]^2 $$

$$ O_1 = [\sum_{i \in [6,11]} (strength_i x_i) - EqualDist]^2 = [ ( 5x_6 + 6x_7 + 8x_8 + 4x_9 + 6x_{10} + 9x_{11} ) - EqualDist ]^2 $$

As already stated above, having only the objective function could lead to undesired solutions. E.g., a solver could assign all players to both teams or no player at all (resulting in \( Objective = 0 \) for both cases). To avoid this, let’s add expressions for the constraints.

Add Functions for the Constraints

We have two constraints we need to add math expressions for. Let’s start with the first one: A player gets assigned to max one team. So, using the binary variables, we need a way to express “either \( x_0 = 1 \) or \( x_6 = 1 \) but not both”. Same is true for other variable pairs, i.e., \( x_1 \) and \( x_7 \) must not both be \(1\) etc. Following table contains a couple of penalty expressions that allow us to express this.

Classic constraint Constraint expression Penalty expression
At maximum one of the variables is \( 1 \) (not both). \( x + y \leq 1 \) \( P(xy) \)
At least one of the variables is \( 1 \). \( x + y \geq 1 \) \( P(1-x-y+xy) \)
Exactly one of the variables is \( 1 \). The other is \( 0 \). \( x \neq y \) \( P(1-x-y+2xy) \)
\( x \) can only be \( 1 \) if \( y \) is also \( 1 \). \( x \leq y \) \( P(x-xy) \)
Either both variables are \( 0 \) or both are \( 1 \) \( x=y \) \( P(x+y-2xy) \)
From 3 variables at maximum only one is \( 1 \). \( x+y+z \leq 1 \) \( P(xy+xz+yz) \)

Line 1 of the table contains the expression we need, so we get 6 expressions:

$$ x_0 + x_6 \leq 1 \Rightarrow P(x_0x_6) = Constraint_1 $$

$$ x_1 + x_7 \leq 1 \Rightarrow P(x_1x_7) = Constraint_2 $$

$$ … $$

$$ x_5 + x_{11} \leq 1 \Rightarrow P(x_5x_{11}) = Constraint_6 $$

These are all expressions needed for the first constraint. Now, let’s look at the second one: A team must not have more than one goalkeeper. The simplest way to express this is by focusing on the two goalkeepers and ensure that both are assigned to different teams, i.e. …

$$ x_1 + x_2 \leq 1 \Rightarrow P(x_1x_2) = Constraint_7 $$

$$ x_7 + x_8 \leq 1 \Rightarrow P(x_7x_8) = Constraint_8 $$

Choosing appropriate penalty values \( P \)

All constraint expressions contain a penalty variable \( P \). This is a variable (typically having integer value) indicating the importance of the constraint. Choosing the right penalty values might be a challenge. Choosing them too large might overwhelm the objective function (i.e., the solver would just try to satisfy the constraint without trying to minimize the objective function anymore). Choosing them too small would lead to tolerating constraint violations too often. As a general rule of thumb:

  • If it must be ensured that a constraint must be satisfied (“hard constraint”), then \(P\) must be large enough to preclude a violation.
  • If slight constraint violations can be tolerated (“soft constraints”), then a more moderate value might be chosen for \(P\).

Combine all Expressions to form a Cost Function

In a final step, we combine all expressions into a cost function \( C \), i.e.

$$ C = Objective + \sum_{i} Constraint_i = $$

$$ = [\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) + … $$

This is our final cost function. In part 4 of this blog series, we’ll convert the cost function into code that can be submitted to an Azure Quantum optimization solver.

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

Web Resources

Whitepapers