Optimizando Jambo-tubos

El problema: dado un Jabotubo con resistencia $R$ , y una secuencia ordenada de $n$ productos $S$ , cada uno con un peso asociado $w_i$ y una resistencia asociada $r_i$ , determinar la máxima cantidad de productos que pueden apilarse en un tubo sin que ninguno esté aplastado.

En la figura se ilustra un ejemplo con $R=50$ , $n=5$ , $w=[10,20,30,10,15]$ y $r=[45,8,15,2,30]$ . La solución óptima es $3$ , y consiste en tomar los elementos $1$ , $3$ y $4$ . Notar que la solución alternativa tomando los elementos $1$ , $3$ y $5$ no es factible porque la suma de sus pesos es $55\textgreater R$ .

Nota: los productos solamente pueden ser apilados en el orden en que son recibidos de la cinta transportadora. Para este problema, asumiremos que todos los valores mencionados son enteros no negativos.

Ejemplo de instancia del problema de Jambo-tubos.

Proyecto

Implementamos 3 algoritmos en C++ para resolver este problema:

Fuerza bruta
Backtracking
Programación dinámica

El proyecto está organizado de la sigueinte forma:

/src contiene el código fuente
/input contiene entradas válidas
/instancias tiene las instancias generadas para la experimentacion
/notebooks tiene los experimentos ejecutados. Ver experiments

Algoritmos

Para compilar el código fuente:

g++ src/main.cpp -o algo3-tp1

Para ejecutar:

./algo3-tp1 RUTA_A_ENTRADA ALGORITMO

1: fuerza bruta
2: backtracking
3: programacion dinamica
4: backtracking sin poda de optimalidad
5: backtracking sin poda de factbilidad

Se puede ejecutar ambos comandos en una sola sentencia:

g++ src/main.cpp -o algo3-tp1 && ./algo3-tp1 RUTA_A_ENTRADA ALGORITMO

Ejemplo:

g++ src/main.cpp -o algo3-tp1 && ./algo3-tp1 ./input/sample2 3

Experimentacion

Para usar Python v3.6.5

Instalar pyenv (una sola vez)

Como instalar pyenv: https://github.com/pyenv/pyenv#installation

Mac:

brew update
brew install pyenv
eval "$(pyenv init -)"

Instalar v3.6.5 (una sola vez)

pyenv install 3.6.5

Activar v3.6.5 (cada nueva consola debe ejecutarlo una vez)

eval "$(pyenv init -)"
pyenv global 3.6.5

Checkear con

$ python --version
Python 3.6.5

Instalar dependencias

pip install -r requirements.txt

Notebooks

Abrir notebooks con

jupyter notebook notebooks/

Experimento 3.1: Comparacion entre algoritmos - Comparacion
Experimento 3.2: Complejidad de fuerza bruta - ComplejidadFuerzaBruta
Experimento 3.3: Efectividad de las podas de backtracking - podas
Experimento 3.4: Orden de productos vs. backtracking con distintas podas - podasOrdenadas
Experimento 3.5: Complejidad de programación dinamica - - ComplejidadDinamica

Ayuda

Mas ayuda en: