The mixing-MIR set with divisible capacities (Q930344)

From MaRDI portal
scientific article
Language Label Description Also known as
English
The mixing-MIR set with divisible capacities
scientific article

    Statements

    The mixing-MIR set with divisible capacities (English)
    0 references
    30 June 2008
    0 references
    The authors study a generalization of the mixed integer rounding set, namely the mixing MIR set \(S=\{(x,y) \in \mathbb{R}_+ \times \mathbb{Z}^n: x+B_j y_j \geq b_j, j=1, \ldots, n\}\), where \(B_j, b_j \in \mathbb{R}_+ \setminus \{0\}\) and \(B_1|\cdots|B_n\), which arises in mixed integer programming. The authors determine all \(n+1\) extreme rays and all extreme points of \(P=conv(S)\) and show that the number of extreme points may grow exponentially with \(n\) in the worst case. They then develop a polynomial time algorithm for maximizing \(cx+dy\) over \((x,y) \in S\) as well as maximizing \((x^*,y^*)\cdot \omega\) over \(\omega \in \Omega\), where \(\Omega\) is the polar of \(P\).
    0 references
    Mixed integer programming
    0 references
    cutting plane
    0 references
    simple mixed integer set
    0 references
    polyhedral combinatorics
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers