Article ID: | iaor19911654 |
Country: | United States |
Volume: | 38 |
Issue: | 5 |
Start Page Number: | 911 |
End Page Number: | 921 |
Publication Date: | Sep 1990 |
Journal: | Operations Research |
Authors: | Bard Jonathan F., Moore James T. |
Keywords: | programming: integer |
A two-person, noncooperative game in which the players move in sequence can be modeled as a bilevel optimization problem. In this paper, the authors 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, the authors 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.