1d bin packing problem with FFD + Simulated annealling not improving the solution. Any thoughts?

Question

Working on a project that i have to implement this. I need to improve the solution given by the FirstFitDecreasing ( minimize the bins used ) but i don't seem to find a way to make it. I think the problem is in the implementation of the annealer or the generate_neighbour function, but i don't know how to fix it. Any thoughts?

the instance used "/home/TEO/main/Falkenauer/Falkenauer_U/Falkenauer_u120_00.txt" is a file with a bunch of numbers (items weights) each in a line, from the BPP lib and it can be found here https://site.unibo.it/operations-research/en/research/bpplib-a-bin-packing-problem-library

optimal solutions

example:

120
150
98
98
98
96
96
94
...

import random
import math

def Le_Instancia(filename):
    try:
        with open(filename, 'r') as file:
            weight = [int(line.strip()) for line in file]
            return weight
    except FileNotFoundError:
        print("Arquivo não encontrado. (Verifique se o arquivo está na pasta correta)")
        return []

def FirstFitDecreasing(weight, n, bin_capacity):
    # Inicializa objetivo (número de bins)
    # Pior caso: n = objetivo
    objetivo = 0

    # Cria uma lista para armazenar o espaço restante nos bins
    bin_rem = [0]*n

    # Lista de listas para armazenar as bins utilizadas com os itens dentro
    bins_used = [[] for _ in range(n)]

    # Ordena os itens em ordem decrescente de peso
    weight.sort(reverse=True)

    # Adiciona os itens um por um
    for i in range(n):
        # Acha a primeira bin que pode acomodar weight[i]
        j = 0
        while j < objetivo:
            if bin_rem[j] >= weight[i]:
                bin_rem[j] = bin_rem[j] - weight[i]
                bins_used[j].append(weight[i])  # Adiciona o item na bin
                break
            j += 1

        # Caso não exista bin que possa acomodar weight[i], cria um novo bin
        if j == objetivo:
            bin_rem[objetivo] = bin_capacity - weight[i]
            bins_used[objetivo].append(weight[i])  # Adiciona o item na nova bin
            objetivo = objetivo + 1

    bins_used = bins_used[:objetivo]

    return objetivo, bins_used


def cost_function(bins_used):
    return len(bins_used)

def simulated_annealing(weight, n, bin_capacity, initial_temperature, cooling_rate, max_iterations):
    # First Fit Decreasing initial solution
    objective, bins_used = FirstFitDecreasing(weight, n, bin_capacity)
    best_objective = objective
    best_solution = bins_used

    # Initialize temperature
    temperature = initial_temperature

    for i in range(max_iterations):
        # Generate a neighbor solution by perturbing the current solution
        neighbor_bins_used = generate_neighbour(bins_used, bin_capacity)
        print(neighbor_bins_used)
        # Calculate the cost (number of bins) of the neighbor solution
        neighbor_objective = cost_function(neighbor_bins_used)
        #print(neighbor_objective)

        # Calculate the cost of the current solution
        current_objective = cost_function(bins_used)

        # Determine if the neighbor solution is accepted
        if neighbor_objective < current_objective:
            # Accept the neighbor solution if it's better
            bins_used = neighbor_bins_used
            objective = neighbor_objective

            # Update the best solution if necessary
            if neighbor_objective < best_objective:
                best_objective = neighbor_objective
                best_solution = neighbor_bins_used
        else:
            # Calculate the probability of accepting a worse solution
            probability = math.exp((current_objective - neighbor_objective) / temperature)

            # Accept the neighbor solution with a probability
            if random.random() < probability:
                bins_used = neighbor_bins_used
                objective = neighbor_objective
        
        # Cool down the temperature
        temperature *= cooling_rate
    #print(len(neighbor_bins_used))
    return best_objective, best_solution


def generate_neighbour(bins_used, bin_capacity):
    num_bins = len(bins_used)
    if num_bins < 2:
        return bins_used
    
    new_bins_used = [bin_content.copy() for bin_content in bins_used]

    # Choose two bins randomly
    bin1, bin2 = random.sample(range(num_bins), 2)

    # Choose a random number of items to swap
    num_items_to_swap = random.randint(1, min(len(new_bins_used[bin1]), len(new_bins_used[bin2])))

    # Swap items between bins
    for _ in range(num_items_to_swap):
        item1 = random.choice(new_bins_used[bin1])
        item2 = random.choice(new_bins_used[bin2])
        if sum(new_bins_used[bin1]) - item1 + item2 <= bin_capacity and sum(new_bins_used[bin2]) - item2 + item1 <= bin_capacity:
            new_bins_used[bin1].remove(item1)
            new_bins_used[bin2].remove(item2)
            new_bins_used[bin1].append(item2)
            new_bins_used[bin2].append(item1)

    # Remove empty bins
    new_bins_used = [bin_content for bin_content in new_bins_used if bin_content]

    return new_bins_used


filename = "/home/TEO/main/Falkenauer/Falkenauer_U/Falkenauer_u120_00.txt"  
weight = Le_Instancia(filename)
n = len(weight)
bin_capacity = 150 # Replace with the bin capacity
initial_temperature = 1000
cooling_rate = 0.95
max_iterations = 100000

best_objective, best_solution = simulated_annealing(weight, n, bin_capacity, initial_temperature, cooling_rate, max_iterations)

print("Best number of bins:", best_objective)
print("Best solution (bins used):", best_solution)

Answer 1

The simple reason that we get 51 is that you include the input file's first two lines as weights, while they rather are the number of weights and the bin capacity.
With this corrected, I get a solution with 49 bins. Why this isn't the optimum of 48 will probably be harder isn't too hard to answer. generate_neighbour functions as commented: Choose two bins randomly, Choose a random number of items to swap and Swap items between bins. This can never change the number of items in any bin, so it never gets to Remove empty bins; the function is just not able to generate a better solution.

Here's a snippet of modified code to swap different numbers of bins (but I don't get a better result with this - it's just too improbable).

    # Choose two bins randomly
    bin1, bin2 = random.sample(range(num_bins), 2)

    # Choose a random number of items to swap
    num1_items_to_swap = random.randint(0, len(new_bins_used[bin1]))
    num2_items_to_swap = random.randint(0, len(new_bins_used[bin2]))

    # Swap items between bins
    items1 = random.sample(new_bins_used[bin1], num1_items_to_swap)
    items2 = random.sample(new_bins_used[bin2], num2_items_to_swap)
    if sum(new_bins_used[bin1]) - sum(items1) + sum(items2) <= bin_capacity and \
       sum(new_bins_used[bin2]) - sum(items2) + sum(items1) <= bin_capacity:
        for _ in range(num1_items_to_swap): new_bins_used[bin1].remove(items1[_])
        for _ in range(num2_items_to_swap): new_bins_used[bin2].remove(items2[_])
        new_bins_used[bin1] += items2
        new_bins_used[bin2] += items1