tl; dr: I have a problem when I have a Boolean circuit and need to implement it with very specific single-threaded primitives, so SIMD calculation after a threshold is much cheaper. I try to optimize the implementation.
In detail, the input is a combinatorial Boolean circuit (so no loops, states, etc.). I implement it in software with a rather unusual set of primitives, so that:
- Logical gates must be calculated individually, since the "engine" is single-threaded
- NOT gates are free
- AND, OR, XOR costs 1 (eg 1 second)
- N identical gates can be evaluated simultaneously at a price of 10 plus a small proportional term (eg, a stack of 20 different AND gates in 10 seconds, 50 different XOR gates in ~ 10 seconds, etc.) can be evaluated.
The goal is to implement the circuit with the given primitives while minimizing costs.
What I tried
This problem is vaguely related to the problem of packing trash cans, but the differences – restrictions on the order of items and different costs for each "trash can" depending on the number of items – make me think that this is not particularly true.
I've been suggested to use integer linear programming that sounds like the best fit yet, but I'm not sure how to interpret the problem. In particular, I would use binary variables to represent if the implementation Gate / Charge M will replace the circuit Tor N, but then I do not know how to express the goals to be maximized / minimized.