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 Vi 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 nij, the expected destroyed value is given by ∑ⁿi=1 Vi {1 – exp (– ∑j αijnij)}. If a unit price of j-type missile is cj and the total cost of missiles is limited by C, we have cost constraints ∑^mj=1 cj ∑ⁿi=1 nij ≤ 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.