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.

Suppose we want to walk from place $A$ to place $B$, but there are several rivers between them. In order to walk from place $A$ to place $B$, we need to build a bridge for each river.

We have several types of planks. Different types of planks have different costs and lengths, but the same type of planks have the same cost and length. We can use planks to build bridges. However, the number of available planks are limited. Our objective is to build a bridge for each river while minimizing the total cost of planks.

To better describe the problem, we draw a figure to describe our problem.

enter image description here

There are three rivers where the length of bridges needed are $d_1$, $d_2$, and $d_3$, respectively.

We have $4$ types of planks. Let $l_i$ and $c_i$ denote the length and cost of the $i$th type of plank. Let $\delta_i$ denote the available number of $i$th type of planks. Let $n_{ij}$ denote the number of planks used for build bridge $j$.

Then the problem can be formulated as follows:

Minimize $\sum_{j=1}^3 \sum_{i=1}^4 n_{ij}c_i$

s.t.

$\sum_{i=1}^4 n_{ij}l_i \geq d_j$

$\sum_{j=1}^3 n_{ij} \leq \delta_i$

$n_{ij}\geq 0$ & $n_{ij} \in Z$

I think this problem should be NP-Hard as it is an integer programming problem. Is this true? Does anyone know how to solve this problem? Even a solution which is not optimal.

share|improve this question

1 Answer 1

Note that Integer Programming is NP-Hard, but this is a subclass of the class of all Integer Programming problems. In particular, the problems in this class have only 12 free variables and Integer Programming in a fixed dimension is in P.

Now, if the number of bridges were not fixed at three, that this would still be a subclass of the class of Integer Programming problems. My guess is that that class would be NP-Hard, but still that doesn't immediately follow from the fact that Integer Programming is NP-Hard.

share|improve this answer
    
Given the problem is in P in a fixed dimension, do you know how to efficiently solve this problem? –  wzb5210 Sep 9 '13 at 19:44
    
Regrettably not, but a quick search for "integer programming fixed dimension" comes up with some papers on this topic, for instance [ii.uni.wroc.pl/~jby/theory_of_lp/ip_llncs.pdf]. I have no idea how practical this is. –  Magdiragdag Sep 9 '13 at 19:49

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.