Optimizaciones lineales en análisis de productos | de Mariya Mansurova | diciembre de 2024

Puede resultar sorprendente, pero en este artículo me gustaría hablar sobre el problema de la mochila, el clásico problema de optimización que se ha estudiado durante más de un siglo. De acuerdo a Wikipediael problema se define de la siguiente manera:

Dado un conjunto de artículos, cada uno con un peso y un valor, determine qué artículos incluir en la colección para que el peso total sea menor o igual a un límite dado y el valor total sea lo más grande posible.

Si bien es posible que los analistas de productos no hagan las maletas físicamente, el modelo matemático subyacente es muy relevante para muchas de nuestras tareas. Existen numerosas aplicaciones del mundo real del problema de la mochila en el análisis de productos. A continuación se muestran algunos ejemplos:

• Campañas de marketing: El equipo de marketing tiene un presupuesto y una capacidad limitados para ejecutar campañas en diferentes canales y regiones. Su objetivo es maximizar un KPI, como el número de nuevos usuarios o los ingresos, respetando al mismo tiempo las restricciones existentes.
• Optimización del espacio comercial: Un minorista con espacio físico limitado en sus tiendas busca optimizar la colocación de productos para maximizar los ingresos.
• Priorización de lanzamiento de productos: Al lanzar un nuevo producto, la capacidad del equipo de operaciones puede ser limitada, lo que requiere priorizar mercados específicos.

Estas y otras tareas similares son bastante comunes y muchos analistas las enfrentan con regularidad. Entonces, en este artículo, exploraré diferentes enfoques para resolverlo, desde técnicas simples e ingenuas hasta métodos más avanzados, como la programación lineal.

Otra razón por la que elegí este tema es que la programación lineal es una de las herramientas más poderosas y populares en el análisis prescriptivo, un tipo de análisis que se enfoca en brindar a las partes interesadas opciones viables para tomar decisiones informadas. Como tal, creo que es una habilidad esencial que cualquier analista debe tener en su caja de herramientas.

Profundicemos directamente en el caso que exploraremos. Imaginemos que somos parte de un equipo de marketing que planifica actividades para el próximo mes. Nuestro objetivo es maximizar los indicadores clave de rendimiento (KPI), como la cantidad de usuarios adquiridos y los ingresos, mientras operamos dentro de un presupuesto de marketing limitado.

Hemos estimado los resultados esperados de diversas actividades de marketing en diferentes países y canales. Aquí están los datos que tenemos:

• country — el mercado donde podemos realizar algunas actividades promocionales;
• channel — el método de adquisición, como redes sociales o campañas de influencers;
• users — el número esperado de usuarios adquiridos dentro de un mes de la campaña de promoción;
• cs_contacts — los contactos incrementales de Atención al Cliente generados por los nuevos usuarios;
• marketing_spending — la inversión necesaria para la actividad;
• revenue – el LTV del primer año generado a partir de clientes adquiridos.

Tenga en cuenta que el conjunto de datos es sintético y se genera aleatoriamente, así que no intente inferir de él ninguna información relacionada con el mercado.

Primero, calculé las estadísticas de alto nivel para tener una vista de los números.

Determinemos el conjunto óptimo de actividades de marketing que maximice los ingresos sin exceder el presupuesto de marketing de 30 millones de dólares.

A primera vista, el problema puede parecer sencillo: podríamos calcular todas las combinaciones posibles de actividades de marketing y seleccionar la óptima. Sin embargo, podría ser una tarea desafiante.

Con 62 segmentos, hay 2⁶² combinaciones posibles, ya que cada segmento puede incluirse o excluirse. Esto da como resultado aproximadamente 4,6*10¹⁸ combinaciones, un número astronómico.

Para comprender mejor la viabilidad computacional, consideremos un subconjunto más pequeño de 15 segmentos y estimemos el tiempo necesario para una iteración.

import itertools
import pandas as pd
import tqdm
# reading data
df = pd.read_csv('marketing_campaign_estimations.csv', sep = '\t')
df['segment'] = df.country + ' - ' + df.channel
# calculating combinations
combinations = []
segments = list(df.segment.values)[:15]
print('number of segments: ', len(segments))
for num_items in range(len(segments) + 1):
combinations.extend(
itertools.combinations(segments, num_items)
)
print('number of combinations: ', len(combinations))
tmp = []
for selected in tqdm.tqdm(combinations):
tmp_df = df[df.segment.isin(selected)]
tmp.append(
{
'selected_segments': ', '.join(selected),
'users': tmp_df.users.sum(),
'cs_contacts': tmp_df.cs_contacts.sum(),
'marketing_spending': tmp_df.marketing_spending.sum(),
'revenue': tmp_df.revenue.sum()
}
)
# number of segments:  15
# number of combinations:  32768

Nos tomó aproximadamente 4 segundos procesar 15 segmentos, lo que nos permitió manejar alrededor de 7000 iteraciones por segundo. Usando esta estimación, calculemos el tiempo de ejecución para el conjunto completo de 62 segmentos.

2**62 / 7000 / 3600 / 24 / 365
# 20 890 800.6

Utilizando la fuerza bruta, se necesitarían alrededor de 20,9 millones de años para obtener la respuesta a nuestra pregunta; claramente no es una opción viable.

El tiempo de ejecución está enteramente determinado por el número de segmentos. Quitar solo un segmento puede reducir el tiempo a la mitad. Con esto en mente, exploremos posibles formas de fusionar segmentos.

Como es habitual, hay más segmentos pequeños que grandes, por lo que fusionarlos es un paso lógico. Sin embargo, es importante tener en cuenta que este enfoque puede reducir la precisión, ya que se agregan varios segmentos en uno solo. A pesar de esto, aún podría generar una solución que sea “suficientemente buena”.

Para simplificar, fusionemos todos los segmentos que contribuyen con menos del 0,1% de los ingresos.

df['share_of_revenue'] = df.revenue/df.revenue.sum() * 100
df['segment_group'] = list(map(
lambda x, y: x if y >= 0.1 else 'other',
df.segment,
df.share_of_revenue
))
print(df[df.segment_group == 'other'].share_of_revenue.sum())
# 0.53
print(df.segment_group.nunique())
# 52

Con este enfoque, fusionaremos diez segmentos en uno, lo que representa el 0,53% de los ingresos totales (el margen de error potencial). Con 52 segmentos restantes, podemos obtener la solución en sólo 20,4K años. Si bien esto es una mejora significativa, todavía no es suficiente.

Puede considerar otras heurísticas adaptadas a su tarea específica. Por ejemplo, si su restricción es una proporción (p. ej., tasa de contacto = contactos/usuarios de CS ≤ 5%), podría agrupar todos los segmentos donde la restricción sea cierta, ya que la solución óptima los incluirá a todos. En nuestro caso, sin embargo, no veo ninguna estrategia adicional para reducir el número de segmentos, por lo que la fuerza bruta parece poco práctica.

Dicho esto, si el número de combinaciones es relativamente pequeño y la fuerza bruta se puede ejecutar en un tiempo razonable, puede ser un enfoque ideal. Es sencillo de desarrollar y proporciona resultados precisos.

Dado que la fuerza bruta no es factible para calcular todas las combinaciones, consideremos un algoritmo más simple para abordar este problema.

Un posible enfoque es centrarse en los segmentos de mayor rendimiento. Podemos evaluar el desempeño del segmento calculando los ingresos por dólar gastado, luego ordenar todas las actividades según esta proporción y seleccionar las de mejor desempeño que se ajusten al presupuesto de marketing. Implementémoslo.

df['revenue_per_spend'] = df.revenue / df.marketing_spending 
df = df.sort_values('revenue_per_spend', ascending = False)
df['spend_cumulative'] = df.marketing_spending.cumsum()
selected_df = df[df.spend_cumulative <= 30000000]
print(selected_df.shape[0])
# 48 
print(selected_df.revenue.sum()/1000000)
# 107.92

Con este enfoque, seleccionamos 48 actividades y obtuvimos 107,92 millones de dólares en ingresos.

Desafortunadamente, aunque la lógica parece razonable, no es la solución óptima para maximizar los ingresos. Veamos un ejemplo sencillo con sólo tres actividades de marketing.

Utilizando el enfoque de los principales mercados, seleccionaríamos Francia y lograríamos 68 millones de dólares en ingresos. Sin embargo, si elegimos otros dos mercados, podríamos lograr resultados significativamente mejores: 97,5 millones de dólares. El punto clave es que nuestro algoritmo optimiza no solo para obtener los máximos ingresos sino también para minimizar la cantidad de segmentos seleccionados. Por lo tanto, este enfoque no producirá los mejores resultados, especialmente considerando su incapacidad para tener en cuenta múltiples restricciones.

Dado que todos los enfoques simples han fracasado, debemos volver a los fundamentos y explorar la teoría detrás de este problema. Afortunadamente, el problema de la mochila se ha estudiado durante muchos años y podemos aplicar técnicas de optimización para resolverlo en segundos en lugar de años.

El problema que intentamos resolver es un ejemplo de programación entera, que en realidad es un subdominio de la programación lineal.

Discutiremos esto en breve, pero primero, alineemos los conceptos clave del proceso de optimización. Cada problema de optimización consta de:

• Variables de decisión: Parámetros que se pueden ajustar en el modelo y que normalmente representan las palancas o decisiones que queremos tomar.
• Función objetivo: La variable objetivo que pretendemos maximizar o minimizar. No hace falta decir que debe depender de las variables de decisión.
• Restricciones: Condiciones impuestas a las variables de decisión que definen sus posibles valores. Por ejemplo, garantizar que el equipo no pueda trabajar un número negativo de horas.

Con estos conceptos básicos en mente, podemos definir la Programación Lineal como un escenario donde se cumplen las siguientes condiciones:

• La función objetivo es lineal.
• Todas las restricciones son lineales.
• Las variables de decisión tienen un valor real.

La programación entera es muy similar a la programación lineal, con una diferencia clave: algunas o todas las variables de decisión deben ser números enteros. Si bien esto puede parecer un cambio menor, afecta significativamente el enfoque de la solución, ya que requiere métodos más complejos que los utilizados en la programación lineal. Una técnica común es ramificarse y encuadernarse. No profundizaremos en la teoría aquí, pero siempre podrás encontrar explicaciones más detalladas en línea.

Para la optimización lineal, prefiero el paquete Python ampliamente utilizado. Pulpa. Sin embargo, hay otras opciones disponibles, como MIP de Python o Piomo. Instalemos PuLP mediante pip.

! pip install pulp

Ahora es el momento de definir nuestra tarea como un problema de optimización matemática. Para ello existen los siguientes pasos:

• Definir el conjunto de variables de decisión. (palancas que podemos ajustar).
• Alinear con la función objetivo (una variable que optimizaremos).
• Formular restricciones (las condiciones que deben cumplirse durante las optimizaciones).

Repasemos los pasos uno por uno. Pero primero, necesitamos crear el objeto del problema y establecer el objetivo: la maximización en nuestro caso.

from pulp import *
problem = LpProblem("Marketing_campaign", LpMaximize)

El siguiente paso es definir las variables de decisión, parámetros que podemos cambiar durante la optimización. Nuestra principal decisión es ejecutar una campaña de marketing o no. Entonces, podemos modelarlo como un conjunto de variables binarias (0 o 1) para cada segmento. Hagámoslo con la biblioteca PuLP.

segments = range(df.shape[0])  
selected = LpVariable.dicts("Selected", segments, cat="Binary")

Después de eso, es hora de alinearse con la función objetivo. Como ya hemos comentado, queremos maximizar los ingresos. Los ingresos totales serán la suma de los ingresos de todos los segmentos seleccionados (donde decision_variable = 1 ). Por tanto, podemos definir esta fórmula como la suma de los ingresos esperados para cada segmento multiplicada por la variable binaria de decisión.

problem += lpSum(
selected[i] * list(df['revenue'].values)[i] 
for i in segments
)

El último paso es agregar restricciones. Comencemos con una restricción simple: nuestro gasto en marketing debe ser inferior a 30 millones de dólares.

problem += lpSum(
selected[i] * df['marketing_spending'].values[i]
for i in segments
) <= 30 * 10**6

Pista: puedes imprimir problem para verificar nuevamente la función objetivo y las restricciones.

Ahora que hemos definido todo, podemos ejecutar la optimización y analizar los resultados.

problem.solve()

Se tarda menos de un segundo en ejecutar la optimización, una mejora significativa en comparación con los miles de años que requeriría la fuerza bruta.

Result - Optimal solution found
Objective value:                110162662.21000001
Enumerated nodes:               4
Total iterations:               76
Time (CPU seconds):             0.02
Time (Wallclock seconds):       0.02

Guardemos los resultados de la ejecución del modelo (las variables de decisión que indican si cada segmento fue seleccionado o no) en nuestro marco de datos.

df['selected'] = list(map(lambda x: x.value(), selected.values()))
print(df[df.selected == 1].revenue.sum()/10**6)
# 110.16

Funciona como magia, permitiéndote obtener la solución rápidamente. Además, tenga en cuenta que logramos mayores ingresos en comparación con nuestro enfoque ingenuo: 110,16 millones de dólares frente a 107,92 millones de dólares.

Hemos probado la programación entera con un ejemplo simple que presenta solo una restricción, pero podemos extenderla más. Por ejemplo, podemos agregar restricciones adicionales para nuestros contactos de CS para garantizar que nuestro equipo de Operaciones pueda manejar la demanda de manera saludable:

• El número de contactos CS adicionales ≤ 5K
• Tasa de contacto (contactos/usuarios de CS) ≤ 0,042

# define the problem
problem_v2 = LpProblem("Marketing_campaign_v2", LpMaximize)
# decision variables
segments = range(df.shape[0]) 
selected = LpVariable.dicts("Selected", segments, cat="Binary")
# objective function
problem_v2 += lpSum(
selected[i] * list(df['revenue'].values)[i] 
for i in segments
)
# Constraints
problem_v2 += lpSum(
selected[i] * df['marketing_spending'].values[i]
for i in segments
) <= 30 * 10**6
problem_v2 += lpSum(
selected[i] * df['cs_contacts'].values[i]
for i in segments
) <= 5000
problem_v2 += lpSum(
selected[i] * df['cs_contacts'].values[i]
for i in segments
) <= 0.042 * lpSum(
selected[i] * df['users'].values[i]
for i in segments
)
# run the optimisation
problem_v2.solve()

El código es sencillo y la única parte complicada es la transformación de la restricción de proporción a una forma lineal más simple.

Otra posible restricción que podría considerar es limitar la cantidad de opciones seleccionadas, por ejemplo, a 10. Esta restricción podría ser muy útil en el análisis prescriptivo, por ejemplo, cuando necesita seleccionar las N áreas de enfoque más impactantes.

# define the problem
problem_v3 = LpProblem("Marketing_campaign_v2", LpMaximize)
# decision variables
segments = range(df.shape[0]) 
selected = LpVariable.dicts("Selected", segments, cat="Binary")
# objective function
problem_v3 += lpSum(
selected[i] * list(df['revenue'].values)[i] 
for i in segments
)
# constraints
problem_v3 += lpSum(
selected[i] * df['marketing_spending'].values[i]
for i in segments
) <= 30 * 10**6
problem_v3 += lpSum(
selected[i] for i in segments
) <= 10
# run the optimisation
problem_v3.solve()
df['selected'] = list(map(lambda x: x.value(), selected.values()))
print(df.selected.sum())
# 10

Otra posible opción para modificar nuestro problema es cambiar la función objetivo. Hemos estado optimizando los ingresos, pero imagina que queremos maximizar tanto los ingresos como los nuevos usuarios al mismo tiempo. Para eso, podemos cambiar ligeramente nuestra función objetivo.

Consideremos el mejor enfoque. Podríamos calcular la suma de los ingresos y los nuevos usuarios y aspirar a maximizarla. Sin embargo, dado que los ingresos son, en promedio, 1000 veces mayores, los resultados podrían estar sesgados hacia la maximización de los ingresos. Para que las métricas sean más comparables, podemos normalizar tanto los ingresos como los usuarios en función de sus sumas totales. Entonces, podemos definir la función objetivo como una suma ponderada de estos ratios. Usaría pesos iguales (0,5) para ambas métricas, pero puedes ajustar los pesos para darle más valor a una de ellas.

# define the problem
problem_v4 = LpProblem("Marketing_campaign_v2", LpMaximize)
# decision variables
segments = range(df.shape[0]) 
selected = LpVariable.dicts("Selected", segments, cat="Binary")
# objective Function
problem_v4 += (
0.5 * lpSum(
selected[i] * df['revenue'].values[i] / df['revenue'].sum()
for i in segments
)
+ 0.5 * lpSum(
selected[i] * df['users'].values[i] / df['users'].sum()
for i in segments
)
)
# constraints
problem_v4 += lpSum(
selected[i] * df['marketing_spending'].values[i]
for i in segments
) <= 30 * 10**6
# run the optimisation
problem_v4.solve()
df['selected'] = list(map(lambda x: x.value(), selected.values()))

Obtuvimos el valor óptimo de la función objetivo de 0,6131, con ingresos de 104,36 millones de dólares y 136,37 mil nuevos usuarios.

¡Eso es todo! Hemos aprendido a utilizar la programación entera para resolver varios problemas de optimización.

Puedes encontrar el código completo en GitHub.

En este artículo, exploramos diferentes métodos para resolver el problema de la mochila y sus análogos en el análisis de productos.

• Comenzamos con un enfoque de fuerza bruta, pero rápidamente nos dimos cuenta de que llevaría una cantidad de tiempo excesiva.
• A continuación, intentamos usar el sentido común seleccionando ingenuamente los segmentos con mejor rendimiento, pero este enfoque arrojó resultados incorrectos.
• Finalmente, recurrimos a la programación entera y aprendimos cómo traducir las tareas de nuestro producto en modelos de optimización y resolverlas de manera efectiva.

Con esto, espero que haya obtenido otra valiosa herramienta analítica para su conjunto de herramientas.

Muchas gracias por leer este artículo. Espero que este artículo haya sido revelador para ti. Si tiene alguna pregunta o comentario de seguimiento, déjelo en la sección de comentarios.

Todas las imágenes son producidas por el autor a menos que se indique lo contrario.