# D-Wave Ocean: Constrained Scheduling

(02/14/2021)

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.

## Solution Steps

D-Wave's 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 ... Optional No - Violates C2 Business hours Office Long Mandatory Yes Business hours Teleconference ... ... No - Violates C1 Non-business hours Office ... ... No - Violates C3 Non-business hours Teleconference Short Mandatory Yes Non- business hours Teleconference Short Optional Yes Non-business hours Teleconference Long ... No - Violates C4

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):
return (location and mandatory)      # In office and mandatory participation
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.

csp = dwavebinarycsp.ConstraintSatisfactionProblem(dwavebinarycsp.BINARY)


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^N_iq_ix_i + \sum^N_{i, which are the inputs for programming the quantum computer.

## 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.
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.
sampler = strangeworks.dwave.ExactSolver()
solution = sampler.sample(bqm)

Valid solutions—assignments of variables that do not violate any constraint—should have the lowest value of the BQM.

## Solving on a D-Wave System

See D-Wave's docs for the continuation of this example.