D-Wave Ocean: Constrained Scheduling

Published by strangeworks (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 24=162^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): 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, qiq_i and qi,jq_{i,j} respectively in iNqixi+i<jNqi,jxixj\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

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.