BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Robert Weismantel

Robert Weismantel appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.OCmath.CODiscrete MathematicsComputational ComplexityData Structures and Algorithmsmath.MGMachine Learning

Catalog footprint

What is connected

28works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

28 published item(s)

preprint2022arXiv

Extension Complexity Lower Bounds for Mixed-Integer Extended Formulations

We prove that any mixed-integer linear extended formulation for the matching polytope of the complete graph on $n$ vertices, with a polynomial number of constraints, requires $Ω(\sqrt{\sfrac{n}{\log n}})$ many integer variables. By known reductions, this result extends to the traveling salesman polytope. This lower bound has various implications regarding the existence of small mixed-integer mathematical formulations of common problems in operations research. In particular, it shows that for many classic vehicle routing problems and problems involving matchings, any compact mixed-integer linear description of such a problem requires a large number of integer variables. This provides a first non-trivial lower bound on the number of integer variables needed in such settings.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Minimizing a low-dimensional convex function over a high-dimensional cube

For a matrix $W \in \mathbb{Z}^{m \times n}$, $m \leq n$, and a convex function $g: \mathbb{R}^m \rightarrow \mathbb{R}$, we are interested in minimizing $f(x) = g(Wx)$ over the set $\{0,1\}^n$. We will study separable convex functions and sharp convex functions $g$. Moreover, the matrix $W$ is unknown to us. Only the number of rows $m \leq n$ and $\|W\|_{\infty}$ is revealed. The composite function $f(x)$ is presented by a zeroth and first order oracle only. Our main result is a proximity theorem that ensures that an integral minimum and a continuous minimum for separable convex and sharp convex functions are always "close" by. This will be a key ingredient to develop an algorithm for detecting an integer minimum that achieves a running time of roughly $(m \| W \|_{\infty})^{\mathcal{O}(m^3)} \cdot \text{poly}(n)$. In the special case when $(i)$ $W$ is given explicitly and $(ii)$ $g$ is separable convex one can also adapt an algorithm of Hochbaum and Shanthikumar. The running time of this adapted algorithm matches with the running time of our general algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Block-Structured Integer and Linear Programming in Strongly Polynomial and Near Linear Time

We consider integer and linear programming problems for which the linear constraints exhibit a (recursive) block-structure: The problem decomposes into independent and efficiently solvable sub-problems if a small number of constraints is deleted. A prominent example are $n$-fold integer programming problems and their generalizations which have received considerable attention in the recent literature. The previously known algorithms for these problems are based on the augmentation framework, a tailored integer programming variant of local search. In this paper we propose a different approach. Our algorithm relies on parametric search and a new proximity bound. We show that block-structured linear programming can be solved efficiently via an adaptation of a parametric search framework by Norton, Plotkin, and Tardos in combination with Megiddo's multidimensional search technique. This also forms a subroutine of our algorithm for the integer programming case by solving a strong relaxation of it. Then we show that, for any given optimal vertex solution of this relaxation, there is an optimal integer solution within $\ell_1$-distance independent of the dimension of the problem. This in turn allows us to find an optimal integer solution efficiently. We apply our techniques to integer and linear programming with $n$-fold structure or bounded dual treedepth, two benchmark problems in this field. We obtain the first algorithms for these cases that are both near-linear in the dimension of the problem and strongly polynomial. Moreover, unlike the augmentation algorithms, our approach is highly parallelizable.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The distributions of functions related to parametric integer optimization

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 the distance between optimal IP and LP solutions. We create a framework for studying the asymptotic distribution of general functions related to integer optimization. There has been a significant amount of research focused around the extreme values that these functions can attain, however less is known about their typical values. Each of these functions is defined for a fixed constraint matrix and objective vector while the right hand sides are treated as input. We show that the typical values of these functions are smaller than the known worst case bounds by providing a spectrum of probability-like results that govern their overall asymptotic distributions.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Note on Non-Degenerate Integer Programs with Small Sub-Determinants

The intention of this note is two-fold. First, we study integer optimization problems in standard form defined by $A \in\mathbb{Z}^{m\times{}n}$ and present an algorithm to solve such problems in polynomial-time provided that both the largest absolute value of an entry in $A$ and $m$ are constant. Then, this is applied to solve integer programs in inequality form in polynomial-time, where the absolute values of all maximal sub-determinants of $A$ lie between $1$ and a constant.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Optimality certificates for convex minimization and Helly numbers

We consider the problem of minimizing a convex function over a subset of R^n that is not necessarily convex (minimization of a convex function over the integer points in a polytope is a special case). We define a family of duals for this problem and show that, under some natural conditions, strong duality holds for a dual problem in this family that is more restrictive than previously considered duals.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

An FPTAS for Minimizing Indefinite Quadratic Forms over Integers in Polyhedra

We present a generic approach that allows us to develop a fully polynomial-time approximation scheme (FTPAS) for minimizing nonlinear functions over the integer points in a rational polyhedron in fixed dimension. The approach combines the subdivision strategy of Papadimitriou and Yannakakis (2000) with ideas similar to those commonly used to derive real algebraic certificates of positivity for polynomials. Our general approach is widely applicable. We apply it, for instance, to the Motzkin polynomial and to indefinite quadratic forms $x^T Q x$ in a fixed number of variables, where $Q$ has at most one positive, or at most one negative eigenvalue. In dimension three, this leads to an FPTAS for general $Q$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Minimizing Cubic and Homogeneous Polynomials over Integers in the Plane

We complete the complexity classification by degree of minimizing a polynomial over the integer points in a polyhedron in $\mathbb{R}^2$. Previous work shows that optimizing a quadratic polynomial over the integer points in a polyhedral region in $\mathbb{R}^2$ can be done in polynomial time, while optimizing a quartic polynomial in the same type of region is NP-hard. We close the gap by showing that this problem can be solved in polynomial time for cubic polynomials. Furthermore, we show that the problem of minimizing a homogeneous polynomial of any fixed degree over the integer points in a bounded polyhedron in $\mathbb{R}^2$ is solvable in polynomial time. We show that this holds for polynomials that can be translated into homogeneous polynomials, even when the translation vector is unknown. We demonstrate that such problems in the unbounded case can have smallest optimal solutions of exponential size in the size of the input, thus requiring a compact representation of solutions for a general polynomial time algorithm for the unbounded case.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Note on the Complexity of the Mixed-Integer Hull of a Polyhedron

We study the complexity of computing the mixed-integer hull $\operatorname{conv}(P\cap\mathbb{Z}^n\times\mathbb{R}^d)$ of a polyhedron $P$. Given an inequality description, with one integer variable, the mixed-integer hull can have exponentially many vertices and facets in $d$. For $n,d$ fixed, we give an algorithm to find the mixed integer hull in polynomial time. Given $P=\operatorname{conv}(V)$ and $n$ fixed, we compute a vertex description of the mixed-integer hull in polynomial time and give bounds on the number of vertices of the mixed integer hull.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Duality for Mixed-Integer Convex Minimization

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 of the variables must be integral. While the standard Karush-Kuhn-Tucker conditions involve separating hyperplanes, our extension is based on lattice-free polyhedra. Our optimality conditions allow us to define an exact dual of our original mixed-integer convex problem.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Graver basis and proximity techniques for block-structured separable convex integer minimization problems

We consider N-fold 4-block decomposable integer programs, which simultaneously generalize N-fold integer programs and two-stage stochastic integer programs with N scenarios. In previous work [R. Hemmecke, M. Koeppe, R. Weismantel, A polynomial-time algorithm for optimizing over N-fold 4-block decomposable integer programs, Proc. IPCO 2010, Lecture Notes in Computer Science, vol. 6080, Springer, 2010, pp. 219--229], it was proved that for fixed blocks but variable N, these integer programs are polynomial-time solvable for any linear objective. We extend this result to the minimization of separable convex objective functions. Our algorithm combines Graver basis techniques with a proximity result [D.S. Hochbaum and J.G. Shanthikumar, Convex separable optimization is not much harder than linear optimization, J. ACM 37 (1990), 843--862], which allows us to use convex continuous optimization as a subroutine.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Mirror-Descent Methods in Mixed-Integer Convex Optimization

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 is a piecewise linear function, is NP-hard. We study an algorithmic approach to this problem, postponing its hardness to the realization of an oracle. If this oracle can be realized in polynomial time, then the problem can be solved in polynomial time as well. For problems with two integer variables, we show that the oracle can be implemented efficiently, that is, in O(ln(B)) approximate minimizations of f over the continuous variables, where B is a known bound on the absolute value of the integer variables.Our algorithm can be adapted to find the second best point of a purely integer convex optimization problem in two dimensions, and more generally its k-th best point. This observation allows us to formulate a finite-time algorithm for mixed-integer convex optimization.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A probabilistic comparison of the strength of split, triangle, and quadrilateral cuts (extended version)

We consider mixed integer linear sets defined by two equations involving two integer variables and any number of non-negative continuous variables. The non-trivial valid inequalities of such sets can be classified into split, type 1, type 2, type 3, and quadrilateral inequalities. We use a strength measure of Goemans to analyze the benefit from adding a non-split inequality on top of the split closure. Applying a probabilistic model, we show that the importance of a type 2 inequality decreases with decreasing lattice width, on average. Our results suggest that this is also true for type 3 and quadrilateral inequalities.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Maximal lattice-free polyhedra: finiteness and an explicit description in dimension three

A convex set with nonempty interior is maximal lattice-free if it is inclusion-maximal with respect to the property of not containing integer points in its interior. Maximal lattice-free convex sets are known to be polyhedra. The precision of a rational polyhedron $P$ in $\mathbb{R}^d$ is the smallest integer $s$ such that $sP$ is an integral polyhedron. In this paper we show that, up to affine mappings preserving $\mathbb{Z}^d$, the number of maximal lattice-free rational polyhedra of a given precision $s$ is finite. Furthermore, we present the complete list of all maximal lattice-free integral polyhedra in dimension three. Our results are motivated by recent research on cutting plane theory in mixed-integer linear optimization.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Intractability of approximate multi-dimensional nonlinear optimization on independence systems

We consider optimization of nonlinear objective functions that balance $d$ linear criteria over $n$-element independence systems presented by linear-optimization oracles. For $d=1$, we have previously shown that an $r$-best approximate solution can be found in polynomial time. Here, using an extended Erdős-Ko-Rado theorem of Frankl, we show that for $d=2$, finding a $ρn$-best solution requires exponential time.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The Quadratic Graver Cone, Quadratic Integer Minimization, and Extensions

We consider the nonlinear integer programming problem of minimizing a quadratic function over the integer points in variable dimension satisfying a system of linear inequalities. We show that when the Graver basis of the matrix defining the system is given, and the quadratic function lies in a suitable {\em dual Graver cone}, the problem can be solved in polynomial time. We discuss the relation between this cone and the cone of positive semidefinite matrices, and show that none contains the other. So we can minimize in polynomial time some non-convex and some (including all separable) convex quadrics. We conclude by extending our results to efficient integer minimization of multivariate polynomial functions of arbitrary degree lying in suitable cones.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Transversal numbers over subsets of linear spaces

Let $M$ be a subset of $\mathbb{R}^k$. It is an important question in the theory of linear inequalities to estimate the minimal number $h=h(M)$ such that every system of linear inequalities which is infeasible over $M$ has a subsystem of at most $h$ inequalities which is already infeasible over $M.$ This number $h(M)$ is said to be the Helly number of $M.$ In view of Helly's theorem, $h(\mathbb{R}^n)=n+1$ and, by the theorem due to Doignon, Bell and Scarf, $h(\mathbb{Z}^d)=2^d.$ We give a common extension of these equalities showing that $h(\mathbb{R}^n \times \mathbb{Z}^d) = (n+1) 2^d.$ We show that the fractional Helly number of the space $M \subseteq \mathbb{R}^d$ (with the convexity structure induced by $\mathbb{R}^d$) is at most $d+1$ as long as $h(M)$ is finite. Finally we give estimates for the Radon number of mixed integer spaces.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

A polynomial-time algorithm for optimizing over N-fold 4-block decomposable integer programs

In this paper we generalize N-fold integer programs and two-stage integer programs with N scenarios to N-fold 4-block decomposable integer programs. We show that for fixed blocks but variable N, these integer programs are polynomial-time solvable for any linear objective. Moreover, we present a polynomial-time computable optimality certificate for the case of fixed blocks, variable N and any convex separable objective function. We conclude with two sample applications, stochastic integer programs with second-order dominance constraints and stochastic integer multi-commodity flows, which (for fixed blocks) can be solved in polynomial time in the number of scenarios and commodities and in the binary encoding length of the input data. In the proof of our main theorem we combine several non-trivial constructions from the theory of Graver bases. We are confident that our approach paves the way for further extensions.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Nonlinear Integer Programming

Research efforts of the past fifty years have led to a development of linear integer programming as a mature discipline of mathematical optimization. Such a level of maturity has not been reached when one considers nonlinear systems subject to integrality requirements for the variables. This chapter is dedicated to this topic. The primary goal is a study of a simple version of general nonlinear integer problems, where all constraints are still linear. Our focus is on the computational complexity of the problem, which varies significantly with the type of nonlinear objective function in combination with the underlying combinatorial structure. Numerous boundary cases of complexity emerge, which sometimes surprisingly lead even to polynomial time algorithms. We also cover recent successful approaches for more general classes of problems. Though no positive theoretical efficiency results are available, nor are they likely to ever be available, these seem to be the currently most successful and interesting approaches for solving practical problems. It is our belief that the study of algorithms motivated by theoretical considerations and those motivated by our desire to solve practical instances should and do inform one another. So it is with this viewpoint that we present the subject, and it is in this direction that we hope to spark further research.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

A polynomial oracle-time algorithm for convex integer minimization

In this paper we consider the solution of certain convex integer minimization problems via greedy augmentation procedures. We show that a greedy augmentation procedure that employs only directions from certain Graver bases needs only polynomially many augmentation steps to solve the given problem. We extend these results to convex $N$-fold integer minimization problems and to convex 2-stage stochastic integer minimization problems. Finally, we present some applications of convex $N$-fold integer minimization problems for which our approach provides polynomial time solution algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension

We show the existence of a fully polynomial-time approximation scheme (FPTAS) for the problem of maximizing a non-negative polynomial over mixed-integer sets in convex polytopes, when the number of variables is fixed. Moreover, using a weaker notion of approximation, we show the existence of a fully polynomial-time approximation scheme for the problem of maximizing or minimizing an arbitrary polynomial over mixed-integer sets in convex polytopes, when the number of variables is fixed.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

Intermediate integer programming representations using value disjunctions

We introduce a general technique to create an extended formulation of a mixed-integer program. We classify the integer variables into blocks, each of which generates a finite set of vector values. The extended formulation is constructed by creating a new binary variable for each generated value. Initial experiments show that the extended formulation can have a more compact complete description than the original formulation. We prove that, using this reformulation technique, the facet description decomposes into one ``linking polyhedron'' per block and the ``aggregated polyhedron''. Each of these polyhedra can be analyzed separately. For the case of identical coefficients in a block, we provide a complete description of the linking polyhedron and a polynomial-time separation algorithm. Applied to the knapsack with a fixed number of distinct coefficients, this theorem provides a complete description in an extended space with a polynomial number of variables.

0 citations0 reviewsNo code linkedOpen access
preprint2005arXiv

Integer Polynomial Optimization in Fixed Dimension

We classify, according to their computational complexity, integer optimization problems whose constraints and objective functions are polynomials with integer coefficients and the number of variables is fixed. For the optimization of an integer polynomial over the lattice points of a convex polytope, we show an algorithm to compute lower and upper bounds for the optimal value. For polynomials that are non-negative over the polytope, these sequences of bounds lead to a fully polynomial-time approximation scheme for the optimization problem.

0 citations0 reviewsNo code linkedOpen access