# Minimize number of pieces required to cover distances, with overlap

The specific optimization problem I'm trying to solve is this:

1. Find the minimum integer number of $$2$$m pieces required to cover $$2$$ or $$4$$ distances of length $$D$$ given that adjacent pieces must have an overlap of $$50$$mm. Pieces may be cut and distributed as desired, e.g. if one and a half pieces are required to cover one distance the remaining half piece can be used in covering the rest of the distances.

Somewhat more generalized, and a bit more interesting, I think the problem can be stated as follows:

1. Find the minimum integer number of pieces of length $$L$$ required to cover $$N_D$$ distances of length $$D$$ given that adjacent pieces must have an overlap of length $$M$$. Pieces may be cut and distributed as desired.

Even more generalized:

1. Find the minimum total length of pieces of lengths $$\{L_1, \dots, L_m\}$$ required to cover the distances $$\{D_1, \dots, D_m\}$$ given that adjacent pieces must have an overlap of length $$M$$. Pieces may be cut and distributed as desired.

I have unsuccessfully tried to map it onto one of these standard optimization problems: Cutting stock problem, Bin packing problem, Subset sum problem

I'm rather inexperienced in optimization theory, so I may be missing even something obvious though.

Although it does not map exactly to a "classical" 1-D cutting stock problem, you can approach your problem the way you would approach a 1-D cutting problem. Here is one possible formulation (assuming a single length $$D$$ for items to be covered). The term "piece" here means a portion of material cut from a stock item. I assume it is okay for the covering pieces to extend a little beyond the end of the item being covered.

Problem parameters:

$$L=$$ length of a unit of stock

$$D=$$ length of each item to be covered

$$N_{D}=$$ number of items to be covered

$$M=$$ required overlap of adjacent pieces covering one item

Patterns:

$$\mathcal{P}=$$ set of patterns

$$\mathcal{K}=$$ set of possible piece lengths

$$\pi_{k,p}=$$ number of pieces of length $$k\in\mathcal{K}$$ obtained from one instance of pattern $$p\in\mathcal{P}$$

All patterns $$p$$ satisfy the requirement $$\sum\limits_{k\in\mathcal{K}}k\cdot\pi_{k,p}\le L$$.

Variables (all nonnegative integers):

$$x_{p}=$$ number of stock units cut using pattern $$p\in\mathcal{P}$$

$$y_{k}=$$ number of pieces of length $$k\in\mathcal{K}$$ produced

$$z_{k,t}=$$ number of pieces of length $$k$$ used to cover item $$t\in\left\{ 1,\dots,N_{D}\right\}$$

Model: \begin{align}\min&\quad\sum_{p\in\mathcal{P}}x_{p}\\\text{s.t.}&\quad y_{k}=\sum_{p\in\mathcal{P}}\pi_{k,p}x_{p}\quad\forall k\in\mathcal{K}\quad(\text{production of smaller pieces}) \\&\quad\sum_{t=1}^{N_{D}}z_{k,t}\le y_{k}\quad\forall k\in\mathcal{K}\quad(\text{consumption of smaller pieces})\\&\quad\sum_{k\in\mathcal{K}}k\cdot z_{k,t}\ge D+M\left(\sum_{k\in\mathcal{K}}z_{k,t}-1\right)\quad\forall t \in \{1,\dots,N_D\}\quad(\text{coverage and overlap requirements})\end{align}

If you can enumerate all possible patterns, solving this model should provide an optimal solution. If enumerating all patterns is not feasible, you can try branch-price-and-cut, or use a heuristic similar to the Gilmore-Gomory heuristic for the "standard" 1-D problem. For a GG-like heuristic, you start with a set of patterns sufficient to get the job done, relax the integrality constraints, solve the LP relaxation and use dual values to tell you what additional pieces of each size might be worth. Then solve a separate pattern-generating problem (basically a knapsack problem) to look for a new pattern. Add it to the LP relaxation, iterate until you do not find a new pattern, then restore the integrality restrictions and optimize.

For performance reasons, you might want to add symmetry-breaking constraints. (Given any feasible solution, permuting the indices $$t$$ for the items being covered produces a different solution with an identical consumption of stock.)

• Thank you for your answer! I don't have the sufficient knowledge and understanding to decide if it's a good one, but given the number of upvotes I'll mark it as accepted nevertheless. On another note: Unfortunately, it seems the project budget is not large enough to look further into this matter. – Martin Stålberg Dec 18 '19 at 12:03