Finding the Dimension of a Non-empty Orthogonal Array Polytope
Document Type
Article
Publication Date
8-2022
Abstract
By using representation theory, we reduce the size of the set of possible values for the dimension of the convex hull of all feasible points polytope of an orthogonal array (OA) defining integer linear program (ILP). Our results address the conjecture that if this polytope is non-empty, then it is full dimensional within the affine space where all the feasible points of the ILP's linear programming (LP) relaxation lie, raised by Appa \etal, [On multi-index assignment polytopes, Linear Algebra and its Applications 416 (23) (2006), 224--241]. In particular, our theoretical results provide a sufficient condition for this polytope to be full dimensional within the LP relaxation affine space when it is non-empty. This sufficient condition implies all the known non-trivial values of the dimension of the (k,s) assignment polytope.
However, our results suggest that the conjecture mentioned above may not be true. More generally we provide previously unknown restrictions on the feasible values of the dimension of convex hull of all feasible points polytope of our OA defining ILP. We also determine all possible corresponding sets of equality constraints up to equivalence that can be implied by the integrality constraints of this ILP. Moreover, we find additional restrictions on the dimension of convex hull of feasible points and larger sets of corresponding equality constraints for the n=2 and even s cases. These cases posses symmetries that do not necessarily exist in the 3≤n or odd s cases.
DOI
10.1016/j.disopt.2022.100727
Source Publication
Discrete Optimization
Recommended Citation
Published version of record: Bulutoglu, D. A. (2022). Finding the dimension of a non-empty orthogonal array polytope. Discrete Optimization, 45(August), 100727. https://doi.org/10.1016/j.disopt.2022.100727
Linked version from arXiv: Bulutoglu, D. (2019) ‘Finding the dimension of a non-empty orthogonal array polytope’. arXiv:1909.02123 [math.RT]
Comments
The "Link to Full Text" button on this page opens or loads the preprint PDF at arXiv:1909.02123 [math.RT]
The final version of record appears as a subscription-acces article in Volume 45 of Discrete Optimization, as cited below.