Adding the Binary Paint Shop Problem

Added the Binary Paint Shop Problem (BPSP) problem class with its corresponding tests. This implementation was based on the following works:

Beating Classical Heuristics for the Binary Paint Shop Problem with the Quantum Approximate Optimization Algorithm
Some Heuristics for the Binary Paint Shop Problem and their Expected Number of Colour Changes
Upcoming/Unpublished work by V Vijendran et al from A*STAR and CQC2T.

Description

This pull request introduces support for the Binary Paint Shop Problem, a combinatorial optimization task inspired by real-world automotive paint shop scenarios. In this challenge, a specific car sequence exists where each car appears twice. The main goal is to determine the most efficient paint sequence to minimize the number of paint swaps between consecutive cars.

The addition includes a new BPSP class within the problem module. This class facilitates the creation of Binary Paint Shop Problem instances. It offers methods to:

Generate random BPSP problem instances.
Convert BPSP instances into their related graph structures.
Solve the problem through traditional heuristics like the Red-First and Greedy Heuristic, as well as using the CPLEX and QUBO solvers.
Visualize the paint sequence for any given car sequence based on the solution provided.

Example:

# Required libraries are imported
import matplotlib.pyplot as plt
from openqaoa.problems import BPSP
from openqaoa.algorithms import QAOA

# A random instance of the Binary Paint Shop Problem is generated with 16 cars
bpsp = BPSP.random_instance(num_cars=16, seed=42)

# Solutions are computed using the CPLEX, Red-First, and Greedy algorithms
cplex_seq, cplex_swaps = bpsp.solve_cplex()
redfirst_seq, redfirst_swaps = bpsp.solve_redfirst()
greedy_seq, greedy_swaps = bpsp.solve_greedy()

# QAOA (Quantum Approximate Optimization Algorithm) is initialized and compiled
qaoa = QAOA()
qaoa.compile(bpsp.qubo)
qaoa.optimize()
# The result from QAOA is fetched, with a focus on the lowest-cost solution
qaoa_bitstring = qaoa.result.lowest_cost_bitstrings()["solutions_bitstrings"][0]
qaoa_seq, qaoa_swaps = bpsp.paintseq_from_bits(qaoa_bitstring)

# Creating a plotting area with 4 rows (one for each method)
fig, ax = plt.subplots(4, 1, figsize=(20, 8))

# Plotting the paint sequence for each of the algorithms used
bpsp.plot_paint_sequence(redfirst_seq, ax[0])
ax[0].set_title(f"Red-First Paint Sequence: {redfirst_swaps} Swaps")
bpsp.plot_paint_sequence(greedy_seq, ax[1])
ax[1].set_title(f"Greedy Paint Sequence: {greedy_swaps} Swaps")
bpsp.plot_paint_sequence(cplex_seq, ax[2])
ax[2].set_title(f"CPLEX Paint Sequence: {int(cplex_swaps)} Swaps")
bpsp.plot_paint_sequence(qaoa_seq, ax[3])
ax[3].set_title(f"QAOA Paint Sequence: {qaoa_swaps} Swaps")

# Adjusting the vertical spacing between plots to avoid overlap
fig.subplots_adjust(hspace=0.75)

# Displaying the final combined plot
plt.show()

Checklist

[x] I have performed a self-review of my code.
[x] I have commented my code and used numpy-style docstrings
[ ] I have made corresponding updates to the documentation.
[x] My changes generate no new warnings
[x] I have added/updated tests to make sure bugfix/feature works.
[x] New and existing unit tests pass locally with my changes.

Type of change

[x] New feature (non-breaking change which adds functionality)

How Has This Been Tested?

The tests for this BPSP class are located within ./tests/test_bpsp.py and ./tests/test_qubo.py.

entropicalabs / openqaoa