The mixing-MIR set with divisible capacities (Q930344)

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\).