Algorithm problem: Packing rods into a row

Question

Alright, this might be a tricky problem. It is actually an analogy for another similar problem relating to my actual application, but I've simplified it into this hypothetical problem for clarity. Here goes:

1. I have a line of rods I need to be sorted. Because it is a line, only 1 dimension needs to be of concern.
2. Rods are different lengths and different weights. There is no correlation between weight and length. A small rod can be extremely heavy, while a large rod can be very light.
3. The rods need to be sorted by weight.
4. The real catch is, however, some rods can only be placed no more than certain distances from the start of the line, regardless of their weight. Anywhere before that is fine, though.
5. No guarantee is given that constraints will be spaced enough away from each other to prevent the possibility of constrained rods being squeezed into overlapping. In this (hopefully rare) case, either the rods need to be re-arranged somehow within their constraints to create the needed space, or an ideal compromise solution may need to be found (such as violating a constraint of the least light rod, for example).
6. It is possible at a future date that additional constraints may be added *in addition to the length constraint to indicate specific (and even non-compromising) boundaries within the line where rods cannot overlap into.

My current solution does not account for the latter situations, and they sound like they'll involve some complex work to resolve them.

Note that this is for a client-side web application, so making the solution apply to Javascript would be helpful!

Answer 1

If it is possible I'd suggest formulating this as a mixed integer program. If you can encode the constraints in this was you can use a solver to satisfy the constraints. See this page for some more info on this type of approach:

http://en.wikipedia.org/wiki/Linear_programming

If you can interface this to Javascript somehow then it might prove to be an elegant solution.