A simplex-based algorithm for 0-1 mixed integer programming

被引：0
|
作者：
Richard, JPP [1 ]
de Farias, IR
Nemhauser, GL
机构：
[1] Georgia Inst Technol, Sch Ind & Syst Engn, Atlanta, GA 30332 USA
[2] Ctr Operat Res & Econometr, B-1348 Louvain, Belgium
来源：
COMBINATORIAL OPTIMIZATION - EUREKA, YOU SHRINK: PAPERS DEDICATED TO JACK EDMONDS | 2003年 / 2570卷
关键词：
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We present a finitely convergent cutting plane algorithm for 0-1 mixed integer programming. The algorithm is a hybrid between a strong cutting plane and a Gomory-type algorithm that generates violated facet-defining inequalities of a relaxation of the simplex tableau and uses them as cuts for the original problem. We show that the cuts can be computed in polynomial time and can be embedded in a finitely convergent algorithm.
引用
收藏
页码：158 / 170
页数：13
相关论文
共 50 条
  • [1] A BRANCH-AND-BOUND ALGORITHM FOR 0-1 PARAMETRIC MIXED INTEGER PROGRAMMING
    OHTAKE, Y
    NISHIDA, N
    OPERATIONS RESEARCH LETTERS, 1985, 4 (01) : 41 - 45
  • [2] An approximation algorithm for quadratic cost 0-1 mixed integer programming problems
    Mukai, K
    Tatsumi, K
    Fukushima, M
    ELECTRONICS AND COMMUNICATIONS IN JAPAN PART III-FUNDAMENTAL ELECTRONIC SCIENCE, 1999, 82 (06): : 9 - 17
  • [3] Approximation algorithm for quadratic cost 0-1 mixed integer programming problems
    Mukai, Kumiko
    Tatsumi, Keiji
    Fukushima, Masao
    Electronics and Communications in Japan, Part III: Fundamental Electronic Science (English translation of Denshi Tsushin Gakkai Ronbunshi), 1999, 82 (06): : 9 - 16
  • [4] A dynamic attribute reduction algorithm based on 0-1 integer programming
    Xu, Yitian
    Wang, Laisheng
    Zhang, Ruiyan
    KNOWLEDGE-BASED SYSTEMS, 2011, 24 (08) : 1341 - 1347
  • [5] Mixed integer programming for the 0-1 maximum probability model
    Billionnet, A
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2004, 156 (01) : 83 - 91
  • [6] New convergent heuristics for 0-1 mixed integer programming
    Wilbaut, Christophe
    Hanafi, Said
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2009, 195 (01) : 62 - 74
  • [7] Pivot, Cut, and Dive: a heuristic for 0-1 mixed integer programming
    Jonathan Eckstein
    Mikhail Nediak
    Journal of Heuristics, 2007, 13 : 471 - 503
  • [8] Lifted inequalities for 0-1 mixed integer programming: Superlinear lifting
    J.-P.P. Richard
    I.R. de Farias Jr
    G.L. Nemhauser
    Mathematical Programming, 2003, 98 : 115 - 143
  • [9] AN APPROXIMATE METHOD FOR MIXED 0-1 INTEGER PROGRAMMING AND ITS APPLICATION
    HARA, H
    YUGAMI, N
    OHTA, Y
    FUJITSU SCIENTIFIC & TECHNICAL JOURNAL, 1994, 30 (01): : 75 - 83
  • [10] Pivot, Cut, and Dive: a heuristic for 0-1 mixed integer programming
    Eckstein, Jonathan
    Nediak, Mikhail
    JOURNAL OF HEURISTICS, 2007, 13 (05) : 471 - 503
12345