Abstract:

The uncapacitated facility location problem is a classic combinatorial optimization problem with wide applications. However, this problem had been proven to be NP-hard and the traditional solving method based on branch-and-bound is slow. In this paper, we studies a class of UFLP problem aiming at maximizing the gap between total income and total investment cost, we transform this problem into a node packing problem and propose a new family of valid inequalities-axis inequalities based on graphic features of the model, which are stronger than the odd-hole inequalities after a strict proof. We also design a fast searching algorithm for cut inequalities and embed it in the branch-and-cut method. In the end, strong validity of axis inequalities are validated by experiments. The experimental results also showed that compared with the branch-and-bound method, the branch-and-cut method can reduce the number of branch nodes as
well as speed up the solving process.

Key words: uncapacitated facility location problem, branch-and-cut, axis inequalities