Lehigh ISE Professor Ted Ralphs, in a continuing partnership with Professor Oleg Prokopyev at University of Pittsburgh, has won a second three-year, half-million dollar grant from the Office of Naval Research. The proposed research is to develop next-generation algorithms for bilevel optimization problems. Multilevel optimization is a framework for modeling and analysis of games and other hierarchical decision processes involving two or more decision-makers, known as “players” in game theory parlance. The players make decisions in turn based on their own objectives with each player choosing from a set of actions limited by the moves made previously by other players.
The case under study is that of two players who make one move each, well-known as the Stackelberg game. The players may be, for examples, companies or military units, and the actions to be taken may involve many inter-linked decisions, such as how much money to invest in various available projects or how to harden a complex network to defend it against damage. Despite there being only two moves, this kind of game may already be difficult for modern computers to analyze. In the long-run, the hope is to use this simple two-level game as a kind of laboratory for the multi-level ones.
One of the key questions that Ralphs and Prokopyev plan to study is what can be learned by solving certain related but easier-to-analyze games obtained by relaxing the rules in some way. Such relaxations can yield bounds on the best outcome that can be expected and can guide the search for the optimal strategy. Ultimately, the methodology developed will make its way into open-source software that is being available not only to the research community, but companies and government agencies as well. The open-source package MibS (https://github.com/coin-or/MibS) has been under development at Lehigh since 2007.
“We are extremely pleased that the Office of Naval Research has entrusted us with this funding for the ongoing development of techniques for analyzing this important class of problems. Without this funding, it would not be possible to develop the open-source software that we are able to make freely available through this support.” says Ted Ralphs.