binpacking_kh.py

# Konstruktions-Heuristik für 1D Binpacking Problem
# Author: Fabian Leuthold

import math
import matplotlib.pyplot as plt


def read_1dbinpacking_file(file_path):
    """
    reads a 1d binpacking problem instance

    :param file_path: the file path
    :return: dictionary with item-id as key, dimension as value, in addition the capacity limit as a separate value
    """
    with open(file_path, 'r') as file:
        lines = file.readlines()

    container_cap = None
    items = {}

    for line in lines:
        line = line.strip()

        # Skip empty lines and the header lines
        if not line or line.startswith("NAME") or line.startswith("TYPE") or line.startswith("COMMENT"):
            continue

        # Extract container capacity
        if line.startswith("CONTAINER_CAP"):
            container_cap = float(line.split(":")[1].strip())
            continue

        # Extract item dimensions (after "OBJ_ID_DIM" line)
        if line[0].isdigit():
            item_id, item_dim = line.split()
            items[int(item_id)] = float(item_dim)

        # Stop reading if "EOF" is reached
        if line == "EOF":
            break

    return items, container_cap


def find_best_container(resulting_containers, container_cap, items, item):
    """
    loops through all existing containers in the resulting_containers (lists in list) and returns the index
    of the container with the minimal leftover capacity after adding item item.

    :param resulting_containers: the list containing lists of item_ids of the packed containers
    :param container_cap: container capacity
    :param items: the dict of all items with their volume
    :param item: the item to be packed
    :return: the index of the best container or None
    """
    container_leftover_capacity = []
    for container in resulting_containers:
        container_volume = [items.get(item_id) for item_id in container]
        container_leftover_capacity.append(container_cap - sum(container_volume) - item)

    best_leftover = math.inf
    best_container_id = None
    # find container-id with minimal leftover capacity
    for container_id, leftover_cap in enumerate(container_leftover_capacity):
        if leftover_cap >= 0 and leftover_cap < best_leftover:
            best_leftover = leftover_cap
            best_container_id = container_id

    return best_container_id


def binpack_greedy(items, container_cap):
    """
    construction of a best-fit heuristic to generate a fairly good offline 1d-binpacking solution.

    :param items: the dict of items to be packed; key is index, value is dimension
    :param container_cap: the capacity of each (standard) container
    :return: a dictionary containing lists of object_ids to be packed in each container, the number of containers needed
    """

    # Sort the jobs by duration in descending order
    # sorted_items = sorted(range(len(items)), key=lambda x: items[x], reverse=True)
    sorted_items = dict(sorted(items.items(), key=lambda item: item[1], reverse=True))
    assert container_cap > 0, "expected container_cap to be > 0!"

    # Initialize a list to keep track of all containers required
    resulting_containers = [[]]

    # loop through all objects
    for item_id, item in sorted_items.items():
        if item > container_cap:
            # instance not feasible
            resulting_containers = None
            break;
        # determine best container id
        best_cont_index = find_best_container(resulting_containers, container_cap, items, item)
        # if no best container exists, start a new one
        if best_cont_index == None:
            resulting_containers.append([item_id])
        else:
            resulting_containers[best_cont_index].append(item_id)

    return resulting_containers, len(resulting_containers)


def plot_binpack_problem(items, container_cap, resulting_containers):
    # Anzahl der Container
    num_containers = len(resulting_containers)

    # Farbe für jedes Item festlegen
    colors = plt.cm.get_cmap('tab20', len(items))

    # Plot erstellen
    fig, ax = plt.subplots(figsize=(10, 6))

    for i, container in enumerate(resulting_containers):
        y_offset = 0  # Startposition im Container
        for item_id in container:
            item_volume = items[item_id]
            ax.bar(i, item_volume, bottom=y_offset, color=colors(item_id), edgecolor='black')
            y_offset += item_volume

            # Text für das Item hinzufügen
            ax.text(i, y_offset - item_volume / 2, f'{item_id} ({item_volume})', ha='center', va='center',
                    color='white')

    # Labels und Titel
    ax.set_xlabel('Container')
    ax.set_ylabel('Volume')
    ax.set_title('Bin Packing Problem Visualization')
    ax.set_xticks(range(num_containers))
    ax.set_xticklabels([f'Container {i + 1}' for i in range(num_containers)])
    ax.set_ylim(0, container_cap)

    plt.show()


# *******************************************************************************************************************
# * Testcases to validate if code is working as expected                                                            *
# *******************************************************************************************************************


def test_read_test():
    """
    test, whether reading function for BIN_PACK_1D_C10_O5 provides the expected output

    :return:
    """
    # read problem instance
    file_path = './data/BIN_PACK_1D_C10_O5.bpk'

    items, container_cap = read_1dbinpacking_file(file_path)
    assert len(items) == 5, "expected 5 items but found else."
    assert container_cap == 10, "expected capacity to be 10 but found else."


def test_kh_test_1():
    """
    test, whether solution for BIN_PACK_1D_C10_O5 upholds the capacity constraint and generates the
    expectes solution

    :return:
    """
    file_path = './data/BIN_PACK_1D_C10_O5.bpk'
    # read problem instance
    items, container_cap = read_1dbinpacking_file(file_path)
    # trigger construction heuristic
    resulting_containers, num_containers = binpack_greedy(items, container_cap)
    assert len(resulting_containers) == 2, "Expected solution to use 2 containers but found else."
    assert resulting_containers[0] == [2, 3, 4], "Expected first container to hold items '[2, 3, 4]' but found else."
    assert resulting_containers[1] == [5, 1], "Expected first container to hold items '[5, 1]' but found else."


# *******************************************************************************************************************
# * Main Program                                                                                                    *
# *******************************************************************************************************************


def main():
    file_paths = ['./data/BIN_PACK_1D_C10_O5.bpk', './data/BIN_PACK_1D_C10_O20.bpk',
                  './data/BIN_PACK_1D_C25_O60.bpk', './data/BIN_PACK_1D_C80_O280.bpk']

    for file in file_paths:
        print(f"*** File {file}:")
        # Read the problem instance
        items, container_cap = read_1dbinpacking_file(file)
        # Create a first solution applying a primitive k-heuristic
        resulting_containers, num_containers = binpack_greedy(items=items, container_cap=container_cap)

        print(f"Container Capacity: {container_cap}")
        print(f"Number of items: {len(items)}")
        print(f"Num Containers: {num_containers}")
        print(f"Solution: {resulting_containers}")
        plot_binpack_problem(items, container_cap, resulting_containers)


if __name__ == "__main__":
    main()