Experimental results on using general disjunctions in branch-and-bound for general-integer linear programs

被引：16
|
作者：
Owen, JH [1 ]
Mehrotra, S [1 ]
机构：
[1] Northwestern Univ, Dept Ind Engn & Management Sci, Robert R McCormick Sch Engn, Evanston, IL 60208 USA
来源：
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS | 2001年 / 20卷 / 02期
关键词：
integer programming; disjunctions; branch-and-bound;
D O I：
10.1023/A:1011207119557
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
Typical implementations of branch-and-bound for integer linear programs choose to branch on single variables. In this paper we explore the use of general disjunctions for branching when solving linear programs with general-integer variables. We give computational results that show that the size of the enumeration tree can be greatly reduced by branching on such disjunctions rather than on single variables.
引用
收藏
页码：159 / 170
页数：12
相关论文
共 50 条
  • [1] Experimental Results on Using General Disjunctions in Branch-and-Bound for General-Integer Linear Programs
    Jonathan H. Owen
    Sanjay Mehrotra
    Computational Optimization and Applications, 2001, 20 : 159 - 170
  • [2] Learning efficient branch-and-bound for solving Mixed Integer Linear Programs
    Du, Shuhan
    Tong, Junbo
    Fan, Wenhui
    APPLIED SOFT COMPUTING, 2025, 172
  • [3] Sub-Exponential Lower Bounds for Branch-and-Bound with General Disjunctions via Interpolation
    Glaeser, Max
    Pfetsch, Marc E.
    PROCEEDINGS OF THE 2024 ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA, 2024, : 3747 - 3764
  • [4] COMPUTATIONAL RESULTS WITH A BRANCH-AND-BOUND ALGORITHM FOR THE GENERAL KNAPSACK PROBLEM
    BULFIN, RL
    PARKER, RG
    SHETTY, CM
    NAVAL RESEARCH LOGISTICS, 1979, 26 (01) : 41 - 46
  • [5] BRANCH-AND-BOUND METHODS - GENERAL FORMULATION AND PROPERTIES
    MITTEN, LG
    OPERATIONS RESEARCH, 1970, 18 (01) : 24 - &
  • [6] A lifted linear programming branch-and-bound algorithm for mixed-integer conic quadratic programs
    Vielma, Juan Pablo
    Ahmed, Shabbir
    Nemhauser, George L.
    INFORMS JOURNAL ON COMPUTING, 2008, 20 (03) : 438 - 450
  • [7] AND/OR branch-and-bound for solving mixed integer linear programming problems
    Marinescu, R
    Dechter, R
    PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING - CP 2005, PROCEEDINGS, 2005, 3709 : 857 - 857
  • [8] Branch-and-Bound for Biobjective Mixed-Integer Linear Programming
    Adelgren, Nathan
    Gupte, Akshay
    INFORMS JOURNAL ON COMPUTING, 2022, 34 (02) : 909 - 933
  • [9] An enhanced branch-and-bound algorithm for bilevel integer linear programming
    Liu, Shaonan
    Wang, Mingzheng
    Kong, Nan
    Hu, Xiangpei
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2021, 291 (02) : 661 - 679
  • [10] A branch-and-bound method for multistage stochastic integer programs with risk objectives
    Heinze, Thomas
    Schultz, Ruediger
    OPTIMIZATION, 2008, 57 (02) : 277 - 293
12345