Solving with preprocessing and postprocessing methods

Preprocessing and postprocessing are optional techniques that can help in solving QUBOs better.

Before solving, QUBO preprocessing attempts to reduce the size of the problem before solving, by deterministically fixing variables to 0 or 1 when possible.

After solving, QUBO solutions can be refined by applying a local bit-flip search to each candidate bitstring. It evaluates each modified solution against the original QUBO instance, aiming to lower the objective cost.

In this tutorial, we show how to enable them using a classical heuristic (Tabu search).

Load a QUBO from the dataset

In [ ]:

import os
import re
from pathlib import Path
from qubosolver.saveload import load_qubo_dataset
output_directory = Path(str(os.path.abspath("01-dataset-generation-and-loading")).replace("docs/tutorial", "qubosolver_logs/tutorial"))

def load_datasets_by_size(directory: str):
    """
    Loads datasets from a directory by extracting the size from filenames.

    Args:
        directory (str): Path to the directory containing dataset files.

    Returns:
        dict[int, torch.Tensor]: A dictionary where keys are sizes and values are loaded datasets.
    """
    # Regular expression to match filenames like "raw_qubo_dataset_size_{size}.pt"
    pattern = r"raw_qubo_dataset_size_(\d+)\.pt"
    datasets_by_size = {}
    os.makedirs(directory, exist_ok=True)
    for filename in os.listdir(directory):
        match = re.match(pattern, filename)
        if match:
            size = int(match.group(1))
            file_path = os.path.join(directory, filename)
            dataset = load_qubo_dataset(file_path)
            datasets_by_size[size] = dataset
            print(f"Loaded dataset with size {size} from {file_path}")
    return datasets_by_size
datasets = load_datasets_by_size(output_directory)
size = 20
data_size_5 = datasets[size]

qubo_cofficents, first_qubo_solution = data_size_5[9]

Postprocessing after a tabu search heuristic

In [ ]:

from qubosolver import QUBOInstance
from qubosolver.config import SolverConfig
from qubosolver.solver import QuboSolver


instance = QUBOInstance(qubo_cofficents)

# Create a SolverConfig object with classical solver options.
config = SolverConfig.from_kwargs(
    use_quantum=False,
    classical_solver_type="tabu_search",
    do_postprocessing=True
)

# Instantiate the classical solver using the dispatcher.
classical_solver = QuboSolver(instance, config)

# Solve the QUBO problem.
solution = classical_solver.solve()
print("Solution result:", solution)

Solution result: QUBOSolution(bitstrings=tensor([[0., 0., 1., 0., 0., 1., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0., 0., 0.,
         1., 0.]]), costs=tensor([-197.7731]), counts=None, probabilities=None, solution_status=<SolutionStatusType.POSTPROCESSED: 'postprocessed'>)

Preprocessing before a tabu search heuristic

In [ ]:

from qubosolver import QUBOInstance
from qubosolver.config import SolverConfig
from qubosolver.solver import QuboSolver


instance = QUBOInstance(qubo_cofficents)

# Create a SolverConfig object with classical solver options.
config = SolverConfig.from_kwargs(
    use_quantum=False,
    classical_solver_type="tabu_search",
    do_preprocessing=True
)

# Instantiate the classical solver using the dispatcher.
classical_solver = QuboSolver(instance, config)

# Solve the QUBO problem.
solution = classical_solver.solve()
print("Solution result:", solution)

Solution result: QUBOSolution(bitstrings=tensor([[0., 0., 1., 0., 0., 1., 0., 0., 0., 1., 1., 0., 0., 1., 0., 0., 0., 0.,
         1., 0.]]), costs=tensor([-145.0744]), counts=None, probabilities=None, solution_status=<SolutionStatusType.PREPROCESSED: 'preprocessed'>)

We can access the number of variables fixed by preprocessing via the attribute n_fixed_variables_preprocessing from the solver:

In [ ]:

classical_solver.n_fixed_variables_preprocessing

Out[ ]:

0