## Abstract

We study the set S = {(x, y) ε R_{+} × Z^{n} : x + B_{j}y_{j} ≥ b_{j}, j = 1, ..., n}, where B _{j}, b_{j} ε Re_{+} - {0}, j = 1, ..., n, and B _{1} | ... | B _{n} . The set S generalizes the mixed-integer rounding (MIR) set of Nemhauser and Wolsey and the mixing-MIR set of Günlük 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.

Original language | English |
---|---|

Pages (from-to) | 73-103 |

Number of pages | 31 |

Journal | Mathematical Programming |

Volume | 115 |

Issue number | 1 |

DOIs | |

State | Published - Sep 2008 |

## Keywords

- Branch-and-cut
- Computational complexity
- Lot-sizing
- Mixed-integer programming
- Polyhedral combinatorics
- Simple mixed-integer set
- Simple-set cutting plane