MS-CFLP-CI-SR Benchmark

Repositorio minimalista para generar perfiles de instancias del problema MS-CFLP-CI-SR: Multi-Source Capacitated Facility Location Problem with Customer Incompatibilities and Service Radius Constraints.

El objetivo es partir de instancias base en formato MiniZinc .dzn y construir, para cada una, tres variantes con restricciones de radio de servicio: low, medium y high. El archivo ms-cflp-ci-base-instances/toy.dzn se incluye como ejemplo pequeño y legible para entender el flujo completo.

Problema

En MS-CFLP-CI-SR se conserva la estructura de una instancia MS-CFLP-CI: clientes, facilities, demandas, capacidades, costes de apertura, matriz de costes de transporte e incompatibilidades entre pares de clientes.

La extensión -SR añade un umbral global de servicio Cmax. Un cliente i solo puede ser servido por una facility j si:

c_ij <= Cmax

Esto induce un grafo bipartito de asignaciones admisibles:

A = {(i, j) : c_ij <= Cmax}

La densidad del grafo se resume como:

rho = |A| / (num_customers * num_facilities)

Valores bajos de rho representan restricciones de radio más fuertes; valores altos representan redes de servicio más flexibles.

Generación de perfiles

Para evitar elegir radios absolutos que no sean comparables entre instancias, los perfiles se obtienen a partir de percentiles de la matriz de costes de transporte.

Para cada .dzn:

1. Se lee la matriz de costes c_ij.
2. Se calculan los percentiles empíricos q25, q50 y q75.
3. Se construyen tres perfiles:
   • low: Cmax = q25
   • medium: Cmax = q50
   • high: Cmax = q75
4. Para cada perfil se construye A = {(i, j) : c_ij <= Cmax}.
5. Si el perfil falla condiciones deterministas básicas de factibilidad, se relaja Cmax al siguiente coste disponible y se recomputa A.
6. Se guarda un JSON radius_profile.

La comprobación de factibilidad incluida es ligera: detecta clientes aislados, capacidad total insuficiente y clientes cuya demanda supera la capacidad alcanzable por sus facilities admisibles. La factibilidad exacta, incluyendo el efecto completo de las incompatibilidades, debe comprobarse con un solver.

Ejemplo con toy.dzn

toy.dzn contiene 4 warehouses, 10 stores, 3 pares de clientes incompatibles y una matriz SupplyCost de tamaño 10 x 4. Por tanto, antes de aplicar el radio de servicio hay:

num_customers * num_facilities = 10 * 4 = 40

posibles asignaciones cliente-facility.

Contenido de la instancia:

Warehouses = 4;
Stores = 10;

Capacity = [100, 40, 60, 60];
FixedCost = [860, 350, 440, 580];
Goods = [12, 17, 5, 13, 20, 20, 17, 19, 11, 20];
SupplyCost = [|27, 66, 44, 55
              |53, 89, 68, 46
              |17, 40, 18, 61
              |20, 68, 44, 78
              |42, 89, 65, 78
              |57, 55, 49, 31
              |89, 101, 90, 16
              |37, 31, 23, 55
              |76, 60, 63, 44
              |82, 107, 91, 31|];

Incompatibilities = 3;
IncompatiblePairs = [| 1, 10 | 2, 7 | 8, 9 |];

La matriz SupplyCost es la que determina los radios de servicio:

Al generar los perfiles, el script calcula percentiles sobre los 40 costes de SupplyCost. En el perfil low, el percentil 25 produce:

cmax_original = 39.25

Ese umbral inicial es demasiado restrictivo para las condiciones básicas de factibilidad. Con Cmax = 39.25, los stores 2, 5 y 9 quedan sin ninguna facility admisible, porque todos sus costes superan el umbral:

store 2: [53, 89, 68, 46]
store 5: [42, 89, 65, 78]
store 9: [76, 60, 63, 44]

Como N(i) queda vacío para esos clientes, el perfil low teórico sería inviable. El generador relaja Cmax al siguiente coste disponible hasta obtener:

cmax_final = 46.0
num_feasible_arcs = 16
rho = 16 / 40 = 0.4

La densidad rho = 0.4 significa que sobreviven 16 de las 40 asignaciones cliente-facility posibles. El perfil medium alcanza rho = 0.525 y el perfil high alcanza rho = 0.75, por lo que sus grafos de asignación son progresivamente menos restrictivos.

El perfil resultante queda guardado en:

ms-cflp-ci-sr-instances/toy/low.json

Estructura

• ms-cflp-ci-base-instances/: instancias base .dzn.
• ms-cflp-ci-sr-instances/: perfiles -SR generados como JSON.
• scripts/generate_radius_profiles.py: genera perfiles low, medium y high desde los .dzn.
• examples/load_profile.py: ejemplo mínimo para cargar un perfil y resolver la ruta al .dzn.
• requirements.txt: dependencias del proyecto.

Preparar el entorno

El proyecto usa solo la librería estándar de Python. Si se trabaja con entorno virtual:

source .venv/bin/activate
pip install -r requirements.txt

Generar las instancias SR

Coloca los .dzn base en:

ms-cflp-ci-base-instances/

Este repositorio incluye ms-cflp-ci-base-instances/toy.dzn como instancia pequeña de ejemplo y ms-cflp-ci-base-instances/wlp01.dzn como instancia real de prueba. Para generar los perfiles:

python scripts/generate_radius_profiles.py

Salida esperada:

ms-cflp-ci-sr-instances/
  toy/
    low.json
    medium.json
    high.json
  wlp01/
    low.json
    medium.json
    high.json

También se pueden indicar carpetas explícitamente:

python scripts/generate_radius_profiles.py \
  --base-dir ms-cflp-ci-base-instances \
  --output-dir ms-cflp-ci-sr-instances

Formato de un perfil

Cada archivo JSON describe una variante -SR de una instancia base. Contiene:

• profile_id: identificador del perfil, por ejemplo wlp01_low.
• base_instance_id: instancia .dzn de origen.
• profile_name: low, medium o high.
• source: ruta, checksum y dialecto del .dzn.
• generation_policy: percentil usado y modo de relajación.
• cmax_original: valor inicial obtenido por percentil.
• cmax_final: valor final tras posible relajación.
• density_ratio: valor rho.
• num_feasible_arcs: cardinalidad de A.
• feasibility_diagnostics: diagnóstico ligero de factibilidad.
• cost_distribution: resumen de la distribución de costes.
• variable_map: nombres de variables detectados en el .dzn.

Cargar un perfil

Primero genera los perfiles:

python scripts/generate_radius_profiles.py

Después ejecuta el ejemplo:

python examples/load_profile.py

O carga un perfil concreto, por ejemplo el perfil low de toy.dzn:

python examples/load_profile.py ms-cflp-ci-sr-instances/toy/low.json

El ejemplo lee el JSON, resuelve source.path contra la raíz del proyecto, comprueba que el .dzn enlazado existe y carga sus datos principales: dimensiones, capacidades, demandas, tamaño de la matriz de costes e incompatibilidades.