# 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 we 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 we 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 we 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 value[1].

```
>>> from math import isclose
>>> min_energy = solution.record.energy.min()
>>> for sample, energy in solution.data(['sample', 'energy']): # doctest: +SKIP
... 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 of `abs_tol=1.0` is used
because by default the `stich()` function increases the
energy of solutions that violate one constraint by `min_classical_gap=2.0` . |

### Solving on a D-Wave System¶

We now solve on a D-Wave system using sampler *DWaveSampler()* from Ocean software’s
dwave-system. We 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, we ask for many samples, not just one. This way, we see multiple “best” answers and reduce the probability of settling on a suboptimal answer. Below, we 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']): # doctest: +SKIP
... 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 then*DWaveSampler()*. - Compute resource: first a local CPU then a D-Wave system.