0

I have an optimization problem and I was wondering where to start from to be able resolve it. I think it can be solved with an NP-complete algorithm but I am not sure where to start from. The problem is the following:

  • There are N types of different colored same-size rectangles that have to be printed.
  • For each type there is a minimum count that has to be printed.
  • Arranging them on a printing plaque costs X amount of money, each piece of paper printed costs Y amount of money.
  • They are all the same size so the maximum amount of rectangles on piece of paper is given as an input, of course you can arrange less than the maximum amount.
  • There could be more pieces printed than the minimum amount required.

What is the best way to combine the rectangles having the given input of types and count and prices for arranging and printing so the amount of X + Y to be the lowest?

Where should I start with this one, it really sounds like an NP problem where I try all the combinations of pieces of paper and record the best outcome.

ziGi
  • 135
  • 5
  • 5
    If your problem is NP-complete, that means that (as far as we know) **any** solution yoyu could come up with would take exponential effort. So you might as well forget about clever strategies and just program the dumb brute-force method of enumerating every alternative. (If you **don't** need a *correct* solution, i.e. approximations are ok, then it's a different matter.) – Kilian Foth Jan 15 '16 at 14:08
  • Thank you for your comment, I am not sure how to approach it and if there are any similar algorithms with solutions that I can check for reference, that would give me some idea how to write it. If I knew for sure that it is NP-complete I would have not asked. – ziGi Jan 15 '16 at 14:11
  • Just to confirm, you __have__ to print all N pieces? And want to minimize the total cost, based on optimizing the combination of how your items fit onto the printing plaque(s)? I edited this a bit too to make it more clear what your constraints are. – enderland Jan 15 '16 at 14:13
  • Yes, that is correct, there should be at least the minimum amount of each N types printed, since there is a different amount for each type. Do you know of any similar problems solved so far so I can take a look how it has been done? – ziGi Jan 15 '16 at 14:16
  • 3
    What "arranging them on a printing plaque" consists of? What exactly determines how many times this arranging needs to be done? – COME FROM Jan 15 '16 at 14:23
  • Your question is pretty unclear. For example, you did not give any information how X is calculated. Why not post an example, maybe including a drawing? – Doc Brown Jan 15 '16 at 14:26
  • @COMEFROM I just added it to the description. They are all the same size so the maximum amount of rectangles on piece of paper is given as an input. – ziGi Jan 15 '16 at 14:26
  • @DocBrown the price per piece of paper, arranging them on the paper, the maximum amount of rectangles on a piece of paper, and the types of rectangles and their respective amounts are all inputs – ziGi Jan 15 '16 at 14:28
  • A picture would tell us more than 1000 words. And sorry, I have no clue how X is calculated, from your current description. The only thing which is clear is that X is **not** an input. – Doc Brown Jan 15 '16 at 14:32
  • Doc Brown, the changing of a plaque that arranges those pieces of paper costs X amount of money which you give as an input to the applicaiton. The Y is the price for each paper printed, meaning that if you make 3 types of arrangements and you print 5000 pieces of paper in total, then the result would be 3 * X + 5000 * Y – ziGi Jan 15 '16 at 14:35
  • 1
    I must have read this question a dozen times and I'm still no clearer. But then it is Friday... :-/ – Robbie Dee Jan 15 '16 at 16:05
  • I don't get it, and you still did not add any picture after 3 day. Voting to close as unclear. – Doc Brown Jan 18 '16 at 14:29

2 Answers2

3

What you are trying to do is variation on a Bin packing problem. Effectively you are placing items into bins (plaques) and trying to minimize the wasted space, since in your example wasted space directly corresponds to lost money. The wikipedia article shows how this can be done/solved.

You may end up with an optimization problem on top of this, because you also have a variable number of items to be placed. In this case you would have a bin packing problem embedded in an optimization loop, running multiple bin packing problems attempting to find the optimal profit that satisfies your constraints.

enderland
  • 12,091
  • 4
  • 51
  • 63
  • Sounds like a legit answer, I will read more on the topic and try to come up with a resolution. – ziGi Jan 15 '16 at 14:29
  • You might also look at the related cutting stock problem. And more specifically at works that investigated minimisation of the number of setups. A typical approach for those problems is branch and price https://en.m.wikipedia.org/wiki/Branch_and_price. For a paper on setup minimization you might look at http://www.math.tu-dresden.de/~capad/PAPERS/03-pmp.pdf – Renaud M. Jan 15 '16 at 14:38
  • 2
    Given that every discrete optimization is a "variation on the Bin packing problem" if you blur your eyes enough, I'm not sure this is helpful. I certainly don't agree that the "wikipedia article shows how this can be done." The statement, "You may end up with an optimization problem on top of this," is confusing. Bin packing _is_ an NP-hard optimization problem. – Corbin March Jan 15 '16 at 15:46
  • Thank you for the comment, I am still wondering about it, since I am not really good with algorithms, to me it sounded also like something that can be resolved with Dynamic Optimization but it also looks like a bin packaging problem – ziGi Jan 15 '16 at 16:08
1

I did a stint at a huge printing company. I believe we ran into the same problem. Let me rephrase it. The constraints:

  • An industrial printing plate costs X dollars to layout and fabricate. It's not an insignificant amount.
  • Each printed sheet costs Y dollars. It's a smaller number but can add up.
  • There are N unique "rectangles" to print. For the sake of explanation, we can say they're different colors, but really they're just different pages of a magazine, different letters, different posters, or whatever.
  • You can layout these rectangles on any number of plates in any configuration you wish. Just keep in mind that plates cost money and it's complicated to keep track of the numbers of rectangles printed when they're on more than one plate.
  • You need a certain number of each rectangle. Given the complications of laying out plates, you'll likely print a few too many. But you can never print too few.

It's not obvious, but these givens provide a system of linear equations:

(# of plates * plate cost) + (# of sheets * sheet cost) = total cost
# of red rectangles >= min red
# of blue rectangles >= min blue
# of yellow rectangles >= min yellow

# of red rectangles = sum(
    # of red rectangles on plate p * # sheets printed from plate p)
# of blue rectangles = sum(
    # of blue rectangles on plate p * # sheets printed from plate p)

etc...

So... all you need to do is solve the system of linear equations to minimize total cost. Easy, right? Not really. Solving linear systems is a big topic and no less NP-hard than any other optimization. To give you an idea of how big:

To be honest, the topic is too big for a Q&A. My hope is that seeing it as a linear system might give you an entry point, but the truth is that it's pretty complicated stuff. Without some in-house expertise, you may need to settle for "good enough". If your project has a little money available, consider bringing in a consultant for a short time.

Corbin March
  • 8,104
  • 3
  • 37
  • 39