They can even come up completely outside of work. I recently had an optimization problem come up around the house that could have been straight out of an exam. Here it is:

Tzs wants to install gutter guards on his house and detached garage. His garage has two 29' straight gutters, and his house has two straight gutters of 43' and 19', and one L-shaped gutter with arms of 19' and 18'.

The guards tzs is going to use [1] are available from Home Depot in 3 ft and 4 ft sections. The 3 ft ones are sold in boxes of 13 for $79.97. The 4 ft ones are sold in boxes of 20, 10, or 3 for $139.97, $99.97, or $39.16.

To cover a gutter, you need slightly more length of guard than length of gutter. You cut off the rails on the end of the guards at the ends of the gutter, leaving a few inches of mesh that you can tuck down into the gutter to keep stuff from getting in through the ends. Assume that the section you cut off is waste.

Question 1: What boxes of guards should tzs buy to cover all his gutters for minimum cost, assuming he needs 3" of mesh at the ends to cover the sides? For the L shaped gutter, assume it effectively has 3 ends.

Question 2: The only ladder tzs has is a 6 ft step ladder. This is sufficient for installing the guards on the front side of his garage. It is not sufficient for anyplace else. To do the rest of the house, at a level of ladder safety he is comfortable with, will require buying at least one new ladder for $260, and might require a second new ladder for $129. Before committing to that, he is considering doing a test on the front of the garage.

If he buys one 13 pack and uses 10 of them on the front of garage, and then decides from there to go ahead with doing all the rest, what boxes should he then buy to finish the project taking into account the 3 leftover 3 ft segments? How much, if any, does this add to the minimum total project cost?

Question 3: the prices given earlier were actually sale prices for the 20 pack and 13 pack. If they go back to normal prices, which are $160.97 and $88.83, how does that change things?

Question 4: Due to rapidly sloping ground behind the garage, tzs has not been able to figure out a way to reach more than about half the gutter there. He is thinking of just not bothering with it. There are a lot of weeds and wildflowers and such in that area, so it doesn't really actually matter much if the gutters are clogged and the water just runs off the edge--it will just land on plants so won't erode the soil, and there is no basement or crawlspace under the garage for the water to leak into.

How do all the previous answers chance if the back garage gutter is omitted? If tzs figures out a way to actually reach the damn thing later, what will be the incremental cost to add that?

Question 5: When you cut an end segment, sometimes the waste piece can be significant. For example, suppose you have 1 ft to cover at the right end of a gutter and use a 3 ft segment. You might cut that segment 1 ft from the left end, and cut the mesh 4" to the right of that to get the mesh flap to fold over the gutter end. That leaves you with a 2ft segment with 4" of missing mesh. You could cut the rails 4.5" from the left of that (4.5" rather than 4" because the mesh needs to be slightly longer than the segment to overlap the adjacent segment). That would leave with a 1.75' segment that could be used just like any other segment.

Can you adapt your algorithm for finding minimal cost to take into account these small, usually non-integral, segments that would be produced as a by product of dealing with gutter end points?

Question 6: Can you adapt your algorithm to handle the possibility of purposefully breaking a long segment down into shorter segments, with the algorithm determining the optimal set of short segments to make? Assume that at each place you split a segment you loss 1" of total length due to the need for overlapping adjacent meshes.

[1] https://www.gutterglove.com/