I am working on an algorithm for optimizing the costs of a printing company by solving a problem they face. The problem is similar to knapsack problem but with a twist, instead of minimizing the number of containers to fit the content, we need to optimize the number of unique containers that we need to use. The problem is that the printing company first needs to design and develop printing plates which are then used for printing sheets. Printing sheets are cheap but printing plates are expensive so the company has to minimize the number of plates that they need to create inorder to achieve the desired outcome. In simple terms, there are X different types of stickers that need to be printed in some quantity. Each printing plate can accomodate N stickers. We need an algorithm that can calculate the minimum amount of plates we will need inorder to print the given stickers (A printing plate can be used infinite times to print a sheet). A simple unoptimized approach to this is to create X printing plates and accomodate N number of stickers in each plate i.e if plate size is 10 and there are 2 different types of stickers and we need to print A(200) and B(300), we can simply create 2 plates, 1st one with 10 A stickers and second one with 10 B stickers and then we can print them according to required quantity (20 sheets for plate 1 and 30 sheets for plate 2). However, a better approach would be to use 1 plate with 4 A stickers and 6 B stickers and then print 50 sheets to achieve the required quantity.
When plate size = 10 and required quantities = {A: 200, B: 300}
Unoptimized Approach:
_________ _________
|A|A|A|A|A| x 20 |B|B|B|B|B| x 30
|A|A|A|A|A| |B|B|B|B|B|
--------- ---------
Optimized Approach:
_________
|A|A|A|A|B| x 50
|B|B|B|B|B|
---------
Any help would be greatly appreciated!
My first bruteforce approach to this problem was to sort the stickers by their required quantityand then calculate their ratios and assign them to a printing plate based on their ratios and then print them until the smallest quantity becomes 0 or negative (printing extra sheets can be a wastage but its not that big of a deal in small amounts). However, this didnt give an optimal answer and therefore, now i am stuck. Tried to search for similar problems but could'nt find any. Tried asking an LLM but it always answered with generic knapsack problem approach.
It can be expressed as an integer programming problem to be solved by tools like OR-Tools, although the constraints of LP like:
mean two things: 1. You have to presume the maximum number of plates because of (F) and 2. You cannot explicitly model "number of sheets printed from plate" to multiply by "number of slots on plate with sticker type t" because of (M).
The trick to model around this is to have a separate variable for each triple of {plate, slot, kind of sticker} with the value v meaning "I need v stickers of particular kind printed from this slot. For example the optimized approach from your question would be:
Slot: 0 1 2 3 4 5 6 7 8 9
A 50 50 50 50 0 0 0 0 0 0
B 0 0 0 0 50 50 50 50 50 50
and the plate would have to print 50 sheets because that's the maximum over individual slots.
Obviously this requires some constraints to avoid trying to print multiple different kinds of stickers from a single slot. Fortunately this is expressible in integer programming.
Also in reality you print the same number of stickers from each slot. Fortunately this just means that for a particular plate you need to print m sheets from it where m is the maximum of the vars from all slots - the cost function has to account for this though.
Now for the trick to prevent same slot being used for different kind of stickers. The first part is to introduce a set of shadow integer variables, one for each v, each having a value in the range [0..1].
Now if we add a set of constraints like v[p,s,k] < b[p,s,k] * 1000000 we express that a particular v can be non-zero if and only if the corresponding b is 1. Now we can just add a per-slot constraint that the sum of the b is at most 1, which in turn makes it possible to only one v be non zero for each slot in each plate.
Obviously there also need to be constraints expressing that the sum of vs over all plates and slots for each kind of sticker produces the required number of stickers but this is straightforward.
For the objective function we need number of used plates, which again can be solved with a "boolean" type of variable one for each plate.
I have coded a PoC for this using OR-tools and it seems to work, although three plates and [20000, 500, 500] for stickers takes 8 seconds to produce first plate with A*10 printed 1600 times, second one with A*8, B,C printed 500 times. On larger instances it seems to quickly converge on the optimal or near-optimal solution but takes forever to "prove" it's optimal.