34 citations · 49 across the 15 of their papers we have counts for
19 papers
Optimal Proximity Bound and Product Function Estimates in Integer Linear Programming
Iskander Aliev, Gennadiy Averkov, William Jones +1
We obtain an optimal proximity bound for integer linear programs in standard form max{cx: Ax=b, x nonnegative integer}, where A is an integer mxn matrix of rank m<n and b is an int…
Exact Decomposition Branching exploiting Lattice Structures
Katrin Halbig, Timm Oertel, Dieter Weninger
Strict inequalities in mixed-integer linear optimization can cause difficulties in guaranteeing convergence and exactness. Utilizing that optimal vertex solutions follow a lattice…
Sparse Approximation in Lattices and Semigroups
Stefan Kuhlmann, Timm Oertel, Robert Weismantel
This paper deals with the following question: Suppose that there exist an integer or a non-negative integer solution to a system , where the number of non-zero componen…
Asymptotic Bounds and Online Algorithms for Average-Case Matrix Discrepancy
Dmitriy Kunisky, Timm Oertel, Nicola Wengiel +1
We study the matrix discrepancy problem in the average-case setting. Given a sequence of symmetric matrices , its discrepancy is defined as the minimal…
New Bounds for the Integer Carathéodory Rank
Iskander Aliev, Martin Henk, Mark Hogan +2
Given a rational pointed -dimensional cone , we study the integer Carathéodory rank and its asymptotic form , where we co…
A Colorful Steinitz Lemma with Applications to Block Integer Programs
Timm Oertel, Joseph Paat, Robert Weismantel
The Steinitz constant in dimension is the smallest value such that for any norm on and for any finite zero-sum sequence in the unit ball, the sequence…
Optimizing Sparsity over Lattices and Semigroups
Iskander Aliev, Gennadiy Averkov, Jesús A. De Loera +1
Motivated by problems in optimization we study the sparsity of the solutions to systems of linear Diophantine equations and linear integer programs, i.e., the number of non-zero en…
Sparsity of integer solutions in the average case
Timm Oertel, Joseph Paat, Robert Weismantel
We examine how sparse feasible solutions of integer programs are, on average. Average case here means that we fix the constraint matrix and vary the right-hand side vectors. For a…
The distributions of functions related to parametric integer optimization
Timm Oertel, Joseph Paat, Robert Weismantel
We consider the asymptotic distribution of the IP sparsity function, which measures the minimal support of optimal IP solutions, and the IP to LP distance function, which measures…
Distances to Lattice Points in Knapsack Polyhedra
Iskander Aliev, Martin Henk, Timm Oertel
We give an optimal upper bound for the maximum-norm distance from a vertex of a knapsack polyhedron to its nearest feasible lattice point. In a randomised setting, we show that the…
The Support of Integer Optimal Solutions
Iskander Aliev, Jesus De Loera, Fritz Eisenbrand +2
The support of a vector is the number of nonzero-components. We show that given an integral matrix , the integer linear optimization problem $\max\left\{\boldsymbol{…
Integrality Gaps of Integer Knapsack Problems
Iskander Aliev, Martin Henk, Timm Oertel
We obtain optimal lower and upper bounds for the (additive) integrality gaps of integer knapsack problems. In a randomised setting, we show that the integrality gap of a "typical"…
A Note on Non-Degenerate Integer Programs with Small Sub-Determinants
Stephan Artmann, Friedrich Eisenbrand, Christoph Glanzer +3
The intention of this note is two-fold. First, we study integer optimization problems in standard form defined by and present an algorithm to solve s…
Sparse solutions of linear Diophantine equations
Iskander Aliev, Jesus A. De Loera, Timm Oertel +1
We present structural results on solutions to the Diophantine system , with the smallest number of non…
Centerpoints: A link between optimization and convex geometry
Amitabh Basu, Timm Oertel
We introduce a concept that generalizes several different notions of a "centerpoint" in the literature. We develop an oracle-based algorithm for convex mixed-integer optimization b…
Duality for Mixed-Integer Convex Minimization
Michel Baes, Timm Oertel, Robert Weismantel
We extend in two ways the standard Karush-Kuhn-Tucker optimality conditions to problems with a convex objective, convex functional constraints, and the extra requirement that some…
Note on the Complexity of the Mixed-Integer Hull of a Polyhedron
Robert Hildebrand, Timm Oertel, Robert Weismantel
We study the complexity of computing the mixed-integer hull of a polyhedron . Given an inequality description, with on…
Mirror-Descent Methods in Mixed-Integer Convex Optimization
Michel Baes, Timm Oertel, Christian Wagner +1
In this paper, we address the problem of minimizing a convex function f over a convex set, with the extra constraint that some variables must be integer. This problem, even when f…
Convex integer minimization in fixed dimension
Timm Oertel, Christian Wagner, Robert Weismantel
We show that minimizing a convex function over the integer points of a bounded convex set is polynomial in fixed dimension.