Dual feasible functions

Objectives

This algorithm computes a bound for the bin-packing, feasibility and knapsack objectives, for instances with a single bin type. It doesn’t produce solutions.

Principle

It is the generalization to three dimensions of the dual feasible functions for rectangle, following the framework of Fekete and Schepers (2004): a dual feasible function is applied to each of the three dimensions of the items and of the bin, with its own breakpoint, and the volume bound of the transformed instance is a valid bound for the original instance. The three families \(f_0\), \(f_1\) and \(f_2\) are tried on each axis, which gives 27 combinations for each triple of breakpoints. The breakpoints of an axis are computed as in two dimensions, from the lengths along this axis which the items can take in their allowed rotations.

  • bin-packing and feasibility: the bound is the total transformed volume of the items divided by the transformed volume of the bin, rounded up, maximized over the breakpoints and the families of functions. For the feasibility objective, the instance is proven infeasible if the bound exceeds the number of bins.

  • knapsack: the bound is the fractional (Dantzig) bound of the knapsack problem with the transformed volumes, minimized over the breakpoints and the families of functions.

When an item can be rotated, its transformed volume depends on its rotation; the smallest one over its allowed rotations (up to 6) is used, which keeps the bound valid whatever the rotation of the item in the packing.

Automatic selection

The number of combinations of breakpoints grows quickly with the number of item types, so the bound is only computed automatically when there is a single bin type and at most 50 items. It can be forced with --use-dual-feasible-functions 1 (CLI) or use_dual_feasible_functions (Python).

Source files

  • src/box/dual_feasible_functions.hpp, src/box/dual_feasible_functions.cpp

References: