0
$\begingroup$

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.

The Problem

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:

Limits

  • 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.

Goals

  1. Minimize (optimize) the number of knapsacks first.
  2. Distribute the items as equally as possible such that no backpack is lighter or heavier than it should be.

Considerations

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.

Notes

The weights can be rounded to integers if that helps.

$\endgroup$
  • 2
    $\begingroup$ I'm afraid this is not how computer science works. It's not that we have 1001 "types" of problems and the way to solve a problem is necessarily to just figure out which of those types it is and then boom you're done. Why do you care what you call or what type it is? Usually you'll get better answers by asking about your ultimate goal (e.g., for an algorithm for it) rather than asking for a name/type. In the former case, there's 2 ways to win: either someone gives you an algorithm; or someone points you to literature on the topic. In the latter there's only 1 way to win. $\endgroup$ – D.W. Sep 7 '16 at 21:21
  • $\begingroup$ Perhaps there are some politics behind this question that aren't purely part of the problem. The nature of this problem may change on me in the coming days because I'm solving this problem for/with a coworker and he is having trouble formulating the problem. Knowing what type of problem this is allows me to explore down the right path without having to get into the dirt of a solution in case they change it on me. I know how how to write a quick algorithm that would brute force a solution. But I'm not interested in a solution at the moment. $\endgroup$ – toshiomagic Sep 7 '16 at 21:43
  • 1
    $\begingroup$ Real problems can usually modelled in different ways. One person comes up with a packing version, another with a cover version, and yet another person with some graph problem. One may even turn out to be sneaky and write down a linear/integer program. This "type of problem"-thinking doesn't get you as far as you think it does. $\endgroup$ – Raphael Sep 8 '16 at 7:21
1
$\begingroup$

There's no special "name" for this problem that I'm aware of. Don't assume that problem specifications this specific will necessarily have a "name" or "type".

Instead, it's simply one of many problems that can be solved straightforwardly with dynamic programming. You fill in an array $A[1..n]$, defined as follows: $A[i]$ is the minimum number of power supplies needed to provide power to sections $1,2,3,\dots,i$. Then there is a simple recurrence for $A[i]$ that allows you to fill in the entire array in $O(n)$ time, namely,

$$A[i] = 1 + \min \{ A[j] : 10-i \le j < i \text{ and } P(j,i-1)\}$$

where $P(j,i-1)$ is true if a single power supply can power sections $j,j+1,\dots,i-1$ simultaneously.

This allows you to compute the minimal number of power supplies needed.

Then, once you know this number, you can know optimize things to find the most equal distribution of power. Let $k$ denote the number of power supplies, and $\mu$ denote the average power per supply when using $k$ supplies. Given a constant threshold $t$, you can determine whether there exists a way to power all sections using $k$ power supplies such that every power supply's power consumption falls in the range $\mu-t \dots \mu+t$, using similar methods. Now use binary search on $t$ to find the minimal $t$ such that this is possible. This will give you the solution to your problem.

In general, computer science provides many techniques that can be combined in creative ways to solve problems. When you have a new problem with multiple specific requirements, you might have to look for how to apply those techniques in a way specific to your particular situation; there's no guarantee that it will fall cleanly into some existing "category" or "type".

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.