NP-completeness for integer linear program

Question

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

Answer 1

This is a classic facility location problem. That Wikipedia article suggests that NP-hardness can be proven by reduction from set cover.

---

Since the asker has now stated to have found a solution by reducing from vertex cover, I will go ahead and reveal the reduction from set cover:

For each value, create a store; for each set, create a warehouse. Assign the cost of each warehouse to be 1. Assign the cost of the route from a warehouse to a store to be an arbitrarily small value if that warehouse's set contains that store's value, or an arbitrarily large value otherwise. Then the minimum cost solution to the facility problem builds precisely the set of warehouses corresponding to the minimum set cover in the original problem.

The $k$ value is used to turn the optimization problem (minimize sets/cost) into a decision problem (is there a solution with no more than $k$ sets/cost?). The $k$ from the set cover instance will be the same as the $k$ in the facility problem instance if you are allowed to set the "arbitrarily small" values to exactly 0 - otherwise you might have to fudge the value by some amount, but less than 1 as long as you pick the "arbitrarily small" weights to be small enough. You just need the total of every "arbitrarily small" cost to be less than 1, and every "arbitrarily large" cost to be greater than the sum of the costs of all the warehouses and all the "arbitrarily small" routes.

Note that, if only integer costs are allowed in the facilities problem, you can still achieve the same result by scaling all the costs by their least common multiple.