The mixing-MIR set with divisible capacities

• 成果类型: Article
• 署名作者: Zhao, M.; de Farias, I. R., Jr.
• 署名单位: State University of New York (SUNY) System; University at Buffalo, SUNY; State University of New York (SUNY) System; SUNY Optometry; SUNY Maritime College; SUNY Community College
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-007-0140-6
• 发表日期: 2008
• 页码: 73-103
• 关键词: mixed-integer programs; intersection cuts; cutting planes; convex-hull; inequalities; optimization; formulations; SEPARATION; closures; Knapsack

摘要

We study the set = {(x, y) is an element of R+ x Z(n) : x + B(j)y(j) >= b(j), j=1,..., n}, where B-j, b(j) is an element of R+ -{0}, j = 1,..., n, and B-1 vertical bar...vertical bar B-n. The set S generalizes the mixed-integer rounding (MIR) set of Nemhauser and Wolsey and the mixing-MIR set of Gunluk and Pochet. In addition, it arises as a substructure in general mixed-integer programming (MIP), such as in lot-sizing. Despite its importance, a number of basic questions about S remain unanswered, including the tractability of optimization over S and how to efficiently find a most violated cutting plane valid for P = conv (S). We address these questions by analyzing the extreme points and extreme rays of P. We give all extreme points and extreme rays of P. In the worst case, the number of extreme points grows exponentially with n. However, we show that, in some interesting cases, it is bounded by a polynomial of n. In such cases, it is possible to derive strong cutting planes for P efficiently. Finally, we use our results on the extreme points of P to give a polynomial-time algorithm for solving optimization over S.