Problema rucsacurilor

Problema rucsacurilor este una cu o largă aplicabilitate practică, de la încărcarea mărfurilor în camioane și planificarea activităților până la amplasarea anunțurilor în pauzele publicitare.

Dându-se un set I={1,…,n} de obiecte cu mărimi s_i \in (0, 1], și un set B={1,..,k} de cutii cu capacitatea 1, să se găsească o aranjare a obiectelor astfel încât numărul de cutii utilizat să fie minim. Formal, să se găsească o asociere a : I \rightarrow B astfel încât pentru \forall b \in B, c(b) = 1 avem \sum_{i:a(i)=b}s_i \leq 1 și a(I) este minimal.

Strategii de rezolvare a problemei rucsacurilor

Next Fit

Voi începe cu algoritm banal, online, numit Next Fit. Totuși, o să vedeți imediat că în ciuda simplității grozave a algoritmului, rezultatele finale nu sunt chiar atât de proaste. Paradoxal, sunt cu doar cu 33% mai proaste decât cel mai bun algoritm posibil (asta dacă P\neq NP).

Ideea algoritmului:

• Pune obiecte într-o cutie până când următorul obiect nu va mai încăpea.
• Atunci, „închide” cutia și începe cu una nouă
• Rata de aproximare 2

Demonstrația ratei de aproximare

Să presupunem că acest algoritm folosește k cutii. Suma obiectelor din oricare două cutii consecutive este tot timpul mai mare ca 1 (altfel nu le-am pune în 2 cutii). De asemenea, știm că valoarea optimală pentru Next Fit, OPT \geq \lceil\sum s_i\rceil.

\Rightarrow k \leq 2\sum s_i \leq 2 \lceil \sum s_i \rceil \leq 2 OPT

Din cele două cazuri vedem că: k \leq 2OPT \Rightarrow Q.E.D.

First Fit

Pune fiecare obiect s_i în prima cutie disponibilă, cu presupunerea că toate cutiile sunt deschise. Returnează o soluție k astfel încât k \leq 1.7OPT + 2.

First Fit Decreasing

1. Sortează obiectele în ordine descrescătoare
2. Procesează obiectele în maniera First Fit

Găsește o soluție astfel încât h \leq 1.5OPT + 1.

Pentru demonstrații asupra limitelor de aproximarea lucrarea Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms.

Folosind un arbore balansat, operația de găsire a cutiei disponibile poate fi îmbunătățită, reducându-se astfel timpul de la O(n^2) la O(nlogn).

Analiza complexității

Problema rucsacurilor este NP-Hard(ca problemă de optimizare), iar problema de decizie în cazul în care avem două cutii este NP-completă.

Reducerea se face din problema PARTIȚIEI, care știm că este NPC (reducere din problema SUBSET-SUM). În problema PARTIȚIEI se dau n numere, c_1,…,c_n \in \mathbb{N} și trebuie decis dacă există un set S\subseteq {1,…,n} astfel încât \sum_{i\in S}c_i = \sum_{i\notin S}c_i.

Dându-se o instanță a problemei PARTIȚIE, putem crea o instanță de PROBLEMA RUCSACURILOR MULTIPLE setând s_i = \mathbf{2}c_i/(\sum_{j=1}^n c_j) \in (0, 1] pentru i=1,…,n. Desigur, două cutii sunt de ajuns dacă și numai dacă există o mulțime S={1,…,n} astfel încât \sum_{i\in S}c_i = \sum_{i\notin S}c_i. Acel \mathbf{2} vine din faptul că vrem o partiție să ocupe o cutie întreagă (i.e. greutatea totală să fie 1). Astfel vedem că bin packing este posibil doar dacă partiția este posibilă.

Algoritmi de rezolvare pentru problema rucsacurilor

Următorii algoritmi sunt preluați din două surse deosebite:

• A Thousand Ways to Pack the Bin – A Practical Approach to Two-Dimensional Rectangle Bin Packing
• Survey on two-dimensional packing

Un caz particular al problemei rucsacurilor este situația când avem o singură cutie, cu înălțime infinită și lățime fixă, W. Obiectivul este să se aranjeze obiectele astfel încât înălțimea să fie minimizată.

Abordarea pe nivele

O abordare simplă este să introducem o serie de nivele și să plasăm obiectele de la dreapta la stânga, pe rândurile formate. Pe același nivel, obiectele se aranjează astfel încât să fie aliniate (fie sus sau jos). Baza următorului nivel este dată de cel mai înalt obiect de pe nivelul anterior. De aici și convenția să se ordoneze inițial obiectele în ordinea descrescătoare a înălțimii.

First Fit Decreasing Height

Obiectele sunt ordonate descrescător, după înălțime, și vor puse pe primul nivel unde încap (i.e. mai este loc în lățime). Dacă nu, se creează un nou nivel.

Best Fit Decreasing Height

Obiectele sunt ordonate descrescător, după înălțime, și vor puse pe acel nivel (din cele posibile), pentru care spațiul orizontal rezidual este minim (i.e. obiectul se pune acolo unde, după amplasare, spațiul rămas este minim). Dacă niciun nivel nu acceptă obiectul, se creează un nou nivel.

Direcții alternative

Lodi et al. propun a abordare diferită, ce nu se bazează pe nivele. Algoritmul începe prin a genera L cutii(L fiind o limită inferioară asupra numărului optim de cutii). AD începe să plaseze la baza fiecărui cutii folosind BFDH. Restul de obiecte îs grupate, în benzi, alternativ, de la dreapta la stânga și invers.

Guillotine

Formularea problemei rucsacurilor multiple în termenii unui probleme de programare liniară

Dacă urmărim abordarea pe nivele și ordonăm obiectele în ordinea descrescătoare a înălțimii, putem să transpunem problema într-o problemă de programare liniară. Vom introduce următoarele notații:

• W este lățimea cutiei;
• h_i marchează înălțimea obiectului i;
• w_i marchează lățimea obiectului i;
• y_i va fi o variabilă indicator ce marchează dacă obiectul i \textbf{inițializează} nivelul i (i.e. y_i=1 dacă primul obiect de la un nivel este obiectul i, respectiv 0 în rest);
• x_{ij}=1 dacă obiectul j merge la nivelul inițializat de obiectul i.

Formalismul matematic pe care îl voi descrie mai jos a fost prezentat în lucrarea lui Lodi et al., Two-dimensional packing problems: A survey.

Rucsacul cu înălțime infinită

\min \sum_{i=1}^n h_i y_i \\ \text{Supusă constrângerii: }\\ \sum_{i=1}^{j-1} x_{ij} + y_j = 1, j=1,…,n\\ \sum_{j=i+1}^n w_{j}x_{ij} \leq (W - w_i)y_i, i=1,…,n-1 y_i, x_{ij} = 0,1

Prima constrângere ne spune că niciun obiect până la obiectul ce inițializează nivelul j, cu excepția acestuia, NU se poate afla pe nivelul j (din presupunerea inițială că obiectele sunt ordonate crescător). A doua constrângere ne spune că toate obiectele de pe nivelele superioare nu pot să încapă pe nivelul curent (demonstrație prin reducere la absurd).

Problema rucsacurilor multiple

Varianta cu mai multe cutii este foarte similară, doar că se aplică constrângeri și pe nivele, față de cutii (starea cutiei se notează cu q_k, iar z_ki dacă nivelul i este inițializat în cutia k).

\min \sum_{k=1}^n q_k \quad \text{(să folosim cât mai puține cutii)}\\ \sum_{i=1}^{j-1} x_{ij} + y_j = 1, j=1,…,n\\ \sum_{j=i+1}^n w_{j}x_{ij} \leq (W - w_i)y_i, i=1,…,n-1\\ \sum_{k=1}^{i-1} z_{ki} + q_i = y_i, i=1,…,n \\ \sum_{i=k+1}^n h_i z_{ki} \leq (H-h_k)q_k, k=1,…,n-1\\ y_i, x_{ij}, q_k, z_{ki} = 0 \lor 1

Exemplu simplu în Python folosind librăria rectpack

Și acum un exemplu tare simplu, doar pentru a vedea cum rulează algoritmul. Înainte de toate, trebuie să subliniez că am folosit Python 3.7, având instalate următoarele pachete:

pip install rectpack
pip install matplotlib
pip install numpy

import matplotlib.pyplot as plt
import numpy as np

from matplotlib.patches import Rectangle
from rectpack import GuillotineBssfSas
from rectpack import newPacker


rectangles = [
    (100, 30), (40, 60), (30, 30), (70, 70), (100, 50), (30, 30),
    (50, 50), (20, 120), (80, 30), (100, 20), (120, 50), (20, 20),
    (10, 10), (150, 150), (200, 120), (170, 30), (80, 80)
]


def guillotine_packer(width, height):
    packer = newPacker(pack_algo=GuillotineBssfSas)

    # Add the rectangles to packing queue
    for r in rectangles:
        packer.add_rect(*r)

    # Add the bins where the rectangles will be placed
    b = (width, height)
    packer.add_bin(*b)

    # Start packing
    packer.pack()
    return packer


def draw_bins(packer):
    for bin in packer:
        # Bin dimensions (bins can be reordered during packing)
        width, height = bin.width, bin.height
        background = np.zeros((height, width), dtype=np.uint8)

        box = Rectangle((0, 0), width, height, linewidth=1, facecolor='w', edgecolor='r')
        fig, ax = plt.subplots(1, figsize=(5, 10))
        ax.imshow(background, aspect='auto')
        ax.add_patch(box)
        for rect in bin:
            # rect is a Rectangle object
            x = rect.x  # rectangle bottom-left x coordinate
            y = rect.y  # rectangle bottom-left y coordinate
            w = rect.width
            h = rect.height
            rect_drawing = Rectangle((x, y), w, h, linewidth=1, edgecolor='blue')
            ax.add_patch(rect_drawing)
    plt.show()


width = input('width= ')
height = input('height= ')
guillotine_pack = guillotine_packer(int(width), int(height))
draw_bins(guillotine_pack)

Rulând codul de mai sus, pentru width=200 și height=540 am obținut următorul rezultat:

Pretty cool bin packing-ul ăsta…