Optimization problem

[cesco]

I have a set of N blocks of different lengths. The length of each
block is a multiple of a basic unit. The blocks, once lined up, make a
path of distance equal to R. Let's say we have 5 blocks with the
following lengths: N_set_lengths = (1, 3, 2, 1, 3), then the path we
cover by lining them up is equal to R = 10.
Now, each of these blocks is associated with a different metric m
(metric) which depends on the location/position that the block
occupies within the path. So a block of length 1 will have R = 10
different m values, one for each of the 10 positions it can occupy
within the path, while a block of length 3 will have R-3+1 = 8
different m values.

Here is a graphical representation:

--------------------------------------------------------------------------------
block 0: |m0,0|m0,1|m0,2|m0,3|m0,4|m0,5|m0,6|m0,7|m0,8|m0,9|
(length 1, 10 different metrics)

--------------------------------------------------------------------------------

-------------------------------------------------------------------------------
block 1: |m1,0|m1,1|m1,2|m1,3|m1,4|m1,5|m1,6|m1,7| |
| (length 3, 8 different metrics, each metric

-------------------------------------------------------------------------------
refers to 3 consecutive units)

-------------------------------------------------------------------------------
block 2: |m2,0|m2,1|m2,2|m2,3|m2,4|m2,5|m2,6|m2,7|m2,8| |
(length 2, 9 different metrics, each

-------------------------------------------------------------------------------
referring to 2 consecutive units)

-------------------------------------------------------------------------------
block 3: |m3,0|m3,1|m3,2|m3,3|m3,4|m3,5|m3,6|m3,7|m3,8|m3,9|
(length 1, 10 different metrics)

-------------------------------------------------------------------------------

-------------------------------------------------------------------------------
block 4: |m4,0|m4,1|m4,2|m4,3|m4,4|m4,5|m4,6|m4,7| |
| (length 3, 8 different metrics)

-------------------------------------------------------------------------------

Those blocks can be allocated in fact(N) possible different ways to
cover the path (In the example considered I have 5 possible blocks to
choose from to cover the first part of the path, 4 blocks to cover the
second part of the path, and so on).

Each of these possible combinations results in a different overall
metric which we can define as the sum of the individual metrics that
each block gets according to the position occupied within the path.
There is at least one combination which is the optimum solution,
because it maximizes the overall metric. Finding such a combination is
possible but it may require a long processing time.

If, for example, the number of blocks is 20 the number of possible
combinations is expressed as 2.4*10^18. In the application I'm
considering the time is really a constraint so I'm trying to find an
algorithm which would give a near optimum solution but with a much
lower complexity.

Does anyone have suggestion on how should such an algorithm behave
(possibly considering implementation issues)?

Sorry for the lengthy description, I was just trying to be as clear as
possible.
Please, don't hesitate to ask questions if the problem statement is
not clear.

Many thanks and regards
Francesco

 

[mkPyVS]

I would suggest taking a look at the python package networkx. It is a
wonderfully created path optimization and presentation package which
has a fair amount of extensabilty.

Basic lowest cost path solutions should be able to solve your
algorithmic needs here in polynomial time (Typically N**P time..
compute time through path to the number of nodes power) which is
typically adequate for most functional needs ( < 1 sec for 20 nodes)
and presents a simple solution path unless the path you present has
many loop options or path costs which are mal-formed. Good Luck,