discrete_optimization.binpack.solvers package

Submodules

discrete_optimization.binpack.solvers.asp module

class discrete_optimization.binpack.solvers.asp.AspBinPackingSolver(problem: BinPackProblem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs)

Bases: AspClingoSolver, WarmstartMixin

Solver based on Answer Set Programming formulation and clingo solver for Bin Packing.

build_heuristic_input(solution: BinPackSolution)

build_string_data_input() → str

Converts the BinPackProblem instance data into ASP facts.

init_model(**kwargs: Any) → None

Initialize internal model used to solve.

Can initialize a ortools, milp, gurobi, … model.

problem: BinPackProblem

retrieve_solution(model: Model) → BinPackSolution

Parses the Clingo model to construct a BinPackSolution.

set_warm_start(solution: BinPackSolution) → None

Make the solver warm start from the given solution.

upper_bound: int

discrete_optimization.binpack.solvers.cpsat module

class discrete_optimization.binpack.solvers.cpsat.CpSatBinPackBinTypeSolver(problem: BinPackProblem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: AllocationCpSatSolver[int, int], SchedulingCpSatSolver[int], WarmstartMixin

get_makespan_upper_bound() → int

Get a upper bound on global makespan.

get_task_start_or_end_variable(task: int, start_or_end: StartOrEnd) → LinearExpr | IntVar | int | int8 | uint8 | int32 | uint32 | int64 | uint64

Retrieve the variable storing the start or end time of given task.

Parameters:

• task

• start_or_end

Returns:

get_task_unary_resource_is_present_variable(task: int, unary_resource: int) → LinearExpr | IntVar | int | int8 | uint8 | int32 | uint32 | int64 | uint64

Return a 0-1 variable/expression telling if the unary_resource is used for the task.

NB: sometimes the given resource is never to be used by a task and the variable has not been created. The convention is to return 0 in that case.

hyperparameters: list[Hyperparameter] = [EnumHyperparameter(name='modeling', default=<ModelingBinPack.BINARY: 0>, depends_on=None, name_in_kwargs='modeling')]

Hyperparameters available for this solver.

These hyperparameters are to be feed to **kwargs found in

• __init__()

• init_model() (when available)

• solve()

init_model(**args: Any) → None

Init cp model and reset stored variables if any.

init_model_binary(**args: Any)

init_model_scheduling(**args: Any)

modeling: ModelingBinPack

problem: BinPackProblemBinType

retrieve_solution(cpsolvercb: CpSolverSolutionCallback) → Solution

Construct a do solution from the cpsat solver internal solution.

It will be called each time the cpsat solver find a new solution. At that point, value of internal variables are accessible via cpsolvercb.Value(VARIABLE_NAME).

Parameters:

cpsolvercb – the ortools callback called when the cpsat solver finds a new solution.

Returns:

the intermediate solution, at do format.

set_warm_start(solution: BinPackSolution) → None

Make the solver warm start from the given solution.

property subset_unaryresources_allowed: Iterable[int]

Unary resources allowed to solve the problem.

By default, all unary resources.

discrete_optimization.binpack.solvers.cpsat.CpSatBinPackSolver

alias of CpSatBinPackBinTypeSolver

class discrete_optimization.binpack.solvers.cpsat.ModelingBinPack(*values)

Bases: Enum

BINARY = 0

SCHEDULING = 1

exception discrete_optimization.binpack.solvers.cpsat.ModelingError

Bases: Exception

Exception raised when calling for variables not existing for chosen modeling.

discrete_optimization.binpack.solvers.dp module

class discrete_optimization.binpack.solvers.dp.DpBinPackSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: DpSolver

hyperparameters: list[Hyperparameter] = [CategoricalHyperparameter(name='solver', default=<class 'builtins.CABS'>, depends_on=None, name_in_kwargs='solver'), EnumHyperparameter(name='modeling', default=<ModelingDpBinPack.ASSIGN_ITEM_BINS: 0>, depends_on=None, name_in_kwargs='modeling')]

Hyperparameters available for this solver.

These hyperparameters are to be feed to **kwargs found in

• __init__()

• init_model() (when available)

• solve()

init_model(**kwargs)

Initialize internal model used to solve.

Can initialize a ortools, milp, gurobi, … model.

init_model_assign_item_and_bins(**kwargs: Any) → None

init_model_fill_bins(**kwargs)

init_model_fill_bins_with_constraints(**kwargs)

modeling: ModelingDpBinPack

problem: BinPackProblem

retrieve_solution(sol: Solution) → Solution

retrieve_solution_color_transition(sol: Solution) → Solution

retrieve_solution_pack_items(sol: Solution) → Solution

transitions: dict

class discrete_optimization.binpack.solvers.dp.ModelingDpBinPack(*values)

Bases: Enum

ASSIGN_ITEM_BINS = 0

PACK_ITEMS = 1

discrete_optimization.binpack.solvers.greedy module

class discrete_optimization.binpack.solvers.greedy.BinSelectionStrategy(*values)

Bases: Enum

Strategy for selecting which bin to assign an item to.

• FIRST_FIT: Choose the first bin that fits the item

• BEST_FIT_MIN_WEIGHT: Choose bin with minimum total weight after adding item

• BEST_FIT_MIN_REMAINING: Choose bin with minimum remaining capacity after adding item

BEST_FIT_MIN_REMAINING = 'best_fit_min_remaining'

BEST_FIT_MIN_WEIGHT = 'best_fit_min_weight'

FIRST_FIT = 'first_fit'

class discrete_optimization.binpack.solvers.greedy.GreedyBinPackSolver(problem: BinPackProblem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: SolverDO

Greedy bin packing solver with configurable sorting and bin selection strategies.

Supports multiple greedy heuristics for bin packing problems with optional incompatibility constraints. The behavior is controlled by two strategy hyperparameters.

Hyperparameters:

sorting_strategy: How to sort items before assignment bin_selection_strategy: How to select bins for items

Example

# Best Fit Decreasing (BFD) heuristic solver = GreedyBinPackSolver(problem) solver.solve(

sorting_strategy=SortingStrategy.CONFLICT_DESC_WEIGHT_DESC, bin_selection_strategy=BinSelectionStrategy.BEST_FIT_MIN_REMAINING

)

hyperparameters: list[Hyperparameter] = [EnumHyperparameter(name='sorting_strategy', default=<SortingStrategy.CONFLICT_DESC_WEIGHT_DESC: 'conflict_desc_weight_desc'>, depends_on=None, name_in_kwargs='sorting_strategy'), EnumHyperparameter(name='bin_selection_strategy', default=<BinSelectionStrategy.BEST_FIT_MIN_REMAINING: 'best_fit_min_remaining'>, depends_on=None, name_in_kwargs='bin_selection_strategy')]

Hyperparameters available for this solver.

These hyperparameters are to be feed to **kwargs found in

• __init__()

• init_model() (when available)

• solve()

problem: BinPackProblem

solve(callbacks: list[Callback] | None = None, **kwargs: Any) → ResultStorage

Solve using greedy bin packing with configured strategies.

class discrete_optimization.binpack.solvers.greedy.SortingStrategy(*values)

Bases: Enum

Strategy for sorting items before bin assignment.

• NONE: Process items in original order

• WEIGHT_DESC: Sort by weight descending

• WEIGHT_DESC_CONFLICT_ASC: Sort by weight descending, then conflict count ascending

• CONFLICT_DESC_WEIGHT_DESC: Sort by conflict count descending, then weight descending

CONFLICT_DESC_WEIGHT_DESC = 'conflict_desc_weight_desc'

NONE = 'none'

WEIGHT_DESC = 'weight_desc'

WEIGHT_DESC_CONFLICT_ASC = 'weight_desc_conflict_asc'

discrete_optimization.binpack.solvers.lp module

class discrete_optimization.binpack.solvers.lp.MathOptBinPackSolver(problem: BinPackProblem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: _BaseLpBinPackSolver, OrtoolsMathOptMilpSolver

convert_to_variable_values(solution: Solution) → dict[Variable, float]

Convert a solution to a mapping between model variables and their values.

Will be used by set_warm_start().

discrete_optimization.binpack.solvers.optal module

class discrete_optimization.binpack.solvers.optal.OptalBinPackSolver(problem: BinPackProblem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs)

Bases: AllocationOptalSolver[int, int], SchedulingOptalSolver[int]

get_task_interval_variable(task: Task) → cp.IntervalVar

Retrieve the interval variable of given task.

get_task_unary_resource_is_present_variable(task: Task, unary_resource: UnaryResource) → cp.BoolExpr

Return a 0-1 variable/expression telling if the unary_resource is used for the task.

NB: sometimes the given resource is never to be used by a task and the variable has not been created. The convention is to return 0 in that case.

init_model(**kwargs: Any) → None

Init cp model and reset stored variables if any.

problem: BinPackProblem

retrieve_solution(result: cp.SolveResult) → Solution

Return a d-o solution from the variables computed by minizinc.

Parameters:

result – output of the cp.solve

Returns:

discrete_optimization.binpack.solvers.toulbar module

class discrete_optimization.binpack.solvers.toulbar.ToulbarBinPackSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: ToulbarSolver, WarmstartMixin

init_model(**kwargs) → None

Initialize internal model used to solve.

Can initialize a ortools, milp, gurobi, … model.

problem: BinPackProblem

retrieve_solution(solution_from_toulbar2: tuple[list, float, int]) → BinPackSolution

set_warm_start(solution: BinPackSolution) → None

Make the solver warm start from the given solution.

Module contents