Notebooks and Examples#
Use Case Tutorials#
In the following, you find notebooks with use cases to get you started with the HybridSolver.
QUBOs Getting Started: Learn how to solve QUBOs to global optimality with Quantagonia’s HybridSolver.
The Drone Delivery Problem: Discover how to optimize drone delivery models.
The Facility Layout Planning Problem: Explore how to optimize facility layout planning models.
The Maintenance Scheduling Problem: Master how to optimize maintenance scheduling models with efficient strategies.
The Workforce Scheduling Problem: Learn how to optimize workforce scheduling models.
Code Examples#
The following examples introduce some of the functionalities of the quantagonia
package.
Modeling problems#
MIP#
It is also possible to solve PuLP models with the HybridSolver.
1from quantagonia.enums import HybridSolverOptSenses, VarType
2from quantagonia.mip.model import Model
3
4# setup model
5model = Model()
6
7# setup variables
8x0 = model.add_variable(lb=-2, ub=10, name="x_0", var_type=VarType.CONTINUOUS)
9x1 = model.add_variable(lb=-7, ub=12, name="x_1", var_type=VarType.INTEGER)
10x2 = model.add_variable(lb=-10, ub=17, name="x_2", var_type=VarType.CONTINUOUS)
11x3 = model.add_variable(name="x_3", var_type=VarType.BINARY)
12x4 = model.add_variable(name="x_4", var_type=VarType.BINARY)
13
14# add constraints
15model.add_constraint(x0 + x1 + x2 + x3 + x4 <= 10, "c0")
16model.add_constraint(x0 - x1 + x2 - x3 + x4 >= 5, "c1")
17
18# set objective and sense
19objective = 2 * x0 - 3 * x1 + 4 * x2 + 5 * x3 - 6 * x4 + 5
20model.set_objective(objective, sense=HybridSolverOptSenses.MAXIMIZE)
21
22# solve the model
23status = model.optimize()
24
25# print the status
26print("Status:", status)
27
28# get the solution
29solution = model.solution
30print("Solution:")
31for var_name, val in solution.items():
32 print(f" {var_name}: {val}")
33
34# get the objective value
35objective_value = model.objective_value
36
37# get the runtime
38runtime = model.total_time
QUBO#
This example shows how to model a QUBO problem with the QuboModel
class. Have a look at our .qubo format for QUBOs to learn about our file format.
1import os
2
3from quantagonia import HybridSolver, HybridSolverParameters
4from quantagonia.enums import HybridSolverOptSenses
5from quantagonia.qubo import QuboModel
6
7API_KEY = os.environ["QUANTAGONIA_API_KEY"]
8
9# setup model
10model = QuboModel()
11
12# setup variables
13x0 = model.add_variable("x_0", initial=1)
14x1 = model.add_variable("x_1", initial=1)
15x2 = model.add_variable("x_2", initial=1)
16x3 = model.add_variable("x_3", initial=1)
17x4 = model.add_variable("x_4", initial=1)
18
19# build objective
20model.objective += 2 * x0
21model.objective += 2 * x2
22model.objective += 2 * x4
23model.objective -= x0 * x2
24model.objective -= x2 * x0
25model.objective -= x0 * x4
26model.objective -= x4 * x0
27model.objective -= x2 * x4
28model.objective -= x4 * x2
29model.objective += 3
30
31# set the sense
32model.sense = HybridSolverOptSenses.MINIMIZE
33
34print("Problem: ", model)
35print("Initial: ", model.eval())
36
37hybrid_solver = HybridSolver(API_KEY)
38
39params = HybridSolverParameters()
40params.set_time_limit(10)
41res = model.solve(hybrid_solver, params)
42
43print("Runtime:", res["timing"])
44print("Status:", res["sol_status"])
45print("Objective:", model.eval())
46
47
48if model.eval() != 3.0:
49 error_message = f"Objective value is not correct: {model.eval()} instead of 3.0"
50 raise AssertionError(error_message)
Import QUBO problems#
The Quantagonia API client offers possibilities to import QUBOs from Qiskit, D-Wave Ocean, and from PyQUBO.
Qiskit#
1import os
2
3from qiskit_optimization.converters import QuadraticProgramToQubo
4from qiskit_optimization.problems.quadratic_program import QuadraticProgram
5
6from quantagonia import HybridSolver, HybridSolverParameters
7from quantagonia.qubo.model import QuboModel
8
9API_KEY = os.environ["QUANTAGONIA_API_KEY"]
10
11
12def build_qiskit_qp() -> QuadraticProgram:
13 """Builds a small subset sum quadratic optimization problem."""
14 weights = [9, 7, 2, 1]
15 capacity = 10
16
17 qp = QuadraticProgram()
18
19 # create binary variables (y_j = 1 if bin j is used, x_i_j = 1 if item i
20 # is packed in bin j)
21 for j in range(len(weights)):
22 qp.binary_var(f"y_{j}")
23 for i in range(len(weights)):
24 for j in range(len(weights)):
25 qp.binary_var(f"x_{i}_{j}")
26
27 # minimize the number of used bins
28 qp.minimize(linear={f"y_{j}": 1 for j in range(len(weights))})
29
30 # ensure that each item is packed in exactly one bin
31 for i in range(len(weights)):
32 qp.linear_constraint(
33 name=f"item_placing_{i}", linear={f"x_{i}_{j}": 1 for j in range(len(weights))}, sense="==", rhs=1
34 )
35
36 # ensure that the total weight of items in each bin does not exceed the capacity
37 for j in range(len(weights)):
38 lhs_x = {f"x_{i}_{j}": weights[i] for i in range(len(weights))}
39 lhs_y = {f"y_{j}": -capacity}
40 qp.linear_constraint(name=f"capacity_bin_{j}", linear={**lhs_x, **lhs_y}, sense="<=", rhs=0)
41
42 return qp
43
44
45# build qiskit qp
46qp = build_qiskit_qp()
47# use qiskit to convert qp to qubo
48qp2qubo = QuadraticProgramToQubo()
49qiskit_qubo = qp2qubo.convert(qp)
50
51# read the qiskit qubo
52qubo = QuboModel.from_qiskit_qubo(qiskit_qubo)
53
54# solve with Quantagonia
55params = HybridSolverParameters()
56hybrid_solver = HybridSolver(API_KEY)
57qubo.solve(hybrid_solver, params)
58
59# to be used in tests
60obj = qubo.eval()
61if obj != -18.0:
62 msg = f"Objective value is not correct: {obj} instead of -18.0"
63 raise ValueError(msg)
D-Wave Ocean#
In this example, we build the map coloring bqm model from here and import it into a QuboModel
to solve it with the HybridSolver.
1import os
2
3from dimod import BinaryQuadraticModel
4from dimod.generators import combinations
5
6from quantagonia import HybridSolver, HybridSolverParameters
7from quantagonia.qubo import QuboModel
8
9# build the map coloring bqm model from here:
10# https://github.com/dwavesystems/dwave-ocean-sdk/blob/master/docs/examples/map_coloring_full_code.rst
11
12# Represent the map as the nodes and edges of a graph
13provinces = ["AB", "BC", "MB", "NB", "NL", "NS", "NT", "NU", "ON", "PE", "QC", "SK", "YT"]
14neighbors = [
15 ("AB", "BC"),
16 ("AB", "NT"),
17 ("AB", "SK"),
18 ("BC", "NT"),
19 ("BC", "YT"),
20 ("MB", "NU"),
21 ("MB", "ON"),
22 ("MB", "SK"),
23 ("NB", "NS"),
24 ("NB", "QC"),
25 ("NL", "QC"),
26 ("NT", "NU"),
27 ("NT", "SK"),
28 ("NT", "YT"),
29 ("ON", "QC"),
30]
31
32colors = ["y", "g", "r", "b"]
33
34# Add constraint that each node (province) select a single color
35bqm_one_color = BinaryQuadraticModel("BINARY")
36for province in provinces:
37 variables = [province + "_" + c for c in colors]
38 bqm_one_color.update(combinations(variables, 1))
39
40# Add constraint that each pair of nodes with a shared edge not both select one color
41bqm_neighbors = BinaryQuadraticModel("BINARY")
42for neighbor in neighbors:
43 v, u = neighbor
44 interactions = [(v + "_" + c, u + "_" + c) for c in colors]
45 for interaction in interactions:
46 bqm_neighbors.add_quadratic(interaction[0], interaction[1], 1)
47
48bqm = bqm_one_color + bqm_neighbors
49
50# read bqm file into QuboModel
51qubo = QuboModel.from_dwave_bqm(bqm)
52
53# solve QUBO with Quantagonia's solver
54API_KEY = os.environ["QUANTAGONIA_API_KEY"]
55params = HybridSolverParameters()
56hybrid_solver = HybridSolver(API_KEY)
57qubo.solve(hybrid_solver, params)
58
59# print solution vector
60print("Optimal solution vector:")
61for var_name, var in qubo.vars.items():
62 print("\t", var_name, "\t", var.eval())
63
64# in order to use these as test
65obj = qubo.eval()
66if obj != 0.0:
67 msg = f"Objective value is not correct: {obj} instead of 0.0"
68 raise ValueError(msg)
PyQUBO#
In this example we model the QUBO
using PyQUBO methods and import it into a QuboModel
to solve it with the HybridSolver:
1import os
2
3import pyqubo as pq
4
5from quantagonia import HybridSolver, HybridSolverParameters
6from quantagonia.qubo import QuboModel
7
8API_KEY = os.environ["QUANTAGONIA_API_KEY"]
9
10x0, x1, x2, x3, x4 = pq.Binary("x0"), pq.Binary("x1"), pq.Binary("x2"), pq.Binary("x3"), pq.Binary("x4")
11pyqubo_qubo = (2 * x0 + 2 * x2 + 2 * x4 - x0 * x2 - x2 * x0 - x0 * x4 - x4 * x0 - x2 * x4 - x4 * x2 + 3).compile()
12
13# setup model
14qubo = QuboModel.from_pyqubo(pyqubo_qubo)
15
16# solve with Quantagonia
17params = HybridSolverParameters()
18hybrid_solver = HybridSolver(API_KEY)
19qubo.solve(hybrid_solver, params)
20
21# to be used in tests
22obj = qubo.eval()
23if obj != 3.0:
24 msg = f"Objective value is not correct: {obj} instead of 3.0"
25 raise ValueError(msg)
Solve existing problems#
We first import the necessary modules and define the path to the input file, which can be either a QUBO or a MIP in .qubo, .mps, or, .lp file format.
1import os
2
3from quantagonia import HybridSolver, HybridSolverParameters
4
5input_file_path = os.path.join(os.path.dirname(os.path.abspath(__file__)), "data", "example.qubo")
Then, we retrieve the API key stored in an environment variable and set up a HybridSolver
object.
9api_key = os.environ["QUANTAGONIA_API_KEY"]
10hybrid_solver = HybridSolver(api_key)
After that, we set solver parameters and solve the problem with the HybridSolver. This is a blocking call, i.e., the solve function blocks until the problem is fully processed.
12params = HybridSolverParameters()
13res_dict, _ = hybrid_solver.solve(input_file_path, params)
After the problem has been solved, we retrieve and print some information and the solution vector.
15# print some results
16print("Runtime:", res_dict["timing"])
17print("Objective:", res_dict["objective"])
18print("Bound:", res_dict["bound"])
19print("Solution:")
20for idx, val in res_dict["solution"].items():
21 print(f"\t{idx}: {val}")
Submit and check#
Instead of using the blocking solve method, you can also use the submit method, to submit problem files to the HybridSolver. The method returns a jobid, which you can use to poll and print the progress.
First, do some setup as before:
2import os
3from time import sleep
4
5from quantagonia import HybridSolver, HybridSolverParameters
6from quantagonia.cloud.enums import JobStatus
7
8input_file_path = os.path.join(os.path.dirname(os.path.abspath(__file__)), "data", "air05.mps.gz")
9
10api_key = os.environ["QUANTAGONIA_API_KEY"]
11
12hybrid_solver = HybridSolver(api_key)
13params = HybridSolverParameters()
Then, submit the problem and retrieve a job ID:
15# submit the job
16jobid = hybrid_solver.submit(input_file_path, params)
We use the job ID to query the progress of the job.
18# check progress
19has_incumbents = False
20while not has_incumbents:
21 sleep(2)
22 # get intermediate progress information
23 p = hybrid_solver.progress(jobid)[0]
24 has_incumbents = p["num_incumbents"] >= 1
25print("Current status:")
26print(f" - Found solutions: {p['num_incumbents']}")
27print(f" - Objective Value: {p['objective']}")
28print(f" - Best Bound: {p['bound']}")
29print(f" - Relative Gap: {p['rel_gap']}")
We can also poll the status of the job and print the logs, after the job has been finished:
32# check status
33while hybrid_solver.status(jobid) != JobStatus.finished:
34 print("Wait until job is finished")
35 sleep(2)
36
37# get logs
38print("\nLogs:")
39logs = hybrid_solver.logs(jobid)
40print(logs[0])
Solve a batch of problems#
It is possible to submit several problems in one batched call. They do not have to be the same type, i.e., you can mix QUBOs and MIPs. Using a batched submission may be beneficial for short-running problems, for which submission times comprise a significant portion of the overall processing time. Not that in the example, the batch contains a garbage file, which cannot be read. Still, the job is processed successfully.
1import os
2
3from quantagonia import HybridSolver, HybridSolverParameters
4
5mip_path0 = os.path.join(os.path.dirname(os.path.abspath(__file__)), "data", "example.mps")
6mip_path1 = os.path.join(os.path.dirname(os.path.abspath(__file__)), "data", "garbage.mps")
7qubo_path = os.path.join(os.path.dirname(os.path.abspath(__file__)), "data", "example.qubo")
8api_key = os.environ["QUANTAGONIA_API_KEY"]
9
10hybrid_solver = HybridSolver(api_key)
11
12params = HybridSolverParameters()
13
14problems = [mip_path0, mip_path1, qubo_path]
15params = [params, params, params] # use the same parameters for all three problems
16results, _ = hybrid_solver.solve(problems, params, suppress_output=True) # blocks until all problems are solved
17
18for ix, res in enumerate(results):
19 print(f"=== PROBLEM {ix}: status {res['status']} ===")
20 print(res["solver_log"])
IP as QUBO#
Purely integer problems (IPs) can be reformulated to and solved as QUBOs by enabling the as_qubo
parameter.
1import math
2import os
3
4from quantagonia import HybridSolver, HybridSolverParameters
5
6input_file_path = os.path.join(os.path.dirname(os.path.abspath(__file__)), "data", "ip_as_qubo.lp")
7
8api_key = os.environ["QUANTAGONIA_API_KEY"]
9
10# setup the cloud-based solver instance
11hybrid_solver = HybridSolver(api_key)
12
13# set solver parameters
14params = HybridSolverParameters()
15params.set_as_qubo(True) # this parameterizes the solver to solve the IP as QUBO
16
17res_dict, _ = hybrid_solver.solve(input_file_path, params)
18
19# print some results
20print("Runtime:", res_dict["timing"])
21print("Objective:", res_dict["objective"])
22print("Bound:", res_dict["bound"])
23print("Solution:")
24for idx, val in res_dict["solution"].items():
25 print(f"\t{idx}: {val}")
26
27# in order to use these as test
28obj = res_dict["objective"]
29if math.fabs(obj - 4.0) > 1e-4:
30 msg = f"Objective value is not correct: {obj} instead of 4.0"
31 raise ValueError(msg)