Supported Optimization Formats and Translating Between Them

LunaSolve supports a broad variety of optimization formats, reflecting the diverse ways in which optimization problems can be structured. Whether your problems are formulated as QUBO, CQM, LP, or any other format, LunaSolve is equipped to handle them.

Different solvers and algorithms may require specific formats, and not all formats are natively supported by each solver. Recognizing this, LunaSolve offers a powerful feature: the ability to translate between different optimization formats. This capability allows you to utilize solvers that do not natively support your problem’s initial format. For example, you can upload a problem in QUBO format and apply an LP solver; LunaSolve will automatically translate the QUBO into an LP file before solving. It’s important to use this feature thoughtfully, especially if the problem was specifically designed for a certain format.

Upon completing this guide, you will be able to:

  1. Identify the range of optimization formats supported by Luna.
  2. Understand how LunaSolve seamlessly translates between these formats to expand the usability of different solvers.

First, you'll need to import the necessary packages and initiate your session with LunaSolve.

# Load the Luna package
from luna_sdk import LunaSolve

# Initialize LunaSolve with your credentials
ls = LunaSolve(email="YOUREMAIL", password="YOURPASSWORD")

QUBO Matrices

Quadratic Unconstrained Binary Optimization (QUBO) is a problem format frequently utilized in quantum computing. In QUBO problems, variables are binary, meaning they are restricted to the values 0 or 1. The "unconstrained" aspect refers to the lack of explicit equality or inequality constraints on the variables, apart from their binary nature. QUBO problems can be represented in matrix form: the diagonal elements of the matrix correspond to the linear coefficients of the variables, while the off-diagonal elements represent the interaction coefficients between variable pairs. This matrix setup allows quantum algorithms to efficiently evaluate the problem's objective function across various potential solutions.

When using QUBO matrices with LunaSolve, it's important to note that the service extracts the relevant information encoded in the matrix and converts it into a more descriptive optimization format.

# Define your QUBO matrix as a list of lists
qubo_matrix = [
    [4, 0, 0, 0, -2],
    [0, -2, 0, 0, 0],
    [0, 0, 6, -3, 0],
    [0, 0, -3, 2, 0],
    [-2, 0, 0, 0, 5]
]

# Upload your QUBO to LunaSolve
optimization = ls.optimization.create_from_qubo(name="My QUBO", matrix=qubo_matrix)

Binary Quadratic Model

In addition to QUBO matrices, QUBO problems can also be formulated as Binary Quadratic Models (BQM). This format has been popularized by D-Wave Systems, a leading provider of quantum annealing hardware. BQMs represent optimization problems where variables are binary (either 0 or 1), and interactions between these variables are quadratic. This provides an identical framework to define QUBOs as the matrix version. For more detailed information on BQMs and their applications, you can refer to the D-Wave Systems documentation.

from luna_sdk.schemas.optimization_formats.bqm import BQMSchema

# Define your QUBO problem as a BQM
bqm_data = {
    "linear": {"0": 4.0, "1": -2.0, "2": 6.0, "3": 2.0, "4": 5.0},
    "quadratic": {("3", "2"): -6.0, ("4", "0"): -4.0},
    "vartype": "BINARY"
}

bqm = BQMSchema(**bqm_data)

# Upload your BQM to LunaSolve
optimization = ls.optimization.create_from_bqm(name="My BQM", bqm=bqm)
from dimod import BinaryQuadraticModel

# Alternatively, directly create a BQM using dimod
bqm = BinaryQuadraticModel(
    {"0": 4.0, "1": -2.0, "2": 6.0, "3": 2.0, "4": 5.0},
    {("3", "2"): -6.0, ("4", "0"): -4.0},
    "BINARY"
)

# Upload your BQM to LunaSolve
optimization = ls.optimization.create_from_bqm(name="My BQM 2", bqm=bqm)

Constrained Quadratic Model

Constrained Quadratic Models (CQM) are a sophisticated format used to represent optimization problems that incorporate both an objective function and constraints. Popularized by D-Wave Systems, a leading provider of quantum annealing hardware, CQMs allow for the modeling of problems with quadratic interactions between binary or integer variables, where the constraints can be linear or quadratic. These models are particularly useful in complex optimization tasks that require adherence to predefined rules or criteria alongside seeking optimal solutions. For more detailed information on CQMs and their applications, you can refer to the D-Wave Systems documentation on CQMs.

from dimod import Integer, ConstrainedQuadraticModel

# Create a CQM using dimod
x = Integer('x', upper_bound=7)
y = Integer('y', upper_bound=3)
cqm = ConstrainedQuadraticModel()
cqm.set_objective(-3 * x - 4 * y)
cqm.add_constraint(x + y <= 5, label='c0')

# Upload your CQM to LunaSolve
optimization = ls.optimization.create_from_cqm(name="My CQM 2", cqm=cqm)

Linear Programming

Linear Programming (LP) is a powerful optimization technique used to find the best outcome in a mathematical model whose requirements are represented by linear relationships. In LP, the objective is to maximize or minimize a linear objective function, subject to a set of linear equality or inequality constraints.

LPs can either be uploaded as a LP file or as a string. LP files are data files that define a linear programming problem. They contain the mathematical representation of the problem, including details about the objective function, constraints, and variables involved.

# Upload your LP file to LunaSolve
with open("example.lp", "rb") as file:
    optimization = ls.optimization.create_from_lp_file(name="My LP", lp_file=file)
# Upload your LP as string to LunaSolve
lp_string = """
    Min
        obj: 4 x0 - 2 x1 + 6 x2 + 2 x3 + 5 x4 + [ - 8 x0 * x4 - 12 x2 * x3 ] / 2
    Bounds
    Binary
        x1 x3 x0 x4 x2
    End
"""
optimization = ls.optimization.create_from_lp_string(name="My LP", lp_string=lp_string)

Translating Between Optimization Formats

With LunaSolve, you can effortlessly translate between optimization formats, saving you time and effort. Instead of manually converting problems, LunaSolve automates the process for you, making it easy to formulate problems in different formats.

This feature is particularly useful as it allows you to use solvers that may not support your initial format. LunaSolve's translation capability enables you to apply quantum algorithms to formats not natively supported by quantum computers, expanding the range of problems you can solve. You can simply upload a problem in one format and use a solver that doesn't support it natively. LunaSolve handles all translations, including transforming the solution back into your initial format.

# As an example, define a QUBO matrix
qubo_matrix = [
    [4, 0, 0, 0, -2],
    [0, -2, 0, 0, 0],
    [0, 0, 6, -3, 0],
    [0, 0, -3, 2, 0],
    [-2, 0, 0, 0, 5]
]

# Upload your QUBO to LunaSolve
optimization = ls.optimization.create_from_qubo(name="My QUBO", matrix=qubo_matrix)

# Translate the QUBO to a LP and solve it using a LP solver
job = ls.solution.create(
    optimization_id=optimization.id,
    solver_name="SCIP",
    provider="zib"
)

# Get the solution for your QUBO
solution = ls.solution.get(job.id)

print(solution)

Output:

--------------------------------------------------------------------------------
META DATA:
--------------------------------------------------------------------------------
id: 664c6293da248277ca4cfb6e
name: None
created_date: 2024-05-21 11:00:03.522000
created_by: 66291cab401df553a5f5ccd6
modified_date: 2024-05-21 11:00:03.661000
modified_by: None
error_message: None
params:
runtime:
    total: 0.005910959000175353
    overhead: None
    qpu: None
sense: SenseEnum.MIN
provider: zib
status: StatusEnum.DONE
optimization:
    id: 664c6293da248277ca4cfb6d
    name: My QUBO
    created_date: 2024-05-21 11:00:03.007000
    created_by: 66291cab401df553a5f5ccd6
    modified_date: None
    modified_by: None
    use_case_name: None
    params: None
representation: None


--------------------------------------------------------------------------------
RESULTS:
--------------------------------------------------------------------------------
Result 1:
    {'sample': {'x0': -0.0, 'x3': -0.0, 'x4': 0.0, 'x2': 0.0, 'x1': 1.0, 'quadobjvar': 0.0}, 'obj_value': -2.0, 'feasible': True, 'constraints': {}}


--------------------------------------------------------------------------------
ZIB META DATA:
--------------------------------------------------------------------------------
    No metadata from provider..

Was this page helpful?