GuillotineModels.PPG2KP.Heuristic

GuillotineModels.PPG2KP.Heuristic implements the heuristic needed for faithful reimplementation of the Priced PP-G2KP from `F. Furini, E. Malaguti, and D. Thomopulos, ``Modeling Two-Dimensional Guillotine Cutting Problems via Integer Programming,'' INFORMS Journal on Computing, vol. 28, no. 4, pp. 736–751, Oct. 2016, doi: 10.1287/ijoc.2016.0710.' The heuristic itself, however, is older and described in: `M. Dolatabadi, A. Lodi, and M. Monaci, ``Exact algorithms for the two-dimensional guillotine knapsack,'' Computers \& Operations Research, vol. 39, no. 1, pp. 48–53, Jan. 2012, doi: 10.1016/j.cor.2010.12.018.'

The methods exported by this module are not of general interest, you need to either want: (1) a fast but shelf-restricted heuristic for the guillotine 2D knapsack problem; (2) to check if they were implemented correctly; (3) to use them to make your own implementation of Priced PP-G2KP.

first_fit_decr(p, l, w, t, n, L, W) :: (P, [D], [[D]])

The first fit width-decreasing heuristic is a deterministic, fast, and shelf-restricted heuristic for the knapsack 2D guillotine problem.

This method is mainly called by iterated_greedy and because of this the arguments are adjusted so the method is aware it is receiving a subset of the complete piece set.

Arguments

1. p::AbstractVector{P}: The pieces profit.
2. l::AbstractVector{S}: The pieces length.
3. w::AbstractVector{S}: The pieces width.
4. t::AbstractVector{D}: The piecex type/index/identifier (index in the original piece set).
5. n::D: The number of pieces in set (necessary to build the second returned vector).
6. L::S: The original plate length.
7. W::S: The original plate width.

Returns

1. The best know value, i.e., the value of the returned solution.
2. A vector v of the same size as the number of pieces; if v[i] == x then the piece i has x copies in the solution returned.
3. A solution with the best known value, as the heuristic only consider shelf-restricted configurations the solution may be represented as a vector of vectors. Each vector is a length strip (with the width of the first piece inside, and the summed length of all pieces inside). Inside each vector the pieces are ordered by non-increasing width, and the vectors/stripes are sorted by non-increasing width too ( i.e., the width of their first element).

iterated_greedy(d, p, l, w, L, W, rng, max_iter_since_last_improv = 10^6)

The iterated greedy procedure is a heuristic that creates a random piece subset that may improve the best known value (BKV) and call the first fit with-decreasing heuristic over it (if this inner heuristic is able to position all pieces then the BKV is improved).

The first fit heuristic is deterministic and gives the same solution for a piece subset (the ordering is irrelevant), so the iterated procedure is adding diversity to it. The first fit heuristic is also shelf-restricted, so the solution is always shelf-restricted and may be impossible to reach the optimality (in the case no optimal solution is shelf-restricted).

The procedure is repeated until max_iter_since_last_improv calls to the first fit width-decreasing were made without improving the BKV.

Arguments

1. d::AbstractVector{D}: The pieces demand.
2. p::AbstractVector{P}: The pieces profit.
3. l::AbstractVector{S}: The pieces length.
4. w::AbstractVector{S}: The pieces width.
5. L::S: The original plate length.
6. W::S: The original plate width.
7. rng::AbstractRNG: The random number generator.
8. max_iter_since_last_improv::I: The parameter for the stopping criteria,

after max_iter_since_last_improv iterations since the last change in the best known value the algorithm ends.

Returns

The same of the first_fit_decr method (the iterated greedy just returns the best solution found by it).

promising_kfirst(::Type{D}, p, a, bkv, A) :: D

!!! Internal use.

Zero if there is no k for which sum(p[1:k]) > bkv && sum(a[1:k]) <= A; otherwise, return the smallest k value satisfying these conditions.

In other words, without changing the order of the given sequence, return size of the prefix of smallest size (a piece subset) that has better profit than the best known value and that it is not immediately obvious that it cannot fit the given area (does not break the naive area bound). If such prefix does not exist, then just return zero.

shelves2cutpattern(shelves :: [[D]], l, w, L, W) :: CutPattern{D,S}

Transform the third return of iterated_greedy or first_fit_decr into a CutPattern object.