Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a simple pipe network like this (not to scale):

Pipe Network

I can place a "valve" on any point on that pipe. What the valve does is it permits a certain viscous fluid to fill the pipes. However, because it is so viscous, it can only travel to a certain length $K_i$ along the pipe in any rectilinear direction, depending on the fluid I use.

Note: The valves need not be at vertices. They can be at any point in the network.

The less viscous the fluid, the larger the cost it incurs. So the farther the fluid can travel, the more expensive it is.

If I'm using a fluid that can travel only 5 units in any direction, and I place the valve at the top leftmost corner, the fluid (red) will travel like this:

k_1 = 5

Whereas if I used a fluid that could travel 10 units in any direction, it would look like this (blue):

k_2 = 10

If I used the first fluid but put the valve at the bottom right corner of the first square, the fluid will spread like this (red):

k_1 = 5 valve placement 2

If I used the second fluid but put the valve at the bottom right corner of the first square again, the fluid spreads this way (blue):

k_2 = 10 valve placement 2

Fluid 1 incurs a cost of 10 per valve where fluid 1 is used, whereas fluid 2 incurs a cost of 18 per valve (the fluids can mix). The goal is to fill the pipes with either fluid 1 or fluid 2 while incurring the least possible cost.

My question is, how can I optimize this situation mathematically? Does it require a linear program?

At first glance, it looks like there are many solutions. It doesn't look very convenient to do an LP. But, how else can it be approached with math?

Also, in the general case where the distances traveled are $K_i$, the costs incurred are $C_i$, and the pipe network is not as simple as the one I presented (all pipes still run up-down or left-right, but are more complex), how do I proceed about optimizing?

share|improve this question
    
The valves need not be at vertices? –  Hagen von Eitzen Jul 21 '13 at 12:42
    
That's right, they don't need to be. I'm sorry, I should have noted that. Thanks! –  markovchain Jul 21 '13 at 12:43
    
Well, you said "any point", but I wanted to make sure –  Hagen von Eitzen Jul 21 '13 at 13:14
add comment

1 Answer 1

If you can discretize the problem (e.g., only look for positions with integral coefficients), it is a set cover problem: consider a matrix with one column for each (integral) position in the network, one row for each possible position of each fluid source, and value 1 if the position (column) can be reached by the fluid (row), 0 otherwise; you are looking for a minimum-cost set of rows with at least one 1 in each column. The problem can be formulated as an integer linear program.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.