Premium
A branch‐and‐price algorithm for a targeting problem
Author(s) -
Kwon Ojeong,
Lee Kyungsik,
Kang Donghan,
Park Sungsoo
Publication year - 2007
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.20247
Subject(s) - column generation , branch and price , integer programming , mathematical optimization , branch and cut , computer science , heuristic , nonlinear programming , branch and bound , integer (computer science) , linear programming , nonlinear system , operations research , algorithm , mathematics , physics , quantum mechanics , programming language
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