Summary of Exercises with Solutions

Below you will find solutions to the exercises included in this “Learn to Formulate Problems” guide. For further discussion of these solutions, please visit our community forum in Leap.

Introduction

Split the following problem into an objective and constraints.

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?

Solution

This problem can be split into an objective and constraints as follows.

Objective

  • Maximize total value

Constraint

  • Total weight of contents is exactly 6 lbs

Definitions

QUBO

Put the following QUBO into matrix form.

\[x_1+x_1x_2-3x_3+5\]

Solution

\[\begin{split}\left[ \begin{array}{ccc} 1 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & -3 \\ \end{array} \right]\end{split}\]

Ising

Put the following Ising model into matrix form.

\[s_1+s_1s_2-3s_3+5\]

Solution

\[\]

Linear

\[\begin{split}h = \left[ \begin{array}{cccc} 1 & 0 & -3 \\ \end{array} \right]\end{split}\]

Quadratic

\[\begin{split}J = \left[ \begin{array}{cccc} 0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{array} \right]\end{split}\]

Converting Between QUBO and Ising

QUBO to Ising:

\[\frac{3}{4}s_1+\frac{1}{4}s_2-\frac{3}{4}s_3+\frac{1}{4}s_1s_2+\frac{17}{4}\]

Ising to QUBO:

\[-2x_2-6x_3+4x_1x_2+8\]

Small Problems with Two Variables

QUBO:

What is the QUBO model for the constraint \(x_1 \geq x_2\)?

Solution

\[x_2-x_1x_2\]

Ising:

What is the Ising model for the constraint \(s_1 \geq s_2\)?

Solution

\[-\frac{1}{4}s_1+\frac{1}{4}s_2-\frac{1}{4}s_1s_2+\frac{1}{4}\]

Problems with Multiple Constraints

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?

Solution

QUBO:

\[(x_1+5x_2+3x_3+4x_4+2x_5)+\gamma (2x_1+4x_2+4x_3+x_4+3x_5-6)^2\]

Ising:

\[\left(\frac{1}{2}s_1+\frac{5}{2}s_2+\frac{3}{2}s_3+2s_4+s_5+\frac{15}{2} \right)\gamma \left(s_1+2s_2+2s_3\frac{1}{2}s_4+\frac{3}{2}s_5+1 \right)^2\]