A branch‐and‐price algorithm for a targeting problem
Authors:
Open Access
- 22 June 2007
- journal article
- research article
- Published by Wiley in Naval Research Logistics (NRL)
- Vol. 54 (7) , 732-741
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, 2007Keywords
This publication has 13 references indexed in Scilit:
- A weapon–target assignment approach to media allocationApplied Mathematics and Computation, 2006
- Modeling uncertainty reasoning with possibilistic petri netsIEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2003
- Efficiently solving general weapon-target assignment problem by genetic algorithms with greedy eugenicsIEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2003
- A Hybrid Search Algorithm of Ant Colony Optimization and Genetic Algorithm Applied to Weapon-Target Assignment ProblemsLecture Notes in Computer Science, 2003
- Telecommunication Node Clustering with Node Compatibility and Network Survivability RequirementsManagement Science, 2000
- Optimizing Assignment of Air-to-Ground Assets and BDA SensorsMilitary Operations Research, 2000
- Lagrangian relaxation approach to the targeting problemNaval Research Logistics (NRL), 1999
- Branch-and-Price: Column Generation for Solving Huge Integer ProgramsOperations Research, 1998
- A Branch-and-Price Algorithm for the Generalized Assignment ProblemOperations Research, 1997
- An exact algorithm for IP column generationOperations Research Letters, 1996