More Web Proxy on the site http://driver.im/

article

A Branch and Bound Algorithm for the Bilevel Programming Problem

Authors:

Jonathan F. Bard,

James T. MooreAuthors Info & Claims

SIAM Journal on Scientific and Statistical Computing, Volume 11, Issue 2

Pages 281 - 292

Published: 01 March 1990 Publication History

Abstract

The bilevel programming problem is a static Stackelberg game in which two players try to maximize their individual objective functions. Play is sequential and uncooperative in nature. This paper presents an algorithm for solving the linear/quadratic case. In order to make the problem more manageable, it is reformulated as a standard mathematical program by exploiting the follower's Kuhn–Tucker conditions. A branch and bound scheme suggested by Fortuny-Amat and McCarl is used to enforce the underlying complementary slackness conditions. An example is presented to illustrate the computations, and results are reported for a wide range of problems containing up to 60 leader variables, 40 follower variables, and 40 constraints. The main contributions of the paper are in the step-by-step details of the implementation, and in the scope of the testing.

References

[1]

E. AIYOSHI AND K. SHIMIZU (1981), Hierarchical decentralized systems and its new solution by a barrier method, IEEE Trans. Systems, Man, Cybernetics, 11, pp. 444-449.

[2]

J. F. BARD (1988), Convex two-level optimization, Math. Programming, 40, pp. 15-27.

[3]

J. F. BARD (1983a), Coordination of a multidivisional firm through two levels of management, Omega, 11, pp. 457-468.

[4]

J. F. BARD (1983b), An efficient point algorithm for a linear two-stage optimization problem, Oper. Res., 31, pp. 670-684.

[5]

J. F. BARD AND J. E. FALK (1982), An explicit solution to the multi-level programming problem, Comput. Oper. Res., 9, pp. 77-100.

[6]

T. BASAR AND H. SELBUZ (1979), Closed loop Stackelberg strategies with applications in optimal control of multilevel systems, IEEE Trans. Automat. Control, 24, pp. 166-178.

[7]

W. F. BIALAS AND M. H. KARWAN (1984), Two-level linear programming, Management Sci., 30, pp. 1004-1020.

[8]

W. CANDLER AND R. TOWNSLEY (1982), A linear two-level programming problem, Comput. Oper. Res., 9, pp. 59-76.

[9]

J. J. DONGARRA (1986), Performance of various computers using standard linear equations software in a Fortran environment, Technical Memorandum No. 23, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL.

[10]

T. A. EDMUNDS (1988), Algorithms for nonlinear bilevel mathematical programs, Ph.D thesis, Department of Mechanical Engineering, University of Texas, Austin, TX.

[11]

J. FORTUNY-AMAT AND B. MCCARL (1981), A representation and economic interpretation of a two-level programming problem, J. Oper. Res. Soc., 32, pp. 783-792.

[12]

B. F. GARDNER, JR. AND J. B. CRUZ, JR. (1978), Feedback Stackelberg strategy for M-level hierarchical games, IEEE Trans. Automat. Control, 23, pp. 489-491.

[13]

R. G. JEROSLOW (1985), The polynomial hierarchy and a simple model for competitive analysis, Math. Programming, 32, pp. 146-164.

[14]

L. S. LASDON, A. D. WARREN, A. JAIN, AND M. RATNER (1978), Design and testing of a generalized reduced gradient code for nonlinear programming, ACM Trans. Math. Software, 4, pp. 34-50.

[15]

R. E. MARSTEN (1981), The design of the XMP linear programming library, ACM Trans. Math. Software, 7, pp. 481-497.

[16]

M. SIMAAN AND J. B. CRUZ, JR. (1973), On the Stackelberg strategy in nonzero-sum games, J. Optim. Theory Appl., 11, pp. 533-555.

Cited By

Gu ZHardjawana WVucetic B(2024)Opportunistic Scheduling Using Statistical Information of Wireless ChannelsIEEE Transactions on Wireless Communications10.1109/TWC.2024.336640223:8_Part_2(9810-9825)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TWC.2024.3366402
Zhang QLangari RTseng HMohan SSzwabowski SFilev D(2024)Stackelberg Differential Lane Change Game Based on MPC and Inverse MPCIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2024.338679025:8(8473-8485)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TITS.2024.3386790
Khorramfar RÖzaltın OKempf KUzsoy R(2022)Managing Product TransitionsINFORMS Journal on Computing10.1287/ijoc.2022.121034:5(2828-2844)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1287/ijoc.2022.1210
Show More Cited By

Index Terms

A Branch and Bound Algorithm for the Bilevel Programming Problem
1. Mathematics of computing
  1. Mathematical analysis
    1. Functional analysis
      1. Approximation
    2. Mathematical optimization
      1. Continuous optimization
        Linear programming
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

New Branch-and-Bound Rules for Linear Bilevel Programming

A new branch-and-bound algorithm for linear bilevel programming is proposed. Necessary optimality conditions expressed in terms of tightness of the follower’s constraints are used to fathom or simplify subproblems, branch and obtain penalties similar to ...
A Lifted Linear Programming Branch-and-Bound Algorithm for Mixed-Integer Conic Quadratic Programs

This paper develops a linear-programming-based branch-and-bound algorithm for mixed-integer conic quadratic programs. The algorithm is based on a known higher-dimensional or lifted polyhedral relaxation of conic quadratic constraints. The algorithm is ...
A Branch and Bound algorithm for general mixed-integer quadratic programs based on quadratic convex relaxation

Let $$(MQP)$$ be a general mixed-integer quadratic program that consists of minimizing a quadratic function $$f(x) = x^TQx +c^Tx$$ subject to linear constraints. Our approach to solve $$(MQP)$$ is first to consider an equivalent general mixed-integer quadratic problem. This equivalent problem ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Scientific and Statistical Computing

SIAM Journal on Scientific and Statistical Computing Volume 11, Issue 2

1990

195 pages

ISSN:0196-5204

Issue’s Table of Contents

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 March 1990

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

41
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Gu ZHardjawana WVucetic B(2024)Opportunistic Scheduling Using Statistical Information of Wireless ChannelsIEEE Transactions on Wireless Communications10.1109/TWC.2024.336640223:8_Part_2(9810-9825)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TWC.2024.3366402
Zhang QLangari RTseng HMohan SSzwabowski SFilev D(2024)Stackelberg Differential Lane Change Game Based on MPC and Inverse MPCIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2024.338679025:8(8473-8485)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TITS.2024.3386790
Khorramfar RÖzaltın OKempf KUzsoy R(2022)Managing Product TransitionsINFORMS Journal on Computing10.1287/ijoc.2022.121034:5(2828-2844)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1287/ijoc.2022.1210
Baggio ACarvalho MLodi ATramontani A(2021)Multilevel Approaches for the Critical Node ProblemOperations Research10.1287/opre.2020.201469:2(486-508)Online publication date: 1-Mar-2021
https://dl.acm.org/doi/10.1287/opre.2020.2014
Kleinert TLabbé MPlein FSchmidt M(2020)Technical Note—There’s No Free LunchOperations Research10.1287/opre.2019.194468:6(1716-1721)Online publication date: 1-Nov-2020
https://dl.acm.org/doi/10.1287/opre.2019.1944
Kleinert TSchmidt M(2020)Computing Feasible Points of Bilevel Problems with a Penalty Alternating Direction MethodINFORMS Journal on Computing10.1287/ijoc.2019.094533:1(198-215)Online publication date: 22-Jun-2020
https://dl.acm.org/doi/10.1287/ijoc.2019.0945
Huang PWang Y(2020)A Framework for Scalable Bilevel Optimization: Identifying and Utilizing the Interactions Between Upper-Level and Lower-Level VariablesIEEE Transactions on Evolutionary Computation10.1109/TEVC.2020.298780424:6(1150-1163)Online publication date: 30-Nov-2020
https://dl.acm.org/doi/10.1109/TEVC.2020.2987804
Kieffer EDanoy GBrust MBouvry PNagih A(2020)Tackling Large-Scale and Combinatorial Bi-Level Problems With a Genetic Programming Hyper-HeuristicIEEE Transactions on Evolutionary Computation10.1109/TEVC.2019.290658124:1(44-56)Online publication date: 1-Feb-2020
https://dl.acm.org/doi/10.1109/TEVC.2019.2906581
Sinha ALu ZDeb KMalo P(2020)Bilevel optimization based on iterative approximation of multiple mappingsJournal of Heuristics10.1007/s10732-019-09426-926:2(151-185)Online publication date: 1-Apr-2020
https://dl.acm.org/doi/10.1007/s10732-019-09426-9
Luo HLiu LYang X(2020)Bi-level programming problem in the supply chain and its solution algorithmSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-019-03930-724:4(2703-2714)Online publication date: 1-Feb-2020
https://dl.acm.org/doi/10.1007/s00500-019-03930-7
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents