I am working on implementing the hill-climbing algorithm to solve the one-dimensional bin packing problem but I got to a bottleneck. The function, which I called
main for lack of a better name, repeats the same set of actions until the number of attempts has been consumed or if it has found the optimum which is given beforehand as part of an instance.
I want to know if this type of looping can be performed in parallel or distributed. And if so, is there a simple way to implement it? I have zero experience doing things in parallel and distributed . The idea is simple, loop and replace If the current “solution” at the current
attempt is better than the better one found at the moment, if the optimal “solution” has been found then stop, continue otherwise.
function main(instance::BPPInstance, attempts::Int; earlybreak = false) # Objective function f(x) = sum(λ -> (λ.fullness)^2, x) # First attempt: # Get a random sorting of the bins, then search the search space, and then compute the score!!! bestbins = randomsort_bins(instance) climb!(bestbins, instance.item_weights, instance.bin_capacity) fbest = f(bestbins) bins_count = length(bestbins) # Remaining attempts for attempt in 2:attempts # Return the found configuration early and the attempts made to find it if earlybreak && bins_count == instance.optimal_solution return bestbins, attempt end # Get a random sorting of the bins, then search the search space, and then compute the score!!! bins = randomsort_bins(instance) climb!(bins, instance.item_weights, instance.bin_capacity) fbins = f(bins) if fbins > fbest bestbins = bins fbest = fbins bins_count = length(bestbins) end end return bestbins, attempts end
Some time ago I saw the existence of Dagger, I wonder if this package can be used in this case.