I have a multiple knapsack problem I am trying to solve. To get the right solution, we need to ask the right question. My question is simply to identify what type of problem I have, not to solve the problem itself.
I have a theoretically large model train track with dozens of short identical trains on it. I need to buy some power supplies to power my model trains.
The track is split in to equal length sections. I have a data structure that describes the power consumption for each individual length of track based on the movement of the trains. Each length has a peak power consumption (for example, when a train needs to accelerate), and an RMS power consumption.
I need to hook my track up to the power supplies, but I can only power contiguous lengths of track for each power supply. I can't power track section 1 with power supply A, then skip track section 2 and power track section 3 with the same power supply A. I have to power either track section 1, 2, and 3, or just 1 and 2, or just 1.
There is only one type of power supply that has a peak and RMS power output limit. When looking at a combination of lengths of track, I combine their power profiles to get a new RMS and peak power for the combined section. If one of these values goes over the power supply limit, it will not work. Assume that no individual length of track on its own will violate the RMS/peak limit of a power supply.
You cannot/will not have more than 1 power supply per length of track.
You can have at most 10 lengths of track on one power supply. You cannot have 11+ lengths of track hooked up to one power supply. The cord is not long enough.
The goal is to FIRST minimize the number of power supplies (these things are expensive) I have to purchase and THEN determine the most optimal distribution of power such that no power supply is loaded significantly heavier or lighter than any other.
Another way of looking at it is:
- All knapsacks have the same capacity (10 items max).
- All items have the same volume.
- All items have different weights (densities).
- All items come in a specific order (a circuit) and must be put into a knapsack with only adjacent items.
- Minimize (optimize) the number of knapsacks first.
- Distribute the items as equally as possible such that no backpack is lighter or heavier than it should be.
I might be asking more than one question here: One about optimization and the other about the knapsack classification. Is this actually a knapsack problem since the items don't have a value/profit? Does the adjacent/contiguous limit I put on the problem make it easier or harder to solve? Should I be considering anything from graph theory because my track is like a bunch of nodes and edges? Or is that an unnecessary complication.
The question still remains: Classify the type of knapsack problem, or at least extract the correct one from the above problem statement.
Please point me in the right direction.
The weights can be rounded to integers if that helps.