A RECURSIVE PROCEDURE TO GENERATE ALL CUTS FOR 0-1 MIXED INTEGER PROGRAMS

被引：116

作者：

NEMHAUSER, GL ^{[1
]}

WOLSEY, LA ^{[1
]}

机构：

[1] CATHOLIC UNIV LOUVAIN,CTR OPERAT RES & ECONOMETR,B-1348 LOUVAIN LA NEUVE,BELGIUM

来源：

MATHEMATICAL PROGRAMMING | 1990年 / 46卷 / 03期

关键词：

0-1 mixed integer programs; Cutting planes; disjunctive inequalities; superadditive functions; valid inequalities;

D O I：

10.1007/BF01585752

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We study several ways of obtaining valid inequalities for mixed integer programs. We show how inequalities obtained from a disjunctive argument can be represented by superadditive functions and we show how the superadditive inequalities relate to Gomory's mixed integer cuts. We also show how all valid inequalities for mixed 0-1 programs can be generated recursively from a simple subclass of the disjunctive inequalities. © 1990 North-Holland.

引用

页码：379 / 390

页数：12

共 10 条

[1]

Balas E., 1975, NONLINEAR PROGRAMMIN, V2, P279

[2] 2 RULES FOR DEDUCING VALID INEQUALITIES FOR 0-1 PROBLEMS [J].

BLAIR, C .

SIAM JOURNAL ON APPLIED MATHEMATICS, 1976, 31 (04) :614-617

[3]

Chvatal V., 1973, Discrete Mathematics, V4, P305, DOI 10.1016/0012-365X(73)90167-2

[4]

COOK W, 1987, 86444OR BONN U I EC

[5]

Gomory Ralph E., 1963, RECENT ADV MATH PROG, P269

[6] CUTTING-PLANE THEORY - ALGEBRAIC METHODS [J].

JEROSLOW, R .

DISCRETE MATHEMATICS, 1978, 23 (02) :121-150

[7]

Jeroslow R., 1972, ANN DISCRETE MATH, V1, P293

[8]

Johnson E.L., 1974, MATH PROGRAM STUD, P137

[9]

NEMHAUSER GL, 1984, CORE DP8439 U CATH L

[10]

Schrijver Alexander, 1980, COMBINATORICS 79, V9, P291, DOI [10.1016/S0167-5060(08)70085-2, DOI 10.1016/S0167-5060(08)70085-2]

← 1 →