GuillotineModels.PPG2KP.Enumeration

Collection of the methods used for generating the cuts and plates that make up the PP-G2KP model.

Collection of internal datastructures used to create the PP-G2KP model and needed to assemble the solution given by the values of the model variables.

• cuts::Array{Tuple{P,P,P},1} where P

  If (pp, fc, sc) is in cuts, then pp may be cut into fc and sc.

• cut_extraction::Array{D,1} where D

  If hybridize-with-restricted, has the extracted piece for each cuts elem.

• first_vertical_cut_idx::Any

  Every cut before this position is horizontal, the rest are vertical.

• np::Array{Tuple{P,D},1} where P where D

  If (n, p) is in np then plate n may be sold as piece p.

• pli_lwb::Array{Tuple{S,S,P},1} where P where S

  Indexed by a plate index, values are the plate length, width, and bound.

• d::Array{D,1} where D

  The demand of the pieces.

• l::Array{S,1} where S

  The length of the pieces.

• w::Array{S,1} where S

  The width of the pieces.

• L::Any

  The length of the original plate.

• W::Any

  The width of the original plate.

• mirror_plates::Bool

  If all plates were rotated so length is never greater than width.

discretize(d::[D], l::[S], w::[S], L::S, W::S; kwargs...) :: [S]

!!! Internal use.

Given the pieces demand, length, and width (d, l, w), as well the plate dimensions (L, W), return a vector of all linear combinations (constrained by demand) of the length of pieces that fit the plate (the returned vector is sorted by increasing value and no value is greater than L). To discretize the width just swap l with w and L with W.

Keyword arguments

All keyword arguments are of type Bool and have false as default.

• only_single_pieces: Instead of discretizing the length, return the piece lengths that exist only as the length of a piece and not as the combination of two or more smaller piece lengths.
• ignore_W: Do not use W to exclude pieces that do not fit the plate.
• ignore_d: Do not use demand information to discretize (consider an unlimited amount of each piece type available).

filter_symm_pos(disc, dim, disc_copy = copy(disc)) -> disc_copy

!!! Internal use.

Implement the symmetry-breaking described in Section 2.1 of 10.1287/ijoc.2016.0710 (just after equation 10). Given a list of discretized lengths (or widths) disc and the plate length (or width) dim, return a copy of disc without all positions i in which disc[i] > div(dim/2) \land (\exists. disc[j] == dim - disc[i]).

fits_at_least_one(sllw, L, W) :: Bool

!!! Internal use.

True if at least one piece in sllw fits inside a LxW plate; false otherwise.

gen_cuts(::Type{P}, d, sllw, L, W; [kwargs])

!!! Internal use.

The main method responsible for generating all the cuts used to create both the original PP-G2KP model as its enhanced version (in this case, it generates the piece extractions too).

Arguments

Positional and required arguments

1. ::Type{P}: The type of the piece profits (and area).
2. d::Vector{D}: The pieces demand.
3. sllw::SortedLinkedLW{D, S}: The SortedLinkedLW containing the length and width of the pieces.
4. L::S: The plate length.
5. W::S: The plate width.

Keyword arguments

All keyword arguments are of type Bool.

• ignore_2th_dim: Default: false. Ignore the dimension not being discretized during discretization.
• ignore_d: Default: false. Ignore the demand information during discretization.
• round2disc: Default: true. Round the size of the second child of a cut to a discretized position.
• faithful2furini2016: Default: false. Tries to be the most faithful possible to the description in 10.1287/ijoc.2016.0710.
• no_redundant_cut: Default: false. Disables the Redundant-Cut reduction described in 10.1287/ijoc.2016.0710.
• no_cut_position: Default: false. Disables the Cut-Position reduction described in 10.1287/ijoc.2016.0710.
• no_furini_symmbreak: Default: false. Ignored if faithful2furini2016 is false. Disables the symmetry-breaking used in 10.1287/ijoc.2016.0710 (consequently all discretized positions are used, none is removed).

Return

The return is a ByproductPPG2KP object.

no_chance_to_fit_6_piece(d, l, w, a, L, W, A; ignore_2th_dim = false)

Returns true if it is demonstrably impossible to fit six pieces into the plate; and false if there is some possibility (but no guarantee) of fitting six pieces in the plate.

If ignore_2th_dim is true, w and W are ignored by the algorithm.

reduce2fit_usl(sl, sli2pii, w, L, W) :: [S]

!!! Internal use.

Given a plate (L, W), and the pieces sorted by length (sl, sli2pii, w), return an increasing vector of unique lengths that pertain to a piece that fits the plate. If two or more pieces share length and fit the plate, only one copy of that length is included in the returned vector.

Arguments

1. sl::Vector{S}: The piece lengths sorted by increase-or-stay order.
2. sli2pii::Vector{D}: If sli2pii[i] == j then sl[i] and w[j] correspond to the same item.
3. w::Vector{S}: The piece widths (in 'original' order).
4. L::S: The length of the plate.
5. W::S: The width of the plate.

reflect!(l, L)

!!! Internal use.

Change l to the sorted union of [li ∈ l ∧ li ≤ L÷2 | li] and `[li ∈ l ∧ li

L÷2 ∧ li < L | L - li]; assumesl` is in increase-or-stay order.

The new value of l has an important property that: any pair of plates generated by a cut using the original l will also be generated by some cut in the modified set, even with the modified set only having cuts in the first half of the plate. Note any values equal to or above L are discarded.

should_extract_piece_from_plate(pii, L, W, sllw, symm = 0x03) :: Bool

!!! Internal use.

Considering the enhanced PP-G2KP model, it is necessary to known if there will be an 'extraction' variable representing the extraction of piece with index pii from a plate with length L and width L.

A piece should be extracted from a plate if:

1. The piece fits inside the plate.
2. It is not possible to extract the piece in consideration together with any other piece (even other copy of the same piece) from the plate in consideration (for the cut orientations allowed by symm which by default are both vertical and horizontal).

Arguments

1. pii::D: The index of the piece.
2. L::S: The length of the plate.
3. W::S: The width of the plate.
4. sllw::SortedLinkedLW{D, S}: The SortedLinkedLW struct for the pieces.
5. symm::UInt8 = 0x03: which cut orientations are allowed: 0x01 means 'allow only horizontal cuts', 0x02 means 'allow only vertical cuts', and 0x03 means 'allow both kinds of cuts'.

ub_num_pieces_fit(d, l, w, a, L, W, A, cutoff; ignore_2th_dim = false)

!!! Internal use.

Given a piece set (defined by demand, length, width, and area), and a plate (defined by Length, Width, and Area), returns the min between cutoff and an upper bound on the number of pieces that fit inside the plate. If ignore_2th_dim is true, do not use w and W to filter pieces that do not even fit the plate when alone.

In other words, ub_num_pieces_fit(..., 6) will return 6 if it is possible (but not guaranteed) for 6 or more pieces to fit in the plate, and will return x if x < 6 is the greatest number of pieces that have yet some possibility of being packed together; x + 1 is already guaranteed to be impossible.