# Quadratic Linearly Constrained Binary Optimization

## Introduction

Quadratic Unconstrained Binary Optimization (Qubo) problems can be formulated from a square, symmetric objective function and a matrix of binary constraints. Suppose we are given an objective function, $O$, of dimension $n \times n$, and a set of $m$ constraints, represented by the matrix $A$, with dimension $m \times n$ and right hand side vector $b$ of length $m$. We want to combine them into a Qubo, which can be defined $Q = O + \alpha (A^T A-2\mathrm{diag}(b^TA))$, where $\alpha \in \mathbb{R}$. At this point, we can find an optimal solution,

$x^{*} = \min_{x} x^T Q x$.

The parameter $\alpha$ plays an important role in guaranteeing that the constraints are satisfied. We will not go into more detail on this page.

We will define a simple problem on the Upload tab and show how to upload the components. The examples on the Running tab will describe how to run the a constraint problem.

Suppose the original problem we want to minimize is

$-3xy + xz,$

subject to the constraints $x + z = 1$ and $2x + 2y= 2$.

There are three matrix components that can be associated with to a constraint problem of this type. The objective function in matrix form, the linear constraints matrix, and an optional right hand side (RHS) representing the linear constraints themselves. This can optionally be appended to the last column of the aforementioned constraints matrix. We will describe them and their upload formats in what follows.

The objective matrix is written

1234

```
import numpy as np
obj = np.array([[ 0. , -1.5, 0.5],
[-1.5, 0. , 0. ],
[ 0.5, 0. , 0. ]]).
```

The constraints take the form

12

```
A = np.array([[1, 0, 1],
[2, 2, 0]])
```

and an explicit RHS vector can be represented as

12

```
rhs = np.array([[1],
[2]]).
```

### API format

We encode the above in a sparse dictionary format for the upload step to the API:

#### Objective

It is essential to label the

`file_type`

value as `"objective":`

1234567891011121314151617181920212223242526

```
{
"data": [
{
"i": 1,
"j": 0,
"val": -1.5
},
{
"i": 2,
"j": 0,
"val": 0.5
},
{
"i": 0,
"j": 1,
"val": -1.5
},
{
"i": 0,
"j": 2,
"val": 0.5
}
],
"file_name": "smallest_objective.json",
"num_variables": 3,
"file_type": "objective"}
```

#### Constraints

Similarly, the

`file_type`

must be labels as `"constraints"`

for the constraints matrix.123456789101112131415161718192021222324252627

```
{
"data": [
{
"i": 0,
"j": 0,
"val": 1.0
},
{
"i": 1,
"j": 0,
"val": 2.0
},
{
"i": 1,
"j": 1,
"val": 2.0
},
{
"i": 0,
"j": 2,
"val": 1.0
}
],
"file_name": "smallest_constraints.json",
"num_constraints": 2,
"num_variables": 3,
"file_type": "constraints"}
```

#### RHS

Similarly,

`file_type`

should be `"rhs"`

for the optional RHS vector.12345678

```
{
"data": [
1.0,
2.0
],
"file_name": "smallest_rhs.json",
"file_type": "rhs",
"num_constraints": 2}
```

### Uploading and file_id's

First, import the necessary packages:

123

```
import json
from qci_client import QciClient
qci = QciClient()
```

Now we can upload the various files using the client. Suppose we store the data in a variable

`data`

. Then we call `upload_file`

to push the data to the server.12

```
response_json = qci.upload_file(constraints_data)
file_id = response_json["file_id"]
```

We can extract the file_id for later use. Triggering a job to run requires the

`file_id`

to tell the backend which data to use. We cover this step in the **Running**tab.