.. _scheduling:
======================
Constrained Scheduling
======================
This example solves a binary *constraint satisfaction problem* (:term:`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
====================
.. include:: hybrid_solver_service.rst
:start-after: example-requirements-start-marker
:end-before: example-requirements-end-marker
Solution Steps
==============
.. include:: hybrid_solver_service.rst
:start-after: example-steps-start-marker
:end-before: example-steps-end-marker
This example represents the problem's constraints as :ref:`penalties `
(small :ref:`bqm_sdk`\ s that have higher values for variable assignments that
violate constraints) and creates an :term:`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
:math:`\{0, 1\}`\ --valued binary variables):
.. list-table:: Problem Variables
:widths: 15 25 25 35
:header-rows: 1
* - **Variable**
- **Represents**
- **Value: 1**
- **Value: 0**
* - :math:`t`
- Time of day
- Business hours
- Non-business hours
* - :math:`v`
- Venue
- Office
- Teleconference
* - :math:`l`
- Length
- Short (< 30 min)
- Long
* - :math:`p`
- Participation
- Mandatory
- Optional
.. note:: A slightly more complex problem might require variables with multiple
values; for example, :code:`l` could have values :code:`{30, 60, 120}`
representing the duration in minutes of meetings of several lengths. For such
problems a :term:`discrete quadratic model` (DQM) could be a better choice.
In general, problems with constraints are more simply solved using a
:ref:`constrained quadratic model ` (CQM) and appropriate hybrid CQM solver, as
demonstrated in the :ref:`example_cqm_binpacking` and
:ref:`example_cqm_stock_selling` 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 :math:`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.
.. table:: All Possible Meeting Options.
:name: MeetingOptions
==================== ================= ============== ================== =================
**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 :ref:`penalty_sdk` in many
different ways.
* Constraint 1: During business hours, all meetings must be attended in person
at the office.
This constraint requires that if :math:`t=1` (time of day is within
business hours) then :math:`v = 1` (venue is the office). A simple
penalty function, :math:`t-tv`, is shown in the truth table below:
.. list-table:: Constraint 1: :math:`t-tv`
:header-rows: 1
* - :math:`t`
- :math:`v`
- :math:`t-tv`
* - 0
- 0
- 0
* - 0
- 1
- 0
* - 1
- 0
- 1
* - 1
- 1
- 0
Penalty function :math:`t-tv` sets a penalty of 1 for the the case
:math:`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, :math:`ab`, penalizes
variable values :math:`a=b=1`. To penalize :math:`a=1, b=0`, you need the
penalty function :math:`a \overline{b}`. For :math:`\{0, 1\}`\ --valued variables,
you can substitute :math:`\overline{b} = 1-b` into the penalty and get
:math:`a \overline{b} = a(1-b) = a - ab`.
For more information on formulating such constraints, see the
:std:doc:`D-Wave Problem-Solving Handbook `
guide.
* Constraint 2: During business hours, participation in meetings is mandatory.
This constraint requires that if :math:`t=1` (time of day is within
business hours) then :math:`p=1` (participation is mandatory). A penalty
function is :math:`t-tp`, analogous to constraint 1.
* Constraint 3: Outside business hours, meetings must be teleconferenced.
This constraint requires that if :math:`t=0` (time of day is outside
business hours) then :math:`v=0` (venue is teleconference, not the office).
A penalty function is :math:`v-tv`, a reversal of constraint 1.
* Constraint 4: Outside business hours, meetings must not exceed 30 minutes.
This constraint requires that if :math:`t=0` (time of day is outside
business hours) then :math:`l=1` (meeting length is short).
A simple penalty function is :math:`1+tl-t-l`, as shown in the truth
table below:
.. list-table:: Constraint 4: :math:`1+tl-t-l`
:header-rows: 1
* - :math:`t`
- :math:`l`
- :math:`1+tl-t-l`
* - 0
- 0
- 1
* - 0
- 1
- 0
* - 1
- 0
- 0
* - 1
- 1
- 0
Penalty function :math:`1+tl-t-l` sets a penalty of 1 for the the case
:math:`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
.. math::
t-tv + t-tp + v-tv + 1+tl-t-l
= -2tv -tp +tl +t +v -l +1
Ocean's :doc:`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
:math:`\{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 :doc:`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 :code:`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']): # doctest: +SKIP
... 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 :class:`~dwave.system.samplers.DWaveSampler`
from Ocean software's :doc:`dwave-system `. Also use
its :class:`~dwave.system.composites.EmbeddingComposite` composite to map your
unstructured problem (variables such as :code:`t` etc.) to the sampler's graph
structure (the QPU's numerically indexed qubits) in a process known as
:term:`minor-embedding`. The next code sets up a D-Wave quantum computer as the
sampler.
.. include:: min_vertex.rst
:start-after: default-config-start-marker
:end-before: default-config-end-marker
>>> 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)) # doctest: +SKIP
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 :ref:`oceanstack`\ , 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 :class:`~dimod.reference.samplers.ExactSolver` and then
:class:`~dwave.system.samplers.DWaveSampler`.
* Compute resource: first a local CPU then a D-Wave quantum computer.