Constrained Scheduling¶
This example solves a binary constraint satisfaction problem (CSP). CSPs require that all a problem’s variables be assigned values that result in the satisfying of all constraints. Here, the constraints are a company’s policy for scheduling meetings:
Constraint 1: During business hours, all meetings must be attended in person at the office.
Constraint 2: During business hours, participation in meetings is mandatory.
Constraint 3: Outside business hours, meetings must be teleconferenced.
Constraint 4: Outside business hours, meetings must not exceed 30 minutes.
Solving such a CSP means finding meetings that meet all the constraints.
The purpose of this example is to help a new user to formulate a constraint satisfaction problem using Ocean tools and solve it on a D-Wave system. Other examples demonstrate more advanced steps that might be needed for complex problems.
Example Requirements¶
To run the code in this example, the following is required.
The requisite information for problem submission through SAPI, as described in Configuring Access to D-Wave Solvers.
Ocean tools dwave-binarycsp, dwave-system, and dimod.
If you installed dwave-ocean-sdk
and ran dwave setup
, your installation should meet these requirements.
In D-Wave’s Leap IDE, the default workspace
meets these requirements.
Solution Steps¶
Section How a D-Wave System Solves Problems describes the process of solving problems on the quantum computer in two steps: (1) Formulate the problem as a binary quadratic model (BQM) and (2) Solve the BQM with a D-wave system or classical sampler. In this example, Ocean’s dwavebinarycsp tool builds the BQM based on the constraints you formulate.
Formulate the Problem¶
D-Wave systems solve binary quadratic models, so the first step is to express the problem with binary variables.
Time of day is represented by binary variable
time
with value \(1\) for business hours and \(0\) for hours outside the business day.Venue is represented by binary variable
location
with value \(1\) for office and \(0\) for teleconference.Meeting duration is represented by variable
length
with value \(1\) for short meetings (under 30 minutes) and \(0\) for meetings of longer duration.Participation is represented by variable
mandatory
with value \(1\) for mandatory participation and \(0\) for optional participation.
For large numbers of variables and constraints, such problems can be hard. This example has four binary variables, so only \(2^4=16\) possible meeting arrangements. As shown in the table below, it is a simple matter to work out all the combinations by hand to find solutions that meet all the constraints.
Time of Day |
Venue |
Duration |
Participation |
Valid? |
---|---|---|---|---|
Business hours |
Office |
Short |
Mandatory |
Yes |
Business hours |
Office |
Short |
Optional |
No (violates 2) |
Business hours |
Office |
Long |
Mandatory |
Yes |
Business hours |
Office |
Long |
Optional |
No (violates 2) |
Business hours |
Teleconference |
Short |
Mandatory |
No (violates 1) |
Business hours |
Teleconference |
Short |
Optional |
No (violates 1, 2) |
Business hours |
Teleconference |
Long |
Mandatory |
No (violates 1) |
Business hours |
Teleconference |
Long |
Optional |
No (violates 1, 2) |
Non-business hours |
Office |
Short |
Mandatory |
No (violates 3) |
Non-business hours |
Office |
Short |
Optional |
No (violates 3) |
Non-business hours |
Office |
Long |
Mandatory |
No (violates 3, 4) |
Non-business hours |
Office |
Long |
Optional |
No (violates 3, 4) |
Non-business hours |
Teleconference |
Short |
Mandatory |
Yes |
Non-business hours |
Teleconference |
Short |
Optional |
Yes |
Non-business hours |
Teleconference |
Long |
Mandatory |
No (violates 4) |
Non-business hours |
Teleconference |
Long |
Optional |
No (violates 4) |
Ocean’s dwavebinarycsp enables the definition of constraints in different ways, including by defining functions that evaluate True when the constraint is met. The code below defines a function that returns True when all this example’s constraints are met.
def scheduling(time, location, length, mandatory):
if time: # Business hours
return (location and mandatory) # In office and mandatory participation
else: # Outside business hours
return ((not location) and length) # Teleconference for a short duration
The next code lines create a constraint from this function and adds it to CSP instance,
csp
, instantiated with binary variables.
>>> import dwavebinarycsp
>>> csp = dwavebinarycsp.ConstraintSatisfactionProblem(dwavebinarycsp.BINARY)
>>> csp.add_constraint(scheduling, ['time', 'location', 'length', 'mandatory'])
This tool, dwavebinarycsp, can also convert the binary CSP to a BQM. The following code does so and the graph below provides a view on the BQM’s linear and quadratic coefficients, \(q_i\) and \(q_{i,j}\) respectively in \(\sum_i^N q_ix_i + \sum_{i<j}^N q_{i,j}x_i x_j\), which are the inputs for programming the quantum computer.
>>> bqm = dwavebinarycsp.stitch(csp)
Solve the Problem by Sampling¶
For small numbers of variables, even your computer’s CPU can solve CSPs quickly. Here you solve both classically on your CPU and on the quantum computer.
Solving Classically on a CPU¶
Before using the D-Wave system, it can sometimes be helpful to test code locally. Here, select one of Ocean software’s test samplers to solve classically on a CPU. Ocean’s dimod provides a sampler that simply returns the BQM’s value (energy) for every possible assignment of variable values.
>>> from dimod.reference.samplers import ExactSolver
>>> sampler = ExactSolver()
>>> solution = sampler.sample(bqm)
Valid solutions—assignments of variables that do not violate any constraint—should have the lowest value of the BQM:
The code below prints all those solutions (assignments of variables) for which the BQM has its minimum value1.
>>> from math import isclose
>>> min_energy = solution.record.energy.min()
>>> for sample, energy in solution.data(['sample', 'energy']):
... if isclose(energy, min_energy, abs_tol=1.0):
... time = 'business hours' if sample['time'] else 'evenings'
... location = 'office' if sample['location'] else 'home'
... length = 'short' if sample['length'] else 'long'
... mandatory = 'mandatory' if sample['mandatory'] else 'optional'
... print("During {} at {}, you can schedule a {} meeting that is {}".format(time, location, length, mandatory))
...
During evenings at home, you can schedule a short meeting that is optional
During evenings at home, you can schedule a short meeting that is mandatory
During business hours at office, you can schedule a short meeting that is mandatory
During business hours at office, you can schedule a long meeting that is mandatory
- 1
Because it compares float values, this code uses the standard
isclose
function to find values that are approximately equal. A small tolerance is needed to overcome rounding errors but for simplicity a value ofabs_tol=1.0
is used because by default thestich()
function increases the energy of solutions that violate one constraint bymin_classical_gap=2.0
.
Solving on a D-Wave System¶
Now solve on a D-Wave system using sampler DWaveSampler
from Ocean software’s dwave-system. Also use
its EmbeddingComposite
composite to map our unstructured
problem (variables such as time
etc.) to the sampler’s graph structure (the QPU’s numerically
indexed qubits) in a process known as minor-embedding. The next code sets up
a D-Wave system as the sampler.
Note
The code below sets a sampler without specifying SAPI parameters. Configure a default solver as described in Configuring Access to D-Wave Solvers to run the code as is, or see dwave-cloud-client to access a particular solver by setting explicit parameters in your code or environment variables.
>>> from dwave.system import DWaveSampler, EmbeddingComposite
>>> sampler = EmbeddingComposite(DWaveSampler())
Because the sampled solution is probabilistic, returned solutions may differ between runs. Typically, when submitting a problem to the system, you ask for many samples, not just one. This way, you see multiple “best” answers and reduce the probability of settling on a suboptimal answer. Below, ask for 5000 samples.
>>> sampleset = sampler.sample(bqm, num_reads=5000)
The code below prints all those solutions (assignments of variables) for which the BQM has its minimum value and the number of times it was found.
>>> total = 0
... for sample, energy, occurrences in sampleset.data(['sample', 'energy', 'num_occurrences']):
... total = total + occurrences
... if isclose(energy, min_energy, abs_tol=1.0):
... time = 'business hours' if sample['time'] else 'evenings'
... location = 'office' if sample['location'] else 'home'
... length = 'short' if sample['length'] else 'long'
... mandatory = 'mandatory' if sample['mandatory'] else 'optional'
... print("{}: During {} at {}, you can schedule a {} meeting that is {}".format(occurrences, time, location, length, mandatory))
... print("Total occurrences: ", total)
...
1676: During business hours at office, you can schedule a long meeting that is mandatory
1229: During business hours at office, you can schedule a short meeting that is mandatory
1194: During evenings at home, you can schedule a short meeting that is optional
898: During evenings at home, you can schedule a short meeting that is mandatory
Total occurrences: 5000
Summary¶
In the terminology of Ocean Software Stack, Ocean tools moved the original problem through the following layers:
Application: scheduling under constraints. There exist many CSPs that are computationally hard problems; for example, the map-coloring problem is to color all regions of a map such that any two regions sharing a border have different colors. The job-shop scheduling problem is to schedule multiple jobs done on several machines with constraints on the machines’ execution of tasks.
Method: constraint compilation.
Sampler API: the Ocean tool builds a BQM with lowest values (“ground states”) that correspond to assignments of variables that satisfy all constraints.
Sampler: classical
ExactSolver
and thenDWaveSampler
.Compute resource: first a local CPU then a D-Wave system.