5

I am busy writing a program which determines the correct length and force on steel cables when hanging objects from the ceiling. One of the features is that it calculates the correct length, but I would like to add a feature which tells you which cables you should use if you only have fixed cable lengths.

For instance if you want to achieve a cable length of 220 feet, but you've only have fixed length of 250, 200, 100 and 75 feet.

I could write a sequence which just calculates all possible solutions with the answers. Similar to this:

250 = too long by 30 feet 
200 = is too short by 20 feet 
200 + 75 = too long by 55 feet 
100 + 100 = the same as 200 but 2 cables instead of 1
100 + 75 = too short by 45 feet 
100 + 75 + 75 = the same as 250 but 3 cables instead of 1
75 + 75 + 75 = too long by 5 feet but the closest one.

In this example I left out that connecting two cables will add a small fixed length to the total sum.

I would like to calculate the combination of cables with the least number of cables and the smallest error. Like the 3x 75 feet cable as solution in the example above. So the first criterion is smallest error and the second is the least number of cables with this small error.

Is there a mathematical way of doing this because for this example I only used a few lengths but in my program there will be +/- 25 cable lengths.

I've searched the internet and it is an optimization problem, but I don't know where to start. So hopefully someone here can point me in the right direction.

Thank you for your help!

Lord_Farin
  • 17,743
patrick
  • 151
  • 2
    How many cable lengths will there be? If it's less than, say, 20, then your method is probably the best practical solution. If it's much more than 20, then it starts to become a hard problem. A provably hard problem. – TonyK Jan 04 '13 at 22:33
  • 2
    Your criteria aren't clear to me - you want to minimise the number of cables of the error? Anyway, it looks similar: http://en.wikipedia.org/wiki/Knapsack_problem – savick01 Jan 04 '13 at 22:58
  • @TonyK: The amount of cables will be +/- 25 so you would advice to use the brute force method? Thank you for your advice! – patrick Jan 05 '13 at 12:23
  • @savick01: The knapsack problem has two variables for instance the price and weight. I've tried to explain my question in more detail hopefully it is more clear. Thank you for your advice! – patrick Jan 05 '13 at 12:23
  • With 25 cables, there are at most 32 million possibilities, even using the very simplest algorithm. This should be doable in a few seconds on a PC, and with a few clever optimisations, it should take less than a second. Is this acceptable? – TonyK Jan 05 '13 at 15:43
  • @patrick Yes, now it is clear. If you put some restrictions it is exactly knapsack problem - say, you don't allow cables longer than the target length and you don't care about the number of parts. Then if you put price=weight=length, you get exactly knapsack problem. If you also want to minimise the number of parts, you put $price=length-\varepsilon$. – savick01 Jan 05 '13 at 16:04
  • You can deal similarly with the second case (only cables longer than the target length are allowed) to get the complete solution. However it may not be effective (if we can talk about effectiveness here;) – savick01 Jan 05 '13 at 16:10
  • 1
    @TonyK: 1.) It is not a 0-1-knapsack problem. In the example the solution consists of 3 cables of length 75. Therefore more than 32 millions of possibilities have to be checked. 2.) The two list algorithm from 'Horowitz, E., and S. Sahni, Computing Partitions with Applications to the Knapsack Problem, Journal of the A.C.M., Vol. 21, No. 2, April 1974, pp. 277-292' needs some space but will perform a lot faster then your proposed exhaustive search algorithm. – miracle173 Jan 05 '13 at 16:17
  • This is not identical to the knapsack problem, but essentially the same pseudo-polynomial time dynamic programming algorithm will still work here. (This may be the same algorithm in @miracle173's link, I haven't checked; it's just "the obvious" dynamic programming solution.) –  Jan 05 '13 at 22:31

2 Answers2

3

Let the cable lengths be distinct positive integers $l_1 \lt l_2 \lt \ldots \lt l_n$ for $n \approx 25$. Let $t; s_{l_1}, s_{l_2}, \ldots, s_{l_n}$ be formal variables. The monomials in the formal series expansion of

$$\prod_{i=1}^n \frac{1}{1 - s_{l_i} t^{l_i}} = \prod_{i=1}^n \left(1 + s_{l_i} t^{l_i} + s_{l_i}^2 t^{2l_i} + \cdots\right)$$

are of the form $t^k s_{l_1}^{k_1}s_{l_2}^{k_2}\cdots s_{l_n}^{k_n}$ where $k = k_1 l_1 + k_2 l_2 + \cdots + k_n l_n$. Each such monomial encodes one distinct way in which $k_1$ cables of length $l_1$, $k_2$ cables of length $l_2$, ..., and $k_n$ cables of length $l_n$ can be combined to form a length of $k$. Thus, if we ignore all powers of $t$ less than the targeted cable length (call it $N$), the lowest remaining power $\hat{N}$ tells us how close we can come to equalling or exceeding $N$ with a combination of cables and its coefficient, which is a polynomial in the $s_{l_i}$, describes all the distinct ways of attaining $\hat{N}$. Among these ways we would choose a monomial of smallest total degree (in the $s_{l_i}$).

For instance, consider the $25$ (randomly selected) lengths $$\{12,25,30,32,37,54,68,69,102,106,111,112,115,122,\\128,129,130,144,149,153,154,165,170,189,203\}.$$

We can quickly compute the power series using convolutions. Here is a Mathematica implementation. (It computes powers up to $250$ in order to find a solution for $N=220$. The $250$ can be replaced by any known upper bound on $\hat{N}$, but the smaller it is, the less work has to be done.)

f[n_Integer, m_Integer, maxPieces_: 4] := With[{k=Min[maxPieces, Ceiling[m/n]]}, 
   1 + Sum[( Subscript[s, n] t^n)^i, {i, 1, k}] + O[t]^(m + 1)];
pieces = MonomialList[Expand[Normal[Product[f[i, 250, 3], {i, lengths}]]]]

(The definition of f includes a limit maxPieces on the number of pieces of the same size one would want to use: it expedites the calculation. It also limits the calculation to a maximum power m, because in practice powers much larger than $N$ will not be needed.)

The rest is a matter of finding $\hat{N}$ and the solution by means of sorting and inspection:

solutions = Select[pieces, Exponent[#, t] >= 220 &]; 
degree = Min[Exponent[#, t] & /@ solutions];
best = Select[solutions, Exponent[#, t] == degree &];

One such solution in this example is

best[[First[Ordering[Exponent[# /. Subscript[s, _] -> s, s] & /@ best]]]]

$t^{220} s_{12} s_{54} s_{154}$

indicating that $220$ feet can be attained by combining cables of $12, 54$, and $154$ feet. (The fact that we found a three-piece solution with $\hat{N}=N$ justifies limiting the expansions in the power series to just three terms; because we found a solution with no duplicated lengths, we could have limited the expansions to just the first term in each, $\prod_{i=1}^n \left(1 + s_{l_i} t^{l_i} \right)$.)

The other ways to attain $220$ can be found by inspecting the rest of best:

SortBy[best, Exponent[# /. Subscript[s, _] -> s, s] &]

$$t^{220} s_{12} s_{102} s_{106},t^{220} s_{54}^2 s_{112},t^{220} s_{37} s_{68} s_{115},t^{220} s_{30} s_{68} s_{122},t^{220} s_{37} s_{54} s_{129},t^{220} s_{30} s_{37} s_{153}, \\ t^{220} s_{12} s_{54} s_{154},t^{220} s_{25} s_{30} s_{165},t^{220} s_{25}^2 s_{170},t^{220} s_{30} s_{54} s_{68}^2,\ldots $$

Seeing these other solutions enables one to implement auxiliary objectives. For instance, if you prefer longer cables to shorter, the second solution with two $54$-foot cables and one $112$ foot cable would be best.

Total timing (as elapsed, using one 3.33 GHz Xeon core) for all these calculations was a quarter second.

If you don't want to implement symbolic convolutions of power series, you can forget about the $s_i$ and just compute the power series without them: this is a numerical convolution, which is relatively easy to code and extremely fast. The smallest power greater than or equal to $N$ is, as before, $\hat{N}$; this time its coefficient--an integer--indicates how many distinct ways these lengths can be combined to find $\hat{N}$. At this point a recursive greedy algorithm would likely work well: that is, assume the longest cable length $l_n$ will be used and recursively find the best solution for $\hat{N}-l_n$. If there is no such solution, try instead to use $l_{n-1}$, etc.

whuber
  • 8,531
  • +1, but I think the question asks for the $\hat N$ closest to $N$, whether higher or lower than it. –  Jan 05 '13 at 22:34
0

It is the special form of an integer programming problem the unbounded knapsack problem:

$$\text{minimize} \sum_{i=1}^n x_i \quad \text{subject to} \sum_{i=1}^n l_ix_i \geqslant L, \quad x_i \in \{0,1,\ldots\}$$

where $L_i$ are the possible cable lengths and $L$ is the length you have to approximat. In the wikipedia article the problem is formulated the following way

$$ \text{maximize} \sum_{i=1}^n v_ix_i \quad\text{subject to} \sum_{i=1}^n w_ix_i \leqslant W,\quad x_i \in \{0,1,\ldots\}$$

Both are the same if you set $v_i=-1$, $w_i=-l_i$ and $W=-L$.

You can try to solve your problem using a version the dynamic programming algorithm that uses $min$ instead of $max$.

miracle173
  • 11,049