# Models

Models classes can be found using:

`from strangeworks_optimization_models.problem_models import *`

## Quadratic Unconstrained Binary Optimization

Quadratic Unconstrained Binary Optimization (QUBO) is a mathematical problem that is used to model a wide range of combinatorial optimization problems. It is a type of optimization problem that is used to find the minimum value of a quadratic function of binary variables. The QUBO problem can be represented as:

`minimize: f(x) = x^T * Q * x`

subject to: x_i ∈ {0, 1}

Where `x`

is a vector of binary variables, `Q`

is a symmetric matrix, and `x^T`

is the transpose of `x`

. The QUBO problem can be used to model a wide range of combinatorial optimization problems such as the Traveling Salesman Problem, the Maximum Cut Problem, and the Graph Coloring Problem.

To create a simple qubo model, you can use the following code:

`from dimod import BinaryQuadraticModel`

linear = {1: -2, 2: -2, 3: -3, 4: -3, 5: -2}

quadratic = {(1, 2): 2, (1, 3): 2, (2, 4): 2, (3, 4): 2, (3, 5): 2, (4, 5): 2}

model = BinaryQuadraticModel(linear, quadratic, "BINARY")

## Mathematical Programming System

Mathematical Programming System (MPS) is a file format that is used to represent linear and mixed-integer programming problems. The MPS file format is widely used in the field of mathematical optimization and is supported by a wide range of optimization solvers. The MPS file format is a plain text file format that is used to represent the objective function, the constraints, and the bounds of the decision variables in a mathematical programming problem.

MPS problems can be represented as:

`minimize: c^T * x`

subject to: Ax = b

l <= x <= u

Where `c`

is a vector of coefficients, `x`

is a vector of decision variables, `A`

is a matrix of coefficients, `b`

is a vector of constants, `l`

is a vector of lower bounds, and `u`

is a vector of upper bounds.

To create an MPS problem, you can load an MPS file using the following code:

`from strangeworks_optimization_models.problem_models import MPSFile`

model = MPSFile.read_file("path/to/file.mps")

## Constrained Quadratic Model

Constrained Quadratic Model (CQM) is used to find the minimum value of a quadratic function of continuous variables subject to linear equality and inequality constraints. The CQM problem can be represented as:

`minimize: f(x) = x^T * Q * x + c^T * x`

subject to: Ax = b

Gx <= h

Where `x`

is a vector of continuous variables, `Q`

is a symmetric matrix, `c`

is a vector of coefficients, `A`

is a matrix of coefficients, `b`

is a vector of constants, `G`

is a matrix of coefficients, and `h`

is a vector of constants.

Here's an example of how to create a CQM for the D-Wave Leap solver using the `dimod`

library:

`from dimod import Binary, ConstrainedQuadraticModel`

weights = [0.9, 0.7, 0.2, 0.1]

capacity = 1

y = [Binary(f"y_{j}") for j in range(len(weights))]

x = [[Binary(f"x_{i}_{j}") for j in range(len(weights))] for i in range(len(weights))]

model = ConstrainedQuadraticModel()

model.set_objective(sum(y))

for i in range(len(weights)):

model.add_constraint(sum(x[i]) == 1, label=f"item_placing_{i}")

for j in range(len(weights)):

model.add_constraint(

sum(weights[i] * x[i][j] for i in range(len(weights))) - y[j] * capacity <= 0,

label=f"capacity_bin_{j}",

)

JiJ also supports CQM problems but they must be created using the `jij`

library and the options must contain the `feed_dict`

:

`from strangeworks_optimization_models.parameter_models import JijLeapHybridCQMParameterModel`

import jijmodeling as jm

d = jm.Placeholder("d", ndim=1) # Define variable d

d.len_at(0, latex="N") # Set latex expression of the length of d

x = jm.BinaryVar("x", shape=(d.shape[0],)) # Define binary variable

i = jm.Element("i", belong_to=(0, d.shape[0])) # Define dummy index in summation

model = jm.Problem("simple problem") # Create problem instance

model += jm.sum(i, d[i] * x[i]) # Add objective function

model += jm.Constraint("one hot", jm.sum(i, x[i]) == 1) # Add constraint condition

model # Display the problem

solver = "jij.LeapHybridCQM"

options = JijLeapHybridCQMParameterModel(feed_dict={"d": [1.0, 0.1, -2.0, 1.0]})

## Discrete Quadratic Model

Discrete Quadratic Model (DQM) is used to find the minimum value of a quadratic function of discrete variables subject to linear equality and inequality constraints. The DQM problem can be represented as:

`minimize: f(x) = x^T * Q * x + c^T * x`

subject to: Ax = b

Gx <= h

x_i ∈ {0, 1}

Where `x`

is a vector of binary variables, `Q`

is a symmetric matrix, `c`

is a vector of coefficients, `A`

is a matrix of coefficients, `b`

is a vector of constants, `G`

is a matrix of coefficients, and `h`

is a vector of constants.

Here's an example DQM:

`from dimod import DiscreteQuadraticModel`

import random

model = DiscreteQuadraticModel()

for i in range(10):

model.add_variable(4)

for i in range(9):

for j in range(i + 1, 10):

model.set_quadratic_case(i, random.randrange(0, 4), j, random.randrange(0, 4), random.random())

## Quadratic Programming Problems

QPLIB is a collection of test problems for quadratic programming (QP) and quadratic unconstrained binary optimization (QUBO).

You can download QPLIB files from the QPLIB website.

QPLIB problems can be represented as:

`minimize: 0.5 * x^T * Q * x + c^T * x`

subject to: Ax = b

l <= x <= u

Where `Q`

is a symmetric matrix, `c`

is a vector of coefficients, `x`

is a vector of decision variables, `A`

is a matrix of coefficients, `b`

is a vector of constants, `l`

is a vector of lower bounds, and `u`

is a vector of upper bounds.

Note: The QPLIB file format is used to store by Quadratic Programming

andPUBO problems. Please make sure you are using the correct solver for your problem.

To load a QPLIB file, you can use the following code:

`from strangeworks_optimization_models.problem_models import QplibFile`

model = QplibFile.read_file("path/to/file.qplib")

## Polynomial Unconstrained Binary Optimization

Polynomial Unconstrained Binary Optimization (PUBO) is used to find the minimum value of a polynomial function of binary variables. The PUBO problem can be represented as:

`minimize: f(x) = ∑_i ∑_j ∑_k a_{ijk} x_i x_j x_k + ∑_i ∑_j a_{ij} x_i x_j + ∑_i a_i x_i + c`

subject to: x_i ∈ {0, 1}

Where `x`

is a vector of binary variables, `a`

is a tensor of coefficients, and `c`

is a constant.

Note: The QPLIB file format is used to store by Quadratic Programming

andPUBO problems. Please make sure you are using the correct solver for your problem.

To load a PUBO, you can use the following code to read in a QPLIB file that stores a PUBO:

`from strangeworks_optimization_models.problem_models import QplibFile`

model = QplibFile.read_file("path/to/file.qplib")

## Matrix Market

Matrix Market is a NIST-sponsored repository of test matrices for use in numerical algorithms.

You can download Matrix Market files from the Matrix Market website.

They are written in the following format:

`%%MatrixMarket matrix coordinate real general`

% comment

M N L

I1 J1 A1

I2 J2 A2

...

Where `M`

is the number of rows, `N`

is the number of columns, `L`

is the number of non-zero elements, `I`

is the row index, `J`

is the column index, and `A`

is the value of the non-zero element.

To load a Matrix Market file, you can use the following code:

`from strangeworks_optimization_models.problem_models import MatrixMarket`

model = MatrixMarket.read_file("path/to/matrix/market.txt")