Locating military equipment in forefront: model and approach

Document Type : Original Article


1 Department of Industrial Engineering, Birjand university of Technology, Iran

2 Mathematics department, Imam Ali University, Iran



In this paper, we study the problem locating military equipment in forefront. In this problem, the goal is how to locate military equipment in such a way that all of the hotspots are covered and the number of the used military equipment are minimized. The problem is formulated as a zero - one linear programming problem. Then, it is investigated in two cases, use of one type and several type of military equipment. In the case that only one type of military equipment is located, it is shown that the problem is transformed into a special instance of minimum cost flow problem and consequently, it can be solved in strongly polynomial time. In the case that various types of military equipment are used, it is proved that the problem is NP-hard due to a reduction from the well-known knapsack problem. Therefore the problem cannot be solved efficiently in this case.