This award provides funding for the study of solution methods for optimization models that arise in hierarchical decision systems. Such systems are characterized by the existence of a decision hierarchy in which multiple, self-interested decision-makers (DMs) each determine an optimal course of action subject to mandates imposed by decisions made at higher levels in the hierarchy. Analysis of such a system most naturally takes the point of view of the highest-level DM, who must take into account the actions of all lower-level DMs in order to act optimally. Such decision problems can be analyzed using multilevel mathematical programming models, which are similar to standard mathematical programs except that the variables are divided into groups, each of which is controlled by a different DM. By requiring the values of the variables controlled by lower-level DMs to be optimal, given those already fixed by higher-level DMs, it is possible to formulate the optimization problem faced by the highest-level DM as a single optimization model.
If successful, this research will develop a prototype system for solving bilevel integer programs, in which there exactly two DMs and in which some of the variables are required to take on integer values. As there are currently no effective methods for solving bilevel integer programs, this research will result in an improvement in our ability to analyze decision systems that can be modeled in this way. A particular focus of the research will be so-called interdiction models, in which the two DMs are direct adversaries. In the simplest case, a high-level DM has the ability to restrict the actions of a low-level DM's actions in various ways. The high-level DM's decision is how to allocate resources so as to have maximum impact on the low-level DM's ability to carry out a given mission. Such models have wide applicability, especially in military settings and in the analysis of certain competitive markets. The software produced as a result of this research will be released open source and will be available to a wide range of researchers who will benefit from its availability.
