On the value of binary expansions for general mixed-integer linear programs

被引：25
|
作者：
Owen, JH
Mehrotra, S
机构：
[1] GM Corp, Ctr Res & Dev, Enterprise Syst Lab, Warren, MI 48090 USA
[2] Northwestern Univ, Robert R McCormick Sch Engn, Dept Ind Engn & Management Sci, Evanston, IL 60208 USA
来源：
OPERATIONS RESEARCH | 2002年 / 50卷 / 05期
关键词：
D O I：
10.1287/opre.50.5.810.370
中图分类号：
C93 [管理学];
学科分类号：
12 ; 1201 ; 1202 ; 120202 ;
摘要：
We study the use of binary variables in reformulating general mixed integer linear programs We show that binary reformulations result in problems for which almost all the binary variables replacing a general integer variable need to be explored during branching We also give computational results on the performance of such reformulations in solving the mixed integer programs which support our theoretical results.
引用
收藏
页码：810 / 819
页数：10
相关论文
共 50 条
  • [1] Analyzing infeasible mixed-integer and integer linear programs
    Guieu, O
    Chinneck, JW
    INFORMS JOURNAL ON COMPUTING, 1999, 11 (01) : 63 - 77
  • [2] A disjunctive cutting plane procedure for general mixed-integer linear programs
    Jonathan H. Owen
    Sanjay Mehrotra
    Mathematical Programming, 2001, 89 : 437 - 448
  • [3] A disjunctive cutting plane procedure for general mixed-integer linear programs
    Owen, JH
    Mehrotra, S
    MATHEMATICAL PROGRAMMING, 2001, 89 (03) : 437 - 448
  • [4] Finite Disjunctive Programming Characterizations for General Mixed-Integer Linear Programs
    Chen, Binyuan
    Kuecuekyavuz, Simge
    Sen, Suvrajeet
    OPERATIONS RESEARCH, 2011, 59 (01) : 202 - 210
  • [5] A New General-Purpose Algorithm for Mixed-Integer Bilevel Linear Programs
    Fischetti, Matteo
    Ljubic, Ivana
    Monaci, Michele
    Sinnl, Markus
    OPERATIONS RESEARCH, 2017, 65 (06) : 1615 - 1637
  • [6] Approximating the stability region for binary mixed-integer programs
    Kilinc-Karzan, Fatma
    Toriello, Alejandro
    Ahmed, Shabbir
    Nemhauser, George
    Savelsbergh, Martin
    OPERATIONS RESEARCH LETTERS, 2009, 37 (04) : 250 - 254
  • [7] Extending the QCR method to general mixed-integer programs
    Billionnet, Alain
    Elloumi, Sourour
    Lambert, Amelie
    MATHEMATICAL PROGRAMMING, 2012, 131 (1-2) : 381 - 401
  • [8] Extending the QCR method to general mixed-integer programs
    Alain Billionnet
    Sourour Elloumi
    Amélie Lambert
    Mathematical Programming, 2012, 131 : 381 - 401
  • [9] A DC Programming Approach for Mixed-Integer Linear Programs
    Niu, Yi-Shuai
    Dinh, Tao Pham
    MODELLING, COMPUTATION AND OPTIMIZATION IN INFORMATION SYSTEMS AND MANAGEMENT SCIENCES, PROCEEDINGS, 2008, 14 : 244 - 253
  • [10] A computational study of the cutting plane tree algorithm for general mixed-integer linear programs
    Chen, Binyuan
    Kuecuekyavuz, Simge
    Sen, Suvrajeet
    OPERATIONS RESEARCH LETTERS, 2012, 40 (01) : 15 - 19
12345