Workflow Scheduling Problem
Introduction
We consider the following optimization problem (based on the formulation in [1]) : we have \(W(t)\) available workers or resources and \(N\) jobs that each job \(j\) requires \(T(j)\) time, and takes \(r(j)\) resources to be completed. Given a set of dependencies for each job, where we know which job depends on the completion of others before starting, we need to determine the order of job completion that minimizes the total execution time.
Assumptions
-
a job may occupy only a single time slot at most: \(\forall j \,\,\, T(j) = 1\)
-
given sufficient resources, jobs can be started in the same time slot
-
all resources are identical and the amount of available resources at a current time step is given by the number \(W(t)\)
-
jobs can only be started if all parent jobs are completed.
Possible extensions
-
Separate resources into multiple categories with jobs requiring different types
-
Jobs that take more than one operation
Mathematical Modeling
The input of the model is
We define a binary variable for the optimization problem: an \(t_{max}\times N\) matrix \(x\) such that \(\begin{aligned} x_{tj} = \begin{cases} 1 & \text{job } j \text{ is done on the } t_\text{th} \text{ time slot} \\ 0 & \text{else} \end{cases}\\ \end{aligned}\)
We have 3 constraints:
(1) All jobs must be completed exactly once: \(\forall j\in[1,N] \,\,\, \sum_t x_{tj}=1\)
(2) All jobs may use no more than the available resources: \(\forall t\in[0,t_{max}] \,\,\, \sum_j x_{tj} r_j \leq W_t\)
(3) All dependent jobs must have parent jobs completed before starting \(x_{t_1j_1} x_{t_2j_2} = 0 \,\,\, \forall j_1, t_1\leq t_2, j_2 \text{ depends on } j_1\)
The objective function to minimize is the total cost function:
\[\min_{x} \sum_{t} x_{tN}\cdot t\]
which favors schedules that are done early.
Defining the optimization model
from typing import List, Tuple, cast # noqa
import matplotlib.pyplot as plt
import networkx as nx
import numpy as np # noqa
import pandas as pd
import pyomo.environ as pyo
from IPython.display import Markdown, display
def define_workflow_problem(
G, num_timeslots, available_capacities, work_loads
) -> pyo.ConcreteModel:
model = pyo.ConcreteModel("task_scheduling")
timeslots = range(num_timeslots)
assert len(timeslots) == len(available_capacities)
works = range(len(G.nodes))
assert len(works) == len(work_loads)
last_works = [node for node in G.nodes if G.out_degree(node) == 0]
assert len(last_works) == 1
last_work = last_works[0]
# works with no dependancies
root_works = [node for node in G.nodes if G.in_degree(node) == 0]
model.x = pyo.Var(timeslots, works, domain=pyo.Binary)
@model.Constraint(works)
def all_works_are_done(model, i): # constraint (1)
return sum(model.x[t, i] for t in timeslots) == 1
@model.Constraint(timeslots)
def capacity_is_valid(model, t): # constraint(2)
return (
sum(model.x[t, i] * work_loads[i] for i in works) <= available_capacities[t]
)
@model.Constraint(works, works, timeslots, timeslots)
def works_done_by_their_order(model, i, j, t1, t2): # constraint (3)
if G.has_edge(i, j) and t1 >= t2:
return model.x[t1, i] * model.x[t2, j] == 0
return pyo.Constraint.Feasible
# eliminate all timeslots that are not possible for the task in order to save qubits
distances_from_ends = nx.floyd_warshall_numpy(G)
distances_from_roots = nx.floyd_warshall_numpy(G.reverse())
@model.Constraint(works, timeslots)
def eliminating_rule(model, i, t):
end_distance = int(np.min(distances_from_ends[i, last_works]))
start_distance = int(np.min(distances_from_roots[i, root_works]))
if (t < start_distance) or (t >= len(timeslots) - end_distance):
return model.x[t, i] == 0
return pyo.Constraint.Feasible
# minimize the end time of the last work
model.cost = pyo.Objective(
expr=sum(model.x[t, last_work] * (t + 1) for t in timeslots), sense=pyo.minimize
)
return model
Visualization helper functions
import random
def plot_graph(solution=None, ax=None):
if solution is not None:
# determine how many tasks start in each timeslot
num_tasks = [sum(solution[t]) for t in range(num_timeslots)]
max_tasks = max(num_tasks)
pos = {}
# find all the tasks that start in particular start time
for start in np.nonzero(solution.sum(axis=1))[0]:
locations = solution[start].nonzero()[0]
pos.update(
{
n: (start, i + (max_tasks - num_tasks[start]) / 2)
for i, n in enumerate(locations)
}
)
else:
pos = {
node: (order, random.random())
for order, node in enumerate((nx.topological_sort(G)))
}
options = {
"font_size": 12,
"node_size": 1000,
"node_color": "white",
"edgecolors": "black",
"linewidths": 3,
"width": 3,
}
# G = nx.DiGraph(edges)
nx.draw_networkx(G, pos, ax=ax, **options)
# Set margins for the axes so that nodes aren't clipped
if ax is None:
ax = plt.subplot()
ax.margins(0.20)
if solution is not None:
ax.set_title("Suggested sequence")
ax.set_xlabel("Timeslot")
def plot_assignments(solution, ax=None):
if ax is None:
ax = plt.subplot()
ax.pcolormesh(solution.T, edgecolors="w", linewidth=4, cmap="OrRd")
ax.set_aspect(0.8)
ax.set_xlabel("Timeslot")
ax.set_ylabel("Task Number")
ax.set_title("Task assignment")
def plot_resource_graph(solution=None, ax=None):
if ax is None:
fig, ax = plt.subplots()
x_pos = np.arange(len(capacities))
if solution is not None:
ax.set_title("Utilization")
num_resources = [np.dot(solution[t], workloads) for t in range(num_timeslots)]
ax.bar(x_pos + 0.1, num_resources, label="used resources", color="r", width=0.5)
ax.bar(x_pos, capacities, label="available_resources", color="g", width=0.5)
ax.set_xticks(x_pos)
ax.legend()
ax.set_xlabel("Timeslot")
ax.set_ylabel("Resources")
def plot_workloads(ax=None):
if ax is None:
fig, ax = plt.subplots()
ax.set_title("Work Loads")
x_pos = np.arange(len(workloads))
ax.bar(x_pos, workloads, width=0.5)
ax.set_xticks(x_pos)
ax.set_xlabel("Jobs")
ax.set_ylabel("Required Resources")
def is_printable_solution(solution):
return np.array_equal(solution.sum(axis=0), np.ones(solution.shape[1]))
def plot_workflow(solution=None):
if solution is None:
fig, axes = plt.subplots(1, 3, figsize=(18, 5))
plot_resource_graph(ax=axes[0])
plot_graph(ax=axes[1])
plot_workloads(ax=axes[2])
else:
if is_printable_solution(solution):
fig, axes = plt.subplots(2, 2, figsize=(12, 10))
plot_resource_graph(solution, axes[0, 0])
plot_workloads(axes[0, 1])
plot_assignments(solution, axes[1, 1])
plot_graph(solution, axes[1, 0])
else:
# illegal solution
fig, axes = plt.subplots(1, 3, figsize=(18, 5))
plot_resource_graph(solution, axes[0])
plot_workloads(axes[1])
plot_assignments(solution, axes[2])
Initialize specific problem instance
We create a workflow dependecies graph. For the small instance, all timeslots capacities and work loads are equal to each other.
def small_example():
G = nx.DiGraph()
nodes = range(4)
edges = [(0, 1), (1, 3), (2, 3)]
G.add_nodes_from(nodes)
G.add_edges_from(edges)
num_timeslots = len(G.nodes) - 1
capacities = 3 * np.ones(num_timeslots)
workloads = np.ones(len(nodes))
return (
define_workflow_problem(
G, num_timeslots, available_capacities=capacities, work_loads=workloads
),
G,
num_timeslots,
capacities,
workloads,
)
def large_example():
G = nx.DiGraph()
nodes = range(6)
edges = [(0, 1), (0, 3), (0, 2), (2, 4), (3, 4), (1, 5), (4, 5)]
workloads = [1, 3, 2, 2, 1, 1]
capacities = [1, 3, 4, 3, 1]
G.add_nodes_from(nodes)
G.add_edges_from(edges)
num_timeslots = len(capacities)
return (
define_workflow_problem(
G, num_timeslots, available_capacities=capacities, work_loads=workloads
),
G,
num_timeslots,
capacities,
workloads,
)
tasks_model, G, num_timeslots, capacities, workloads = small_example()
plot_workflow()
The resulting Pyomo model
tasks_model.pprint()
13 Set Declarations
all_works_are_done_index : Size=1, Index=None, Ordered=Insertion
Key : Dimen : Domain : Size : Members
None : 1 : Any : 4 : {0, 1, 2, 3}
capacity_is_valid_index : Size=1, Index=None, Ordered=Insertion
Key : Dimen : Domain : Size : Members
None : 1 : Any : 3 : {0, 1, 2}
eliminating_rule_index : Size=1, Index=None, Ordered=True
Key : Dimen : Domain : Size : Members
None : 2 : eliminating_rule_index_0*eliminating_rule_index_1 : 12 : {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2), (3, 0), (3, 1), (3, 2)}
eliminating_rule_index_0 : Size=1, Index=None, Ordered=Insertion
Key : Dimen : Domain : Size : Members
None : 1 : Any : 4 : {0, 1, 2, 3}
eliminating_rule_index_1 : Size=1, Index=None, Ordered=Insertion
Key : Dimen : Domain : Size : Members
None : 1 : Any : 3 : {0, 1, 2}
works_done_by_their_order_index : Size=1, Index=None, Ordered=True
Key : Dimen : Domain : Size : Members
None : 4 : works_done_by_their_order_index_0*works_done_by_their_order_index_1*works_done_by_their_order_index_2*works_done_by_their_order_index_3 : 144 : {(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 0, 2), (0, 0, 1, 0), (0, 0, 1, 1), (0, 0, 1, 2), (0, 0, 2, 0), (0, 0, 2, 1), (0, 0, 2, 2), (0, 1, 0, 0), (0, 1, 0, 1), (0, 1, 0, 2), (0, 1, 1, 0), (0, 1, 1, 1), (0, 1, 1, 2), (0, 1, 2, 0), (0, 1, 2, 1), (0, 1, 2, 2), (0, 2, 0, 0), (0, 2, 0, 1), (0, 2, 0, 2), (0, 2, 1, 0), (0, 2, 1, 1), (0, 2, 1, 2), (0, 2, 2, 0), (0, 2, 2, 1), (0, 2, 2, 2), (0, 3, 0, 0), (0, 3, 0, 1), (0, 3, 0, 2), (0, 3, 1, 0), (0, 3, 1, 1), (0, 3, 1, 2), (0, 3, 2, 0), (0, 3, 2, 1), (0, 3, 2, 2), (1, 0, 0, 0), (1, 0, 0, 1), (1, 0, 0, 2), (1, 0, 1, 0), (1, 0, 1, 1), (1, 0, 1, 2), (1, 0, 2, 0), (1, 0, 2, 1), (1, 0, 2, 2), (1, 1, 0, 0), (1, 1, 0, 1), (1, 1, 0, 2), (1, 1, 1, 0), (1, 1, 1, 1), (1, 1, 1, 2), (1, 1, 2, 0), (1, 1, 2, 1), (1, 1, 2, 2), (1, 2, 0, 0), (1, 2, 0, 1), (1, 2, 0, 2), (1, 2, 1, 0), (1, 2, 1, 1), (1, 2, 1, 2), (1, 2, 2, 0), (1, 2, 2, 1), (1, 2, 2, 2), (1, 3, 0, 0), (1, 3, 0, 1), (1, 3, 0, 2), (1, 3, 1, 0), (1, 3, 1, 1), (1, 3, 1, 2), (1, 3, 2, 0), (1, 3, 2, 1), (1, 3, 2, 2), (2, 0, 0, 0), (2, 0, 0, 1), (2, 0, 0, 2), (2, 0, 1, 0), (2, 0, 1, 1), (2, 0, 1, 2), (2, 0, 2, 0), (2, 0, 2, 1), (2, 0, 2, 2), (2, 1, 0, 0), (2, 1, 0, 1), (2, 1, 0, 2), (2, 1, 1, 0), (2, 1, 1, 1), (2, 1, 1, 2), (2, 1, 2, 0), (2, 1, 2, 1), (2, 1, 2, 2), (2, 2, 0, 0), (2, 2, 0, 1), (2, 2, 0, 2), (2, 2, 1, 0), (2, 2, 1, 1), (2, 2, 1, 2), (2, 2, 2, 0), (2, 2, 2, 1), (2, 2, 2, 2), (2, 3, 0, 0), (2, 3, 0, 1), (2, 3, 0, 2), (2, 3, 1, 0), (2, 3, 1, 1), (2, 3, 1, 2), (2, 3, 2, 0), (2, 3, 2, 1), (2, 3, 2, 2), (3, 0, 0, 0), (3, 0, 0, 1), (3, 0, 0, 2), (3, 0, 1, 0), (3, 0, 1, 1), (3, 0, 1, 2), (3, 0, 2, 0), (3, 0, 2, 1), (3, 0, 2, 2), (3, 1, 0, 0), (3, 1, 0, 1), (3, 1, 0, 2), (3, 1, 1, 0), (3, 1, 1, 1), (3, 1, 1, 2), (3, 1, 2, 0), (3, 1, 2, 1), (3, 1, 2, 2), (3, 2, 0, 0), (3, 2, 0, 1), (3, 2, 0, 2), (3, 2, 1, 0), (3, 2, 1, 1), (3, 2, 1, 2), (3, 2, 2, 0), (3, 2, 2, 1), (3, 2, 2, 2), (3, 3, 0, 0), (3, 3, 0, 1), (3, 3, 0, 2), (3, 3, 1, 0), (3, 3, 1, 1), (3, 3, 1, 2), (3, 3, 2, 0), (3, 3, 2, 1), (3, 3, 2, 2)}
works_done_by_their_order_index_0 : Size=1, Index=None, Ordered=Insertion
Key : Dimen : Domain : Size : Members
None : 1 : Any : 4 : {0, 1, 2, 3}
works_done_by_their_order_index_1 : Size=1, Index=None, Ordered=Insertion
Key : Dimen : Domain : Size : Members
None : 1 : Any : 4 : {0, 1, 2, 3}
works_done_by_their_order_index_2 : Size=1, Index=None, Ordered=Insertion
Key : Dimen : Domain : Size : Members
None : 1 : Any : 3 : {0, 1, 2}
works_done_by_their_order_index_3 : Size=1, Index=None, Ordered=Insertion
Key : Dimen : Domain : Size : Members
None : 1 : Any : 3 : {0, 1, 2}
x_index : Size=1, Index=None, Ordered=True
Key : Dimen : Domain : Size : Members
None : 2 : x_index_0*x_index_1 : 12 : {(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3), (2, 0), (2, 1), (2, 2), (2, 3)}
x_index_0 : Size=1, Index=None, Ordered=Insertion
Key : Dimen : Domain : Size : Members
None : 1 : Any : 3 : {0, 1, 2}
x_index_1 : Size=1, Index=None, Ordered=Insertion
Key : Dimen : Domain : Size : Members
None : 1 : Any : 4 : {0, 1, 2, 3}
1 Var Declarations
x : Size=12, Index=x_index
Key : Lower : Value : Upper : Fixed : Stale : Domain
(0, 0) : 0 : None : 1 : False : True : Binary
(0, 1) : 0 : None : 1 : False : True : Binary
(0, 2) : 0 : None : 1 : False : True : Binary
(0, 3) : 0 : None : 1 : False : True : Binary
(1, 0) : 0 : None : 1 : False : True : Binary
(1, 1) : 0 : None : 1 : False : True : Binary
(1, 2) : 0 : None : 1 : False : True : Binary
(1, 3) : 0 : None : 1 : False : True : Binary
(2, 0) : 0 : None : 1 : False : True : Binary
(2, 1) : 0 : None : 1 : False : True : Binary
(2, 2) : 0 : None : 1 : False : True : Binary
(2, 3) : 0 : None : 1 : False : True : Binary
1 Objective Declarations
cost : Size=1, Index=None, Active=True
Key : Active : Sense : Expression
None : True : minimize : x[0,3] + 2*x[1,3] + 3*x[2,3]
4 Constraint Declarations
all_works_are_done : Size=4, Index=all_works_are_done_index, Active=True
Key : Lower : Body : Upper : Active
0 : 1.0 : x[0,0] + x[1,0] + x[2,0] : 1.0 : True
1 : 1.0 : x[0,1] + x[1,1] + x[2,1] : 1.0 : True
2 : 1.0 : x[0,2] + x[1,2] + x[2,2] : 1.0 : True
3 : 1.0 : x[0,3] + x[1,3] + x[2,3] : 1.0 : True
capacity_is_valid : Size=3, Index=capacity_is_valid_index, Active=True
Key : Lower : Body : Upper : Active
0 : -Inf : x[0,0] + x[0,1] + x[0,2] + x[0,3] : 3.0 : True
1 : -Inf : x[1,0] + x[1,1] + x[1,2] + x[1,3] : 3.0 : True
2 : -Inf : x[2,0] + x[2,1] + x[2,2] + x[2,3] : 3.0 : True
eliminating_rule : Size=6, Index=eliminating_rule_index, Active=True
Key : Lower : Body : Upper : Active
(0, 1) : 0.0 : x[1,0] : 0.0 : True
(0, 2) : 0.0 : x[2,0] : 0.0 : True
(1, 0) : 0.0 : x[0,1] : 0.0 : True
(1, 2) : 0.0 : x[2,1] : 0.0 : True
(2, 2) : 0.0 : x[2,2] : 0.0 : True
(3, 0) : 0.0 : x[0,3] : 0.0 : True
works_done_by_their_order : Size=18, Index=works_done_by_their_order_index, Active=True
Key : Lower : Body : Upper : Active
(0, 1, 0, 0) : 0.0 : x[0,0]*x[0,1] : 0.0 : True
(0, 1, 1, 0) : 0.0 : x[1,0]*x[0,1] : 0.0 : True
(0, 1, 1, 1) : 0.0 : x[1,0]*x[1,1] : 0.0 : True
(0, 1, 2, 0) : 0.0 : x[2,0]*x[0,1] : 0.0 : True
(0, 1, 2, 1) : 0.0 : x[2,0]*x[1,1] : 0.0 : True
(0, 1, 2, 2) : 0.0 : x[2,0]*x[2,1] : 0.0 : True
(1, 3, 0, 0) : 0.0 : x[0,1]*x[0,3] : 0.0 : True
(1, 3, 1, 0) : 0.0 : x[1,1]*x[0,3] : 0.0 : True
(1, 3, 1, 1) : 0.0 : x[1,1]*x[1,3] : 0.0 : True
(1, 3, 2, 0) : 0.0 : x[2,1]*x[0,3] : 0.0 : True
(1, 3, 2, 1) : 0.0 : x[2,1]*x[1,3] : 0.0 : True
(1, 3, 2, 2) : 0.0 : x[2,1]*x[2,3] : 0.0 : True
(2, 3, 0, 0) : 0.0 : x[0,2]*x[0,3] : 0.0 : True
(2, 3, 1, 0) : 0.0 : x[1,2]*x[0,3] : 0.0 : True
(2, 3, 1, 1) : 0.0 : x[1,2]*x[1,3] : 0.0 : True
(2, 3, 2, 0) : 0.0 : x[2,2]*x[0,3] : 0.0 : True
(2, 3, 2, 1) : 0.0 : x[2,2]*x[1,3] : 0.0 : True
(2, 3, 2, 2) : 0.0 : x[2,2]*x[2,3] : 0.0 : True
19 Declarations: x_index_0 x_index_1 x_index x all_works_are_done_index all_works_are_done capacity_is_valid_index capacity_is_valid works_done_by_their_order_index_0 works_done_by_their_order_index_1 works_done_by_their_order_index_2 works_done_by_their_order_index_3 works_done_by_their_order_index works_done_by_their_order eliminating_rule_index_0 eliminating_rule_index_1 eliminating_rule_index eliminating_rule cost
Solve the optimization model with hybrid classical/quantum QAOA (Quantum Approximate Optimization Algorithm)
Setting Up the Classiq Problem Instance
In order to solve the Pyomo model defined above, we use the Classiq combinatorial optimization engine. For the quantum part of the QAOA algorithm (QAOAConfig) - define the number of repetitions (num_layers):
from classiq import construct_combinatorial_optimization_model
from classiq.applications.combinatorial_optimization import OptimizerConfig, QAOAConfig
qaoa_config = QAOAConfig(num_layers=8, penalty_energy=20)
For the classical optimization part of the QAOA algorithm we define the maximum number of classical iterations (max_iteration) and the \(\alpha\)-parameter (alpha_cvar) for running CVaR-QAOA, an improved variation of the QAOA algorithm [3]:
optimizer_config = OptimizerConfig(max_iteration=20.0, alpha_cvar=0.3)
Lastly, we load the model, based on the problem and algorithm parameters, which we can use to solve the problem:
qmod = construct_combinatorial_optimization_model(
pyo_model=tasks_model,
qaoa_config=qaoa_config,
optimizer_config=optimizer_config,
)
We also set the quantum backend we want to execute on:
from classiq import set_execution_preferences
from classiq.execution import ClassiqBackendPreferences, ExecutionPreferences
backend_preferences = ExecutionPreferences(
backend_preferences=ClassiqBackendPreferences(backend_name="simulator")
)
qmod = set_execution_preferences(qmod, backend_preferences)
from classiq import write_qmod
write_qmod(qmod, "task_scheduling_problem")
Synthesizing the QAOA Circuit and Solving the Problem
We can now synthesize and view the QAOA circuit (ansatz) used to solve the optimization problem:
from classiq import show, synthesize
qprog = synthesize(qmod)
show(qprog)
Opening: https://platform.classiq.io/circuit/f5e85b37-3f5f-45a4-851e-c3690030a4cd?version=0.41.0.dev39%2B79c8fd0855
We now solve the problem by calling the execute function on the quantum program we have generated:
from classiq import execute
res = execute(qprog).result()
Analyzing the results
We can check the convergence of the run:
from classiq.execution import VQESolverResult
vqe_result = res[0].value
vqe_result.convergence_graph
And print the optimization results:
import pandas as pd
from classiq.applications.combinatorial_optimization import (
get_optimization_solution_from_pyo,
)
solution = get_optimization_solution_from_pyo(
tasks_model, vqe_result=vqe_result, penalty_energy=qaoa_config.penalty_energy
)
optimization_result = pd.DataFrame.from_records(solution)
optimization_result.sort_values(by="cost", ascending=True).head(5)
| probability | cost | solution | count | |
|---|---|---|---|---|
| 0 | 0.069 | 3.0 | [0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0] | 69 |
| 1 | 0.068 | 3.0 | [1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0] | 68 |
| 3 | 0.064 | 3.0 | [0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0] | 64 |
| 4 | 0.059 | 3.0 | [1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0] | 59 |
| 39 | 0.003 | 23.0 | [0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0] | 3 |
idx = optimization_result.cost.idxmin()
print(
"x =", optimization_result.solution[idx], ", cost =", optimization_result.cost[idx]
)
x = [0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0] , cost = 3.0
And the histogram:
optimization_result.hist("cost", weights=optimization_result["probability"])
array([[<Axes: title={'center': 'cost'}>]], dtype=object)
Best solution
qaoa_solution = np.array(
optimization_result.solution[optimization_result.cost.idxmin()]
).reshape(num_timeslots, len(G.nodes))
plot_workflow(qaoa_solution)
Compare to a classical optimizer result
from pyomo.opt import SolverFactory
solver = SolverFactory("couenne")
solver.solve(tasks_model)
tasks_model.display()
Model task_scheduling
Variables:
x : Size=12, Index=x_index
Key : Lower : Value : Upper : Fixed : Stale : Domain
(0, 0) : 0 : 1.0 : 1 : False : False : Binary
(0, 1) : 0 : 0.0 : 1 : False : False : Binary
(0, 2) : 0 : 1.0 : 1 : False : False : Binary
(0, 3) : 0 : 0.0 : 1 : False : False : Binary
(1, 0) : 0 : 0.0 : 1 : False : False : Binary
(1, 1) : 0 : 1.0 : 1 : False : False : Binary
(1, 2) : 0 : 0.0 : 1 : False : False : Binary
(1, 3) : 0 : 0.0 : 1 : False : False : Binary
(2, 0) : 0 : 0.0 : 1 : False : False : Binary
(2, 1) : 0 : 0.0 : 1 : False : False : Binary
(2, 2) : 0 : 0.0 : 1 : False : False : Binary
(2, 3) : 0 : 1.0 : 1 : False : False : Binary
Objectives:
cost : Size=1, Index=None, Active=True
Key : Active : Value
None : True : 3.0
Constraints:
all_works_are_done : Size=4
Key : Lower : Body : Upper
0 : 1.0 : 1.0 : 1.0
1 : 1.0 : 1.0 : 1.0
2 : 1.0 : 1.0 : 1.0
3 : 1.0 : 1.0 : 1.0
capacity_is_valid : Size=3
Key : Lower : Body : Upper
0 : None : 2.0 : 3.0
1 : None : 1.0 : 3.0
2 : None : 1.0 : 3.0
works_done_by_their_order : Size=18
Key : Lower : Body : Upper
(0, 1, 0, 0) : 0.0 : 0.0 : 0.0
(0, 1, 1, 0) : 0.0 : 0.0 : 0.0
(0, 1, 1, 1) : 0.0 : 0.0 : 0.0
(0, 1, 2, 0) : 0.0 : 0.0 : 0.0
(0, 1, 2, 1) : 0.0 : 0.0 : 0.0
(0, 1, 2, 2) : 0.0 : 0.0 : 0.0
(1, 3, 0, 0) : 0.0 : 0.0 : 0.0
(1, 3, 1, 0) : 0.0 : 0.0 : 0.0
(1, 3, 1, 1) : 0.0 : 0.0 : 0.0
(1, 3, 2, 0) : 0.0 : 0.0 : 0.0
(1, 3, 2, 1) : 0.0 : 0.0 : 0.0
(1, 3, 2, 2) : 0.0 : 0.0 : 0.0
(2, 3, 0, 0) : 0.0 : 0.0 : 0.0
(2, 3, 1, 0) : 0.0 : 0.0 : 0.0
(2, 3, 1, 1) : 0.0 : 0.0 : 0.0
(2, 3, 2, 0) : 0.0 : 0.0 : 0.0
(2, 3, 2, 1) : 0.0 : 0.0 : 0.0
(2, 3, 2, 2) : 0.0 : 0.0 : 0.0
eliminating_rule : Size=6
Key : Lower : Body : Upper
(0, 1) : 0.0 : 0.0 : 0.0
(0, 2) : 0.0 : 0.0 : 0.0
(1, 0) : 0.0 : 0.0 : 0.0
(1, 2) : 0.0 : 0.0 : 0.0
(2, 2) : 0.0 : 0.0 : 0.0
(3, 0) : 0.0 : 0.0 : 0.0
classical_solution = np.array(
[
int(pyo.value(tasks_model.x[idx]))
for idx in np.ndindex(num_timeslots, len(G.nodes))
]
).reshape(num_timeslots, len(G.nodes))
plot_workflow(classical_solution)
Large Example
We will try a more elaborate example, involving more works with non-uniform workloads and resources.
tasks_model_large, G, num_timeslots, capacities, workloads = large_example()
plot_workflow()
tasks_model_large.pprint()
13 Set Declarations
all_works_are_done_index : Size=1, Index=None, Ordered=Insertion
Key : Dimen : Domain : Size : Members
None : 1 : Any : 6 : {0, 1, 2, 3, 4, 5}
capacity_is_valid_index : Size=1, Index=None, Ordered=Insertion
Key : Dimen : Domain : Size : Members
None : 1 : Any : 5 : {0, 1, 2, 3, 4}
eliminating_rule_index : Size=1, Index=None, Ordered=True
Key : Dimen : Domain : Size : Members
None : 2 : eliminating_rule_index_0*eliminating_rule_index_1 : 30 : {(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (3, 0), (3, 1), (3, 2), (3, 3), (3, 4), (4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (5, 0), (5, 1), (5, 2), (5, 3), (5, 4)}
eliminating_rule_index_0 : Size=1, Index=None, Ordered=Insertion
Key : Dimen : Domain : Size : Members
None : 1 : Any : 6 : {0, 1, 2, 3, 4, 5}
eliminating_rule_index_1 : Size=1, Index=None, Ordered=Insertion
Key : Dimen : Domain : Size : Members
None : 1 : Any : 5 : {0, 1, 2, 3, 4}
works_done_by_their_order_index : Size=1, Index=None, Ordered=True
Key : Dimen : Domain : Size : Members
None : 4 : works_done_by_their_order_index_0*works_done_by_their_order_index_1*works_done_by_their_order_index_2*works_done_by_their_order_index_3 : 900 : {(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 0, 2), (0, 0, 0, 3), (0, 0, 0, 4), (0, 0, 1, 0), (0, 0, 1, 1), (0, 0, 1, 2), (0, 0, 1, 3), (0, 0, 1, 4), (0, 0, 2, 0), (0, 0, 2, 1), (0, 0, 2, 2), (0, 0, 2, 3), (0, 0, 2, 4), (0, 0, 3, 0), (0, 0, 3, 1), (0, 0, 3, 2), (0, 0, 3, 3), (0, 0, 3, 4), (0, 0, 4, 0), (0, 0, 4, 1), (0, 0, 4, 2), (0, 0, 4, 3), (0, 0, 4, 4), (0, 1, 0, 0), (0, 1, 0, 1), (0, 1, 0, 2), (0, 1, 0, 3), (0, 1, 0, 4), (0, 1, 1, 0), (0, 1, 1, 1), (0, 1, 1, 2), (0, 1, 1, 3), (0, 1, 1, 4), (0, 1, 2, 0), (0, 1, 2, 1), (0, 1, 2, 2), (0, 1, 2, 3), (0, 1, 2, 4), (0, 1, 3, 0), (0, 1, 3, 1), (0, 1, 3, 2), (0, 1, 3, 3), (0, 1, 3, 4), (0, 1, 4, 0), (0, 1, 4, 1), (0, 1, 4, 2), (0, 1, 4, 3), (0, 1, 4, 4), (0, 2, 0, 0), (0, 2, 0, 1), (0, 2, 0, 2), (0, 2, 0, 3), (0, 2, 0, 4), (0, 2, 1, 0), (0, 2, 1, 1), (0, 2, 1, 2), (0, 2, 1, 3), (0, 2, 1, 4), (0, 2, 2, 0), (0, 2, 2, 1), (0, 2, 2, 2), (0, 2, 2, 3), (0, 2, 2, 4), (0, 2, 3, 0), (0, 2, 3, 1), (0, 2, 3, 2), (0, 2, 3, 3), (0, 2, 3, 4), (0, 2, 4, 0), (0, 2, 4, 1), (0, 2, 4, 2), (0, 2, 4, 3), (0, 2, 4, 4), (0, 3, 0, 0), (0, 3, 0, 1), (0, 3, 0, 2), (0, 3, 0, 3), (0, 3, 0, 4), (0, 3, 1, 0), (0, 3, 1, 1), (0, 3, 1, 2), (0, 3, 1, 3), (0, 3, 1, 4), (0, 3, 2, 0), (0, 3, 2, 1), (0, 3, 2, 2), (0, 3, 2, 3), (0, 3, 2, 4), (0, 3, 3, 0), (0, 3, 3, 1), (0, 3, 3, 2), (0, 3, 3, 3), (0, 3, 3, 4), (0, 3, 4, 0), (0, 3, 4, 1), (0, 3, 4, 2), (0, 3, 4, 3), (0, 3, 4, 4), (0, 4, 0, 0), (0, 4, 0, 1), (0, 4, 0, 2), (0, 4, 0, 3), (0, 4, 0, 4), (0, 4, 1, 0), (0, 4, 1, 1), (0, 4, 1, 2), (0, 4, 1, 3), (0, 4, 1, 4), (0, 4, 2, 0), (0, 4, 2, 1), (0, 4, 2, 2), (0, 4, 2, 3), (0, 4, 2, 4), (0, 4, 3, 0), (0, 4, 3, 1), (0, 4, 3, 2), (0, 4, 3, 3), (0, 4, 3, 4), (0, 4, 4, 0), (0, 4, 4, 1), (0, 4, 4, 2), (0, 4, 4, 3), (0, 4, 4, 4), (0, 5, 0, 0), (0, 5, 0, 1), (0, 5, 0, 2), (0, 5, 0, 3), (0, 5, 0, 4), (0, 5, 1, 0), (0, 5, 1, 1), (0, 5, 1, 2), (0, 5, 1, 3), (0, 5, 1, 4), (0, 5, 2, 0), (0, 5, 2, 1), (0, 5, 2, 2), (0, 5, 2, 3), (0, 5, 2, 4), (0, 5, 3, 0), (0, 5, 3, 1), (0, 5, 3, 2), (0, 5, 3, 3), (0, 5, 3, 4), (0, 5, 4, 0), (0, 5, 4, 1), (0, 5, 4, 2), (0, 5, 4, 3), (0, 5, 4, 4), (1, 0, 0, 0), (1, 0, 0, 1), (1, 0, 0, 2), (1, 0, 0, 3), (1, 0, 0, 4), (1, 0, 1, 0), (1, 0, 1, 1), (1, 0, 1, 2), (1, 0, 1, 3), (1, 0, 1, 4), (1, 0, 2, 0), (1, 0, 2, 1), (1, 0, 2, 2), (1, 0, 2, 3), (1, 0, 2, 4), (1, 0, 3, 0), (1, 0, 3, 1), (1, 0, 3, 2), (1, 0, 3, 3), (1, 0, 3, 4), (1, 0, 4, 0), (1, 0, 4, 1), (1, 0, 4, 2), (1, 0, 4, 3), (1, 0, 4, 4), (1, 1, 0, 0), (1, 1, 0, 1), (1, 1, 0, 2), (1, 1, 0, 3), (1, 1, 0, 4), (1, 1, 1, 0), (1, 1, 1, 1), (1, 1, 1, 2), (1, 1, 1, 3), (1, 1, 1, 4), (1, 1, 2, 0), (1, 1, 2, 1), (1, 1, 2, 2), (1, 1, 2, 3), (1, 1, 2, 4), (1, 1, 3, 0), (1, 1, 3, 1), (1, 1, 3, 2), (1, 1, 3, 3), (1, 1, 3, 4), (1, 1, 4, 0), (1, 1, 4, 1), (1, 1, 4, 2), (1, 1, 4, 3), (1, 1, 4, 4), (1, 2, 0, 0), (1, 2, 0, 1), (1, 2, 0, 2), (1, 2, 0, 3), (1, 2, 0, 4), (1, 2, 1, 0), (1, 2, 1, 1), (1, 2, 1, 2), (1, 2, 1, 3), (1, 2, 1, 4), (1, 2, 2, 0), (1, 2, 2, 1), (1, 2, 2, 2), (1, 2, 2, 3), (1, 2, 2, 4), (1, 2, 3, 0), (1, 2, 3, 1), (1, 2, 3, 2), (1, 2, 3, 3), (1, 2, 3, 4), (1, 2, 4, 0), (1, 2, 4, 1), (1, 2, 4, 2), (1, 2, 4, 3), (1, 2, 4, 4), (1, 3, 0, 0), (1, 3, 0, 1), (1, 3, 0, 2), (1, 3, 0, 3), (1, 3, 0, 4), (1, 3, 1, 0), (1, 3, 1, 1), (1, 3, 1, 2), (1, 3, 1, 3), (1, 3, 1, 4), (1, 3, 2, 0), (1, 3, 2, 1), (1, 3, 2, 2), (1, 3, 2, 3), (1, 3, 2, 4), (1, 3, 3, 0), (1, 3, 3, 1), (1, 3, 3, 2), (1, 3, 3, 3), (1, 3, 3, 4), (1, 3, 4, 0), (1, 3, 4, 1), (1, 3, 4, 2), (1, 3, 4, 3), (1, 3, 4, 4), (1, 4, 0, 0), (1, 4, 0, 1), (1, 4, 0, 2), (1, 4, 0, 3), (1, 4, 0, 4), (1, 4, 1, 0), (1, 4, 1, 1), (1, 4, 1, 2), (1, 4, 1, 3), (1, 4, 1, 4), (1, 4, 2, 0), (1, 4, 2, 1), (1, 4, 2, 2), (1, 4, 2, 3), (1, 4, 2, 4), (1, 4, 3, 0), (1, 4, 3, 1), (1, 4, 3, 2), (1, 4, 3, 3), (1, 4, 3, 4), (1, 4, 4, 0), (1, 4, 4, 1), (1, 4, 4, 2), (1, 4, 4, 3), (1, 4, 4, 4), (1, 5, 0, 0), (1, 5, 0, 1), (1, 5, 0, 2), (1, 5, 0, 3), (1, 5, 0, 4), (1, 5, 1, 0), (1, 5, 1, 1), (1, 5, 1, 2), (1, 5, 1, 3), (1, 5, 1, 4), (1, 5, 2, 0), (1, 5, 2, 1), (1, 5, 2, 2), (1, 5, 2, 3), (1, 5, 2, 4), (1, 5, 3, 0), (1, 5, 3, 1), (1, 5, 3, 2), (1, 5, 3, 3), (1, 5, 3, 4), (1, 5, 4, 0), (1, 5, 4, 1), (1, 5, 4, 2), (1, 5, 4, 3), (1, 5, 4, 4), (2, 0, 0, 0), (2, 0, 0, 1), (2, 0, 0, 2), (2, 0, 0, 3), (2, 0, 0, 4), (2, 0, 1, 0), (2, 0, 1, 1), (2, 0, 1, 2), (2, 0, 1, 3), (2, 0, 1, 4), (2, 0, 2, 0), (2, 0, 2, 1), (2, 0, 2, 2), (2, 0, 2, 3), (2, 0, 2, 4), (2, 0, 3, 0), (2, 0, 3, 1), (2, 0, 3, 2), (2, 0, 3, 3), (2, 0, 3, 4), (2, 0, 4, 0), (2, 0, 4, 1), (2, 0, 4, 2), (2, 0, 4, 3), (2, 0, 4, 4), (2, 1, 0, 0), (2, 1, 0, 1), (2, 1, 0, 2), (2, 1, 0, 3), (2, 1, 0, 4), (2, 1, 1, 0), (2, 1, 1, 1), (2, 1, 1, 2), (2, 1, 1, 3), (2, 1, 1, 4), (2, 1, 2, 0), (2, 1, 2, 1), (2, 1, 2, 2), (2, 1, 2, 3), (2, 1, 2, 4), (2, 1, 3, 0), (2, 1, 3, 1), (2, 1, 3, 2), (2, 1, 3, 3), (2, 1, 3, 4), (2, 1, 4, 0), (2, 1, 4, 1), (2, 1, 4, 2), (2, 1, 4, 3), (2, 1, 4, 4), (2, 2, 0, 0), (2, 2, 0, 1), (2, 2, 0, 2), (2, 2, 0, 3), (2, 2, 0, 4), (2, 2, 1, 0), (2, 2, 1, 1), (2, 2, 1, 2), (2, 2, 1, 3), (2, 2, 1, 4), (2, 2, 2, 0), (2, 2, 2, 1), (2, 2, 2, 2), (2, 2, 2, 3), (2, 2, 2, 4), (2, 2, 3, 0), (2, 2, 3, 1), (2, 2, 3, 2), (2, 2, 3, 3), (2, 2, 3, 4), (2, 2, 4, 0), (2, 2, 4, 1), (2, 2, 4, 2), (2, 2, 4, 3), (2, 2, 4, 4), (2, 3, 0, 0), (2, 3, 0, 1), (2, 3, 0, 2), (2, 3, 0, 3), (2, 3, 0, 4), (2, 3, 1, 0), (2, 3, 1, 1), (2, 3, 1, 2), (2, 3, 1, 3), (2, 3, 1, 4), (2, 3, 2, 0), (2, 3, 2, 1), (2, 3, 2, 2), (2, 3, 2, 3), (2, 3, 2, 4), (2, 3, 3, 0), (2, 3, 3, 1), (2, 3, 3, 2), (2, 3, 3, 3), (2, 3, 3, 4), (2, 3, 4, 0), (2, 3, 4, 1), (2, 3, 4, 2), (2, 3, 4, 3), (2, 3, 4, 4), (2, 4, 0, 0), (2, 4, 0, 1), (2, 4, 0, 2), (2, 4, 0, 3), (2, 4, 0, 4), (2, 4, 1, 0), (2, 4, 1, 1), (2, 4, 1, 2), (2, 4, 1, 3), (2, 4, 1, 4), (2, 4, 2, 0), (2, 4, 2, 1), (2, 4, 2, 2), (2, 4, 2, 3), (2, 4, 2, 4), (2, 4, 3, 0), (2, 4, 3, 1), (2, 4, 3, 2), (2, 4, 3, 3), (2, 4, 3, 4), (2, 4, 4, 0), (2, 4, 4, 1), (2, 4, 4, 2), (2, 4, 4, 3), (2, 4, 4, 4), (2, 5, 0, 0), (2, 5, 0, 1), (2, 5, 0, 2), (2, 5, 0, 3), (2, 5, 0, 4), (2, 5, 1, 0), (2, 5, 1, 1), (2, 5, 1, 2), (2, 5, 1, 3), (2, 5, 1, 4), (2, 5, 2, 0), (2, 5, 2, 1), (2, 5, 2, 2), (2, 5, 2, 3), (2, 5, 2, 4), (2, 5, 3, 0), (2, 5, 3, 1), (2, 5, 3, 2), (2, 5, 3, 3), (2, 5, 3, 4), (2, 5, 4, 0), (2, 5, 4, 1), (2, 5, 4, 2), (2, 5, 4, 3), (2, 5, 4, 4), (3, 0, 0, 0), (3, 0, 0, 1), (3, 0, 0, 2), (3, 0, 0, 3), (3, 0, 0, 4), (3, 0, 1, 0), (3, 0, 1, 1), (3, 0, 1, 2), (3, 0, 1, 3), (3, 0, 1, 4), (3, 0, 2, 0), (3, 0, 2, 1), (3, 0, 2, 2), (3, 0, 2, 3), (3, 0, 2, 4), (3, 0, 3, 0), (3, 0, 3, 1), (3, 0, 3, 2), (3, 0, 3, 3), (3, 0, 3, 4), (3, 0, 4, 0), (3, 0, 4, 1), (3, 0, 4, 2), (3, 0, 4, 3), (3, 0, 4, 4), (3, 1, 0, 0), (3, 1, 0, 1), (3, 1, 0, 2), (3, 1, 0, 3), (3, 1, 0, 4), (3, 1, 1, 0), (3, 1, 1, 1), (3, 1, 1, 2), (3, 1, 1, 3), (3, 1, 1, 4), (3, 1, 2, 0), (3, 1, 2, 1), (3, 1, 2, 2), (3, 1, 2, 3), (3, 1, 2, 4), (3, 1, 3, 0), (3, 1, 3, 1), (3, 1, 3, 2), (3, 1, 3, 3), (3, 1, 3, 4), (3, 1, 4, 0), (3, 1, 4, 1), (3, 1, 4, 2), (3, 1, 4, 3), (3, 1, 4, 4), (3, 2, 0, 0), (3, 2, 0, 1), (3, 2, 0, 2), (3, 2, 0, 3), (3, 2, 0, 4), (3, 2, 1, 0), (3, 2, 1, 1), (3, 2, 1, 2), (3, 2, 1, 3), (3, 2, 1, 4), (3, 2, 2, 0), (3, 2, 2, 1), (3, 2, 2, 2), (3, 2, 2, 3), (3, 2, 2, 4), (3, 2, 3, 0), (3, 2, 3, 1), (3, 2, 3, 2), (3, 2, 3, 3), (3, 2, 3, 4), (3, 2, 4, 0), (3, 2, 4, 1), (3, 2, 4, 2), (3, 2, 4, 3), (3, 2, 4, 4), (3, 3, 0, 0), (3, 3, 0, 1), (3, 3, 0, 2), (3, 3, 0, 3), (3, 3, 0, 4), (3, 3, 1, 0), (3, 3, 1, 1), (3, 3, 1, 2), (3, 3, 1, 3), (3, 3, 1, 4), (3, 3, 2, 0), (3, 3, 2, 1), (3, 3, 2, 2), (3, 3, 2, 3), (3, 3, 2, 4), (3, 3, 3, 0), (3, 3, 3, 1), (3, 3, 3, 2), (3, 3, 3, 3), (3, 3, 3, 4), (3, 3, 4, 0), (3, 3, 4, 1), (3, 3, 4, 2), (3, 3, 4, 3), (3, 3, 4, 4), (3, 4, 0, 0), (3, 4, 0, 1), (3, 4, 0, 2), (3, 4, 0, 3), (3, 4, 0, 4), (3, 4, 1, 0), (3, 4, 1, 1), (3, 4, 1, 2), (3, 4, 1, 3), (3, 4, 1, 4), (3, 4, 2, 0), (3, 4, 2, 1), (3, 4, 2, 2), (3, 4, 2, 3), (3, 4, 2, 4), (3, 4, 3, 0), (3, 4, 3, 1), (3, 4, 3, 2), (3, 4, 3, 3), (3, 4, 3, 4), (3, 4, 4, 0), (3, 4, 4, 1), (3, 4, 4, 2), (3, 4, 4, 3), (3, 4, 4, 4), (3, 5, 0, 0), (3, 5, 0, 1), (3, 5, 0, 2), (3, 5, 0, 3), (3, 5, 0, 4), (3, 5, 1, 0), (3, 5, 1, 1), (3, 5, 1, 2), (3, 5, 1, 3), (3, 5, 1, 4), (3, 5, 2, 0), (3, 5, 2, 1), (3, 5, 2, 2), (3, 5, 2, 3), (3, 5, 2, 4), (3, 5, 3, 0), (3, 5, 3, 1), (3, 5, 3, 2), (3, 5, 3, 3), (3, 5, 3, 4), (3, 5, 4, 0), (3, 5, 4, 1), (3, 5, 4, 2), (3, 5, 4, 3), (3, 5, 4, 4), (4, 0, 0, 0), (4, 0, 0, 1), (4, 0, 0, 2), (4, 0, 0, 3), (4, 0, 0, 4), (4, 0, 1, 0), (4, 0, 1, 1), (4, 0, 1, 2), (4, 0, 1, 3), (4, 0, 1, 4), (4, 0, 2, 0), (4, 0, 2, 1), (4, 0, 2, 2), (4, 0, 2, 3), (4, 0, 2, 4), (4, 0, 3, 0), (4, 0, 3, 1), (4, 0, 3, 2), (4, 0, 3, 3), (4, 0, 3, 4), (4, 0, 4, 0), (4, 0, 4, 1), (4, 0, 4, 2), (4, 0, 4, 3), (4, 0, 4, 4), (4, 1, 0, 0), (4, 1, 0, 1), (4, 1, 0, 2), (4, 1, 0, 3), (4, 1, 0, 4), (4, 1, 1, 0), (4, 1, 1, 1), (4, 1, 1, 2), (4, 1, 1, 3), (4, 1, 1, 4), (4, 1, 2, 0), (4, 1, 2, 1), (4, 1, 2, 2), (4, 1, 2, 3), (4, 1, 2, 4), (4, 1, 3, 0), (4, 1, 3, 1), (4, 1, 3, 2), (4, 1, 3, 3), (4, 1, 3, 4), (4, 1, 4, 0), (4, 1, 4, 1), (4, 1, 4, 2), (4, 1, 4, 3), (4, 1, 4, 4), (4, 2, 0, 0), (4, 2, 0, 1), (4, 2, 0, 2), (4, 2, 0, 3), (4, 2, 0, 4), (4, 2, 1, 0), (4, 2, 1, 1), (4, 2, 1, 2), (4, 2, 1, 3), (4, 2, 1, 4), (4, 2, 2, 0), (4, 2, 2, 1), (4, 2, 2, 2), (4, 2, 2, 3), (4, 2, 2, 4), (4, 2, 3, 0), (4, 2, 3, 1), (4, 2, 3, 2), (4, 2, 3, 3), (4, 2, 3, 4), (4, 2, 4, 0), (4, 2, 4, 1), (4, 2, 4, 2), (4, 2, 4, 3), (4, 2, 4, 4), (4, 3, 0, 0), (4, 3, 0, 1), (4, 3, 0, 2), (4, 3, 0, 3), (4, 3, 0, 4), (4, 3, 1, 0), (4, 3, 1, 1), (4, 3, 1, 2), (4, 3, 1, 3), (4, 3, 1, 4), (4, 3, 2, 0), (4, 3, 2, 1), (4, 3, 2, 2), (4, 3, 2, 3), (4, 3, 2, 4), (4, 3, 3, 0), (4, 3, 3, 1), (4, 3, 3, 2), (4, 3, 3, 3), (4, 3, 3, 4), (4, 3, 4, 0), (4, 3, 4, 1), (4, 3, 4, 2), (4, 3, 4, 3), (4, 3, 4, 4), (4, 4, 0, 0), (4, 4, 0, 1), (4, 4, 0, 2), (4, 4, 0, 3), (4, 4, 0, 4), (4, 4, 1, 0), (4, 4, 1, 1), (4, 4, 1, 2), (4, 4, 1, 3), (4, 4, 1, 4), (4, 4, 2, 0), (4, 4, 2, 1), (4, 4, 2, 2), (4, 4, 2, 3), (4, 4, 2, 4), (4, 4, 3, 0), (4, 4, 3, 1), (4, 4, 3, 2), (4, 4, 3, 3), (4, 4, 3, 4), (4, 4, 4, 0), (4, 4, 4, 1), (4, 4, 4, 2), (4, 4, 4, 3), (4, 4, 4, 4), (4, 5, 0, 0), (4, 5, 0, 1), (4, 5, 0, 2), (4, 5, 0, 3), (4, 5, 0, 4), (4, 5, 1, 0), (4, 5, 1, 1), (4, 5, 1, 2), (4, 5, 1, 3), (4, 5, 1, 4), (4, 5, 2, 0), (4, 5, 2, 1), (4, 5, 2, 2), (4, 5, 2, 3), (4, 5, 2, 4), (4, 5, 3, 0), (4, 5, 3, 1), (4, 5, 3, 2), (4, 5, 3, 3), (4, 5, 3, 4), (4, 5, 4, 0), (4, 5, 4, 1), (4, 5, 4, 2), (4, 5, 4, 3), (4, 5, 4, 4), (5, 0, 0, 0), (5, 0, 0, 1), (5, 0, 0, 2), (5, 0, 0, 3), (5, 0, 0, 4), (5, 0, 1, 0), (5, 0, 1, 1), (5, 0, 1, 2), (5, 0, 1, 3), (5, 0, 1, 4), (5, 0, 2, 0), (5, 0, 2, 1), (5, 0, 2, 2), (5, 0, 2, 3), (5, 0, 2, 4), (5, 0, 3, 0), (5, 0, 3, 1), (5, 0, 3, 2), (5, 0, 3, 3), (5, 0, 3, 4), (5, 0, 4, 0), (5, 0, 4, 1), (5, 0, 4, 2), (5, 0, 4, 3), (5, 0, 4, 4), (5, 1, 0, 0), (5, 1, 0, 1), (5, 1, 0, 2), (5, 1, 0, 3), (5, 1, 0, 4), (5, 1, 1, 0), (5, 1, 1, 1), (5, 1, 1, 2), (5, 1, 1, 3), (5, 1, 1, 4), (5, 1, 2, 0), (5, 1, 2, 1), (5, 1, 2, 2), (5, 1, 2, 3), (5, 1, 2, 4), (5, 1, 3, 0), (5, 1, 3, 1), (5, 1, 3, 2), (5, 1, 3, 3), (5, 1, 3, 4), (5, 1, 4, 0), (5, 1, 4, 1), (5, 1, 4, 2), (5, 1, 4, 3), (5, 1, 4, 4), (5, 2, 0, 0), (5, 2, 0, 1), (5, 2, 0, 2), (5, 2, 0, 3), (5, 2, 0, 4), (5, 2, 1, 0), (5, 2, 1, 1), (5, 2, 1, 2), (5, 2, 1, 3), (5, 2, 1, 4), (5, 2, 2, 0), (5, 2, 2, 1), (5, 2, 2, 2), (5, 2, 2, 3), (5, 2, 2, 4), (5, 2, 3, 0), (5, 2, 3, 1), (5, 2, 3, 2), (5, 2, 3, 3), (5, 2, 3, 4), (5, 2, 4, 0), (5, 2, 4, 1), (5, 2, 4, 2), (5, 2, 4, 3), (5, 2, 4, 4), (5, 3, 0, 0), (5, 3, 0, 1), (5, 3, 0, 2), (5, 3, 0, 3), (5, 3, 0, 4), (5, 3, 1, 0), (5, 3, 1, 1), (5, 3, 1, 2), (5, 3, 1, 3), (5, 3, 1, 4), (5, 3, 2, 0), (5, 3, 2, 1), (5, 3, 2, 2), (5, 3, 2, 3), (5, 3, 2, 4), (5, 3, 3, 0), (5, 3, 3, 1), (5, 3, 3, 2), (5, 3, 3, 3), (5, 3, 3, 4), (5, 3, 4, 0), (5, 3, 4, 1), (5, 3, 4, 2), (5, 3, 4, 3), (5, 3, 4, 4), (5, 4, 0, 0), (5, 4, 0, 1), (5, 4, 0, 2), (5, 4, 0, 3), (5, 4, 0, 4), (5, 4, 1, 0), (5, 4, 1, 1), (5, 4, 1, 2), (5, 4, 1, 3), (5, 4, 1, 4), (5, 4, 2, 0), (5, 4, 2, 1), (5, 4, 2, 2), (5, 4, 2, 3), (5, 4, 2, 4), (5, 4, 3, 0), (5, 4, 3, 1), (5, 4, 3, 2), (5, 4, 3, 3), (5, 4, 3, 4), (5, 4, 4, 0), (5, 4, 4, 1), (5, 4, 4, 2), (5, 4, 4, 3), (5, 4, 4, 4), (5, 5, 0, 0), (5, 5, 0, 1), (5, 5, 0, 2), (5, 5, 0, 3), (5, 5, 0, 4), (5, 5, 1, 0), (5, 5, 1, 1), (5, 5, 1, 2), (5, 5, 1, 3), (5, 5, 1, 4), (5, 5, 2, 0), (5, 5, 2, 1), (5, 5, 2, 2), (5, 5, 2, 3), (5, 5, 2, 4), (5, 5, 3, 0), (5, 5, 3, 1), (5, 5, 3, 2), (5, 5, 3, 3), (5, 5, 3, 4), (5, 5, 4, 0), (5, 5, 4, 1), (5, 5, 4, 2), (5, 5, 4, 3), (5, 5, 4, 4)}
works_done_by_their_order_index_0 : Size=1, Index=None, Ordered=Insertion
Key : Dimen : Domain : Size : Members
None : 1 : Any : 6 : {0, 1, 2, 3, 4, 5}
works_done_by_their_order_index_1 : Size=1, Index=None, Ordered=Insertion
Key : Dimen : Domain : Size : Members
None : 1 : Any : 6 : {0, 1, 2, 3, 4, 5}
works_done_by_their_order_index_2 : Size=1, Index=None, Ordered=Insertion
Key : Dimen : Domain : Size : Members
None : 1 : Any : 5 : {0, 1, 2, 3, 4}
works_done_by_their_order_index_3 : Size=1, Index=None, Ordered=Insertion
Key : Dimen : Domain : Size : Members
None : 1 : Any : 5 : {0, 1, 2, 3, 4}
x_index : Size=1, Index=None, Ordered=True
Key : Dimen : Domain : Size : Members
None : 2 : x_index_0*x_index_1 : 30 : {(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (3, 0), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5)}
x_index_0 : Size=1, Index=None, Ordered=Insertion
Key : Dimen : Domain : Size : Members
None : 1 : Any : 5 : {0, 1, 2, 3, 4}
x_index_1 : Size=1, Index=None, Ordered=Insertion
Key : Dimen : Domain : Size : Members
None : 1 : Any : 6 : {0, 1, 2, 3, 4, 5}
1 Var Declarations
x : Size=30, Index=x_index
Key : Lower : Value : Upper : Fixed : Stale : Domain
(0, 0) : 0 : None : 1 : False : True : Binary
(0, 1) : 0 : None : 1 : False : True : Binary
(0, 2) : 0 : None : 1 : False : True : Binary
(0, 3) : 0 : None : 1 : False : True : Binary
(0, 4) : 0 : None : 1 : False : True : Binary
(0, 5) : 0 : None : 1 : False : True : Binary
(1, 0) : 0 : None : 1 : False : True : Binary
(1, 1) : 0 : None : 1 : False : True : Binary
(1, 2) : 0 : None : 1 : False : True : Binary
(1, 3) : 0 : None : 1 : False : True : Binary
(1, 4) : 0 : None : 1 : False : True : Binary
(1, 5) : 0 : None : 1 : False : True : Binary
(2, 0) : 0 : None : 1 : False : True : Binary
(2, 1) : 0 : None : 1 : False : True : Binary
(2, 2) : 0 : None : 1 : False : True : Binary
(2, 3) : 0 : None : 1 : False : True : Binary
(2, 4) : 0 : None : 1 : False : True : Binary
(2, 5) : 0 : None : 1 : False : True : Binary
(3, 0) : 0 : None : 1 : False : True : Binary
(3, 1) : 0 : None : 1 : False : True : Binary
(3, 2) : 0 : None : 1 : False : True : Binary
(3, 3) : 0 : None : 1 : False : True : Binary
(3, 4) : 0 : None : 1 : False : True : Binary
(3, 5) : 0 : None : 1 : False : True : Binary
(4, 0) : 0 : None : 1 : False : True : Binary
(4, 1) : 0 : None : 1 : False : True : Binary
(4, 2) : 0 : None : 1 : False : True : Binary
(4, 3) : 0 : None : 1 : False : True : Binary
(4, 4) : 0 : None : 1 : False : True : Binary
(4, 5) : 0 : None : 1 : False : True : Binary
1 Objective Declarations
cost : Size=1, Index=None, Active=True
Key : Active : Sense : Expression
None : True : minimize : x[0,5] + 2*x[1,5] + 3*x[2,5] + 4*x[3,5] + 5*x[4,5]
4 Constraint Declarations
all_works_are_done : Size=6, Index=all_works_are_done_index, Active=True
Key : Lower : Body : Upper : Active
0 : 1.0 : x[0,0] + x[1,0] + x[2,0] + x[3,0] + x[4,0] : 1.0 : True
1 : 1.0 : x[0,1] + x[1,1] + x[2,1] + x[3,1] + x[4,1] : 1.0 : True
2 : 1.0 : x[0,2] + x[1,2] + x[2,2] + x[3,2] + x[4,2] : 1.0 : True
3 : 1.0 : x[0,3] + x[1,3] + x[2,3] + x[3,3] + x[4,3] : 1.0 : True
4 : 1.0 : x[0,4] + x[1,4] + x[2,4] + x[3,4] + x[4,4] : 1.0 : True
5 : 1.0 : x[0,5] + x[1,5] + x[2,5] + x[3,5] + x[4,5] : 1.0 : True
capacity_is_valid : Size=5, Index=capacity_is_valid_index, Active=True
Key : Lower : Body : Upper : Active
0 : -Inf : x[0,0] + 3*x[0,1] + 2*x[0,2] + 2*x[0,3] + x[0,4] + x[0,5] : 1.0 : True
1 : -Inf : x[1,0] + 3*x[1,1] + 2*x[1,2] + 2*x[1,3] + x[1,4] + x[1,5] : 3.0 : True
2 : -Inf : x[2,0] + 3*x[2,1] + 2*x[2,2] + 2*x[2,3] + x[2,4] + x[2,5] : 4.0 : True
3 : -Inf : x[3,0] + 3*x[3,1] + 2*x[3,2] + 2*x[3,3] + x[3,4] + x[3,5] : 3.0 : True
4 : -Inf : x[4,0] + 3*x[4,1] + 2*x[4,2] + 2*x[4,3] + x[4,4] + x[4,5] : 1.0 : True
eliminating_rule : Size=15, Index=eliminating_rule_index, Active=True
Key : Lower : Body : Upper : Active
(0, 3) : 0.0 : x[3,0] : 0.0 : True
(0, 4) : 0.0 : x[4,0] : 0.0 : True
(1, 0) : 0.0 : x[0,1] : 0.0 : True
(1, 4) : 0.0 : x[4,1] : 0.0 : True
(2, 0) : 0.0 : x[0,2] : 0.0 : True
(2, 3) : 0.0 : x[3,2] : 0.0 : True
(2, 4) : 0.0 : x[4,2] : 0.0 : True
(3, 0) : 0.0 : x[0,3] : 0.0 : True
(3, 3) : 0.0 : x[3,3] : 0.0 : True
(3, 4) : 0.0 : x[4,3] : 0.0 : True
(4, 0) : 0.0 : x[0,4] : 0.0 : True
(4, 1) : 0.0 : x[1,4] : 0.0 : True
(4, 4) : 0.0 : x[4,4] : 0.0 : True
(5, 0) : 0.0 : x[0,5] : 0.0 : True
(5, 1) : 0.0 : x[1,5] : 0.0 : True
works_done_by_their_order : Size=105, Index=works_done_by_their_order_index, Active=True
Key : Lower : Body : Upper : Active
(0, 1, 0, 0) : 0.0 : x[0,0]*x[0,1] : 0.0 : True
(0, 1, 1, 0) : 0.0 : x[1,0]*x[0,1] : 0.0 : True
(0, 1, 1, 1) : 0.0 : x[1,0]*x[1,1] : 0.0 : True
(0, 1, 2, 0) : 0.0 : x[2,0]*x[0,1] : 0.0 : True
(0, 1, 2, 1) : 0.0 : x[2,0]*x[1,1] : 0.0 : True
(0, 1, 2, 2) : 0.0 : x[2,0]*x[2,1] : 0.0 : True
(0, 1, 3, 0) : 0.0 : x[3,0]*x[0,1] : 0.0 : True
(0, 1, 3, 1) : 0.0 : x[3,0]*x[1,1] : 0.0 : True
(0, 1, 3, 2) : 0.0 : x[3,0]*x[2,1] : 0.0 : True
(0, 1, 3, 3) : 0.0 : x[3,0]*x[3,1] : 0.0 : True
(0, 1, 4, 0) : 0.0 : x[4,0]*x[0,1] : 0.0 : True
(0, 1, 4, 1) : 0.0 : x[4,0]*x[1,1] : 0.0 : True
(0, 1, 4, 2) : 0.0 : x[4,0]*x[2,1] : 0.0 : True
(0, 1, 4, 3) : 0.0 : x[4,0]*x[3,1] : 0.0 : True
(0, 1, 4, 4) : 0.0 : x[4,0]*x[4,1] : 0.0 : True
(0, 2, 0, 0) : 0.0 : x[0,0]*x[0,2] : 0.0 : True
(0, 2, 1, 0) : 0.0 : x[1,0]*x[0,2] : 0.0 : True
(0, 2, 1, 1) : 0.0 : x[1,0]*x[1,2] : 0.0 : True
(0, 2, 2, 0) : 0.0 : x[2,0]*x[0,2] : 0.0 : True
(0, 2, 2, 1) : 0.0 : x[2,0]*x[1,2] : 0.0 : True
(0, 2, 2, 2) : 0.0 : x[2,0]*x[2,2] : 0.0 : True
(0, 2, 3, 0) : 0.0 : x[3,0]*x[0,2] : 0.0 : True
(0, 2, 3, 1) : 0.0 : x[3,0]*x[1,2] : 0.0 : True
(0, 2, 3, 2) : 0.0 : x[3,0]*x[2,2] : 0.0 : True
(0, 2, 3, 3) : 0.0 : x[3,0]*x[3,2] : 0.0 : True
(0, 2, 4, 0) : 0.0 : x[4,0]*x[0,2] : 0.0 : True
(0, 2, 4, 1) : 0.0 : x[4,0]*x[1,2] : 0.0 : True
(0, 2, 4, 2) : 0.0 : x[4,0]*x[2,2] : 0.0 : True
(0, 2, 4, 3) : 0.0 : x[4,0]*x[3,2] : 0.0 : True
(0, 2, 4, 4) : 0.0 : x[4,0]*x[4,2] : 0.0 : True
(0, 3, 0, 0) : 0.0 : x[0,0]*x[0,3] : 0.0 : True
(0, 3, 1, 0) : 0.0 : x[1,0]*x[0,3] : 0.0 : True
(0, 3, 1, 1) : 0.0 : x[1,0]*x[1,3] : 0.0 : True
(0, 3, 2, 0) : 0.0 : x[2,0]*x[0,3] : 0.0 : True
(0, 3, 2, 1) : 0.0 : x[2,0]*x[1,3] : 0.0 : True
(0, 3, 2, 2) : 0.0 : x[2,0]*x[2,3] : 0.0 : True
(0, 3, 3, 0) : 0.0 : x[3,0]*x[0,3] : 0.0 : True
(0, 3, 3, 1) : 0.0 : x[3,0]*x[1,3] : 0.0 : True
(0, 3, 3, 2) : 0.0 : x[3,0]*x[2,3] : 0.0 : True
(0, 3, 3, 3) : 0.0 : x[3,0]*x[3,3] : 0.0 : True
(0, 3, 4, 0) : 0.0 : x[4,0]*x[0,3] : 0.0 : True
(0, 3, 4, 1) : 0.0 : x[4,0]*x[1,3] : 0.0 : True
(0, 3, 4, 2) : 0.0 : x[4,0]*x[2,3] : 0.0 : True
(0, 3, 4, 3) : 0.0 : x[4,0]*x[3,3] : 0.0 : True
(0, 3, 4, 4) : 0.0 : x[4,0]*x[4,3] : 0.0 : True
(1, 5, 0, 0) : 0.0 : x[0,1]*x[0,5] : 0.0 : True
(1, 5, 1, 0) : 0.0 : x[1,1]*x[0,5] : 0.0 : True
(1, 5, 1, 1) : 0.0 : x[1,1]*x[1,5] : 0.0 : True
(1, 5, 2, 0) : 0.0 : x[2,1]*x[0,5] : 0.0 : True
(1, 5, 2, 1) : 0.0 : x[2,1]*x[1,5] : 0.0 : True
(1, 5, 2, 2) : 0.0 : x[2,1]*x[2,5] : 0.0 : True
(1, 5, 3, 0) : 0.0 : x[3,1]*x[0,5] : 0.0 : True
(1, 5, 3, 1) : 0.0 : x[3,1]*x[1,5] : 0.0 : True
(1, 5, 3, 2) : 0.0 : x[3,1]*x[2,5] : 0.0 : True
(1, 5, 3, 3) : 0.0 : x[3,1]*x[3,5] : 0.0 : True
(1, 5, 4, 0) : 0.0 : x[4,1]*x[0,5] : 0.0 : True
(1, 5, 4, 1) : 0.0 : x[4,1]*x[1,5] : 0.0 : True
(1, 5, 4, 2) : 0.0 : x[4,1]*x[2,5] : 0.0 : True
(1, 5, 4, 3) : 0.0 : x[4,1]*x[3,5] : 0.0 : True
(1, 5, 4, 4) : 0.0 : x[4,1]*x[4,5] : 0.0 : True
(2, 4, 0, 0) : 0.0 : x[0,2]*x[0,4] : 0.0 : True
(2, 4, 1, 0) : 0.0 : x[1,2]*x[0,4] : 0.0 : True
(2, 4, 1, 1) : 0.0 : x[1,2]*x[1,4] : 0.0 : True
(2, 4, 2, 0) : 0.0 : x[2,2]*x[0,4] : 0.0 : True
(2, 4, 2, 1) : 0.0 : x[2,2]*x[1,4] : 0.0 : True
(2, 4, 2, 2) : 0.0 : x[2,2]*x[2,4] : 0.0 : True
(2, 4, 3, 0) : 0.0 : x[3,2]*x[0,4] : 0.0 : True
(2, 4, 3, 1) : 0.0 : x[3,2]*x[1,4] : 0.0 : True
(2, 4, 3, 2) : 0.0 : x[3,2]*x[2,4] : 0.0 : True
(2, 4, 3, 3) : 0.0 : x[3,2]*x[3,4] : 0.0 : True
(2, 4, 4, 0) : 0.0 : x[4,2]*x[0,4] : 0.0 : True
(2, 4, 4, 1) : 0.0 : x[4,2]*x[1,4] : 0.0 : True
(2, 4, 4, 2) : 0.0 : x[4,2]*x[2,4] : 0.0 : True
(2, 4, 4, 3) : 0.0 : x[4,2]*x[3,4] : 0.0 : True
(2, 4, 4, 4) : 0.0 : x[4,2]*x[4,4] : 0.0 : True
(3, 4, 0, 0) : 0.0 : x[0,3]*x[0,4] : 0.0 : True
(3, 4, 1, 0) : 0.0 : x[1,3]*x[0,4] : 0.0 : True
(3, 4, 1, 1) : 0.0 : x[1,3]*x[1,4] : 0.0 : True
(3, 4, 2, 0) : 0.0 : x[2,3]*x[0,4] : 0.0 : True
(3, 4, 2, 1) : 0.0 : x[2,3]*x[1,4] : 0.0 : True
(3, 4, 2, 2) : 0.0 : x[2,3]*x[2,4] : 0.0 : True
(3, 4, 3, 0) : 0.0 : x[3,3]*x[0,4] : 0.0 : True
(3, 4, 3, 1) : 0.0 : x[3,3]*x[1,4] : 0.0 : True
(3, 4, 3, 2) : 0.0 : x[3,3]*x[2,4] : 0.0 : True
(3, 4, 3, 3) : 0.0 : x[3,3]*x[3,4] : 0.0 : True
(3, 4, 4, 0) : 0.0 : x[4,3]*x[0,4] : 0.0 : True
(3, 4, 4, 1) : 0.0 : x[4,3]*x[1,4] : 0.0 : True
(3, 4, 4, 2) : 0.0 : x[4,3]*x[2,4] : 0.0 : True
(3, 4, 4, 3) : 0.0 : x[4,3]*x[3,4] : 0.0 : True
(3, 4, 4, 4) : 0.0 : x[4,3]*x[4,4] : 0.0 : True
(4, 5, 0, 0) : 0.0 : x[0,4]*x[0,5] : 0.0 : True
(4, 5, 1, 0) : 0.0 : x[1,4]*x[0,5] : 0.0 : True
(4, 5, 1, 1) : 0.0 : x[1,4]*x[1,5] : 0.0 : True
(4, 5, 2, 0) : 0.0 : x[2,4]*x[0,5] : 0.0 : True
(4, 5, 2, 1) : 0.0 : x[2,4]*x[1,5] : 0.0 : True
(4, 5, 2, 2) : 0.0 : x[2,4]*x[2,5] : 0.0 : True
(4, 5, 3, 0) : 0.0 : x[3,4]*x[0,5] : 0.0 : True
(4, 5, 3, 1) : 0.0 : x[3,4]*x[1,5] : 0.0 : True
(4, 5, 3, 2) : 0.0 : x[3,4]*x[2,5] : 0.0 : True
(4, 5, 3, 3) : 0.0 : x[3,4]*x[3,5] : 0.0 : True
(4, 5, 4, 0) : 0.0 : x[4,4]*x[0,5] : 0.0 : True
(4, 5, 4, 1) : 0.0 : x[4,4]*x[1,5] : 0.0 : True
(4, 5, 4, 2) : 0.0 : x[4,4]*x[2,5] : 0.0 : True
(4, 5, 4, 3) : 0.0 : x[4,4]*x[3,5] : 0.0 : True
(4, 5, 4, 4) : 0.0 : x[4,4]*x[4,5] : 0.0 : True
19 Declarations: x_index_0 x_index_1 x_index x all_works_are_done_index all_works_are_done capacity_is_valid_index capacity_is_valid works_done_by_their_order_index_0 works_done_by_their_order_index_1 works_done_by_their_order_index_2 works_done_by_their_order_index_3 works_done_by_their_order_index works_done_by_their_order eliminating_rule_index_0 eliminating_rule_index_1 eliminating_rule_index eliminating_rule cost
from classiq import (
construct_combinatorial_optimization_model,
execute,
set_execution_preferences,
show,
synthesize,
)
from classiq.applications.combinatorial_optimization import OptimizerConfig, QAOAConfig
from classiq.execution import ExecutionPreferences, IBMBackendPreferences
qaoa_config = QAOAConfig(num_layers=8, penalty_energy=20.0)
optimizer_config = OptimizerConfig(max_iteration=1, alpha_cvar=0.6)
qmod = construct_combinatorial_optimization_model(
pyo_model=tasks_model_large,
qaoa_config=qaoa_config,
optimizer_config=optimizer_config,
)
backend_preferences = ExecutionPreferences(
backend_preferences=ClassiqBackendPreferences(backend_name="simulator")
)
qmod = set_execution_preferences(qmod, backend_preferences)
from classiq import write_qmod
write_qmod(qmod, "task_scheduling_problem_large")
qprog = synthesize(qmod)
show(qprog)
Opening: https://platform.classiq.io/circuit/d48a3b5a-103e-402e-b81c-544840912860?version=0.41.0.dev39%2B79c8fd0855
res = execute(qprog).result()
As the search space here is much larger and involving many qubits, the optimizer takes much more time and might not converge to a legal solution
And print the optimization results:
import pandas as pd
from classiq.applications.combinatorial_optimization import (
get_optimization_solution_from_pyo,
)
solution = get_optimization_solution_from_pyo(
tasks_model_large,
vqe_result=res[0].value,
penalty_energy=qaoa_config.penalty_energy,
)
optimization_result = pd.DataFrame.from_records(solution)
optimization_result.sort_values(by="cost", ascending=True).head(5)
| probability | cost | solution | count | |
|---|---|---|---|---|
| 20 | 0.001 | 105.0 | [0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, ... | 1 |
| 292 | 0.001 | 105.0 | [0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, ... | 1 |
| 17 | 0.001 | 140.0 | [1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, ... | 1 |
| 777 | 0.001 | 140.0 | [1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, ... | 1 |
| 978 | 0.001 | 140.0 | [0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, ... | 1 |
idx = optimization_result.cost.idxmin()
print(
"x =", optimization_result.solution[idx], ", cost =", optimization_result.cost[idx]
)
x = [0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0] , cost = 104.99999999999997
And the histogram:
optimization_result.hist("cost", weights=optimization_result["probability"])
array([[<Axes: title={'center': 'cost'}>]], dtype=object)
Best solution
qaoa_solution_large = np.array(
optimization_result.solution[optimization_result.cost.idxmin()]
).reshape(num_timeslots, len(G.nodes))
plot_workflow(qaoa_solution_large)
Classical solution for the large problem
from pyomo.opt import SolverFactory
solver = SolverFactory("couenne")
solver.solve(tasks_model_large)
tasks_model_large.display()
Model task_scheduling
Variables:
x : Size=30, Index=x_index
Key : Lower : Value : Upper : Fixed : Stale : Domain
(0, 0) : 0 : 1.0 : 1 : False : False : Binary
(0, 1) : 0 : 0.0 : 1 : False : False : Binary
(0, 2) : 0 : 0.0 : 1 : False : False : Binary
(0, 3) : 0 : 0.0 : 1 : False : False : Binary
(0, 4) : 0 : 0.0 : 1 : False : False : Binary
(0, 5) : 0 : 0.0 : 1 : False : False : Binary
(1, 0) : 0 : 0.0 : 1 : False : False : Binary
(1, 1) : 0 : 1.0 : 1 : False : False : Binary
(1, 2) : 0 : 0.0 : 1 : False : False : Binary
(1, 3) : 0 : 0.0 : 1 : False : False : Binary
(1, 4) : 0 : 0.0 : 1 : False : False : Binary
(1, 5) : 0 : 0.0 : 1 : False : False : Binary
(2, 0) : 0 : 0.0 : 1 : False : False : Binary
(2, 1) : 0 : -6.666389110910511e-13 : 1 : False : False : Binary
(2, 2) : 0 : 1.0 : 1 : False : False : Binary
(2, 3) : 0 : 1.0 : 1 : False : False : Binary
(2, 4) : 0 : 0.0 : 1 : False : False : Binary
(2, 5) : 0 : 0.0 : 1 : False : False : Binary
(3, 0) : 0 : 0.0 : 1 : False : False : Binary
(3, 1) : 0 : 6.66577903984944e-13 : 1 : False : False : Binary
(3, 2) : 0 : 0.0 : 1 : False : False : Binary
(3, 3) : 0 : 0.0 : 1 : False : False : Binary
(3, 4) : 0 : 1.0 : 1 : False : False : Binary
(3, 5) : 0 : 0.0 : 1 : False : False : Binary
(4, 0) : 0 : 0.0 : 1 : False : False : Binary
(4, 1) : 0 : 6.100710610707113e-17 : 1 : False : False : Binary
(4, 2) : 0 : 0.0 : 1 : False : False : Binary
(4, 3) : 0 : 0.0 : 1 : False : False : Binary
(4, 4) : 0 : 0.0 : 1 : False : False : Binary
(4, 5) : 0 : 1.0 : 1 : False : False : Binary
Objectives:
cost : Size=1, Index=None, Active=True
Key : Active : Value
None : True : 5.0
Constraints:
all_works_are_done : Size=6
Key : Lower : Body : Upper
0 : 1.0 : 1.0 : 1.0
1 : 1.0 : 1.0 : 1.0
2 : 1.0 : 1.0 : 1.0
3 : 1.0 : 1.0 : 1.0
4 : 1.0 : 1.0 : 1.0
5 : 1.0 : 1.0 : 1.0
capacity_is_valid : Size=5
Key : Lower : Body : Upper
0 : None : 1.0 : 1.0
1 : None : 3.0 : 3.0
2 : None : 3.999999999998 : 4.0
3 : None : 1.0000000000019997 : 3.0
4 : None : 1.0000000000000002 : 1.0
works_done_by_their_order : Size=105
Key : Lower : Body : Upper
(0, 1, 0, 0) : 0.0 : 0.0 : 0.0
(0, 1, 1, 0) : 0.0 : 0.0 : 0.0
(0, 1, 1, 1) : 0.0 : 0.0 : 0.0
(0, 1, 2, 0) : 0.0 : 0.0 : 0.0
(0, 1, 2, 1) : 0.0 : 0.0 : 0.0
(0, 1, 2, 2) : 0.0 : -0.0 : 0.0
(0, 1, 3, 0) : 0.0 : 0.0 : 0.0
(0, 1, 3, 1) : 0.0 : 0.0 : 0.0
(0, 1, 3, 2) : 0.0 : -0.0 : 0.0
(0, 1, 3, 3) : 0.0 : 0.0 : 0.0
(0, 1, 4, 0) : 0.0 : 0.0 : 0.0
(0, 1, 4, 1) : 0.0 : 0.0 : 0.0
(0, 1, 4, 2) : 0.0 : -0.0 : 0.0
(0, 1, 4, 3) : 0.0 : 0.0 : 0.0
(0, 1, 4, 4) : 0.0 : 0.0 : 0.0
(0, 2, 0, 0) : 0.0 : 0.0 : 0.0
(0, 2, 1, 0) : 0.0 : 0.0 : 0.0
(0, 2, 1, 1) : 0.0 : 0.0 : 0.0
(0, 2, 2, 0) : 0.0 : 0.0 : 0.0
(0, 2, 2, 1) : 0.0 : 0.0 : 0.0
(0, 2, 2, 2) : 0.0 : 0.0 : 0.0
(0, 2, 3, 0) : 0.0 : 0.0 : 0.0
(0, 2, 3, 1) : 0.0 : 0.0 : 0.0
(0, 2, 3, 2) : 0.0 : 0.0 : 0.0
(0, 2, 3, 3) : 0.0 : 0.0 : 0.0
(0, 2, 4, 0) : 0.0 : 0.0 : 0.0
(0, 2, 4, 1) : 0.0 : 0.0 : 0.0
(0, 2, 4, 2) : 0.0 : 0.0 : 0.0
(0, 2, 4, 3) : 0.0 : 0.0 : 0.0
(0, 2, 4, 4) : 0.0 : 0.0 : 0.0
(0, 3, 0, 0) : 0.0 : 0.0 : 0.0
(0, 3, 1, 0) : 0.0 : 0.0 : 0.0
(0, 3, 1, 1) : 0.0 : 0.0 : 0.0
(0, 3, 2, 0) : 0.0 : 0.0 : 0.0
(0, 3, 2, 1) : 0.0 : 0.0 : 0.0
(0, 3, 2, 2) : 0.0 : 0.0 : 0.0
(0, 3, 3, 0) : 0.0 : 0.0 : 0.0
(0, 3, 3, 1) : 0.0 : 0.0 : 0.0
(0, 3, 3, 2) : 0.0 : 0.0 : 0.0
(0, 3, 3, 3) : 0.0 : 0.0 : 0.0
(0, 3, 4, 0) : 0.0 : 0.0 : 0.0
(0, 3, 4, 1) : 0.0 : 0.0 : 0.0
(0, 3, 4, 2) : 0.0 : 0.0 : 0.0
(0, 3, 4, 3) : 0.0 : 0.0 : 0.0
(0, 3, 4, 4) : 0.0 : 0.0 : 0.0
(1, 5, 0, 0) : 0.0 : 0.0 : 0.0
(1, 5, 1, 0) : 0.0 : 0.0 : 0.0
(1, 5, 1, 1) : 0.0 : 0.0 : 0.0
(1, 5, 2, 0) : 0.0 : -0.0 : 0.0
(1, 5, 2, 1) : 0.0 : -0.0 : 0.0
(1, 5, 2, 2) : 0.0 : -0.0 : 0.0
(1, 5, 3, 0) : 0.0 : 0.0 : 0.0
(1, 5, 3, 1) : 0.0 : 0.0 : 0.0
(1, 5, 3, 2) : 0.0 : 0.0 : 0.0
(1, 5, 3, 3) : 0.0 : 0.0 : 0.0
(1, 5, 4, 0) : 0.0 : 0.0 : 0.0
(1, 5, 4, 1) : 0.0 : 0.0 : 0.0
(1, 5, 4, 2) : 0.0 : 0.0 : 0.0
(1, 5, 4, 3) : 0.0 : 0.0 : 0.0
(1, 5, 4, 4) : 0.0 : 6.100710610707113e-17 : 0.0
(2, 4, 0, 0) : 0.0 : 0.0 : 0.0
(2, 4, 1, 0) : 0.0 : 0.0 : 0.0
(2, 4, 1, 1) : 0.0 : 0.0 : 0.0
(2, 4, 2, 0) : 0.0 : 0.0 : 0.0
(2, 4, 2, 1) : 0.0 : 0.0 : 0.0
(2, 4, 2, 2) : 0.0 : 0.0 : 0.0
(2, 4, 3, 0) : 0.0 : 0.0 : 0.0
(2, 4, 3, 1) : 0.0 : 0.0 : 0.0
(2, 4, 3, 2) : 0.0 : 0.0 : 0.0
(2, 4, 3, 3) : 0.0 : 0.0 : 0.0
(2, 4, 4, 0) : 0.0 : 0.0 : 0.0
(2, 4, 4, 1) : 0.0 : 0.0 : 0.0
(2, 4, 4, 2) : 0.0 : 0.0 : 0.0
(2, 4, 4, 3) : 0.0 : 0.0 : 0.0
(2, 4, 4, 4) : 0.0 : 0.0 : 0.0
(3, 4, 0, 0) : 0.0 : 0.0 : 0.0
(3, 4, 1, 0) : 0.0 : 0.0 : 0.0
(3, 4, 1, 1) : 0.0 : 0.0 : 0.0
(3, 4, 2, 0) : 0.0 : 0.0 : 0.0
(3, 4, 2, 1) : 0.0 : 0.0 : 0.0
(3, 4, 2, 2) : 0.0 : 0.0 : 0.0
(3, 4, 3, 0) : 0.0 : 0.0 : 0.0
(3, 4, 3, 1) : 0.0 : 0.0 : 0.0
(3, 4, 3, 2) : 0.0 : 0.0 : 0.0
(3, 4, 3, 3) : 0.0 : 0.0 : 0.0
(3, 4, 4, 0) : 0.0 : 0.0 : 0.0
(3, 4, 4, 1) : 0.0 : 0.0 : 0.0
(3, 4, 4, 2) : 0.0 : 0.0 : 0.0
(3, 4, 4, 3) : 0.0 : 0.0 : 0.0
(3, 4, 4, 4) : 0.0 : 0.0 : 0.0
(4, 5, 0, 0) : 0.0 : 0.0 : 0.0
(4, 5, 1, 0) : 0.0 : 0.0 : 0.0
(4, 5, 1, 1) : 0.0 : 0.0 : 0.0
(4, 5, 2, 0) : 0.0 : 0.0 : 0.0
(4, 5, 2, 1) : 0.0 : 0.0 : 0.0
(4, 5, 2, 2) : 0.0 : 0.0 : 0.0
(4, 5, 3, 0) : 0.0 : 0.0 : 0.0
(4, 5, 3, 1) : 0.0 : 0.0 : 0.0
(4, 5, 3, 2) : 0.0 : 0.0 : 0.0
(4, 5, 3, 3) : 0.0 : 0.0 : 0.0
(4, 5, 4, 0) : 0.0 : 0.0 : 0.0
(4, 5, 4, 1) : 0.0 : 0.0 : 0.0
(4, 5, 4, 2) : 0.0 : 0.0 : 0.0
(4, 5, 4, 3) : 0.0 : 0.0 : 0.0
(4, 5, 4, 4) : 0.0 : 0.0 : 0.0
eliminating_rule : Size=15
Key : Lower : Body : Upper
(0, 3) : 0.0 : 0.0 : 0.0
(0, 4) : 0.0 : 0.0 : 0.0
(1, 0) : 0.0 : 0.0 : 0.0
(1, 4) : 0.0 : 6.100710610707113e-17 : 0.0
(2, 0) : 0.0 : 0.0 : 0.0
(2, 3) : 0.0 : 0.0 : 0.0
(2, 4) : 0.0 : 0.0 : 0.0
(3, 0) : 0.0 : 0.0 : 0.0
(3, 3) : 0.0 : 0.0 : 0.0
(3, 4) : 0.0 : 0.0 : 0.0
(4, 0) : 0.0 : 0.0 : 0.0
(4, 1) : 0.0 : 0.0 : 0.0
(4, 4) : 0.0 : 0.0 : 0.0
(5, 0) : 0.0 : 0.0 : 0.0
(5, 1) : 0.0 : 0.0 : 0.0
classical_solution = np.array(
[
int(pyo.value(tasks_model_large.x[idx]))
for idx in np.ndindex(num_timeslots, len(G.nodes))
]
).reshape(num_timeslots, len(G.nodes))
plot_workflow(classical_solution)
References
[1]: Pakhomchik et. al. "Solving workflow scheduling problems with QUBO modeling." arXiv preprint arXiv:2205.04844 (2022).