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

research-article

New Branch-and-Bound Rules for Linear Bilevel Programming

Authors:

Brigitte Jaumard,

Gilles SavardAuthors Info & Claims

SIAM Journal on Scientific and Statistical Computing, Volume 13, Issue 5

Pages 1194 - 1217

https://doi.org/10.1137/0913069

Published: 01 September 1992 Publication History

Abstract

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 those used in mixed-integer programming. Computational results are reported and compare favorably to those of previous methods. Problems with up to 150 constraints, 250 variables controlled by the leader, and 150 variables controlled by the follower have been solved.

References

[1]

Eitaro Aiyoshi, Kiyotaka Shimizu, Hierarchical decentralized systems and its new solution by a barrier method, IEEE Trans. Systems Man Cybernet., 11 (1981), 444–449

[2]

Eitaro Aiyoshi, Kiyotaka Shimizu, A solution method for the static constrained Stackelberg problem via penalty method, IEEE Trans. Automat. Control, 29 (1984), 1111–1114

[3]

Faiz A. Al-Khayyal, Reiner Horst, Panos M. Pardalos, Global optimization of concave functions subject to quadratic constraints: an application in nonlinear bilevel programming, Ann. Oper. Res., 34 (1992), 125–147

Digital Library

[4]

G. Anandalingam, D. J. White, A penalty function approach for solving bilevel linear programs, Res. Report, Department of Systems Engineering, University of Pennsylvania, Philadelphia, 1989, November

[5]

Jonathan F. Bard, An efficient point algorithm for a linear two-stage optimization problem, Oper. Res., 31 (1983), 670–684

Digital Library

[6]

Jonathan F. Bard, An algorithm for solving the general bilevel programming problem, Math. Oper. Res., 8 (1983), 260–272

Digital Library

[7]

Jonathan F. Bard, Convex two-level optimization, Math. Programming, 40 (1988), 15–27

Digital Library

[8]

Jonathan F. Bard, James E. Falk, An explicit solution to the multilevel programming problem, Comput. Oper. Res., 9 (1982), 77–100

[9]

Jonathan F. Bard, James T. Moore, A branch and bound algorithm for the bilevel programming problem, SIAM J. Sci. Statist. Comput., 11 (1990), 281–292

Digital Library

[10]

W. F. Bialas, M. H. Karwan, On two-level linear optimization, IEEE Trans. Automat. Control, AC-27 (1982), 211–214

[11]

Wayne F. Bialas, Mark H. Karwan, Two-level linear programming, Management Sci., 30 (1984), 1004–1020

Digital Library

[12]

Omar Ben-Ayed, Charles E. Blair, Computational difficulties of bilevel linear programming, Oper. Res., 38 (1990), 556–560

Digital Library

[13]

J. Bracken, J. McGill, Mathematical programs with optimization problems in the constraints, Operations Res., 21 (1973), 37–44

Digital Library

[14]

W. Candler, J. Fortuny-Amat, B. McCarl, The potential role of multilevel programming in agricultural economics, Amer. J. Agricultural Econ., 63 (1981), 521–531

[15]

W. Candler, R. Norton, Multilevel programming and development policy, World Bank Staff Working Paper, 258, IBRD, Washington DC, 1977

[16]

Wilfred Candler, Robert Townsley, A linear two-level programming problem, Comput. Oper. Res., 9 (1982), 59–76

[17]

S. Dempe, A simple algorithm for the linear bilevel programming problem, Optimization, 18 (1987), 373–385

[18]

James E. Falk, A linear max-min problem, Math. Programming, 5 (1973), 169–188

Digital Library

[19]

J. Fortuny-Amat, B. McCarl, A representation and economic interpretation of a two-level programming problem, J. Oper. Res. Soc., 32 (1981), 783–792

[20]

Michael R. Garey, David S. Johnson, Computers and intractability, W. H. Freeman and Co., San Francisco, Calif., 1979x+338, A Guide to the Theory of NP-Completeness

Digital Library

[21]

P. Hansen, B. Jaumard, S.-H. Lu, A framework for algorithms in globally optimal design, J. Mech. Trans. Automat. Design, 11 (1989), 353–360

[22]

Pierre Hansen, Brigitte Jaumard, Shi-Hui Lu, An analytical approach to global optimization, Math. Programming, 52 (1991), 227–254

Digital Library

[23]

A. Haurie, R. Loulou, G. Savard, A two-player game model of power cogeneration in New England, IEEE Trans. Automat. Control, 37 (1992), 1451–1456

[24]

A. Haurie, G. Savard, J. C. White, A note on an efficient point algorithm for a linear two-stage optimization problem, Oper. Res., 38 (1990), 553–555

Digital Library

[25]

J. P. Ignizio, Goal Programming and Extensions, Lexington Books, Lexington, MA, 1976

[26]

Robert G. Jeroslow, The polynomial hierarchy and a simple model for competitive analysis, Math. Programming, 32 (1985), 146–164

[27]

J. J. Judice, A. M. Faustino, The solution of the linear bilevel programming problem by using the linear complementarity problem, Investigação Oper., 8 (1988), 77–95

[28]

J. J. Judice, A. M. Faustino, A sequential LCP method for bilevel linear programming, Res. Report, Department of Mathematics, University of Coïmbra, Coïmbra, Portugal, 1989

[29]

Larry J. LeBlanc, David E. Boyce, A bilevel programming algorithm for exact solution of the network design problem with user-optimal flows, Transportation Res. Part B, 20 (1986), 259–265

[30]

P. Marcotte, Network design problem with congestion effects: a case of bilevel programming, Math. Programming, 34 (1986), 142–162

Digital Library

[31]

R. E. Marsten, The design of the XMP linear programming library, Trans. Math. Software, 7 (1981), 481–497

Digital Library

[32]

K. G. Murty, Solving the fixed-charge problem by ranking the extreme points, Oper. Res., 16 (1968), 268–279

Digital Library

[33]

P. M. Pardalos, J. B. Rosen, Constrained global optimization: algorithms and applications, Lecture Notes in Computer Science, Vol. 268, Springer-Verlag, Berlin, 1987viii+143

Digital Library

[34]

G. Papavassilopoulos, Algorithms for static Stakelberg games with linear costs and polyhedral constraints, Proc. 21st IEEE Conference on Decisions and Control, 1982, 647–652

[35]

G. Savard, Ph.D. Thesis, Contributions a la programmation mathématique à deux niveaux, École Polytechnique de Montréal, Montréal, Canada, 1989, April

[36]

Hamdy A. Taha, Integer Programming: Theory, Applications and Computations, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, 1975xii+380

[37]

G. Ünlü, A linear bilevel programming algorithm based on bicriteria programming, Comput. Oper. Res., 14 (1987), 173–179

Digital Library

[38]

Richard E. Wendell, Multiple objective mathematical programming with respect to multiple decision-makers, Oper. Res., 28 (1980), 1100–1111

Cited By

Banerjee SHssaine CLuo QSamaranayake S(2025)Plan Your System and Price for FreeTransportation Science10.1287/trsc.2022.045259:1(13-27)Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1287/trsc.2022.0452
Chen ZWang YSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Locally differentially private decentralized stochastic bilevel optimization with guaranteed convergence accuracyProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692358(7389-7439)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692358
Li YLin GZhu X(2024)Solving Bilevel Programs Based on Lower-Level Mond-Weir DualityINFORMS Journal on Computing10.1287/ijoc.2023.010836:5(1225-1241)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1287/ijoc.2023.0108
Show More Cited By

Index Terms

New Branch-and-Bound Rules for Linear Bilevel Programming
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Continuous optimization
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Continuous optimization
        Linear programming
      2. Mixed discrete-continuous optimization
        Integer programming

Index terms have been assigned to the content through auto-classification.

Recommendations

A Branch and Bound Algorithm for the Bilevel Programming Problem

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 ...
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 ...
Reformulation of bilevel linear fractional/linear programming problem into a mixed integer programming problem via complementarity problem

The bilevel programming problem is a static version of the Stackelberg's leader follower game in which Stackelberg strategy is used by the higher level decision maker called the leader given the rational reaction of the lower decision maker called the ...

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 13, Issue 5

Sep 1992

226 pages

ISSN:0196-5204

Issue’s Table of Contents

Copyright © 1992 Society for Industrial and Applied Mathematics.

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 September 1992

Author Tags

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

118
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

Banerjee SHssaine CLuo QSamaranayake S(2025)Plan Your System and Price for FreeTransportation Science10.1287/trsc.2022.045259:1(13-27)Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1287/trsc.2022.0452
Chen ZWang YSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Locally differentially private decentralized stochastic bilevel optimization with guaranteed convergence accuracyProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692358(7389-7439)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692358
Li YLin GZhu X(2024)Solving Bilevel Programs Based on Lower-Level Mond-Weir DualityINFORMS Journal on Computing10.1287/ijoc.2023.010836:5(1225-1241)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1287/ijoc.2023.0108
Lunday B(2024)The maximal covering location disruption problemComputers and Operations Research10.1016/j.cor.2024.106721169:COnline publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1016/j.cor.2024.106721
Malo PEskelinen JZhou XKuosmanen T(2024)Computing Synthetic Controls Using Bilevel OptimizationComputational Economics10.1007/s10614-023-10471-764:2(1113-1136)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s10614-023-10471-7
Dogan VPrestwich SO’Sullivan B(2024)A Fully Bayesian Approach to Bilevel ProblemsAlgorithmic Decision Theory10.1007/978-3-031-73903-3_10(144-159)Online publication date: 14-Oct-2024
https://dl.acm.org/doi/10.1007/978-3-031-73903-3_10
Yang YXiao PJi KOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Achieving O(ε-1.5) complexity in hessian/jacobian-free stochastic bilevel optimizationProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3667837(39491-39503)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3667837
Xiao PJi KKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Communication-efficient federated hypergradient computation via aggregated iterative differentiationProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3619992(38059-38086)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3619992
Xu SZhu MWilliams BChen YNeville J(2023)Efficient gradient approximation method for constrained bilevel optimizationProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i10.26473(12509-12517)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i10.26473
Nguyen CHoang NVu H(2023)A Joint Trajectory Planning and Signal Control Framework for a Network of Connected and Autonomous VehiclesIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2023.324128124:5(5052-5068)Online publication date: 1-May-2023
https://dl.acm.org/doi/10.1109/TITS.2023.3241281
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents