473,327 Members | 2,094 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,327 software developers and data experts.

Optimization problem

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

Mar 18 '07 #1
1 973
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,

Mar 18 '07 #2

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

9
by: Rune | last post by:
Is it best to use double quotes and let PHP expand variables inside strings, or is it faster to do the string manipulation yourself manually? Which is quicker? 1) $insert = 'To Be';...
12
by: WantedToBeDBA | last post by:
Hi all, db2 => create table emp(empno int not null primary key, \ db2 (cont.) => sex char(1) not null constraint s_check check \ db2 (cont.) => (sex in ('m','f')) \ db2 (cont.) => not enforced...
93
by: roman ziak | last post by:
I just read couple articles on this group and it keeps amazing me how the portability is used as strong argument for language cleanliness. In my opinion, porting the program (so you just take the...
3
by: Dmitry Jouravlev | last post by:
Hi, I have a number of C++ solutions in Visual Studio .NET and when i compile them using "Whole Program Optimization", certain projects report a LNK1171 error saying that c2.dll could not be...
21
by: mjbackues at yahoo | last post by:
Hello. I'm having a problem with the Visual Studio .net (2003) C++ speed optimization, and hope someone can suggest a workaround. My project includes many C++ files, most of which work fine...
3
by: Abhishek | last post by:
Recently i found that my C++ program was running fine with no optimization and giving segmentation fault with error code 139 when compiled with optimization level 2. I searched somewhat but never...
5
by: wkaras | last post by:
I've compiled this code: const int x0 = 10; const int x1 = 20; const int x2 = 30; int x = { x2, x0, x1 }; struct Y {
3
by: amitsoni.1984 | last post by:
Hi, I need to do a quadratic optimization problem in python where the constraints are quadratic and objective function is linear. What are the possible choices to do this. Thanks Amit
6
by: Explore_Imagination | last post by:
The task is to solve a constrained optimization problem in C/C++. Computational Time is of high priority. One approach can be to use ready functions in a "free ware" Optimization Library (if...
2
by: Explore_Imagination | last post by:
The task is to solve a constrained optimization problem in C. Computational Time is of high priority. One approach can be to use ready functions in a "free ware" Optimization Library (if...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.