A branch‐and‐price algorithm for a targeting problem |
| |
| Authors: | Ojeong Kwon Kyungsik Lee Donghan Kang Sungsoo Park |
| |
| Institution: | 1. Combined Battle Simulation Center, ROK‐US Combined Forces Command P.O. Box 181, Yongsan‐dong 3‐1, Yongsan‐gu, Seoul 140‐701, Korea;2. School of Industrial Information & Systems Engineering, Hankuk University of Foreign Studies, 89 Wangsan‐ri, Mohyeon‐myeon, Yongin‐si, Kyeonggi‐do 449‐791, Korea;3. Information Management Team, Samsung Electro‐Mechanics, 314 Maetan3‐dong, Suwon‐si, Kyeonggi‐do 442‐743, Korea;4. Department of Industrial Engineering, Korea Advanced Institute of Science and Technology, 373‐1 Guseong‐dong, Yuseong‐gu, Daejeon 305‐701, KoreaDepartment of Industrial Engineering, Korea Advanced Institute of Science and Technology, 373‐1 Guseong‐dong, Yuseong‐gu, Daejeon 305‐701, Korea |
| |
| Abstract: | In this paper, we consider a new weapon‐target allocation problem with the objective of minimizing the overall firing cost. The problem is formulated as a nonlinear integer programming model, but it can be transformed into a linear integer programming model. We present a branch‐and‐price algorithm for the problem employing the disaggregated formulation, which has exponentially many columns denoting the feasible allocations of weapon systems to each target. A greedy‐style heuristic is used to get some initial columns to start the column generation. A branching strategy compatible with the pricing problem is also proposed. Computational results using randomly generated data show this approach is promising for the targeting problem. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007 |
| |
| Keywords: | targeting problem weapon‐target assignment integer programming branch‐and‐price |
|
|
