I have a one-dimensional block of material. I run an analysis that divides the material into usable and unusable regions.

In a manufacturing process, said material is cut and the unusable regions are discarded. My two limitations are:

  • The factory deems any tiny usable region as unusable, since they cannot be processed.

  • The factory's cutting tool cannot cut under a minimum width, so bad regions smaller than this width need to be expanded into a good region to reach the minimum width. This is the waste I would like to minimize.

The number of regions will not go above 50

I would like to create an algorithm that optimizes these expanding bad regions and shrinking good ones by creating as little waste as possible.

E.g.: A too small bad region between a good and a too small good one could be expanded into the good one as much as possible, since that will become waste either way.

My first guess would be that this is an LP problem, but above an introductory level, I'm inexperienced with that.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.