On the polyhedral lift-and-project methods and the fractional stable set polytope

Discrete Optimization - Tập 6 - Trang 206-213 - 2009
Yu-Hin Au1, Levent Tunçel1
1Department of Combinatorics and Optimization Faculty of Mathematics University of Waterloo Waterloo, Ontario N2L 3G1, Canada

Tài liệu tham khảo

Aguilera, 2004, Lift and project relaxations for the matching and related polytopes, Discrete Appl. Math., 134, 193, 10.1016/S0166-218X(03)00337-8

S. Arora, B. Bollobás, L. Lovász, Proving integrality gaps without knowing the linear program, in: Proc. 43rd IEEE Symp. FOCS, 2002, pp. 313–322

Y. Au, On the polyhedral lift-and-project rank conjecture for the fractional stable set polytope, M.Math. Thesis, Dept. of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Canada, 2008

E. Balas, Disjunctive programming: Properties of the convex hull of feasible points, Management Science Research Report 348 GSIA, Carnegie Mellon University, Pittsburgh, PA, USA, 1974. (Appeared as: E. Balas, Disjunctive programming: Properties of the convex hull of feasible points, Discrete Appl. Math. 89 (1998) 3–44.)

Balas, 1993, A lift-and-project cutting plane algorithm for mixed 0-1 programs, Math. Program., 58, 295, 10.1007/BF01581273

Bienstock, 2004, Tree-width and the Sherali-Adams operator, Discrete Optim., 1, 13, 10.1016/j.disopt.2004.03.002

Bienstock, 2004, Subset algebra lift operators for 0-1 integer programming, SIAM J. Optim., 15, 63, 10.1137/S1052623402420346

Cook, 2001, On the matrix-cut rank of polyhedra, Math. Oper. Res., 26, 19, 10.1287/moor.26.1.19.10593

Cornuéjols, 2008, Valid inequalities for mixed integer linear programs, Math. Program., 112, 3, 10.1007/s10107-006-0086-0

Cornuéjols, 2001, Elementary closures for integer programs, Oper. Res. Lett., 28, 1, 10.1016/S0167-6377(00)00067-5

de Klerk, 2002, Approximation of the stability number of a graph via copositive programming, SIAM J. Optim., 12, 875, 10.1137/S1052623401383248

Goemans, 2001, When does the positive semidefiniteness constraint help in lifting procedures, Math. Oper. Res., 26, 796, 10.1287/moor.26.4.796.10012

Laurent, 2003, A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for 0-1 programming, Math. Oper. Res., 28, 470, 10.1287/moor.28.3.470.16391

L. Lipták, Critical facets of the stable set polytope, Ph.D. Thesis, Yale University, 1999

Lipták, 2003, Stable set problem and the lift-and-project ranks of graphs, Math. Program., 98, 319, 10.1007/s10107-003-0407-5

Lovász, 1991, Cones of matrices and set-functions and 0-1 optimization, SIAM J. Optim., 1, 166, 10.1137/0801013

Peña, 2007, Computing the stability number of a graph via linear and semidefinite programming, SIAM J. Optim., 18, 87, 10.1137/05064401X

Sherali, 1999, 31

Sherali, 1990, A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems, SIAM J. Discrete Math., 3, 411, 10.1137/0403036

Sherali, 1996, Tighter representations for set partitioning problems, Discrete Appl. Math., 68, 153, 10.1016/0166-218X(95)00060-5

Stephen, 1999, On a representation of the matching polytope via semidefinite liftings, Math. Oper. Res., 24, 1, 10.1287/moor.24.1.1

Thông tin
Thông tin xuất bản

Discrete Optimization

Tập 6

206-213

Thông tin tác giả