Happy week-before-spring-break! In less than a month, I am going to be presenting a paper entitled “Interdicting a Nuclear-Weapons Project,” by Brown et al., written in 2009. While I will obviously be getting into more of the gritty details in my presentation, I wanted to give you a little flavor of what the problem looks like. In particular, I’d like to briefly introduce the concept of bilevel programming and how it relates to nuclear weapon project interdiction.
A bilevel problem can be thought as a “game” between two decision makers. One decision maker makes an decision based on a set of constraints and some objective that benefits them, and then a second decision maker with a different (often contrasting) objective takes action that benefits them. In [2], the authors present the general form of the bilevel programming problem as follows:
In this general form, the first decision maker tries to guess how the second decision maker will minimize their objective and acts accordingly, counteracting the expected actions of the second decision maker. Then the second decision maker takes action after seeing what the first decision maker chose to do, which affects their feasible set of actions. Of course, further restrictions can be imposed, such as requiring certain variables to be integer. Many bilevel problems are nonconvex, so they can be incredibly difficult to solve.
The interdiction problem is a good example of a bilevel programming problem. With nuclear weapon proliferation, specifically, the proliferator would like to quickly produce (and possibly disseminate) a batch of weapons, whereas the interdictor would like to delay the production as much as possible. The underlying assumption is that the proliferator can see any action done by the interdictor and thus can act to inhibit or avoid any such action. The objective used in the nuclear weapon interdiction paper is
where S is the earliest start time of the final task that must be completed by the proliferator, and x and y are the decisions made by the interdictor and the proliferator, respectively.
The nuclear weapons interdiction problem also has many constraints and multiple decisions to be made, so it is a complex problem. I’ll get into the details of the model and the algorithms used to solve it in my presentation, and probably in a future blog post as well, but for the time being I wanted to set up the idea of bilevel programming and how nuclear weapons proliferation can be viewed as a bilevel program.
[1] Brown, Gerald G., et al. “Interdicting a nuclear-weapons project.” Operations Research 57.4 (2009): 866-877.
[2] Bard, Jonathan F. “An algorithm for solving the general bilevel programming problem.” Mathematics of Operations Research 8.2 (1983): 260-272.
Public Sector Operations Research 
You wrote, “Many bilevel problems are nonconvex, so they can be incredibly difficult to solve.” Can you elaborate on this, maybe in a future post? What is a simple example of a non-convex bi-level programming model? Do they happen a lot?
LikeLike
Sure thing! Mostly I was referring to cases involving integer variables, which are inherently nonconvex. Since bilevel programs can be thought of as a type of game with decision makers choosing whether to act in a certain way, binary decisions are common. Whenever a decision maker has to decide whether or not to do something, a binary (nonconvex) element is introduced. Except in specific cases where polynomial-time algorithms exist, IPs are very hard to solve. A simple example of a binary bilevel program would be a network interdiction scenario, where the first decision maker decides which arcs to fortify and the interdictor decides which non-fortified arcs to interdict, subject to any constraints you like. (Certainly there are other cases of nonconvexity, including nonlinear situations where decision variables are multiplied together in the objective function.)
LikeLiked by 1 person
I thought this was a really great overview of bilevel programming. I’ve been finding it pretty difficult to consolidate more complicated explanations into a single blog post, so I’m impressed you were able to explain the topic and provide an accessible example in a relatively limited amount of text. I also like how you left the door open to elaborate on the topic in a future blog post, so kudos all around.
The application of bilevel programming to nuclear weapon proliferation is also really interesting, and it’s definitely not something I would have thought of as an operations research problem prior to taking this course. Now that I’ve thought about it, though, it makes a lot of sense, and I wouldn’t be surprised if operations research techniques were used in the development of the Iran nuclear agreement that was reached last year.
LikeLike