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 arrangements of 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 quantum computer. Other examples demonstrate more advanced steps that might be needed for complex problems.

Example Requirements#

The code in this example requires that your development environment have Ocean software and be configured to access SAPI, as described in the Initial Set Up section.

Solution Steps#

Section Workflow Steps: Formulation and Sampling describes the problem-solving workflow as consisting of two main steps: (1) Formulate the problem as an objective function in a supported model and (2) Solve your model with a D-Wave solver.

This example represents the problem’s constraints as penalties (small Binary Quadratic Modelss that have higher values for variable assignments that violate constraints) and creates an objective function by summing all four penalty models. Solvers that seek low-energy states are thus less likely to return meeting arrangements that violate constraints.

Formulate the Problem#

D-Wave quantum computers solve binary quadratic models, so the first step is to express the problem with binary variables (this example uses \(\{0, 1\}\)–valued binary variables):

Problem Variables#

Variable

Represents

Value: 1

Value: 0

\(t\)

Time of day

Business hours

Non-business hours

\(v\)

Venue

Office

Teleconference

\(l\)

Length

Short (< 30 min)

Long

\(p\)

Participation

Mandatory

Optional

Note

A slightly more complex problem might require variables with multiple values; for example, l could have values {30, 60, 120} representing the duration in minutes of meetings of several lengths. For such problems a discrete quadratic model (DQM) could be a better choice.

In general, problems with constraints are more simply solved using a constrained quadratic model (CQM) and appropriate hybrid CQM solver, as demonstrated in the Bin Packing and Stock-Sales Strategy in a Simplified Market examples; however, the purpose of this example is to demonstrate solution directly on a D-Wave quantum computer.

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.

All Possible Meeting Options.#

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)

Represent Constraints as Penalties#

You can represent constraints as BQMs using Penalty Models in many different ways.

  • Constraint 1: During business hours, all meetings must be attended in person at the office.

    This constraint requires that if \(t=1\) (time of day is within business hours) then \(v = 1\) (venue is the office). A simple penalty function, \(t-tv\), is shown in the truth table below:

    Constraint 1: \(t-tv\)#

    \(t\)

    \(v\)

    \(t-tv\)

    0

    0

    0

    0

    1

    0

    1

    0

    1

    1

    1

    0

    Penalty function \(t-tv\) sets a penalty of 1 for the the case \(t=1 \; \& \; v=0\), representing a meeting outside the office during business hours, which violates constraint 1. When incorporated in an objective function, solutions that violate constraint 1 do not yield minimal values.

    Note

    One way to derive such a penalty function is to start with the simple case of a Boolean operator: the AND constraint, \(ab\), penalizes variable values \(a=b=1\). To penalize \(a=1, b=0\), you need the penalty function \(a \overline{b}\). For \(\{0, 1\}\)–valued variables, you can substitute \(\overline{b} = 1-b\) into the penalty and get \(a \overline{b} = a(1-b) = a - ab\). For more information on formulating such constraints, see the D-Wave Problem-Solving Handbook guide.

  • Constraint 2: During business hours, participation in meetings is mandatory.

    This constraint requires that if \(t=1\) (time of day is within business hours) then \(p=1\) (participation is mandatory). A penalty function is \(t-tp\), analogous to constraint 1.

  • Constraint 3: Outside business hours, meetings must be teleconferenced.

    This constraint requires that if \(t=0\) (time of day is outside business hours) then \(v=0\) (venue is teleconference, not the office). A penalty function is \(v-tv\), a reversal of constraint 1.

  • Constraint 4: Outside business hours, meetings must not exceed 30 minutes.

    This constraint requires that if \(t=0\) (time of day is outside business hours) then \(l=1\) (meeting length is short). A simple penalty function is \(1+tl-t-l\), as shown in the truth table below:

    Constraint 4: \(1+tl-t-l\)#

    \(t\)

    \(l\)

    \(1+tl-t-l\)

    0

    0

    1

    0

    1

    0

    1

    0

    0

    1

    1

    0

    Penalty function \(1+tl-t-l\) sets a penalty of 1 for the the case \(t=0 \; \& \; l=0\), representing a lengthy meeting outside business hours, which violates constraint 4. When incorporated in an objective function, solutions that violate constraint 4 do not yield minimal values.

Create a BQM#

The total penalty for all four constraints is

\[ \begin{align}\begin{aligned}t-tv + t-tp + v-tv + 1+tl-t-l\\= -2tv -tp +tl +t +v -l +1\end{aligned}\end{align} \]

Ocean’s dimod enables the creation of BQMs. Below, the first list of terms are the linear terms and the second are the quadratic terms; the offset is set to 1; and the variable type is set to use \(\{0, 1\}\)–valued binary variables.

>>> from dimod import BinaryQuadraticModel
>>> bqm = BinaryQuadraticModel({'t': 1, 'v': 1, 'l': -1},
...                            {'tv': -2, 'tl': 1, 'tp': -1},
...                            1,
...                            'BINARY')

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 a D-Wave quantum computer, 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()
>>> sampleset = sampler.sample(bqm)

Valid solutions—assignments of variables that do not violate constraints—have the lowest value of the BQM (values of zero in the energy field below):

>>> print(sampleset.lowest(atol=.5))
   l  p  t  v energy num_oc.
0  1  0  0  0    0.0       1
1  1  1  0  0    0.0       1
2  1  1  1  1    0.0       1
3  0  1  1  1    0.0       1
['BINARY', 4 rows, 4 samples, 4 variables]

The code below prints all those solutions (assignments of variables) for which the BQM has its minimum value.

>>> for sample, energy in sampleset.data(['sample', 'energy']):  
...     if energy==0:
...         time = 'business hours' if sample['t'] else 'evenings'
...         venue = 'office' if sample['v'] else 'home'
...         length = 'short' if sample['l'] else 'long'
...         participation = 'mandatory' if sample['p'] else 'optional'
...         print("During {} at {}, you can schedule a {} meeting that is {}".format(time, venue, length, participation))
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

Solving on a D-Wave Quantum Computer#

Now solve on a D-Wave system using sampler DWaveSampler from Ocean software’s dwave-system. Also use its EmbeddingComposite composite to map your unstructured problem (variables such as t 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 quantum computer as the sampler.

Note

The code below sets a sampler without specifying SAPI parameters. Configure a default solver as described in Configuring Access to Leap’s 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 a quantum computer, 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, label='SDK Examples - Scheduling')

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.

>>> print(sampleset.lowest(atol=.5))                     
   l  p  t  v energy num_oc. chain_.
0  1  0  0  0    0.0    1238     0.0
1  0  1  1  1    0.0    1255     0.0
2  1  1  0  0    0.0    1212     0.0
3  1  1  1  1    0.0    1290     0.0
['BINARY', 4 rows, 4995 samples, 4 variables]

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 then DWaveSampler.

  • Compute resource: first a local CPU then a D-Wave quantum computer.