Job Sequencing
- class qubovert.problems.JobSequencing(*args, **kwargs)
JobSequencing.
Class to manage converting Job Sequencing to and from its QUBO and QUSO formluations. Based on the paper “Ising formulations of many NP problems”, hereforth designated as [Lucas].
The goal of the JobSequencing problem is as follows. Given workers and jobs, where each job has a designated length, assign each of the jobs to one of the workers such that largest total length assigned to a worker is minimized.
This class inherits some methods and attributes from the
qubovert.problems.Problem
class.Example
>>> from qubovert.problems import JobSequencing >>> from any_module import qubo_solver >>> # or you can use my bruteforce solver... >>> # from qubovert.utils import solve_qubo_bruteforce as qubo_solver
>>> job_lengths = {"job1": 2, "job2": 3, "job3": 1} >>> num_workers = 2 >>> problem = JobSequencing(job_lengths, num_workers) >>> Q = problem.to_qubo() >>> obj, sol = qubo_solver(Q) >>> solution = problem.convert_solution(sol)
>>> print(solution) ({'job1', 'job3'}, {'job2'}) # or ({'job2'}, {'job1', 'job3'}) >>> print(problem.is_solution_valid(solution)) True # since each job is covered exactly once >>> print( obj == max(sum(job_lengths[i] for i in x) for x in solution) == 3 ) True
__init__.
The goal of the JobSequencing problem is as follows. Given workers and jobs, where each job has a designated length, assign each of the jobs to one of the workers such that largest total length assigned to a worker is minimized.
- Parameters
job_lengths (tuple or list of integers, or a dict.) – The length of each job. If
job_lengths
is adict
then each key is a job that maps to its length. Otherwise, the index ofjob_lengths
is the job and it is mapped to its length. Note that the lengths must be integers!num_workers (int.) – The number of workers that can be assigned jobs.
log_trick (boolean (optional, defaults to True)) – Indicates whether or not to use the log trick discussed in [Lucas].
M (int (optional, defaults to None) We recommend not adjusting this.) – The maximum expected numbers of jobs assigned to a single worker, see [Lucas]. If M is None, then it will be set to the value required to ensure accuracy of the model. To possibly sacrifice accuracy but decrease the number of variables in the model, you can set M to something smaller.
- property M
A copy of the
M
constant.- Returns
M – If
M
was supplied in the initialization of the class, then this will return the same. Otherwise, it will return the value that the class calculated for its default.- Return type
int.
- convert_solution(solution, spin=False)
convert_solution.
Convert the solution to the QUBO or QUSO to the solution to the Job Sequencing problem.
- Parameters
solution (iterable or dict.) – The QUBO or QUSO solution output. The QUBO solution output is either a list or tuple where indices specify the label of the variable and the element specifies whether it’s 0 or 1 for QUBO (or 1 or -1 for QUSO), or it can be a dictionary that maps the label of the variable to is value.
spin (bool (optional, defaults to False)) – spin indicates whether
solution
is the solution to the boolean {0, 1} formulation of the problem or the spin {1, -1} formulation of the problem. This parameter usually does not matter, and it will be ignored if possible. The only time it is used is ifsolution
contains all 1’s. In this case, it is unclear whethersolution
came from a spin or boolean formulation of the problem, and we will figure it out based on thespin
parameter.
- Returns
res – Each element of the tuple corresponds to a worker. Each element of the tuple is a set of jobs that are assigned to that worker.
- Return type
tuple of sets.
- is_solution_valid(solution, spin=False)
is_solution_valid.
Returns whether or not the proposed solution completes all the jobs exactly once.
- Parameters
solution (iterable or dict.) – solution can be the output of JobSequencing.convert_solution, or the QUBO or QUSO solver output. The QUBO solution output is either a list or tuple where indices specify the label of the variable and the element specifies whether it’s 0 or 1 for QUBO (or 1 or -1 for QUSO), or it can be a dictionary that maps the label of the variable to is value.
spin (bool (optional, defaults to False)) – spin indicates whether
solution
is the solution to the boolean {0, 1} formulation of the problem or the spin {1, -1} formulation of the problem. This parameter usually does not matter, and it will be ignored if possible. The only time it is used is ifsolution
contains all 1’s. In this case, it is unclear whethersolution
came from a spin or boolean formulation of the problem, and we will figure it out based on thespin
parameter.
- Returns
valid – True if the proposed solution is valid, else False.
- Return type
boolean.
- property job_lengths
job_lengths.
A copy of the job lengths.
- Returns
job_lengths – Will be whichever type was inputted in the initialization of the class. The length of each job. If
job_lengths
is adict
then each key is a job that maps to its length. Otherwise, the index ofjob_lengths
is the job and it is mapped to its length.- Return type
tuple or list of integers, or dict.
- property log_trick
log_trick.
A copy of the value for log_trick, indicating whether or not to use the log trick. See [Lucas].
- Returns
log_trick
- Return type
bool.
- property num_binary_variables
num_binary_variables.
The number of binary variables that the QUBO and QUSO use.
- Returns
num – The number of variables in the QUBO/QUSO formulation.
- Return type
int.
- property num_workers
num_workers.
A copy of the number of workers.
- Returns
num_workers – The number of workers allowed for the problem.
- Return type
int.
- solve_bruteforce(all_solutions=False)
solve_bruteforce.
Solves the JobSequence problem exactly with a brute force method. THIS SHOULD NOT BE USED FOR LARGE PROBLEMS! The advantage over this method as opposed to using a brute force QUBO solver is that the QUBO formulation has many slack variables.
- Parameters
all_solutions (boolean (optional, defaults to False)) – If
all_solutions
is set to True, all the best solutions to the problem will be returned rather than just one of the best. If the problem is very big, then it is best ifall_solutions == False
, otherwise this function will use a lot of memory.- Returns
res – Each element of the tuple corresponds to a worker. Each element of the tuple is a set of jobs that are assigned to that worker. If
all_solutions == True
thenres
will be a list, where each element of the list will be one of the optimal solutions.- Return type
tuple of sets or list of tuple of sets.
Example
>>> job_lengths = {"job1": 2, "job2": 3, "job3": 1} >>> num_workers = 2 >>> problem = JobSequencing(job_lengths, num_workers) >>> print(problem.solve_bruteforce()) ({'job1', 'job3'}, {'job2'}) # or ({'job2'}, {'job1', 'job3'})
>>> print(problem.solve_bruteforce(True)) [({'job1', 'job3'}, {'job2'}), ({'job2'}, {'job1', 'job3'})]
- to_pubo(*args, **kwargs)
to_pubo.
Since the model is already degree two,
self.to_pubo
will simply returnqubovert.utils.PUBOMatrix(self.to_qubo(*args, **kwargs))
.- Returns
P – The upper triangular PUBO matrix, a PUBOMatrix object. For most practical purposes, you can use PUBOMatrix in the same way as an ordinary dictionary. For more information, see
help(qubovert.utils.PUBOMatrix)
.- Return type
qubovert.utils.PUBOMatrix object.
- to_puso(*args, **kwargs)
to_puso.
Create and return PUSO model representing the problem. Should be implemented in child classes. If this method is not implemented in the child class, then it simply calls
to_pubo
orto_quso
and converts to a PUSO formulation.- Parameters
arguments (Defined in the child class.) – They should be parameters that define lagrange multipliers or factors in the QUSO model.
- Returns
H – For most practical purposes, you can use PUSOMatrix in the same way as an ordinary dictionary. For more information, see
help(qubovert.utils.PUSOMatrix)
.- Return type
qubovert.utils.PUSOMatrix object.
- Raises
RecursionError` if neither to_pubo nor to_puso are define –
in the subclass. –
- to_qubo(A=None, B=1)
to_qubo.
Create and return the job sequencing problem in QUBO form following section 6.3 of [Lucas]. The Q matrix for the QUBO will be returned as an uppertriangular dictionary. Thus, the problem becomes minimizing \(\sum_{i \leq j} x_i x_j Q_{ij}\). A and B are parameters to enforce constraints.
If all the constraints are satisfied, then the objective function will be equal to the total length of the scheduling.
- Parameters
A (positive float (optional, defaults to None)) –
A
enforces the constraints. IfA is None
, thenA
will be chosen such that the minimum of the QUBO is guaranteed to satisfy the constraints (A = B*max(L)
). This may not be the best value for any particular QUBO solver, since it may cause a non smooth landscape that is hard to minimize.B (positive float (optional, defaults to 1)) –
B
is the constant in front of the portion of the QUBO to minimize.
- Returns
Q – The upper triangular QUBO matrix, a QUBOMatrix object. For most practical purposes, you can use QUBOMatrix in the same way as an ordinary dictionary. For more information, see
help(qubovert.utils.QUBOMatrix)
.- Return type
qubovert.utils.QUBOMatrix object.
- to_quso(*args, **kwargs)
to_quso.
Create and return QUSO model representing the problem. Should be implemented in child classes. If this method is not implemented in the child class, then it simply calls
to_qubo
and converts the QUBO formulation to an QUSO formulation.- Parameters
arguments (Defined in the child class.) – They should be parameters that define lagrange multipliers or factors in the QUSO model.
- Returns
L – The upper triangular coupling matrix, where two element tuples represent couplings and one element tuples represent fields. For most practical purposes, you can use IsingCoupling in the same way as an ordinary dictionary. For more information, see
help(qubovert.utils.QUSOMatrix)
.- Return type
qubovert.utils.QUSOMatrix object.
- Raises
RecursionError` if neither to_qubo nor to_quso are define –
in the subclass. –