Generic algorithms¶
The following algorithms are conceptually the same across all domains: each one solves a multi-bin problem by repeatedly solving single-bin (knapsack) sub-problems of the same domain.
Sequential single knapsack¶
This algorithm solves the knapsack, bin-packing, bin-packing-with-leftovers and variable-sized-bin-packing objectives.
It fills the bins one by one, each with a knapsack sub-problem on the remaining items; the content of a bin is repeated in as many bins as the remaining items allow. In anytime mode, after each pass, it restarts with more effort for the sub-problems.
Sequential value correction¶
This algorithm solves the knapsack, bin-packing, bin-packing-with-leftovers and variable-sized-bin-packing objectives.
It is closely related to sequential single knapsack, but instead of restarting with a larger search effort, it restarts by increasing the profit of the items that were packed in high-waste bins, so that they get packed earlier in the next pass and hopefully generate less waste.
Dichotomic search¶
This algorithm solves the variable-sized-bin-packing objective.
It searches, by dichotomy, for the smallest achievable waste percentage: for a given waste estimate, it deduces which bins would be needed to reach that quantity of waste, and solves a bin packing sub-problem restricted to those bins.
Column generation¶
This algorithm solves the knapsack, bin-packing and variable-sized-bin-packing objectives.
It solves the linear relaxation of a model whose variables are the possible contents of the bins (patterns), generated dynamically by column generation, the pricing problems being single-bin knapsack problems. Then a limited discrepancy search fixes the patterns of the relaxation one by one, solving the relaxation of the remaining problem at each node. It also gives a bound.
Sequential feasibility¶
This algorithm solves the bin-packing, bin-packing-with-leftovers, open-dimension-x, open-dimension-y, open-dimension-z and open-dimension-xy objectives with an algorithm solving the feasibility objective.
It repeatedly solves a feasibility sub-problem asking whether all the items fit into a shrinking amount of space, and stops as soon as a sub-problem isn’t solved.
