Linear Programming: Packing rods into a row

H

HamsterEater

New member
Joined
Sep 28, 2010
Messages
5
This is related to real-world application I'm attempting to solve, but I've restructured it into an analogy that helps better explain it. Here are the parameters:
  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.[/*:m:14bp3a3l]
  2. The rods need to be sorted by their weight. Length has no correlation with weight. Heavy rods can be very short just as easily as long rods can be very light.[/*:m:14bp3a3l]
  3. 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.[/*:m:14bp3a3l]
  4. No guarantee is given that length 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 dense rod, for example).[/*:m:14bp3a3l]
  5. 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.[/*:m:14bp3a3l]

Simply put, how do I translate these parameters into a linear programming problem? That would at least be a start.


Thanks in advance.
 
Methinks you better supply an example.
If lengths don't matter, why mention lengths?
 
Lengths do matter. Just not for sorting. They matter when the constrains force lesser-weighted rods up front, requiring other rods to be sorted around them, for example.
 
You must log in or register to reply here.
Top