
We introduce a novel scheme based on a blending of Fourier-Motzkin elimination (FME) and adjustable robust optimization techniques to compute the maximum volume inscribed ellipsoid (MVE) in a polytopic projection. It is well-known that deriving an explicit description of a projected polytope is NP-hard. Our approach does not require an explicit description of the projection, and can easily be generalized to find a maximally sized convex body of a polytopic projection. Our obtained MVE is an inner approximation of the projected polytope, and its center is a centralized relative interior point of the projection. Since FME may produce many redundant constraints, we apply an LP-based procedure to keep the description of the projected polytopes at its minimal size. Furthermore, we propose an upper bounding scheme to evaluate the quality of the inner approximations. We test our approach on a simple polytope and a color tube design problem, and observe that as more auxiliary variables are eliminated, our inner approximations and upper bounds converge to optimal solutions. The online supplement is available at https://doi.org/10.1287/ijoc.2017.0763 .
adjustable robust optimization, removing redundant constraints, Maximum volume inscribed ellipsoid, polytopic projection, Chebyshev center; removing redundant constraints, Robustness in mathematical programming, Approximation methods and heuristics in mathematical programming, maximum volume inscribed ellipsoid, Maximum volume inscribed ellipsoid; chebyshev center; polytopic projection; adjustable robust optimization, chebyshev center, Production models, Chebyshev center, Fourier-Motzkin elimination, jel: jel:C63, jel: jel:C61, jel: jel:C44
adjustable robust optimization, removing redundant constraints, Maximum volume inscribed ellipsoid, polytopic projection, Chebyshev center; removing redundant constraints, Robustness in mathematical programming, Approximation methods and heuristics in mathematical programming, maximum volume inscribed ellipsoid, Maximum volume inscribed ellipsoid; chebyshev center; polytopic projection; adjustable robust optimization, chebyshev center, Production models, Chebyshev center, Fourier-Motzkin elimination, jel: jel:C63, jel: jel:C61, jel: jel:C44
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 23 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
