A Combined Linear/Integer Programming Heuristic to Control a Network of semi-Markov Decision Processes

For even moderately sized networks and a small number of actions finding an optimal policy, i.e., determining which actions to apply to which nodes of the network given the states of the nodes, may be computationally infeasible. Heuristics have been developed that are applicable to the case of multiple homogeneous actions such that each action affects exactly one entity. For many applications, e.g., remote sensing with localization and identification sensors, multiple disparate actions may be available, an action may a ect multiple entities, and actions may require different amounts of time to complete. The present work develops a two-step heuristic to generate action plans under these more general circumstances. Linear programming applied either to the individual nodes of the network or to all nodes collectively but with an average aggregate utilization constraint is used to obtain optimal policies and reduced cost coefficients for each node. Integer programming, using the reduced cost coefficients, is then used at each time-step to assign resources to projects. These methodologies are applied to a simulated remote sensing problem, and the performance of the current methods is compared with an optimal solution where its computation is feasible and with a greedy solution. Results show minimal degradation in comparison with an optimal policy and substantial improvement over the greedy approach. Computation time studies show that the method is practical for large scale real time applications.