AN INTEGER RESOURCE ALLOCATION PROBLEM WITH COST CONSTRAINT

概要

論文の詳細を見る
This paper investigates a non-linear integer programming problem with an exponential objective function and cost constraints, which is a general model and could be applied to the assignment problem or the search problem. As a representative example, we consider a following problem of assigning m types of missiles to n targets. The value of target i is V_i and the single shot kill probability (SSKP) of a j-type missile to target i is β_<ij> = 1 - exp(-α_<ij>) where α_<ij> ≥ 0. Denoting the number of j-type missiles assigned to target i by n_<ij>, the expected destroyed value is given by Σ^n_<i=1>V_i{1 - exp(-Σ_jα_<ij>n_<ij>)}. If a unit price of j-type missile is c_j and the total cost of missiles is limited by C, we have cost constraints Σ^m_<j=1>c_jΣ^n_<i=1>n_<ij>≤C. To this problem which is NP-hard, we propose two methods, the dynamic programming method and the branch and bound method. An approximate algorithm and an estimation of the upper bound of the objective function are incorporated in the branch and bound method. Each of these methods has its characteristic merits for the computational time. We clarify their characteristics through the sensitivity analysis by some examples in this paper.
社団法人日本オペレーションズ・リサーチ学会の論文