This is a homework problem, so I don't want the solution. I need a hint which problem to reduce to the following and/or how to start on it. We were thinking of TSP or independent set but couldn't come up with a solution.
We have $i\ldots j$ stores and $i\ldots n$ possible places to build a new warehouse. Costs to build a new warehouse are $c_j$. Between each store and warehouse is a path of cost $d_{i,j}$. Every store needs to be connected to at least one warehouse.
The decision problem is: is there a set of warehouses and paths so that the sum is smaller than a given number $k$.