Resuelve el problema de la segmentación del mercado con el optimizador Parity Twine de ParityQC

Estimación de tiempo de ejecución: 10 segundos en un procesador Nighthawk r2. (NOTA: Se trata únicamente de una estimación. (El tiempo de ejecución puede variar.)

Resultados del aprendizaje

• Consigue y formatea el problema «Market Split» de la biblioteca QOBLIB (Quantum Optimization Benchmarking Library).
• Configura y utiliza el Parity Twine Optimizer para resolver un caso de «Market Split».
• Descubre cómo seleccionar las opciones del optimizador Parity Twine y qué resultados se obtienen.

En segundo plano

Este tutorial muestra cómo resolver el problema de la división del mercado utilizando el optimizador «Parity Twine» de ParityQC.

El ejemplo del problema procede de QOBLIB (Quantum Optimization Benchmarking Library).

Problema de división del mercado

El problema de la división del mercado es un problema real de asignación de recursos de complejidad NP-difícil y se ha convertido en un punto de referencia para los algoritmos de optimización cuántica. Supone un reto logístico de gran envergadura: cómo dividir un panorama complejo de clientes y productos en territorios manejables y equilibrados.

El objetivo es dividir los mercados de $n$ en dos regiones de ventas equilibradas, de modo que cada región reciba exactamente la mitad de la demanda total de los productos de $m$. La solución consiste en la configuración específica que permite lograr la distribución más uniforme posible de la demanda de productos, lo que permite a una empresa aplicar una estrategia logística y de dotación de personal en la que ambas regiones estén equilibradas, minimizando así riesgos como la escasez localizada de productos o el desbordamiento de los almacenes.

A medida que aumenta el número de mercados y productos, el número de permutaciones posibles crece exponencialmente, lo que dificulta encontrar la mejor distribución mediante búsquedas exhaustivas tradicionales.

Formulación matemática

Sea $A$ una matriz de tipo $m \times n$ que representa la demanda de productos en los distintos mercados, donde $A_{ij}$ es la demanda del producto $i$ en el mercado $j$.

Se define un vector de asignación binario, $x = [x_1, x_2, \dots, x_n]^T \in \{0, 1\}^n$, en el que:

• $x_j = 1$ asigna el mercado $j$ a la Región A.
• $x_j = 0$ asigna el mercado « $j$ » a la Región B.

Sea $d = [d_1, d_2, \dots, d_m]^T$ el vector de demanda total de cada producto, calculado como $d = A \cdot \mathbf{1}$. El volumen de ventas objetivo por región para el producto $i$ es exactamente $\frac{d_i}{2}$.

La restricción de optimización o viabilidad exige que las ventas totales asignadas a la Región A coincidan exactamente con la mitad de la demanda total de cada producto:

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

En la práctica, dado que rara vez es posible realizar una división exacta, el problema se formula para minimizar el cuadrado de la desviación respecto a la restricción (la función de coste):

$\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.$

Al desarrollar esto, se obtiene una forma equivalente a un problema de optimización binaria cuadrática sin restricciones (QUBO).

Una vez resuelta la ecuación, el vector de solución $x$ determina a qué región se asigna el mercado. Esta es la configuración que permite lograr la distribución más equilibrada posible de la demanda de productos.

Requisitos

Antes de comenzar este tutorial, asegúrate de que tengas instalados los siguientes elementos:

• Qiskit Functions Catalog IBM Cliente (pip install qiskit-ibm-catalog)
• Complemento de Qiskit «Optimization Mapper» (pip install qiskit_addon_opt_mapper)
• NumPy (pip install numpy)

También necesitas permiso para acceder a la función « ParityQC » de Twine Optimizer. Para solicitar acceso, rellena este formulario.

Configuración

(Este código da por hecho que ya has guardado tu cuenta en tu entorno local.)

En primer lugar, importa todos los paquetes necesarios para este tutorial.

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

Carga el «Parity Twine Optimizer» del catálogo « Qiskit Functions »:

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

Paso 1: Definir el problema como una función objetivo

Obtén un ejemplo de problema de división de mercado de la biblioteca QOBLIB (Quantum Optimization Benchmarking Library) de la siguiente manera.

La función load_market_split_problem recupera un problema determinado de QOBLIB y lo convierte en un problema QUBO.

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)

La función load_market_split_problem requiere las siguientes funciones de análisis sintáctico para recuperar y procesar los datos del problema de división de mercados procedentes de QOBLIB.

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)

Una vez definido, se load_marketsplit_problem puede utilizar para cargar una instancia concreta del problema desde la biblioteca:

ms_instance = "ms_04_050_001"

ms_problem = load_market_split_problem(ms_instance)

Paso 2: Convertir al formato JSON

En el primer paso, has obtenido la formulación QUBO del problema. Ahora, conviértelo al formato JSON para la función del optimizador:

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

La instancia QUBO del problema «Market Split» se ha convertido ahora al formato JSON de la siguiente manera:

json_ms_problem = optimization_problem_to_json(ms_problem)

Paso 3: Resuelve el problema utilizando el optimizador Parity Twine

Ahora que ya has obtenido el problema de división del mercado y lo has convertido a la forma correcta, puedes hallar una solución utilizando el Optimizador de Twine y el backend de IBM® que hayas elegido.

Para ejecutar la función, elige un dispositivo de fondo adecuado; por ejemplo, ibm_phoenix.

Puedes utilizar options para tener un control adicional (opcional) sobre el envío:

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

donde es shots un número entero que especifica el número de ejecuciones del circuito, postprocessing_level determina si se aplica un posprocesamiento al resultado, transpile_onlyespecifica si el problema solo se transpilaba a un circuito (y no se resuelve), y job_tags es la etiqueta utilizada para identificar el trabajo en IBM Quantum® Platform.

Ejecuta el optimizador:

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}")

Comprueba el estado del trabajo:

# Monitor the job status
function_job.status()

Obtener resultados:

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

result

El resultado tiene la siguiente forma:

{
    '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},
        },
    }
}

donde el diccionario solution se corresponde con los qubits definidos en el problema y proporciona sus valores de espín optimizados. metadata ofrece información sobre la transpilación (número de puertas de dos qubits/profundidad, puertas utilizadas, qubits activos) y diversos tiempos de ejecución.

En el contexto del problema de la división del mercado, la cadena de bits de la solución representa un vector de asignación binario que se utiliza para dividir los mercados en dos regiones distintas. Un valor de 1 asigna ese mercado concreto a la Región A, mientras que un valor de 0 lo asigna a la Región B. En la solución óptima, la combinación equilibra el reparto, lo que significa que ambas regiones reciben exactamente la mitad de la demanda total de la empresa para cada producto.

Próximos pasos