kishorkukreja/awesome-supply-chain/2d-bin-packing

from pulp import *
def solve_2d_bin_packing_ip(items, bin_width, bin_height, max_bins=None):
    """
    2D Bin Packing using Integer Programming
    Parameters:
    - items: list of (width, height) tuples
    - bin_width: width of each bin
    - bin_height: height of each bin
    - max_bins: maximum number of bins to consider
    Returns optimal packing solution
    Note: Only practical for small problems (<20 items)
    """
    n = len(items)
    if max_bins is None:
        max_bins = n  # Worst case: one item per bin
    bins = range(max_bins)
    item_ids = range(n)
    # Create problem
    prob = LpProblem("2D_Bin_Packing", LpMinimize)
    # Decision variables
    # x[i,b] = x coordinate of item i in bin b
    x = LpVariable.dicts("x",
                        [(i, b) for i in item_ids for b in bins],
                        lowBound=0, upBound=bin_width, cat='Continuous')
    # y[i,b] = y coordinate of item i in bin b
    y = LpVariable.dicts("y",
                        [(i, b) for i in item_ids for b in bins],
                        lowBound=0, upBound=bin_height, cat='Continuous')
    # a[i,b] = 1 if item i assigned to bin b
    a = LpVariable.dicts("assign",
                        [(i, b) for i in item_ids for b in bins],
                        cat='Binary')
    # w[b] = 1 if bin b is used
    w = LpVariable.dicts("use_bin", bins, cat='Binary')
    # Objective: minimize number of bins
    prob += lpSum([w[b] for b in bins]), "Total_Bins"
    # Constraints
    # 1. Each item assigned to exactly one bin
    for i in item_ids:
        prob += lpSum([a[i,b] for b in bins]) == 1, f"Assign_{i}"
    # 2. Item fits within bin boundaries
    for i in item_ids:
        for b in bins:
            prob += x[i,b] + items[i][0] <= bin_width + (1 - a[i,b]) * bin_width, \
                    f"Fit_Width_{i}_{b}"
            prob += y[i,b] + items[i][1] <= bin_height + (1 - a[i,b]) * bin_height, \
                    f"Fit_Height_{i}_{b}"
    # 3. Bin is used if any item assigned to it
    for b in bins:
        for i in item_ids:
            prob += a[i,b] <= w[b], f"Bin_Used_{i}_{b}"
    # 4. Non-overlapping constraints (simplified - full version more complex)
    # This is a simplified model; full non-overlap requires additional binary variables
    # Solve
    status = prob.solve(PULP_CBC_CMD(msg=1, timeLimit=300))
    if LpStatus[status] != 'Optimal':
        return None
    # Extract solution
    solution = {
        'num_bins': int(value(prob.objective)),
        'bins': []
    }
    for b in bins:
        if w[b].varValue > 0.5:
            bin_items = []
            for i in item_ids:
                if a[i,b].varValue > 0.5:
                    bin_items.append({
                        'item_id': i,
                        'x': x[i,b].varValue,
                        'y': y[i,b].varValue,
                        'width': items[i][0],
                        'height': items[i][1]
                    })
            solution['bins'].append(bin_items)
    return solution

def first_fit_decreasing_height(items, bin_width, bin_height):
    """
    First Fit Decreasing Height (FFDH) Algorithm
    Classic shelf-based packing heuristic
    - Sorts items by decreasing height
    - Packs items left-to-right on shelves
    - Opens new shelf/bin when needed
    Parameters:
    - items: list of (width, height, item_id) tuples
    - bin_width: bin width
    - bin_height: bin height
    Returns packing solution
    """
    # Sort by decreasing height, then decreasing width
    sorted_items = sorted(items, key=lambda x: (x[1], x[0]), reverse=True)
    bins = []
    for item_width, item_height, item_id in sorted_items:
        placed = False
        # Try to place in existing bins
        for bin_idx, bin_data in enumerate(bins):
            shelves = bin_data['shelves']
            # Try each shelf
            for shelf in shelves:
                if (shelf['remaining_width'] >= item_width and
                    shelf['height'] >= item_height):
                    # Place on this shelf
                    x = bin_width - shelf['remaining_width']
                    y = shelf['y']
                    bin_data['items'].append({
                        'id': item_id,
                        'x': x,
                        'y': y,
                        'width': item_width,
                        'height': item_height
                    })
                    shelf['remaining_width'] -= item_width
                    placed = True
                    break
            if placed:
                break
            # Try to create new shelf in this bin
            if not placed:
                current_height = sum(s['height'] for s in shelves)
                if current_height + item_height <= bin_height:
                    # Create new shelf
                    new_shelf = {
                        'y': current_height,
                        'height': item_height,
                        'remaining_width': bin_width - item_width
                    }
                    shelves.append(new_shelf)
                    bin_data['items'].append({
                        'id': item_id,
                        'x': 0,
                        'y': current_height,
                        'width': item_width,
                        'height': item_height
                    })
                    placed = True
                    break
        # Need new bin
        if not placed:
            new_bin = {
                'items': [{
                    'id': item_id,
                    'x': 0,
                    'y': 0,
                    'width': item_width,
                    'height': item_height
                }],
                'shelves': [{
                    'y': 0,
                    'height': item_height,
                    'remaining_width': bin_width - item_width
                }]
            }
            bins.append(new_bin)
    return {
        'num_bins': len(bins),
        'bins': bins,
        'utilization': calculate_utilization(bins, bin_width, bin_height)
    }
def calculate_utilization(bins, bin_width, bin_height):
    """Calculate space utilization percentage"""
    total_item_area = 0
    for bin_data in bins:
        for item in bin_data['items']:
            total_item_area += item['width'] * item['height']
    total_bin_area = len(bins) * bin_width * bin_height
    return (total_item_area / total_bin_area * 100) if total_bin_area > 0 else 0

def best_fit_decreasing_height(items, bin_width, bin_height):
    """
    Best Fit Decreasing Height Algorithm
    Finds the shelf with minimum remaining space that fits the item
    """
    sorted_items = sorted(items, key=lambda x: (x[1], x[0]), reverse=True)
    bins = []
    for item_width, item_height, item_id in sorted_items:
        best_bin = None
        best_shelf = None
        min_waste = float('inf')
        # Find best fitting shelf
        for bin_idx, bin_data in enumerate(bins):
            for shelf_idx, shelf in enumerate(bin_data['shelves']):
                if (shelf['remaining_width'] >= item_width and
                    shelf['height'] >= item_height):
                    waste = shelf['remaining_width'] - item_width
                    if waste < min_waste:
                        min_waste = waste
                        best_bin = bin_idx
                        best_shelf = shelf_idx
        if best_bin is not None:
            # Place on best shelf
            shelf = bins[best_bin]['shelves'][best_shelf]
            x = bin_width - shelf['remaining_width']
            y = shelf['y']
            bins[best_bin]['items'].append({
                'id': item_id,
                'x': x,
                'y': y,
                'width': item_width,
                'height': item_height
            })
            shelf['remaining_width'] -= item_width
        else:
            # Try to create new shelf or new bin
            placed = False
            for bin_idx, bin_data in enumerate(bins):
                shelves = bin_data['shelves']
                current_height = sum(s['height'] for s in shelves)
                if current_height + item_height <= bin_height:
                    new_shelf = {
                        'y': current_height,
                        'height': item_height,
                        'remaining_width': bin_width - item_width
                    }
                    shelves.append(new_shelf)