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 and PUBO 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 and PUBO 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")