Source code for discrete_optimization.binpack.solvers.greedy

#  Copyright (c) 2025 AIRBUS and its affiliates.
#  This source code is licensed under the MIT license found in the
#  LICENSE file in the root directory of this source tree.
from collections import defaultdict
from enum import Enum
from typing import Any, Optional, Union

import networkx as nx

from discrete_optimization.binpack.problem import BinPackProblem, BinPackSolution
from discrete_optimization.generic_tools.callbacks.callback import (
    Callback,
    CallbackList,
)
from discrete_optimization.generic_tools.do_solver import SolverDO
from discrete_optimization.generic_tools.result_storage.result_storage import (
    ResultStorage,
)


[docs] class GreedyBinPackSolver(SolverDO): problem: BinPackProblem def __init__(self, problem: BinPackProblem, **kwargs: Any): super().__init__(problem, **kwargs) graph = nx.Graph() graph.add_nodes_from(range(self.problem.nb_items)) if self.problem.has_constraint: graph.add_edges_from(list(self.problem.incompatible_items)) neighs = graph.adj self.graph = graph self.neighbors = {n: set(self.graph.neighbors(n)) for n in self.graph.nodes}
[docs] def solve( self, callbacks: Optional[list[Callback]] = None, **kwargs: Any ) -> ResultStorage: callback = CallbackList(callbacks=callbacks) callback.on_solve_start(self) allocation = [None for i in range(self.problem.nb_items)] capa_per_bins = defaultdict(lambda: 0) used_bins = [] item_per_bins = defaultdict(lambda: set()) nb_bins = 0 for j in range(self.problem.nb_items): weight = self.problem.list_items[j].weight neighbors = self.neighbors[j] if nb_bins == 0: nb_bins = 1 used_bins.append(0) capa_per_bins[0] += weight allocation[j] = 0 item_per_bins[0].add(j) else: success = False for bin in used_bins: if weight + capa_per_bins[bin] > self.problem.capacity_bin: continue if any(n in item_per_bins[bin] for n in neighbors): continue capa_per_bins[bin] += weight allocation[j] = bin item_per_bins[bin].add(j) success = True break if not success: new_bin = used_bins[-1] + 1 used_bins.append(new_bin) item_per_bins[new_bin].add(j) capa_per_bins[new_bin] += weight allocation[j] = new_bin res = self.create_result_storage([]) sol = BinPackSolution(problem=self.problem, allocation=allocation) fit = self.aggreg_from_sol(sol) res.append((sol, fit)) callback.on_solve_end(res, self) return res
[docs] class GreedyBinPackOpenEvolve(SolverDO): problem: BinPackProblem def __init__(self, problem: BinPackProblem, **kwargs: Any): super().__init__(problem, **kwargs) graph = nx.Graph() graph.add_nodes_from(range(self.problem.nb_items)) if self.problem.has_constraint: graph.add_edges_from(list(self.problem.incompatible_items)) self.graph = graph self.neighbors = {n: set(self.graph.neighbors(n)) for n in self.graph.nodes}
[docs] def solve(self, callbacks: Optional[list[Callback]] = None, **kwargs): """ - list_weights: give for each item its size. - set_conflicts: {(index1, index2), (index0, index4)...} : means that index1 and index2 are not put in the same bin etc - capacity_bin : is the size of each bin Returns a list of int (corresponding to bin index for each item index), the len of the list should be len(list_weights). """ callback = CallbackList(callbacks=callbacks) callback.on_solve_start(self) list_weights = [item.weight for item in self.problem.list_items] n = self.problem.nb_items bin_assignment = [0] * n bin_weights = [0] # Keeps track of weights in each bin. bin_conflicts = [ set() ] # Keeps track of items in each bin for conflict checking. # Heuristic: Sort by decreasing weight, then decreasing number of conflicts sorted_items = sorted( range(n), key=lambda i: (list_weights[i], -len(self.neighbors[i])), reverse=True, ) for i in sorted_items: best_bin = -1 min_weight_increase = float("inf") # Minimizes the increase in bin weight for j in range(len(bin_weights)): valid_placement = True # Efficient conflict check using sets for k in bin_conflicts[j]: if k in self.neighbors[i]: valid_placement = False break if ( valid_placement and bin_weights[j] + list_weights[i] <= self.problem.capacity_bin ): # Prioritize bins with less increase in weight if bin_weights[j] + list_weights[i] < min_weight_increase: min_weight_increase = bin_weights[j] + list_weights[i] best_bin = j if best_bin != -1: bin_assignment[i] = best_bin bin_weights[best_bin] += list_weights[i] bin_conflicts[best_bin].add(i) else: bin_assignment[i] = len(bin_weights) bin_weights.append(list_weights[i]) bin_conflicts.append({i}) sol = BinPackSolution(problem=self.problem, allocation=bin_assignment) fit = self.aggreg_from_sol(sol) res = self.create_result_storage([(sol, fit)]) callback.on_solve_end(res, self) return res