Optimization problem

Discussion in 'Python' started by cesco, Mar 18, 2007.

  1. cesco

    cesco Guest

    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
    cesco, Mar 18, 2007
    #1
    1. Advertising

  2. cesco

    mkPyVS Guest

    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,
    mkPyVS, Mar 18, 2007
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. JE
    Replies:
    0
    Views:
    449
  2. ashu
    Replies:
    5
    Views:
    1,184
    umerarain
    May 16, 2006
  3. JE
    Replies:
    2
    Views:
    392
    Karl Heinz Buchegger
    Aug 5, 2004
  4. DENG
    Replies:
    6
    Views:
    293
  5. Ravikiran

    Zero Optimization and Sign Optimization???

    Ravikiran, Nov 17, 2008, in forum: C Programming
    Replies:
    22
    Views:
    840
    Thad Smith
    Nov 24, 2008
Loading...

Share This Page