Lösen Sie das Problem der Marktaufteilung mit dem „ ParityQC “ Parity Twine Optimizer

Geschätzte Ausführungszeit: 10 Sekunden auf einem Nighthawk- r2 -Prozessor. (HINWEIS: Dies ist lediglich eine Schätzung. (Die Laufzeit kann variieren.)

Lernziele

• Rufen Sie das Marktanteils-Problem aus der QOBLIB – Quantum Optimization Benchmarking Library ab und formatieren Sie es.
• Richten Sie den Parity Twine Optimizer ein und nutzen Sie ihn, um einen Fall von Marktaufspaltung zu lösen.
• Erfahren Sie, wie Sie die Optionen für den Parity Twine Optimizer auswählen und welche Ergebnisse ausgegeben werden.

Hintergrund

In diesem Tutorial wird gezeigt, wie man das Problem der Marktaufteilung mit dem „ ParityQC “ von Parity Twine Optimizer löst.

Das Beispielproblem stammt aus der QOBLIB – Quantum Optimization Benchmarking Library.

Problem der Marktaufteilung

Das Marktteilungsproblem ist ein reales, NP-schweres Problem der Ressourcenallokation und hat sich zu einem Maßstab für Quantenoptimierungsalgorithmen entwickelt. Dies stellt eine logistische Herausforderung mit hohem Einsatz dar: Wie lässt sich eine komplexe Landschaft aus Kunden und Produkten in überschaubare, gleich große Gebiete aufteilen?

Das Ziel besteht darin, die Märkte von „ $n$ “ in zwei ausgewogene Vertriebsregionen aufzuteilen, sodass jede Region genau die Hälfte der Gesamtnachfrage nach „ $m$ “-Produkten erhält. Die Lösung besteht in einer spezifischen Konfiguration, die eine möglichst gleichmäßige Verteilung der Produktnachfrage gewährleistet und es einem Unternehmen ermöglicht, eine Logistik- und Personalstrategie umzusetzen, bei der beide Regionen ausgewogen bedeckt werden, wodurch Risiken wie lokale Produktengpässe oder Überbelegung der Lager minimiert werden.

Da die Anzahl der Märkte und Produkte zunimmt, wächst die Anzahl der möglichen Kombinationen exponentiell, was es schwierig macht, mit herkömmlichen exhaustiven Suchverfahren die optimale Aufteilung zu finden.

Mathematische Formulierung

Sei $A$ eine $m \times n$ -Matrix, die die Nachfrage nach Produkten über verschiedene Märkte hinweg darstellt, wobei $A_{ij}$ die Nachfrage nach dem Produkt $i$ im Markt $j$ ist.

Es wird ein binärer Zuordnungsvektor $x = [x_1, x_2, \dots, x_n]^T \in \{0, 1\}^n$ definiert, wobei gilt:

• $x_j = 1$ weist der Region A die Markt $j$ en zu.
• $x_j = 0$ ordnet die Markt $j$ en der Region B zu.

Sei $d = [d_1, d_2, \dots, d_m]^T$ der Gesamtnachfragevektor für jedes Produkt, berechnet als $d = A \cdot \mathbf{1}$. Das angestrebte Absatzvolumen pro Region für das Produkt $i$ beträgt genau $\frac{d_i}{2}$.

Die Optimierungs- bzw. Machbarkeitsbedingung besagt, dass der der Region A zugewiesene Gesamtumsatz bei jedem Produkt genau der Hälfte der Gesamtnachfrage entsprechen muss:

$A x = \frac{1}{2} A \mathbf{1} = b.$

Da eine exakte Division in der Praxis selten möglich ist, wird das Problem so formuliert, dass die quadrierte Abweichung von den Nebenbedingungen (die Kostenfunktion) minimiert wird:

$\min_{x} \left\Vert{} A x - b \right\Vert{}^2 = \sum_{i=1}^{m} \left( \sum_{j=1}^{n} A_{ij} x_j - b\right)^2.$

Erweitert man dies, erhält man eine Form, die einem quadratischen, uneingeschränkten binären Optimierungsproblem (QUBO) entspricht.

Nach der Berechnung bestimmt der Lösungsvektor $x$, welcher Region der Markt zugeordnet wird. Dies ist die Konfiguration, mit der eine möglichst ausgewogene Verteilung der Produktnachfrage erreicht wird.

Anforderungen

Bevor Sie mit dieser Anleitung beginnen, stellen Sie bitte sicher, dass folgende Komponenten installiert sind:

• Qiskit Functions Catalog IBM Client (pip install qiskit-ibm-catalog)
• Qiskit-Add-on „Optimization Mapper“ (pip install qiskit_addon_opt_mapper)
• NumPy (pip install numpy)

Außerdem benötigen Sie die Berechtigung, auf die Twine-Optimizer-Funktion „ ParityQC “ zuzugreifen. Um Zugang zu beantragen, füllen Sie bitte dieses Formular aus.

Einrichtung

(Dieser Code setzt voraus, dass Sie Ihr Konto bereits in Ihrer lokalen Umgebung gespeichert haben.)

Importieren Sie zunächst alle für dieses Tutorial erforderlichen Pakete.

import tempfile

from collections.abc import Callable
from pathlib import Path

import numpy as np
import requests

from qiskit_addon_opt_mapper import OptimizationProblem
from qiskit_addon_opt_mapper.converters import OptimizationProblemToQubo
from qiskit_ibm_catalog import QiskitFunctionsCatalog

Laden Sie den „Parity Twine Optimizer“ aus dem Katalog „ Qiskit Functions “ herunter:

catalog = QiskitFunctionsCatalog(channel="ibm_quantum_platform")
function = catalog.load("parityqc/parity-twine-optimizer")

Schritt 1: Definieren Sie das Problem als Zielfunktion

Beziehen Sie wie folgt ein Beispiel für ein Marktteilungs-Problem aus der QOBLIB – Quantum Optimization Benchmarking Library.

Die Funktion load_market_split_problem ruft ein bestimmtes Problem aus QOBLIB ab und wandelt es in ein QUBO-Problem um.

def load_market_split_problem(instance_name: str) -> OptimizationProblem:
    """Load and formulate a market split optimization problem from an QOBLIB instance.

    The QOBLIB library can be found here:
    https://github.com/ZIB-AOPT/QOBLIB.

    Args:
        instance_name: Name of the market split instance to load as specified by the .dat file
            in the QOBLIB repo.

    Returns:
        The output OptimizationProblem containing the loaded market split problem.
    """

    problem_matrix, problem_vector = fetch_and_parse(
        instance_name, "01-marketsplit", parse_marketsplit_dat
    )

    # Create optimization problem
    optimization_problem = OptimizationProblem(instance_name)

    # Add binary variables (one for each market)
    optimization_problem.binary_var_list(problem_matrix.shape[1])

    # Add equality constraints (one for each product)
    for idx, rhs in enumerate(problem_vector):
        optimization_problem.linear_constraint(
            problem_matrix[idx, :], sense="==", rhs=rhs
        )

    # Convert to QUBO with penalty parameter
    return OptimizationProblemToQubo(penalty=1).convert(optimization_problem)

Die Funktion load_market_split_problem benötigt die folgenden Parser-Funktionen, um die Daten zum Marktaufteilungsproblem aus QOBLIB abzurufen und zu verarbeiten.

def fetch_and_parse(instance_name: str, problem: str, parse_func: Callable):
    """Generic function to fetch and parse data from QOBLIB repository.

    Args:
        instance_name: Name of the instance to fetch.
        problem: Category of the problem (e.g., '01-marketsplit', '07-independentset').
        parse_func: Function used to parse the downloaded file
            (e.g., parse_marketsplit_dat, parse_gph_file).

    Returns:
        Result of `parse_func` - either (np.ndarray, np.ndarray) for marketsplit
        or nx.Graph for MIS.
    """
    base_url = (
        "https://raw.githubusercontent.com/ZIB-AOPT/QOBLIB/refs/heads/main/"
    )
    url = (
        base_url
        + problem
        + "/instances/"
        + instance_name
        + (".dat" if problem == "01-marketsplit" else ".gph")
    )

    try:
        response = requests.get(url, timeout=30)
        response.raise_for_status()

        with tempfile.NamedTemporaryFile(
            mode="w",
            suffix=".dat" if problem == "01-marketsplit" else ".gph",
            delete=False,
            encoding="utf-8",
        ) as temp_file:
            temp_file.write(response.text)
            temp_file_path = temp_file.name

        try:
            return parse_func(temp_file_path)
        finally:
            Path(temp_file_path).unlink(missing_ok=True)

    except requests.RequestException as e:
        print(f"Error fetching data from repository: {e}")
    except (ValueError, OSError) as e:
        print(f"Error processing data: {e}")
        return None


def parse_marketsplit_dat(filename: str) -> tuple[np.ndarray, np.ndarray]:
    """Parse a market split problem from a .dat file format.

    Args:
        filename: Path to the .dat file.

    Returns:
        Tuple of (A, b) where:
            - A: (m, n) array of coefficients.
            - b: (m,) array of target values.

    Raises:
        ValueError: If file format is invalid or file is empty.
    """
    with Path(filename).open(encoding="utf-8") as f:
        lines = [
            line.strip()
            for line in f
            if line.strip() and not line.startswith("#")
        ]

    if not lines:
        raise ValueError("Empty or invalid .dat file")

    # First line: m n (number of products and markets)
    try:
        m, n = map(int, lines[0].split())
    except (ValueError, IndexError) as e:
        raise ValueError(
            "Invalid file format: first line must contain 'm n' integers"
        ) from e

    if len(lines) < m + 1:
        raise ValueError(
            f"File contains {len(lines)} lines but expected {m + 1} lines"
        )

    # Next m lines: each row of A followed by corresponding element of b
    mat_a = []
    vec_b = []

    for i in range(1, m + 1):
        try:
            values = list(map(int, lines[i].split()))
        except ValueError as e:
            raise ValueError(f"Invalid integer values in line {i + 1}") from e

        if len(values) != n + 1:
            raise ValueError(
                f"Line {i + 1} contains {len(values)} values but expected {n + 1}"
            )

        mat_a.append(values[:-1])  # First n values: product sales per market
        vec_b.append(values[-1])  # Last value: target sales for this product

    return np.array(mat_a), np.array(vec_b)

Sobald definiert ist, load_marketsplit_problem kann damit eine bestimmte Probleminstanz aus der Bibliothek geladen werden:

ms_instance = "ms_04_050_001"

ms_problem = load_market_split_problem(ms_instance)

Schritt 2: In das JSON-Format konvertieren

Im ersten Schritt haben Sie die QUBO-Form des Problems ermittelt. Wandeln Sie es nun für die Optimierungsfunktion in das JSON-Format um:

def optimization_problem_to_json(
    problem: OptimizationProblem,
) -> dict[str, float]:
    """
    Converts an unconstrained quadratic OptimizationProblem in terms of binary or spin variables
    to the JSON input format of the Parity Twine Qiskit Function.

    Args:
        problem: The optimization problem to convert to JSON.

    Returns:
        The JSON input format of the given problem.
    """
    ising, constant = problem.to_ising()
    output = {"()": float(constant)}
    for op, coefficient in zip(ising.paulis, ising.coeffs, strict=True):
        # Invert the label strings because Qiskit has opposite convention
        qubits = tuple(
            num
            for num, pauli in enumerate(op.to_label()[::-1])
            if pauli == "Z"
        )
        output[str(qubits)] = float(coefficient)
    return output

Die QUBO-Instanz des Marktaufteilungsproblems wird nun wie folgt in das JSON-Format konvertiert:

json_ms_problem = optimization_problem_to_json(ms_problem)

Schritt 3: Lösen Sie das Problem mit dem „Parity Twine Optimizer“

Nachdem Sie nun das Marktteilungsproblem formuliert und in die richtige Form gebracht haben, können Sie mithilfe des Twine Optimizers und eines ausgewählten Backends unter IBM® eine Lösung finden.

Um die Funktion auszuführen, wählen Sie ein geeignetes Backend-Gerät aus; zum Beispiel ibm_phoenix.

Sie können verwenden, options um (optional) zusätzliche Kontrolle über die Übermittlung zu erhalten:

options = {
    "shots": 100000,
    "postprocessing_level": 1,
    "transpile_only": False,
    "job_tags": ["market_split"],
}

wobei eine ganze Zahl ist shots , die die Anzahl der Schaltkreisaufrufe angibt, postprocessing_level bestimmt, ob das Ergebnis einer Nachbearbeitung unterzogen wird, transpile_onlygibt an, ob das Problem lediglich in einen Schaltkreis transpiliert (und nicht gelöst) wird, und job_tags ist die Kennung, mit der der Auftrag auf IBM Quantum® Platform identifiziert wird.

Führen Sie den Optimierer aus:

function_job = function.run(
    problem=json_ms_problem,
    variable_type="spin",
    backend_name="ibm_phoenix",
    options=options,
)
print(f"Job ID: {function_job.job_id}")

Überprüfen Sie den Auftragsstatus:

# Monitor the job status
function_job.status()

Ergebnisse abrufen:

# Retrieve the job result if the status is DONE
result = function_job.result()

result

Das Ergebnis hat folgende Form:

{
    'solution': {'0': 1, '1': -1, '10': 1, ... },
    'objective_value':  1.0,
    'solution_bitstring': '010000011101111011001001110010',
    'metadata': {
        'circuit_metrics': {
            'depth': 309,
            'gate_count': 3880,
            'two_qubit_gate_depth': 116,
            'two_qubit_gate_count': 899,
            'num_qubits': 30,
            'operations': {'sx': 1244, 'rz': 1227, 'cz': 899, 'delay': 473, 'measure': 30, 'x': 7},
        },
        'solver_info': {
            'variable_mapping': {'0': 0, '1': 1, '10': 2, ... },
            'bitstring_distributions': {
                'before_postprocessing': {'011101110010110111001110011000': 1, ...},
                'after_postprocessing': {'011011110000110101001111011000': 1, ...}
            },
            'best_parameters': {
                'beta': [-0.18054534155552715],
                'gamma': [1.4141236348317905]
            }
        },
        'resource_usage': {
            'RUNNING: MAPPING': {'CPU_TIME': 172.936},
            'RUNNING: OPTIMIZING_FOR_HARDWARE': {'CPU_TIME': 0.272},
            'RUNNING: WAITING_FOR_QPU': {'CPU_TIME': 7.798},
            'RUNNING: EXECUTING_QPU': {'QPU_TIME': 30.0},
            'RUNNING: POST_PROCESSING': {'CPU_TIME': 31.613},
        },
    }
}

wobei das Wörterbuch solution den in der Aufgabe definierten Qubits entspricht und deren optimierte Spinwerte angibt. metadata liefert Informationen zur Transpilierung (Anzahl der Zwei-Qubit-Gatter/Tiefe, verwendete Gatter, aktive Qubits) sowie zu verschiedenen Laufzeiten.

Im Zusammenhang mit dem Marktaufteilungsproblem stellt die Lösungsbitstring einen binären Zuordnungsvektor dar, der dazu dient, Märkte in zwei separate Bereiche aufzuteilen. Der Wert 1 ordnet diesen bestimmten Markt der Region A zu, während der Wert 0 ihn der Region B zuordnet. Bei der optimalen Lösung sorgt die Kombination für eine ausgewogene Aufteilung, d. h., beide Regionen erhalten genau die Hälfte der gesamten Unternehmensnachfrage für jedes Produkt.

Nächste Schritte