
arXiv: 2311.00099
In pure integer linear programming it is often desirable to work with polyhedra that are full-dimensional, and it is well known that it is possible to reduce any polyhedron to a full-dimensional one in polynomial time. More precisely, using the Hermite normal form, it is possible to map a non full-dimensional polyhedron to a full-dimensional isomorphic one in a lower-dimensional space, while preserving integer vectors. In this paper, we extend the above result simultaneously in two directions. First, we consider mixed integer vectors instead of integer vectors, by leveraging on the concept of "integer reflexive generalized inverse." Second, we replace polyhedra with convex quadratic sets, which are sets obtained from polyhedra by enforcing one additional convex quadratic inequality. We study structural properties of convex quadratic sets, and utilize them to obtain polynomial time algorithms to recognize full-dimensional convex quadratic sets, and to find an affine function that maps a non full-dimensional convex quadratic set to a full-dimensional isomorphic one in a lower-dimensional space, while preserving mixed integer vectors. We showcase the applicability and the potential impact of these results by showing that they can be used to prove that mixed integer convex quadratic programming is fixed parameter tractable with parameter the number of integer variables. Our algorithm unifies and extends the known polynomial time solvability of pure integer convex quadratic programming in fixed dimension and of convex quadratic programming.
FOS: Computer and information sciences, Convex programming, Discrete Mathematics (cs.DM), Mixed integer programming, convex quadratic sets, Optimization and Control (math.OC), FOS: Mathematics, mixed integer quadratic programming, Quadratic programming, 90C11, 90C20, 90C26, 90C60, Mathematics - Optimization and Control, FPT algorithm, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Convex programming, Discrete Mathematics (cs.DM), Mixed integer programming, convex quadratic sets, Optimization and Control (math.OC), FOS: Mathematics, mixed integer quadratic programming, Quadratic programming, 90C11, 90C20, 90C26, 90C60, Mathematics - Optimization and Control, FPT algorithm, Computer Science - Discrete Mathematics
| 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). | 0 | |
| 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. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
