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.
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")
⚠️ : 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.
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")
QPLIB
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.