problem knapsack code algorithm math optimization knapsack-problem

algorithm - knapsack - Extraño, pero práctico, bidimensional bin embalaje optimización



knapsack subset sum (3)

Intento escribir una aplicación que genere dibujos para el Panel compartimentado.

Tengo N cubículos (rectángulos 2D) (N <= 40). Para cada cubículo hay una altura mínima (minHeight [i]) y un ancho mínimo (minWidth [i]) asociado. El panel también tiene una restricción MAXIMUM_HEIGHT.

Estos N cubículos deben estar dispuestos en una cuadrícula de forma que las restricciones anteriores se cumplan para cada cubículo.

Además, el ancho de cada columna se decide por el máximo de minWidths de cada cubículo en esa columna.

Además, la altura de cada columna debe ser la misma. Esto decide la altura del panel

Podemos agregar cubículos de repuesto en el espacio vacío que queda en cualquier columna o podemos aumentar el alto / ancho de cualquier cubículo más allá del mínimo especificado. Sin embargo, no podemos rotar ninguno de los cubículos.

OBJECTIVE: TO MINIMIZE TOTAL PANEL WIDTH.

En la actualidad lo he implementado simplemente ignorando el ancho de cubículos en mi optimización. Simplemente elijo el cubículo con el minHeight más grande e intento colocarlo en mi panel. Sin embargo, no garantiza una solución óptima.

¿Puedo obtener algo mejor que esto?

EDIT 1: MAXIMUM_HEIGHT del panel = 2100 mm, rango de minimaje (350 mm a 800 mm), rango mínimo (225 mm a 2100 mm)

EDIT 2: OBJETIVO DEL PROBLEMA: MINIMIZAR EL ANCHO DEL PANEL (no el área del panel).

Una solución es dividir el ancho de la fila del cubículo por el ancho mínimo. Esto le da la cantidad máxima de cubículos que pueden caber en una fila.

Divida el resto de la primera división por el número de cubículos. Esto le da el ancho adicional para agregar al ancho mínimo para igualar todos los anchos de cubículo.

Ejemplo: Tienes una fila de cubículos de 63 metros. Cada cubículo tiene un ancho mínimo de 2 metros. Supongo que el grosor de una de las paredes del cubículo está incluido en los 2 metros. También estoy asumiendo que un cubículo extremo estará contra una pared.

Haciendo los cálculos, obtenemos 63/2 = 31.5 o 31 cubículos.

Ahora dividimos 0.5 metros por 31 cubículos y obtenemos 16 milímetros. Entonces, el ancho del cubículo es 2.016 metros.

Formulación

Dado:

  • para cada celda i = 1, ..., M , el (min) ancho W_i y (min) altura H_i
  • la altura máxima permitida de cualquier pila, T

Podemos formular el programa entero mixto de la siguiente manera:

minimize sum { CW_k | k = 1, ..., N } with respect to C_i in { 1, ..., N }, i = 1, ..., M CW_k >= 0, k = 1, ..., N and subject to [1] sum { H_i | C_i = k } <= T, k = 1, ..., N [2] CW_k = max { W_i | C_i = k }, k = 1, ..., N (or 0 when set is empty)

Puede elegir N para que sea un entero suficientemente grande (por ejemplo, N = M ).

Algoritmo

Conecte este programa de entero mixto a un solucionador de programa entero mixto existente para determinar el mapeo de celda a columna dado por los C_i, i = 1, ..., M óptimos.

Esta es la parte que no quieres reinventar. ¡Usa un solucionador existente!

Nota

Dependiendo de la potencia expresiva de su paquete de solución de programa de entero mixto, puede o no puede aplicar directamente la formulación que describí anteriormente. Si las restricciones [1] y [2] no se pueden especificar debido a la naturaleza "basada en conjunto" de ellas o al max , puede transformar manualmente la formulación a una equivalente menos declarativa pero más canónica que no necesita esta expresiva poder:

minimize sum { CW_k | k = 1, ..., N } with respect to C_i_k in { 0, 1 }, i = 1, ..., M; k = 1, ..., N CW_k >= 0, k = 1, ..., N and subject to [1] sum { H_i * C_i_k | i = 1, ..., M } <= T, k = 1, ..., N [2] CW_k >= W_i * C_i_k, i = 1, ..., M; k = 1, ..., N [3] sum { C_i_k | k = 1, ..., N } = 1, i = 1, ..., M

Aquí las variables C_i de antes (tomando valores en { 1, ..., N } ) han sido reemplazadas por variables C_i_k (tomando valores en { 0, 1 } ) bajo la relación C_i = sum { C_i_k | k = 1, ..., N } C_i = sum { C_i_k | k = 1, ..., N } .

El mapeo final de celda a columna se describe por el C_i_k : la celda i pertenece en la columna k si y solo si C_i_k = 1 .