optimcut

Simple library to optimize leftovers from cutting slices from longer material pieces in one dimension - so called Cutting Stock Problem.

Annealing

Currently used, however may be not precise (gives 'locally' optimal solution and can never reach 'global' optimum).

Advantages and drawbacks

simpler algorithm -> less code storage requirements (could be the case while working with microcontrollers)

better memory efficiency

Algorithm

We assume that slices are cut in certain order and while material piece is too small for the next cut slice is moved to the next material piece.

Annealing algorithm randomly swaps two slices and decides if swap is accepted with acceptance probability depending on the amount of leftovers.

Swaps are repeated many times sampling different configurations of cutting the slices. This kind of 'random walk' in the space of configuration is concentrated 'near' the points with locally smallest cost function (this function could be simply length of leftovers) and gives high probability of visiting best configurations.

Acceptance probability is given by

$$P_{acceptance} = \exp\left[ \frac{fi - f{i+1}}{T} \right]$$

$f_i$ - cost function value for configuration in $i$-th step of algorithm

$f_{i+1}$ - cost function value for configuration in the next step

$T$ - parameter regulating acceptance probablity (usually called 'temperature')

The form of acceptance means that in every case while new configuration is better than before swapping slices we accept new configuration ( $f_{i+1} \leq f_i ~\implies~ P_{acc} \geq 1$ ), however while new configuration is worse we accept it with some probability ( $f_{i+1} > f_i ~\implies~ P_{acc} \in (0,1)$ ).