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 a dict then each key is a job that maps to its length. Otherwise, the index of job_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 if solution contains all 1’s. In this case, it is unclear whether solution came from a spin or boolean formulation of the problem, and we will figure it out based on the spin 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 if solution contains all 1’s. In this case, it is unclear whether solution came from a spin or boolean formulation of the problem, and we will figure it out based on the spin 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 a dict then each key is a job that maps to its length. Otherwise, the index of job_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 if all_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 then res 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 return qubovert.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 or to_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. If A is None, then A 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. –