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.
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.
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.