Enhanced exact algorithms for discrete bilevel linear problems

被引：27
|
作者：
Caramia, Massimiliano [1 ]
Mari, Renato [1 ]
机构：
[1] Univ Roma Tor Vergata, Dipartimento Ingn Impresa, I-00133 Rome, Italy
来源：
OPTIMIZATION LETTERS | 2015年 / 9卷 / 07期
关键词：
Bilevel linear programming; Discrete bilevel linear problems; Exact methods; Cutting planes; Branch and cut; PROGRAMMING PROBLEM; CUT ALGORITHM; BRANCH;
D O I：
10.1007/s11590-015-0872-9
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
We address a particular class of bilevel linear programming problems in which all the variables are discrete. The main computational complexities are analyzed and two enhanced exact algorithms are proposed. The rationale behind these two algorithms is described and a modified version is presented for both. A common test bed is used to assess their computational efficiency along with a comparison with an existing benchmark algorithm.
引用
收藏
页码：1447 / 1468
页数：22
相关论文
共 50 条
  • [1] Enhanced exact algorithms for discrete bilevel linear problems
    Massimiliano Caramia
    Renato Mari
    Optimization Letters, 2015, 9 : 1447 - 1468
  • [2] An Exact Correspondence of Linear Problems and Randomizing Linear Algorithms
    Eaves, B. Curtis
    Rothblum, Uriel G.
    MATHEMATICS OF OPERATIONS RESEARCH, 2014, 39 (03) : 607 - 623
  • [3] Exact and Approximation Algorithms for Linear Arrangement Problems
    Quilliot, Alain
    Rebaine, Djamal
    FEDERATED CONFERENCE ON COMPUTER SCIENCE AND INFORMATION SYSTEMS, 2014, 2014, 2 : 493 - 500
  • [4] Discrete differential evolution algorithm for integer linear bilevel programming problems
    Hong Li
    Li Zhang
    Yongchang Jiao
    Journal of Systems Engineering and Electronics, 2016, 27 (04) : 912 - 919
  • [5] Discrete differential evolution algorithm for integer linear bilevel programming problems
    Li, Hong
    Zhang, Li
    Jiao, Yongchang
    JOURNAL OF SYSTEMS ENGINEERING AND ELECTRONICS, 2016, 27 (04) : 912 - 919
  • [6] A new approach for solving linear bilevel problems using genetic algorithms
    Calvete, Herminia I.
    Gale, Carmen
    Mateo, Pedro M.
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 188 (01) : 14 - 28
  • [7] Exact Optimization Conditions for Discrete Linear Inverse Problems
    Tuysuzoglu, Ahmet
    Yilmaz, Emre
    Karl, W. Clem
    Castanon, David
    2013 IEEE GLOBAL CONFERENCE ON SIGNAL AND INFORMATION PROCESSING (GLOBALSIP), 2013, : 1117 - 1121
  • [8] Solving discrete linear bilevel optimization problems using the optimal value reformulation
    S. Dempe
    F. Mefo Kue
    Journal of Global Optimization, 2017, 68 : 255 - 277
  • [9] Solving discrete linear bilevel optimization problems using the optimal value reformulation
    Dempe, S.
    Kue, F. Mefo
    JOURNAL OF GLOBAL OPTIMIZATION, 2017, 68 (02) : 255 - 277
  • [10] Discrete linear bilevel programming problem
    Departamento de Matemática, Universidade de Coimbra, Coimbra, Portugal
    不详
    不详
    J. Optim. Theory Appl., 3 (597-614):
12345