GuillotineModels.Flow

build_model(::Val{:Flow}, model, d, p, l, w, L, W, [options])

The Flow model is a variant of the PPG2KP model using flow constraints. The result is a considerably larger model with a slight enhancement on the relaxation bound.

Arguments

The required arguments are the same as all build_model methods, and the optional argument options is always ignored.

High-Level Model Description

Both length and width of the original plate may be seen as line segments. From these line segments, let us just consider a subset of the points: the first point (zero), the last point (L or W), and the ones in the middle that match a normal cut position.

For each width cut position, there is an instance of the length point set representing plates with all possible lengths but with a fixed width. The analogue (each length cut position ... width point set) also exists. Each of these point set instances is the vertex set of a strongly connected directed graph. There are no edges connecting one of such graphs with another (they interact by special constrainsts that cannot be seen as 'flow constraints'/edges).

The variables of the model are the edges between those graphs. The edges are may be divided into forward edges and backward/circulation edges. The forward edges go from a node representing a point closer to the start of the line segment to a node representing a point farther from the start. The backward/circulation edges always go from a non-first (non-zero) point to the first/zero point of the graph. The forward edges represent cutting part of the plate for use or trimming. The backard edges represent the availibity of a plate of some dimensions to be cut in some orientation. For example, if there are two units of flow flowing through a forward edge that goes from point length 15 to point length 35 of the set with fixed width 50, then there are at least two plates of width 50 that have a subplate of length 20 (and width 50) cut from two parallel cuts, one in position 15 and another in 35. The two parent plates may have the same dimensions (i.e., their length is also equal to each other), or they may have different total length (they only share the same width); for an example, one of them may stop at length 35 and the other may have length 1000. Considering this same example, if there are a plate of size 35x50 and another of size 1000x50 available, then there is one of flow in the backward edge from point length 35 to point zero and from point length 1000 to point zero (all inside the set with fixed width 50).

Finally, forward edges may be subdivided into waste edges, piece edges and subplate edges. Waste edges do nothing besides letting the flow pass through them. The variables representing piece edges are in the objective function with coefficient equal to the profit of the corresponding piece. Subplate edges "introduce" new flow in the system, they do not only allow the flow to pass through them but also increase the flow in a correspondent circulation edge of the (other) graph that represents the plate they are extracting, but to be cut in the opposite orientation. For example, an increase in the flow of the subplate edge from length 50 to length 150 of the set with fixed width 200 will increase by the same amount the flow of the backward edge from width 200 to width zero of the set with fixed length 100.

The number and dimension of the original plates available is given by all backward edges that have their value fixed to a non-zero value a priori.

Slightly Misleading Low-Level Explanation

Variables

• edge[i]: Positive Integer. The only variable. Measures the amount of flow passing through the edge. Has all edges indexed by their globalized index. Uses the many reverse indexes created by the enumeration process to build the model.

Objective function:

Maximize the profit of the pieces cut.

sum(p[CP] * edge[1:number_of_pieces])

Constraints

• There is exactly one of the original plate, so its circulation arc is available since start, and cannot ever go over one. It must be one.
  • sum(edge[is the backward edge of the original plate]) == 1
• The flow must go round.
  • sum(edge[all edges ending in node x]) == sum(edge[all edges starting at node x]) : for every node x
• If you cut a subplate anywhere then you allow its flow to circle again.
  • sum(edge[a backward edge]) <= sum(edge[a forward edge that cuts the subplate corresponging to that backward edge]) : for each backward edges
• The number of pieces of some type is always less than or equal to its demand.
  • edge[i] <= d[i] : for each i in 1:number_of_pieces

Dummy Plate Identifiers:

• 0 - No plate. Waste and backward edges use this value in the back field.
• 1:n - A dummy edge corresponding to a piece index, used in the objective function. Edges cutting pieces do not actually appear in the objective function but, in fact, allow more flow to pass through by some of these dummy piece edges.
• n+1 - A dummy edge that is upper bounded at one and allows one extra flow to the original plate default cutting (vertical) backward edge (i.e., n+2). Necessary to avoid n+2 to be restricted by a possible edge that cuts the whole original plate alternative cutting (horizontal). In other words, without this, if a piece has the same length as the plate, then the model has a deadlock problem, and will give a zero objective problem.
• n+2 - The original plate default cutting (vertical) backward edge.
• n+3 - The original plate vertical forward edge that takes the whole plate and allows it to be horizontally cut (i.e., allow flow to n+2).
• n+4 - The original plate alternative cutting (horizontal) backward edge. It is allowed by cutting n+2.
• n+5:m - The remaining intermediary plates.