<p>You could easily formulate this as a <a href="http://en.wikipedia.org/wiki/Linear_programming#Integer_unknowns" rel="nofollow">integer linear programming</a> (ILP) problem. This is a linear programming problem where the solutions are constrained to be integers. The problem is NP-hard as indicated in other answers, but software does exist to address this sort of problem.</p>

<p>Let $L$ be the ultimate length you are aiming for, $a$ be the number of
Track A used, $b$ be the number of Track B used, and so forth. Finally,
let $A$, $B$, $C$, and $D$ be the amount of each kind of track you have.</p>

<p>($a,b,c,d$ are variables; the rest are constants.)</p>

<p>Then the integer linear programming problem is formulated as:</p>

<ul>
<li>$L - 0.5 \le 3.0 a + 5.0 b + 6.5 c + 10.5 d \le L + 0.5$</li>
<li>$0 \le a \le A$ </li>
<li>$0 \le b \le B$ </li>
<li>$0 \le c \le C$ </li>
<li>$0 \le d \le D$ </li>
<li>$a,b,c,d$ are integers</li>
<li>minimise $a+b+c+d$</li>
</ul>

<p>The condition $a+b+c+d$ can be changed to what you want to minimise/maximise to suit your needs so long as 
it is linear in the variables $a,b,c,d$. The could be something capturing the costs of the various Tracks. All of the other ingredients can be changed in an obvious way, for different track lengths, different tolerance level, and so forth, so long as they are constants when you submit your question to an ILP system.</p>

<p>Plenty of software packages exist to solve such problems; many are listed on the page linked to above.</p>

CC BY-SA 2.5
2010-11-11T14:58:49.057Z
I guess you are referring to *integer linear programming*, not linear programming.
Jukka Suomela
CC BY-SA 2.5
2010-11-11T15:00:20.817Z
Indeedy. I just realised my mistake.
Dave Clarke
CC BY-SA 2.5
2010-11-11T20:45:46.787Z
“integer linear programming (LP)”?!
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-11T21:53:20.303Z
Fixed. Added one character.
Dave Clarke
CC BY-SA 2.5
2010-11-11T23:28:16.103Z
As the number of variables of this ILP formulation is bounded by the number of distinct tracks, and ILP is fixed-parameter tractable parameterized by the number of variables, this method should work very well in practice if the number of types of tracks is small.
Serge Gaspers
CC BY-SA 2.5
2010-11-11T14:51:50.250Z
2010-11-11T21:49:51.540Z
2010-11-11T21:49:51.540Z
Dave Clarke
<p>Unless I misunderstood, your problem is NP Hard in general.  You have different tracks of different lengths, and you need them to add up to a given distance.  <a href="http://en.wikipedia.org/wiki/Subset_sum_problem" rel="nofollow">Subset sum</a> reduces to your problem, so I am afraid there's little hope for an efficient algorithm in the worst case.</p>

<p>However, it does not mean the cases you care about are hopeless.  For example, if you don't have too many track sizes, you can even do brute-force search.  If you don't need a very small margin, then <a href="http://en.wikipedia.org/wiki/Dynamic_programming" rel="nofollow">dynamic programming</a> should work.</p>

CC BY-SA 2.5
2010-11-12T09:38:18.443Z
Is it still subset sum given the error margin?
Dave Clarke
CC BY-SA 2.5
2010-11-12T12:55:47.527Z
@Dave, @Lev, As I would read the question, subset sum is (forgive the terminology) a subset of this problem. In the special case where the margin is 0, it's precisely subset sum, meaning subset sum *does* reduce to this problem (and hence this problem is NP-hard). Unless the intention was a static margin of exactly [-0.5, 0.5] for all instances, in which case you would be correct...
Daniel Apon
CC BY-SA 2.5
2010-11-12T17:00:05.517Z
@Daniel: In addition, a usual convention is that the input to the Subset Sum problem is integers, which makes the static margin [−0.5, 0.5] irrelevant even if that is the intent of the question.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-12T18:44:04.003Z
@Tsuyoshi, good catch.
Daniel Apon
CC BY-SA 2.5
2010-11-11T14:36:02.757Z
2010-11-11T14:36:02.757Z
Lev Reyzin
<p>I have a list of tracks (model railroad tracks) with different length, example: TrackA on 3.0cm, TrackB on 5.0cm, TrackC on 6.5cm, TrackD on 10.5cm</p>

<p>Then I want to find out of what kind of track I should put together to get from point A to point B with a given distance and a margin. And I should also be able to a prioritizes the use of track type.</p>

<p>Example; Distance from point A to B is 1.7m, and I have lot of TrackC and few of TrackB. And I will allow a margin on +/- 0.5cm to the distance.</p>

<p>What kind of tracks should I use, and how many of each track, and how many combination do I have, sorted after the track where I have most of.</p>

<p>I have Google after some C# help using genetic algorithm, but I am lost in, how I can implement this in a good method.</p>

<p>Or just a mathematical method, that can solve my problem..</p>

<p>Please help..</p>

CC BY-SA 2.5
2010-11-11T13:36:07.327Z
So you have a set of numbers and need a subset of them to add up to a specific sum? (I'm curious what motivated you to think about this problem in terms of railroad tracks?)
Lev Reyzin
CC BY-SA 2.5
2010-11-11T14:01:09.310Z
Since you have a reasonably small total track, it should be possible to use dynamic programming to obtain an optimal solution quite quickly.  You might want to post this on StackOverflow instead if you are looking for code.
András Salamon
<ds.algorithms><optimization>
Find the right/best track combination for a given distance, using a genetic algorithm or ?.
David
# Find the right/best track combination for a given distance, using a genetic algorithm or ?.

(Asked by: username_0 on 2010-11-11)

I have a list of tracks (model railroad tracks) with different length, example: TrackA on 3.0cm, TrackB on 5.0cm, TrackC on 6.5cm, TrackD on 10.5cm

Then I want to find out of what kind of track I should put together to get from point A to point B with a given distance and a margin. And I should also be able to a prioritizes the use of track type.

Example; Distance from point A to B is 1.7m, and I have lot of TrackC and few of TrackB. And I will allow a margin on +/- 0.5cm to the distance.

What kind of tracks should I use, and how many of each track, and how many combination do I have, sorted after the track where I have most of.

I have Google after some C# help using genetic algorithm, but I am lost in, how I can implement this in a good method.

Or just a mathematical method, that can solve my problem..

Please help..

**Tags:** ds.algorithms, optimization

> **Comments:**
> **username_1**: So you have a set of numbers and need a subset of them to add up to a specific sum? (I'm curious what motivated you to think about this problem in terms of railroad tracks?)  
> **username_2**: Since you have a reasonably small total track, it should be possible to use dynamic programming to obtain an optimal solution quite quickly.  You might want to post this on StackOverflow instead if you are looking for code.  

---

## 2 answers

### Answer by username_3 on 2010-11-11. Score: 5

You could easily formulate this as a [integer linear programming](http://en.wikipedia.org/wiki/Linear_programming#Integer_unknowns) (ILP) problem. This is a linear programming problem where the solutions are constrained to be integers. The problem is NP-hard as indicated in other answers, but software does exist to address this sort of problem.

Let $L$ be the ultimate length you are aiming for, $a$ be the number of
Track A used, $b$ be the number of Track B used, and so forth. Finally,
let $A$, $B$, $C$, and $D$ be the amount of each kind of track you have.

($a,b,c,d$ are variables; the rest are constants.)

Then the integer linear programming problem is formulated as:

* $L - 0.5 \le 3.0 a + 5.0 b + 6.5 c + 10.5 d \le L + 0.5$
* $0 \le a \le A$
* $0 \le b \le B$
* $0 \le c \le C$
* $0 \le d \le D$
* $a,b,c,d$ are integers
* minimise $a+b+c+d$

The condition $a+b+c+d$ can be changed to what you want to minimise/maximise to suit your needs so long as
it is linear in the variables $a,b,c,d$. The could be something capturing the costs of the various Tracks. All of the other ingredients can be changed in an obvious way, for different track lengths, different tolerance level, and so forth, so long as they are constants when you submit your question to an ILP system.

Plenty of software packages exist to solve such problems; many are listed on the page linked to above.

> **Comments:**
> **username_4**: I guess you are referring to *integer linear programming*, not linear programming.  
> **username_3**: Indeedy. I just realised my mistake.  
> **username_5**: “integer linear programming (LP)”?!  
> **username_3**: Fixed. Added one character.  
> **username_6**: As the number of variables of this ILP formulation is bounded by the number of distinct tracks, and ILP is fixed-parameter tractable parameterized by the number of variables, this method should work very well in practice if the number of types of tracks is small.  

---

### Answer by username_1 on 2010-11-11. Score: 4

Unless I misunderstood, your problem is NP Hard in general. You have different tracks of different lengths, and you need them to add up to a given distance. [Subset sum](http://en.wikipedia.org/wiki/Subset_sum_problem) reduces to your problem, so I am afraid there's little hope for an efficient algorithm in the worst case.

However, it does not mean the cases you care about are hopeless. For example, if you don't have too many track sizes, you can even do brute-force search. If you don't need a very small margin, then [dynamic programming](http://en.wikipedia.org/wiki/Dynamic_programming) should work.

> **Comments:**
> **username_3**: Is it still subset sum given the error margin?  
> **username_7**: @Dave, @Lev, As I would read the question, subset sum is (forgive the terminology) a subset of this problem. In the special case where the margin is 0, it's precisely subset sum, meaning subset sum *does* reduce to this problem (and hence this problem is NP-hard). Unless the intention was a static margin of exactly [-0.5, 0.5] for all instances, in which case you would be correct...  
> **username_5**: @Daniel: In addition, a usual convention is that the input to the Subset Sum problem is integers, which makes the static margin [−0.5, 0.5] irrelevant even if that is the intent of the question.  
> **username_7**: @Tsuyoshi, good catch.  

---

