The Mixed Integer Linear Bilevel Programming Problem

James T. Moore and Jonathan F. Bard
Additional contact information
James T. Moore: Offutt Air Force Base, Omaha, Nebraska
Jonathan F. Bard: University of Texas, Austin, Texas

Operations Research, 1990, vol. 38, issue 5, 911-921

Abstract: A two-person, noncooperative game in which the players move in sequence can be modeled as a bilevel optimization problem. In this paper, we examine the case where each player tries to maximize the individual objective function over a jointly constrained polyhedron. The decision variables are variously partitioned into continuous and discrete sets. The leader goes first, and through his choice may influence but not control the responses available to the follower. For two reasons the resultant problem is extremely difficult to solve, even by complete enumeration. First, it is not possible to obtain tight upper bounds from the natural relaxation; and second, two of the three standard fathoming rules common to branch and bound cannot be applied fully. In light of these limitations, we develop a basic implicit enumeration scheme that finds good feasible solutions within relatively few iterations. A series of heuristics are then proposed in an effort to strike a balance between accuracy and speed. The computational results suggest that some compromise is needed when the problem contains more than a modest number of integer variables.

Keywords: games: noncooperative; programming; integer: branch-and-bound algorithms (search for similar items in EconPapers)
Date: 1990
References: Add references at CitEc
Citations: View citations in EconPapers (76)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.38.5.911 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:38:y:1990:i:5:p:911-921

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().