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 条

[21] Nonlinear separation of data via mixed 0-1 Integer and Linear Programming [J].

Kim, Kwangsoo ;

Ryoo, Hong Seo .

APPLIED MATHEMATICS AND COMPUTATION, 2007, 193 (01) :183-196

[22] Lifted inequalities for 0-1 mixed integer programming: Basic theory and algorithms [J].

Richard, JPP ;

de Farias, IR ;

Nemhauser, GL .

MATHEMATICAL PROGRAMMING, 2003, 98 (1-3) :89-113

[23] Heuristic approaches for biobjective mixed 0-1 integer linear programming problems [J].

Soylu, Banu .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2015, 245 (03) :690-703

[24] Optimization Algorithm for Credibility of Equipment Operational Test Based on 0-1 Integer Linear Programming [J].

Lei, Z. ;

Sun, Y. ;

He, J. W. ;

Zhang, W. .

2015 INTERNATIONAL CONFERENCE ON COMPUTER SCIENCE AND TECHNOLOGY (ICCST 2015), 2015, :347-352

[25] Using a mixed integer programming tool for solving the 0-1 quadratic knapsack problem [J].

Billionnet, A ;

Soutif, E .

INFORMS JOURNAL ON COMPUTING, 2004, 16 (02) :188-197

[26] Constraint violation reduction search for 0-1 mixed integer linear programming problems [J].

Bansal, Ankit ;

Uzsoy, Reha .

ENGINEERING OPTIMIZATION, 2021, 53 (04) :609-626

[27] Using a mixed integer quadratic programming solver for the unconstrained quadratic 0-1 problem [J].

Billionnet, Alain ;

Elloumi, Sourour .

MATHEMATICAL PROGRAMMING, 2007, 109 (01) :55-68

[28] A MIXED INTEGER 0-1 PROGRAMMING HEURISTIC FOR RESOURCE-ALLOCATION IN A DECENTRALIZED SYSTEM [J].

ROY, P .

LECTURE NOTES IN CONTROL AND INFORMATION SCIENCES, 1988, 113 :338-347

[29] Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem [J].

Alain Billionnet ;

Sourour Elloumi .

Mathematical Programming, 2007, 109 :55-68

[30] Mixed integer (0-1) fractional programming for decision support in paper production industry [J].

Claassen, G. D. H. .

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 2014, 43 :21-29

← 1 2 3 4 5 →