DWave Ocean: 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.
Solution Steps
Formulate the Problem
 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.
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 
Nonbusiness hours  Office
 ...  ...
 No  Violates C3 
Nonbusiness hours  Teleconference  Short  Mandatory  Yes 
Non business hours  Teleconference  Short  Optional  Yes 
Nonbusiness 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):
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.
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^N_iq_ix_i + \sum^N_{i<j}q_{i,j}x_ix_j$, which are the inputs for programming the quantum computer.
Solve the Problem by Sampling
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.