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