Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case

被引：17

作者：

Lee, H ^{[1
]}

Nemhauser, GL ^{[1
]}

Wang, YH ^{[1
]}

机构：

[1] GEORGIA INST TECHNOL,SCH IND & SYST ENGN,ATLANTA,GA 30332

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1996年 / 94卷 / 01期

基金：

美国国家科学基金会;

关键词：

quadratic cost partition; submodular function; mixed-integer programming;

D O I：

10.1016/0377-2217(95)00205-7

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

We give a new mixed integer programming (MIP) formulation for the quadratic cost partition problem that is derived from a MIP formulation for maximizing a submodular function, Several classes of valid inequalities for the convex hull of the feasible solutions are derived using the valid inequalities for the node packing polyhedron. Facet defining conditions and separation algorithms are discussed and computational results are reported.

引用

页码：154 / 166

页数：13

共 17 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2] EXPERIMENTS IN QUADRATIC 0-1 PROGRAMMING [J].

BARAHONA, F ;

JUNGER, M ;

REINELT, G .

MATHEMATICAL PROGRAMMING, 1989, 44 (02) :127-137

[3]

BIXBY RE, 1982, ADV TECHNIQUES PRACT, P333

[4] THE INDEFINITE ZERO-ONE QUADRATIC PROBLEM [J].

CARTER, MW .

DISCRETE APPLIED MATHEMATICS, 1984, 7 (01) :23-44

[5]

Grotschel M., 1988, GEOMETRIC ALGORITHMS

[6]

HOFFMAN K, 1985, ANN DISCRETE MATH, V2, P201

[7]

LEE H, 1991, THESIS GEORGIA I TEC

[8]

Lovasz L., 1983, Mathematical Programming: The State of the Art, P235, DOI [DOI 10.1007/978-3-642-68874-4_10, 10.1007/978-3-642-68874-410]

[9]

Nemhauser G. L., 1988, Integer and Combinatorial Optimization

[10] ANALYSIS OF APPROXIMATIONS FOR MAXIMIZING SUBMODULAR SET FUNCTIONS .1. [J].

NEMHAUSER, GL ;

WOLSEY, LA ;

FISHER, ML .

MATHEMATICAL PROGRAMMING, 1978, 14 (03) :265-294

← 1 2 →