Seleccionar un subconjunto de N ítems candidatos, cada uno con un valor y un peso, de modo que el peso total no supere una capacidad (presupuesto, horas-hombre, horas-máquina) y el valor total sea máximo. En la literatura es el Knapsack Problem — el antepasado de los problemas de selección discreta.
En pocas palabras
¿Te suena?
- Comité de inversión anual con 50-200 proyectos candidatos y un presupuesto total fijo de 50-500M TRY — el orden es intuitivo y político; existe una tabla de 'NPV/inversión' pero no se garantiza la optimalidad matemática.
- Para cada candidato hay estimación de NPV, inversión requerida, horas-hombre y horas-máquina (tres dimensiones de restricción) — pero nunca hemos construido un modelo de selección que las respete simultáneamente.
- La planificación presupuestaria usa 'ordenar y elegir de arriba' — pero los proyectos pequeños de alta relación NPV/unidad que cabrían en el último 5-10% del presupuesto suelen quedarse fuera.
- Selección de campañas de marketing digital: 30-80 propuestas, presupuesto mensual o trimestral fijo; ¿qué subconjunto maximiza alcance/conversión?
- Existen dependencias entre candidatos (el proyecto A reduce el coste de B si se elige; C y D son mutuamente excluyentes) — el knapsack clásico no las captura y requiere restricciones adicionales.
- En logística: avión cargo o contenedor con capacidad limitada — cada paquete tiene valor y peso; maximizar el valor total sin superar la capacidad.
- Gestor de fondos small-cap: universo de 200-500 acciones, tamaño de fondo fijo, cada acción con retorno esperado y lote mínimo; ¿qué subconjunto elegir?
- Contrato con proveedores: 100+ candidatos, presupuesto anual fijo; cada proveedor con pedido mínimo y máximo; ¿qué subconjunto maximiza el valor total?
Por qué importa
Cómo se resuelve
Profundidad técnica
Cómo se resuelve
Profundidad técnicaEn una frase: Ordena los candidatos por valor por unidad de peso como inicio greedy; para la respuesta exacta, ejecuta programación dinámica (capacidad bajo 10K) o MIP (sobre todo con restricciones multidimensionales o dependencias) — el mejor subconjunto sale en minutos.
En la literatura de Investigación de Operaciones (disciplina que usa matemáticas e informática para resolver decisiones de negocio) e informática este problema se estudia como Knapsack Problem (problema de la mochila) — N ítems candidatos con valor (vᵢ) y peso (wᵢ); capacidad W; ¿qué subconjunto maximiza Σvᵢ sujeto a Σwᵢ ≤ W? Un problema clásico estudiado desde los años 1950, con soluciones estándar de la industria a través de programación dinámica, branch-and-bound y solvers MIP modernos. Solución en tres etapas:
1. Modelado — elección de variante y entradas de datos. La familia es amplia; la aplicación determina la variante:
- 0/1 Knapsack (binario): cada ítem se elige o no, sin duplicados. Selección clásica de proyectos de inversión. xᵢ ∈ {0, 1}.
- Bounded Knapsack: número limitado de copias por ítem (xᵢ ∈ {0, 1, …, cᵢ}). Contratos con lotes por proveedor.
- Unbounded Knapsack: copias ilimitadas (xᵢ ≥ 0 entero). Producción con capacidad, lotes de acciones enteras.
- Multi-Dimensional Knapsack (MKP): m restricciones; cada ítem con pesos en m dimensiones (presupuesto + horas-hombre + horas-máquina + …). Σⱼwᵢⱼxᵢ ≤ Wⱼ para todo j. Mucho más difícil.
- Quadratic Knapsack (QKP): objetivo cuadrático con sinergias entre ítems.
- Multiple-Choice Multi-Dimensional Knapsack: ítems agrupados; exactamente uno por grupo.
- Subset-Sum: valor objetivo igual al peso; total tan cercano a la capacidad como sea posible.
- Knapsack con Set-Up: elegir un ítem implica un coste fijo de set-up (grupo).
Entradas: lista de candidatos N, estimaciones de valor y peso (NPV e inversión; en marketing, valor estimado de conversión y coste de campaña), capacidad W (presupuesto anual, mensual, carga del avión), restricciones multidimensionales (horas-hombre, horas-máquina, sub-presupuesto por categoría), estructura de dependencias.
2. Solución — herramientas algorítmicas.
- Greedy + relajación LP: enfoque más simple — ordenar por relación valor/peso y elegir desde arriba hasta llenar la capacidad. No garantiza optimalidad (contraejemplo clásico: capacidad 10, tres ítems (v,w) = (6,5), (5,4), (4,3) — greedy 6+5=11, óptimo 5+4+3=12); la relajación LP da la cota superior para branch-and-bound. Útil para un chequeo rápido one-shot.
- Programación Dinámica (DP): algoritmo pseudo-polinómico clásico (el tiempo depende del valor numérico de la capacidad W). Estado dp[i][w] = valor máximo con los primeros i ítems sin superar peso w. Transición dp[i][w] = max(dp[i-1][w], dp[i-1][w-wᵢ] + vᵢ). Complejidad O(N×W). N = 1000, W = 100.000 TRY-unidad = 10⁸ operaciones, segundos en hardware moderno. Realidad práctica: instancias moderadas (N ≤ 1000, W ≤ 10⁶) se resuelven al óptimo en minutos; la intuición ‘NP-hard, irresoluble’ es incorrecta.
- Branch-and-bound (búsqueda en árbol con poda de ramas no prometedoras): con poda por cota LP. Una técnica de núcleo de variables es el state-of-the-art práctico para 0/1 knapsack de millones de ítems.
- MIP (Mixed-Integer Linear Programming — optimización con algunas variables 0/1 y otras continuas): herramienta natural para MKP y casos con dependencias. Solvers MIP de código abierto o comerciales resuelven MKPs de 100-1000 ítems al óptimo (o con gap pequeño) en minutos a horas.
- FPTAS (Fully Polynomial-Time Approximation Scheme — para cualquier ε > 0, una (1-ε)-aproximación en tiempo polinómico): con ε = 0.01 garantiza el 99% del óptimo.
- Metaheurísticas (genético, tabú, simulated annealing): para MKP muy grandes o ricos en dependencias; sin garantía de optimalidad, calidad práctica.
Selección de proyectos de inversión (50-200 ítems, un presupuesto o 2-4 restricciones): MIP o DP 0/1 da el óptimo en segundos. MKP muy grande (500+ ítems, 5+ restricciones): MIP cercano al óptimo o FPTAS. En la práctica MIP basta en la mayoría de escenarios empresariales; un algoritmo de knapsack especializado rara vez es necesario.
3. Integración de campo y análisis de sensibilidad. Salida: subconjunto elegido, valor total, utilización por restricción, sensibilidad basada en relajación LP (qué proyecto entró por poco, cuál quedó por poco fuera). Informe al comité de inversión: propuesta de selección, escenarios alternativos (qué proyecto cambia si presupuesto ±10%, cuál entra si la restricción de horas-hombre se afloja), reporte explícito de dependencias y restricciones político-estratégicas. Re-planificación trimestral: se añaden nuevas propuestas, se comparan NPV real vs prognóstico, se resuelve el modelo.
Alternativas
Manual + hoja de cálculo
GratisSin licencia
Para quién: Escala pequeña, 10-30 candidatos, un presupuesto, dependencias simples
- + Sin setup
- + Fácil para intervenciones político-estratégicas del comité
- + Suficiente para una discusión rápida de top-N
- − Ordenar-y-elegir no garantiza el mejor subconjunto — 5-15% de pérdida de valor típica
- − Restricciones multidimensionales no se respetan a mano
- − Estructura de dependencias tosca (proyectos prioritarios, pares mutuamente excluyentes)
- − Sin análisis de sensibilidad (presupuesto ±10%)
Solver MIP open-source + modelo interno
Código abiertoLicencia gratis; desarrollo interno 4-12 semanas o 200K-600K TRY consultoría
Para quién: Organización con equipo de OR o analítica, presupuesto anual 50M+ TRY
- + Sin coste de licencia
- + Los modelos de selección de proyectos encajan bien con solvers open-source
- + Análisis de escenarios rápido (presupuesto, horas-hombre, capacidad)
- + Propiedad interna — modelo transparente, supuestos auditables
- − Requiere especialista en optimización e ingeniero de datos
- − El mantenimiento del modelo queda en casa
- − El ruido en la estimación de retorno persiste — la calidad del input es lo decisivo
Solver MIP comercial + modelo interno
EmpresarialLicencia anual 200K-1.5M TRY (observación del mercado TR); gran empresa 2-5M TRY
Para quién: Gran holding, presupuesto anual 500M+ TRY, restricciones multidimensionales
- + Motor de resolución óptima de nivel industrial
- + Resolución paralela de alto rendimiento
- + Interfaz de modelado madura (scripting más soporte de lenguaje de modelado)
- + Soporte industrial
- − Licencia alta
- − El desarrollo y mantenimiento interno aún exigen un especialista en optimización
- − Riesgo de dependencia del proveedor — migrar a otro solver lleva 4-12 semanas
Software empresarial de gestión de cartera de proyectos
EmpresarialLicencia anual 500K-3M TRY (observación del mercado TR), por escala
Para quién: Multi-cartera, multi-categoría, multi-geografía
- + Flujo integrado de propuesta a selección
- + Dependencias (proyectos prioritarios, pares excluyentes, descuento por sinergia) modelables en la UI
- + Re-planificación trimestral y comparación con retorno real incorporadas
- + Informes para el comité listos
- − Licencia alta más 6-12 meses de implantación
- − El módulo de resolución integrado suele ser limitado — insuficiente para carteras grandes
- − Dependencia del proveedor
- − La personalización sectorial alarga el proyecto
Recomendación
Pregunta en la reunión
- ¿Qué variantes soporta el módulo de selección de proyectos — 0/1, número limitado de lotes, presupuesto único, restricciones multidimensionales, selección por grupos, coste de set-up?
- ¿Qué método conduce el solver — solver con garantía de óptimo, programación dinámica, aproximación, búsqueda avanzada? ¿Tiempo típico de resolución para una cartera de 200-1.000 proyectos con varias restricciones?
- ¿La estructura de dependencias (proyectos prioritarios, pares excluyentes, descuento por sinergia, coste de set-up) es modelable en la UI o hay que escribir las reglas a mano?
- Análisis de sensibilidad — en escenarios de presupuesto ±10% u horas-hombre ±20%, ¿qué proyectos cambian y el reporte está automatizado?
- ¿La incertidumbre en los inputs de retorno es modelable (selección bajo incertidumbre) o solo punto estimado?
- En soluciones multi-restricción, ¿se reporta el porcentaje de desviación entre el valor obtenido y la cota teórica para que el usuario sepa si el resultado es óptimo o cercano al óptimo?
- ¿La salida produce directamente un informe para el comité de inversión — subconjunto elegido, porcentaje de presupuesto utilizado, decisiones por poco?
- Si el contrato termina, ¿en qué formato estándar se pueden exportar datos de proyectos candidatos, inputs del modelo, historial de soluciones y análisis de sensibilidad?
Detalles técnicos
Nota del editor
En lenguaje llano el problema se llama “selección de proyectos”, “asignación de presupuesto” o “priorización de inversión”. En la literatura su nombre es Knapsack Problem (problema de la mochila) — la metáfora de llenar una mochila con la carga más valiosa (Dantzig 1957). Es el antepasado de los problemas de selección discreta. No debe confundirse con el problema de optimización de cartera (#018 Markowitz media-varianza): Markowitz da pesos continuos (a cada activo le toca una fracción real entre 0% y 100% de la cartera) y modela el riesgo vía varianza y correlación; el knapsack es una decisión discreta de elegir o no (xᵢ ∈ {0, 1}) y maximiza valor sujeto a presupuesto y NPV. Detrás de la mayoría de los problemas clásicos de decisión hay un knapsack — selección de proyectos de inversión, selección de campañas, carga de carga aérea, selección de subconjuntos de proveedores. Cutting stock (#005, corte geométrico multidimensional) y 3D bin packing (#015, empaquetado volumétrico) son parientes cercanos pero problemas distintos: el knapsack maximiza valor, el cutting stock minimiza el número de rollos, el 3D bin packing acomoda paquetes en cajas. La planificación de surtido (#017) es una variante especializada del knapsack — acoplada con un modelo de demanda por producto.
Punto más pasado por alto en el sector: la diferencia entre DP pseudo-polinómico y la etiqueta de clase de complejidad. El knapsack es NP-hard — no se conoce un algoritmo polinómico en la longitud en bits de la entrada. El práctico lo lee como ‘irresoluble’ — incorrecto. La DP de Bellman corre en O(N×W) — W es la capacidad. En presupuesto de capital W = 50M TRY, pero se modela en miles de TRY (W = 50.000); con N = 200 proyectos son 10⁷ operaciones, segundos en hardware moderno. Pseudo-polinómico: el tiempo es polinómico en el valor de W (y exponencial en su longitud en bits). Consecuencia: cuando W es moderado (miles, decenas de miles), la DP resuelve instancias de millones de ítems al óptimo en minutos. En el comité no se debe saltar a ’no podemos conocer el óptimo matemático, decidamos por intuición’ — las herramientas prácticas (MIP, DP) están al alcance de todos.
Segundo punto pasado por alto: la incertidumbre en los inputs de NPV/valor. La matemática del knapsack supone inputs deterministas. En realidad las estimaciones de NPV se basan en proyecciones a 5 años con ±20-40% de desviación; en proyectos de nueva tecnología y transformación digital la incertidumbre es aún mayor. Un solver clásico de knapsack absorbe esa incertidumbre y devuelve un único subconjunto ‘óptimo’; bajo NPV ±20% el subconjunto puede cambiar por completo. Soluciones: knapsack estocástico (Bertsimas y Sim 2003 optimización robusta, óptimo worst-case en un conjunto de incertidumbre del NPV), chance-constrained knapsack (probabilidad de superar presupuesto a lo sumo 5%) o un simple análisis de sensibilidad (proyectos estables a través de escenarios NPV ±20%). Tercer punto pasado por alto: estructura de dependencias. El knapsack clásico supone que los ítems son independientes — los valores se suman sin más. En la práctica hay sinergias (A + B juntos ganan valor extra), exclusión mutua (A xor B), precedencia (A → B), descuento de capacidad (A abarata B). Se modelan como restricciones MIP; hay que salir de la interfaz estándar del knapsack y pasar a un MIP más rico.
Paso a paso — para la PYME
Etapa 1 — Medir primero, planificar después. Los últimos 3-5 años de proyectos candidatos (aceptados más rechazados): estimación de NPV propuesta, NPV realizado (para los aceptados), monto de inversión, horas-hombre, horas-máquina. Estadística de desviación del NPV por categoría (ampliación, modernización, digital, TI) y por tamaño, ratio prognóstico/real, banda ±%. Documentar en qué momento de la planificación anual se cierran el presupuesto y demás restricciones (horas-hombre, horas-máquina, sub-presupuesto por categoría).
Etapa 2 — Aflorar el capital de conocimiento. Estructura típica de dependencias entre candidatos (cadenas de precedencia, pares excluyentes, sinergias de descuento). Bandas de fiabilidad de NPV: proyecto estándar pequeño ±10%, transformación digital ±30-40%, I+D ±50%. Requisitos políticos de sub-presupuesto por categoría (balance regional, diversificación sectorial).
Etapa 3 — Piloto. 6-10 semanas. En un ciclo anual del comité, correr en paralelo a la selección intuitiva existente un MIP open-source. Reportar ambas salidas lado a lado para el mismo conjunto de candidatos; explicar las diferencias (qué proyecto eligió greedy, cuál MIP y por qué). La decisión sigue siendo del comité; el MIP es una recomendación. Criterio de éxito fijado de antemano: el NPV del portafolio recomendado por MIP es al menos 5% superior al de greedy.
Etapa 4 — Despliegue. 6-12 meses hasta el proceso completo del comité con MIP. Re-planificación trimestral (nuevas propuestas se añaden, proyectos cancelados se retiran). Análisis anual de sensibilidad (escenarios presupuesto ±10%). Knapsack estocástico o robusto sólo después de asentar la base de incertidumbre del NPV. Comité trimestral: recomendación MIP vs portafolio aprobado, decisiones por poco, calibración prognóstico/real del NPV.
Riesgos — qué puede salir mal
- Error de estimación del NPV/retorno. La solución es matemáticamente óptima a los NPV dados; si NPV ±20-40%, el subconjunto óptimo puede cambiar. Es obligatoria una extensión robusta o estocástica o, como mínimo, un análisis de sensibilidad (proyectos estables a NPV ±20%). Para calibrar, seguir NPV real / NPV prognóstico por categoría en el tiempo.
- Supuesto de independencia de proyectos. El knapsack clásico suma valores de los ítems; en la práctica hay sinergia (A + B juntos ganan valor extra), exclusión mutua (A xor B), precedencia (A → B), descuento de capacidad (A abarata B). Hay que pasar a restricciones MIP, abandonando la interfaz estándar del knapsack.
- No se considera la dispersión del riesgo. El knapsack puro maximiza valor total; no modela riesgo de cartera (varianza, covarianza, riesgo de cola). Elegir cinco proyectos en el mismo sector puede dar alto NPV pero hacer la cartera frágil ante un shock sectorial. Añadir restricciones de sub-presupuesto por sector / geografía / categoría o acoplar la selección con una medida de riesgo tipo CVaR (#063).
- Lock-in con un solo proveedor de software de planificación de inversiones. Sin cláusula contractual de exportación anual de datos de candidatos, inputs del modelo, historial de soluciones y análisis de sensibilidad en formato estándar, cambiar de proveedor implica perder la memoria institucional. MIP open-source + modelo interno otorga independencia a escala media.
Una mirada técnica a la solución
| Enfoque | Escala típica | Tiempo de resolución | ¿Garantía de optimalidad? |
|---|---|---|---|
| Greedy (ordenar por NPV/inversión) | Cualquiera | instantáneo | No (85-95% del óptimo típico) |
| Cota superior LP | Cualquiera | instantáneo | No (cota superior) |
| Programación Dinámica (Bellman 1957) | Moderada (N≤1000, W≤10⁶) | segundos-minutos | Sí |
| Branch-and-Bound (Martello-Toth 1990) | Mediana-grande 0/1 KP | minutos-horas | Sí |
| Expanding Core de Pisinger (1997) | Muy grande 0/1 KP | minutos | Sí |
| MIP (solver general) | General (MKP, QKP, set-up) | segundos-horas | Sí (dentro de gap) |
| FPTAS (Ibarra-Kim 1975) | Muy grande, ε-aprox aceptable | minutos | (1-ε) del óptimo |
| Metaheurística (genético, tabú, SA) | MKP muy grande, denso en dependencias | minutos-horas | No, buena calidad práctica |
Comparativa de variantes del knapsack:
- 0/1 Knapsack: cada ítem elegido o no. Presupuesto de capital clásico.
- Bounded Knapsack: copias limitadas. Lotes con proveedores.
- Unbounded Knapsack: copias ilimitadas. Producción con capacidad, lotes enteros de acciones.
- Multi-Dimensional Knapsack (MKP): m restricciones — presupuesto + trabajo + máquina + categoría.
- Quadratic Knapsack (QKP): sinergia o interacción por pares.
- Multiple-Choice MKP: ítems agrupados, exactamente uno por grupo.
- Subset-Sum: objetivo = peso; total tan cercano a la capacidad como sea posible.
- Knapsack con Set-Up: coste fijo de set-up por grupo.
Elección de la función objetivo:
- Objetivo 1 — Valor total máximo (NPV, valor de conversión): clásico.
- Objetivo 2 — Máximo uso del presupuesto (cercano a subset-sum): disciplina de consumo total.
- Objetivo 3 — Valor worst-case máximo (sobre conjunto de incertidumbre del NPV): optimización robusta Bertsimas-Sim.
- Objetivo 4 — Valor esperado menos penalización por varianza (estocástico): knapsack media-varianza.
Modelado de dependencias (en MIP):
- Precedencia (A → B): xB ≤ xA.
- Exclusión mutua (A xor B): xA + xB ≤ 1.
- Descuento por sinergia: decisión adicional yA·B.
- Coste de set-up: decisión adicional yk por grupo.
- Sub-presupuesto por categoría: Σᵢ∈Cwᵢxᵢ ≤ Wc por categoría C.
Fuentes académicas
Listadas en el frontmatter bajo sources.
Fuentes
- Dantzig, G. B. (1957). Discrete-variable extremum problems. Operations Research, 5(2), 266-288. Fuente fundacional de la formulación LP/IP del knapsack.
- Bellman, R. (1957). Dynamic Programming. Princeton University Press. Libro fundacional de la programación dinámica; el knapsack es el ejemplo canónico.
- Martello, S. y Toth, P. (1990). Knapsack Problems: Algorithms and Computer Implementations. Wiley. Libro clásico; algoritmos branch-and-bound y comparaciones experimentales.
- Kellerer, H., Pferschy, U. y Pisinger, D. (2004). Knapsack Problems. Springer. Referencia moderna integral; todas las variantes, FPTAS, MKP, QKP.
- Pisinger, D. (1997). A minimal algorithm for the 0-1 knapsack problem. Operations Research, 45(5), 758-767. Algoritmo expanding-core, state-of-the-art práctico.
- Ibarra, O. H. y Kim, C. E. (1975). Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM, 22(4), 463-468. Fuente fundacional del FPTAS del knapsack.
- Centro de Tesis YÖK — palabras clave ‘sırt çantası’, ‘knapsack’ o ‘proje seçimi’ — 25+ tesis de la academia turca. tez.yok.gov.tr
Glosario
- Knapsack Problem
- El problema fundacional de optimización discreta de seleccionar un subconjunto de N ítems, cada uno con un valor y un peso, para maximizar el valor total bajo una restricción de capacidad sobre el peso total.
- Dynamic Programming
- La técnica de OR / informática para resolver problemas de decisión multietapa mediante descomposición recursiva en subproblemas superpuestos almacenando resultados intermedios; introducida por Bellman (1957).
- MIP
- Modelo de optimización donde parte de las variables de decisión deben ser números enteros (p. ej. número de camiones o de turnos).
Problemas relacionados
¿Qué porcentaje de mi dinero va a qué inversión?
Una de las preguntas básicas de una pyme o inversor individual: hay un capital y varias opciones de inversión (acciones, bonos, divisas, materias primas, depósitos, inmuebles, reinversión en el negocio), cada una con rendimiento esperado y riesgo distintos, con correlaciones entre sí (cuando una baja otra sube, etc.). ¿Qué porcentaje del capital va a cada una? El nombre matemático es Portfolio Optimization Problem. En 1952 Harry Markowitz formalizó el mean-variance — fundamento, ganador del Nobel, de la teoría moderna de carteras. Maximizar rendimiento esperado minimizando varianza es un problema de programación cuadrática.
Cuánto efectivo en qué cajero, con qué frecuencia reponer — equilibrio entre cajero vacío e inmovilización elevada
Si es un banco comercial o de participación de tamaño medio que opera 50-500 cajeros, cada mañana debe responder a tres preguntas: cuánto efectivo poner en cada cajero, con qué frecuencia reponer cada uno y qué ruta debe seguir el vehículo blindado. Los dos extremos son caros: demasiado efectivo dentro del cajero infla el coste de oportunidad del 5-15 % anual de interés más la prima de seguro; muy poco efectivo vacía la máquina, el cliente no puede retirar, llegan quejas y daño de marca. Como un centro comercial, una parada de autobús, un campus y un distrito de oficinas tienen patrones de retirada muy distintos, una regla intuitiva del tipo 'la misma cantidad para todos' perjudica los dos extremos a la vez. Esta página está dirigida a equipos de operaciones bancarias que quieren tomar las tres decisiones juntas y basadas en datos.
Múltiples entradas + múltiples salidas — ¿cómo mido la eficiencia relativa de mis sucursales o unidades?
Esta página es para usted si dirige un banco con 100-500 sucursales, una cadena hospitalaria multisede con 200-1.500 camas, una dirección de educación con cientos de escuelas o un organismo público que compara provincias. La pregunta clave: ¿qué sucursal/hospital/escuela es eficiente y cuál no — y para las que no lo son, qué unidad 'peer' deben tomar como referencia y cuánto deben mejorar? Cada unidad consume varias entradas a la vez (personal, superficie, presupuesto) y produce varias salidas a la vez (ingresos, clientes/pacientes/alumnos, calidad); un indicador único como 'ingresos por empleado' no captura esa realidad y puede marcar como débil a una unidad eficiente o al revés. Bien aplicado — porque el peer benchmark da una referencia concreta de mejora — la aceptación de los planes de mejora para unidades débiles sube un 40-70%, lo que equivale a 10-50 millones TRY al año de margen operativo en una red de sucursales mediana.