Problems with Multiple Constraints

When we work with problems in the real world, we often have an objective and multiple constraints playing a role simultaneously. How do we incorporate all of these components into a single BQM?

Social Networks (Friends and Enemies)

We work through the “Social Networks” problem, sometimes referred to as “Friends and Enemies”. For more examples that discuss this problem and some applications take a look at our demo and Jupyter Notebook available on the Leap platform.

Problem Setup

In a group of people, we have some existing relationships. Some pairs of people are friends, others are enemies, and some have no relationship (maybe they’ve never met each other before).

For example, let’s say we have the following friend and enemy relationships.

Friends

  • Katie and Anthony
  • Carlos and Betty

Enemies

  • Anthony and Carlos

Suppose that we are asked to split this group of people into two sets. Maybe they’re being divided into two teams, or being split into groups for a project. Our goal is to split the people into two groups so that we have friends in the same group and enemies in different groups. How can we map this to a BQM?

The first step is to think about how we can use binary variables to represent the answer to our problem. When we consider our problem, the answer that we’re looking for is which group each person should be assigned to. If we call these groups “A” and “B”, then an answer should look something like:

  • Katie in Group A
  • Anthony in Group A
  • Carlos in Group B
  • Betty in Group B

To do this we can assign a binary variable to each person that tells us which group they belong to. If we’re working with a QUBO model we could say \(x_K=0\) means Katie is in Group A, while \(x_K=1\) means Katie is in Group B. Similarly, if we’re working with an Ising model we can say \(s_K=-1\) means Katie is in Group A, while \(s_K=1\) means Katie is in Group B.

  Group A Group B
QUBO 0 1
Ising -1 +1

Now that we have figured out how to align our answers with binary valued variables, we need to figure out how to write our minimization function. A good way to tackle this problem is to think about individual relationships instead of the entire set of people as a whole. For two friends with a given relationship, which team assignments are good and which are bad?

Katie Anthony Good/Bad?
A A Good
A B Bad
B A Bad
B B Good

This table should look familiar now — it’s similar to what we did for our two variable relationships in the beginning of this guide! In fact, this is exactly the same as the QUBO/Ising truth tables we used to create a BQM that represents the constraint \(v_1=v_2\).

Combining Relationships

At this point we are able to write a BQM for each relationship. How can we combine them into one BQM? The answer is surprisingly simple: addition.

Once we have a BQM for every relationship, we can add all of the BQMs together to make a single, comprehensive BQM for the entire population.

BQM Formulation

Friend Relationship

For our friend relationships, we saw in a previous section (Small Problems with Two Variables) that we can represent this relationship (\(x_1=x_2\)) by the following BQMs.

QUBO Ising
\(x_i+x_j-2x_i x_j\) \(-0.5s_is_j+0.5\)

This gives us the following BQMs for our friend relationships.

  QUBO Ising
Katie and Anthony \(x_A+x_K-2x_A x_K\) \(-0.5s_As_K+0.5\)
Carlos and Betty \(x_B+x_C-2x_B x_C\) \(-0.5s_Bs_C+0.5\)

Enemy Relationship

For our enemy relationship, we need to figure out what BQM models the relationship. We do this in the same way we did our two-variable BQMs in the earlier section.

Constrain Satisfaction Table:

QUBO Ising Different?
\(x_1\) \(x_2\) \(s_1\) \(s_2\)
0 0 -1 -1 No
0 1 -1 +1 Yes
1 0 +1 -1 Yes
1 1 +1 +1 No

Replacing the final column of yes/no values with small/large values.

QUBO Ising Value
\(x_1\) \(x_2\) \(s_1\) \(s_2\)
0 0 -1 -1 1
0 1 -1 +1 0
1 0 +1 -1 0
1 1 +1 +1 1

Building our system of equations.

QUBO Ising
\(a_1\cdot 0+a_2 \cdot 0 +b_{1,2} \cdot 0 \cdot 0 +c=1\) \(h_1\cdot (-1)+h_2\cdot (-1)+J_{1,2}\cdot (-1)\cdot (-1)+c=1\)
\(a_1\cdot 0+a_2 \cdot 1 +b_{1,2} \cdot 0 \cdot 1 +c=0\) \(h_1\cdot (-1)+h_2\cdot (+1)+J_{1,2}\cdot (-1)\cdot (+1)+c=0\)
\(a_1\cdot 1+a_2 \cdot 0 +b_{1,2} \cdot 1 \cdot 0 +c=0\) \(h_1\cdot (+1)+h_2\cdot (-1)+J_{1,2}\cdot (+1)\cdot (-1)+c=0\)
\(a_1\cdot 1+a_2 \cdot 1 +b_{1,2} \cdot 1 \cdot 1 +c=1\) \(h_1\cdot (+1)+h_2\cdot (+1)+J_{1,2}\cdot (+1)\cdot (+1)+c=1\)

Solving our system of equations:

QUBO Ising
\(a_1=-1\) \(h_1=0\)
\(a_2 =-1\) \(h_2 =0\)
\(b_{1,2}=2\) \(J_{1,2}=0.5\)
\(c=1\) \(c=0.5\)

Our final models are:

QUBO:

\[-x_1-x_2+2x_1x_2+1\]

Ising:

\[0.5s_1s_2+0.5\]

For the pair of enemies in our set of people, we now have:

  QUBO Ising
Anthony and Carlos \(-x_A-x_C+2x_A x_C+1\) \(0.5s_As_C+0.5\)

Combining All Relationships

Now that we have a BQM for each relationship, we add them together to get our BQM for the entire problem.

QUBO

\[(x_A+x_K-2x_A x_K)+(x_B+x_C-2x_B x_C)+(-x_A-x_C+2x_Ax_C+1)\]

This simplifies down to the following.

\[x_B+x_K+2x_Ax_C-2x_Ax_K-2x_Bx_C+1\]

Ising

\[(-0.5s_As_K+0.5)+(-0.5s_B s_C+0.5)+(0.5s_As_C+0.5)\]

This simplifies down to the following.

\[-0.5s_As_K-0.5s_Bs_C+0.5s_As_C+1.5\]

To double-check our work, we can evaluate our BQM values for all possible assigments for these four people. The rows with the smallest value tell us the best assignment of people to teams.

Anthony Betty Carlos Katie Value
A A A A 1
A A A B 2
A A B A 1
A A B B 2
A B A A 2
A B A B 3
A B B A 0
A B B B 1
B A A A 1
B A A B 0
B A B A 3
B A B B 2
B B A A 2
B B A B 1
B B B A 2
B B B B 1

BQM Development Process

To successfully map problems to BQMs, we work through a series of steps.

Step 1: Write Objective and Constraints

This should be written out in terms of your problem domain (i.e. not using math!).

The objective of a problem is what we are looking to minimize or maximize. Look for those key words in your problem to determine if your problem has one, or if you are just looking to satisfy a set of constraints.

A constraint in a problem is a rule that we have to follow. An answer that doesn’t satisfy a given constraint is called infeasible –– it’s not a good answer, and generally we won’t be able to use it.

For example, the previous problem might be described with the following:

  • Objective: None
  • Constraint 1: Friends on the same team
  • Constraint 2: Enemies on different teams

Note that there may be more than one way to interpret your problem as objectives and constraints.

Step 2: Convert Objective and Constraints into Binary Math Expressions

The first step is to think about binary variables. What answer are you seeking to your problem? What “Yes” or “No” questions can you ask that will give you that answer? Once we think of our problem in these terms, we can assign a binary variable for each question.

Next, we transform our objective and constraints into math expressions using these binary variables. Often this can be done with our truth table approach if can find a way to break our problem down into two- or three-variable relationships.

Step 3: Transform Math Expressions into a BQM

Different types of expressions will require different strategies. If you used the truth table approach in step 2, you may not need to make any adjustments!

Some common transformations are:

Squared Terms

Our QUBO and Ising models don’t have room for squared binary variables. It turns out that we don’t actually need them.

QUBO

Our binary variables in a QUBO are 0 and 1. Note that \(0^2=0\) and \(1^2=1\), so we can replace any term \(x_i^2\) with \(x_i\).

Ising

Our binary variables in an Ising model are -1 and +1. Note that \((-1)^2=1\) and \((+1)^2=1\), so we can replace any term \(s_i^2\) with the constant 1.

Maximization to Minimization

If our objective function is a maximization function (for example, you might be maximizing profit), we can convert this to a minimization by multiplying the entire expression by -1.

Example:

\[\mbox{arg max} (3v_1+2v_1v_2) = \mbox{arg min} (-3v_1-2v_1v_2)\]

Equality to Minimization

If you have a constraint that is an equality, we can convert it to a minimization expression by moving all arguments and constants to one side of the equality and squaring the non-zero side of the equation. This will leave us with an expression that is satisfied at its smallest value (0) and unsatisfied at any larger value (>0).

Example:

Original constraint:

\[v_1+v_2=1\]

Move all arguments and constants to one side:

\[v_1+v_2-1=0\]

Square the expression:

\[(v_1+v_2-1)^2\]

Note that the smallest value a squared expression can equal is zero, so the smallest value \((v_1+v_2-1)^2\) can equal is zero. This expression will equal zero when \(v_1+v_2-1=0\), which is exactly the constraint that we are looking to satisfy.

Step 4: Combine Expressions

Once we have written all of the components (objective and constraints) as BQM expressions, we make our final BQM by adding all of the components together.

In this step, we have the choice to weight the components if we choose. This weighting is done using a Lagrange parameter. Generally, we will assign individual Lagrange parameters to each constraint to prioritize valid solutions (ones in which all of our constraints are satisfied).

\[\mbox{BQM} = \min (\mbox{objective} + \gamma (\mbox{constraint}))\]

Example

Suppose that we have two companies that can complete the same job, each for a different price. Company 1 can complete the job for \(\$12\), while Company 2 can complete the job for \(\$8\). We want to have the job completed for the smallest cost.

We can model this problem as a QUBO. The objective is to minimize cost and the constraint is that we must choose exactly one company. The binary variables \(x_1\) and \(x_2\) can be used to indicate whether we will hire Company 1 or Company 2 to complete the job. Using these binary variables, we write the objective as \(12x_1+8x_2\) and the constraint as \((x_1+x_2-1)^2\). These can be combined to make the following QUBO.

\[\min \left((12x_1+8x_2)+\gamma(x_1+x_2-1)^2 \right)\]

If we choose \(\gamma=1\), we see the following values for our QUBO.

\(x_1\) \(x_2\) Value
0 0 1
0 1 8
1 0 12
1 1 21

Note that the smallest value of 1 corresponds to not choosing either company to complete the job! Clearly this is not the optimal solution to our original problem, so we need to adjust the Lagrange parameter to ensure that our constraint (choose exactly one company) is satisfied.

Setting a larger Lagrange parameter will enforce our constraint. The following table demonstrates the QUBO values for \(\gamma=20\).

\(x_1\) \(x_2\) Value
0 0 20
0 1 8
1 0 12
1 1 40

Now we see that the smallest value corresponds to the optimal solution of hiring Company 2 to complete the job.

Note that you may need to try a few different values to identify the best Lagrange parameter value for your specific BQM. A good starting value is to set \(\gamma\) equal to your best estimate of the value of your objective function. If you find that your constraints are not satisfied in the solutions returned, you may need to increase \(\gamma\). On the other hand, if your constraints are all satisfied but your solutions are not close to optimal, you may need to decrease \(\gamma\).

Example: Choosing Boxes

Let’s take a look at how we can use these methods to model a BQM for a larger problem with more than two variables.

Problem Description

We’re given three boxes with different weights. We want to choose the two boxes with the smallest sum.

  Box 1 Box 2 Box 3
Box Weight 15 20 25

This is a simple problem – we know that the answer is to choose boxes 15 and 20. But how do we phrase this problem as a BQM?

Step 1: Write Objective and Constraints

Objective:

We are looking for the smallest sum, so our objective is “minimize the sum of the boxes chosen”.

Constraint:

We are allowed to choose two boxes, so our constraint is “choose exactly two boxes”.

Step 2: Convert Objective and Constraints into Binary Math Expressions

Binary Variables

First, we need to define our binary variables. The answer that we are looking for is which boxes we should choose. For each box, we can ask “do we choose this box?”. This points us to how we should define our binary variables.

  QUBO Ising
Use Box i \(x_i=1\) \(s_i=+1\)
Don’t use Box i \(x_i=0\) \(s_i=-1\)

Once we have defined our binary variables, we can convert our objective and constraint into math expressions.

Objective

QUBO

To figure out the sum of the boxes that are chosen, we can use a weighted sum: \(15x_1+20x_2+25x_3\). In this sum, the boxes that are chosen will have \(x_i=1\) and the boxes that are not chosen will have \(x_i=0\). In other words, the value of boxes that are not chosen will be multiplied by zero and so we will only be adding up the value of the boxes that are chosen. Our objective function becomes:

\[\min 15x_1+20x_2+25x_3\]

Ising

Using our binary variables, we can convert our +1/-1 to 1/0 using the Ising to QUBO translation shown earlier, which maps \(+1 \mapsto 1\) and \(-1 \mapsto 0\). Our objective function can then be written as:

\[\min \left(15 \left( \frac{s_1+1} {2}\right) + 20\left(\frac{s_2+1}{2} \right) + 25 \left( \frac{s_3+1} {2}\right)\right)\]

Constraint

QUBO

Our constraint “choose exactly two boxes” means that we need exactly two of our binary variables to have value 1, and the remaining binary variable will have value 0. In other words, our constraint can be written as:

\[x_1+x_2+x_3=2\]

Ising

Our constraint “choose exactly two boxes” means that we need exactly two of our binary variables to have value +1, and the remaining binary variable will have value -1. In other words, our constraint can be written as:

\[s_1+s_2+s_3=1\]

Step 3: Transform Math Expressions into a BQM

Our objective function is fine as written, so we only need to modify our constraint.

QUBO

To modify our constraint, we need to use the method for equalities.

Original constraint:

\[x_1+x_2+x_3=2\]

Move everything to one side:

\[x_1+x_2+x_3-2=0\]

Square the expression:

\[(x_1+x_2+x_3-2)^2\]

Ising

Following the same method, we can rewrite our constraint as follows.

\[(s_1+s_2+s_3-1)^2\]

Step 4: Combine Expressions

Now that we have written our objective and constraint in BQM form, we can combine them together to make our final model using addition and adding in a Lagrange parameter. Both of these can be expanded and simplified to prepare for input to an Ocean python program.

QUBO

\[\mbox{QUBO} = \min (15x_1+20x_2+25x_3)+\gamma(x_1+x_2+x_3-2)^2\]

Ising

\[\mbox{Ising} = \min \left(15 \left( \frac{s_1+1}{2} \right) + 20\left(\frac{s_2+1} {2}\right) + 25 \left( \frac{s_3+1}{2} \right) + \gamma (s_1+s_2+s_3-1)^2 \right)\]

Exercise

Write a BQM for the following problem.

A business is trying to figure out the best way to pack a box full of items. There are five items, with values 1, 5, 3, 4, and 2 dollars. These items have weights 2, 4, 4, 1, and 3 lbs, respectively. The contents of the box must weigh exactly 6 lbs. What is the best way to pack the box so that the box has the highest total value?