Given a convex set Q ⊆ ℝm and an integer matrix W ∈ ℤm×n, we consider statements of the form ∀b ∈ Q ∩ ℤm ∃x ∈ ℤn s.t. Wx ≤ b. Such statements can be verified in polynomial time with the algorithm of Kannan and its improvements if n is fixed and Q is a polyhedron. The running time of the best-known algorithms is doubly exponential in n. We provide a pseudopolynomial-time algorithm if m is fixed. Its running time is (mΔ)O (m2 ) where Δ is the largest absolute value of an entry in W. Furthermore it applies to general convex sets Q.

We study the lattice width of lattice-free polyhedra given by ${A}{x}\leq{b}$ in terms of $\Delta({A})$, the maximal $n\times n$ minor in absolute value of ${A}\in\mathbb{Z}^{m\times n}$. Our main contribution is to link the lattice width of lattice-free polyhedra to the height of Hilbert bases and to the diameter of finite abelian groups. This leads to a bound on the lattice width of lattice-free pyramids which solely depends on $\Delta({A})$ provided a conjecture regarding the height of Hilbert bases holds. Further, we exploit a combination of techniques to obtain novel bounds on the lattice width of simplices. A second part of the paper is devoted to a study of the above-mentioned Hilbert basis conjecture. We give a complete characterization of the Hilbert basis if $\Delta({A}) = 2$ which implies the conjecture in that case and prove its validity for simplicial cones.

We consider the problem of solving integer programs of the form $\min \{\,c^\intercal x\ \colon\ Ax=b, x\geq 0\}$, where $A$ is a multistage stochastic matrix in the following sense: the primal treedepth of $A$ is bounded by a parameter $d$, which means that the columns of $A$ can be organized into a rooted forest of depth at most $d$ so that columns not bound by the ancestor/descendant relation in the forest do not have non-zero entries in the same row. We give an algorithm that solves this problem in fixed-parameter time $f(d,\|A\|_{\infty})\cdot n\log^{O(2^d)} n$, where $f$ is a computable function and $n$ is the number of rows of $A$. The algorithm works in the strong model, where the running time only measures unit arithmetic operations on the input numbers and does not depend on their bitlength. This is the first fpt algorithm for multistage stochastic integer programming to achieve almost linear running time in the strong sense. For the case of two-stage stochastic integer programs, our algorithm works in time $2^{(2\|A\|_\infty)^{O(r(r+s))}}\cdot n\log^{O(rs)} n$. The algorithm can be also parallelized: we give an implementation in the PRAM model that achieves running time $f(d,\|A\|_{\infty})\cdot \log^{O(2^d)} n$ using $n$ processors. The main conceptual ingredient in our algorithms is a new proximity result for multistage stochastic integer programs. We prove that if we consider an integer program $P$, say with a constraint matrix $A$, then for every optimum solution to the linear relaxation of $P$ there exists an optimum (integral) solution to $P$ that lies, in the $\ell_{\infty}$-norm, within distance bounded by a function of $\|A\|_{\infty}$ and the primal treedepth of $A$. On the way to achieve this result, we prove a generalization and considerable improvement of a structural result of Klein for multistage stochastic integer programs.

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 ℓ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.

We consider integer programming problems in standard form max{cTx : Ax = b, x ≥ 0, x ∊ ℤn} where A ∊ ℤm×n, b ∊ ℤm and c ∊ ℤn. We show that such an integer program can be solved in time (m·Δ)O(m) · ||b||∞2, where Δ is an upper bound on each absolute value of an entry in A. This improves upon the longstanding best bound of Papadimitriou (1981) of (m · Δ)O(m2), where in addition, the absolute values of the entries of b also need to be bounded by Δ. Our result relies on a lemma of Steinitz that states that a set of vectors in ℝm that is contained in the unit ball of a norm and that sum up to zero can be ordered such that all partial sums are of norm bounded by m. We also use the Steinitz lemma to show that the ℓ1-distance of an optimal integer and fractional solution, also under the presence of upper bounds on the variables, is bounded by m · (2m · Δ + 1)m. Here Δ is again an upper bound on the absolute values of the entries of A. The novel strength of our bound is that it is independent of n. We provide evidence for the significance of our bound by applying it to general knapsack problems where we obtain structural and algorithmic results that improve upon the recent literature.

Let $A \in \mathbb{Z}^{m \times n}$ be a matrix with $\mathrm{rank}(A) = n$, whose $(n \times n)$-submatrices have a determinant of at most ${\mathop{\vartriangle}}$ in absolute value. Assume that $A$ does not contain the zero-row, nor any duplicate rows, and neither two rows where one is the negation of the other. Under these assumptions, we show that $m \leq \frac{1}{2} \cdot {\mathop{\vartriangle}}^{\log_2\log_2{\mathop{\vartriangle}} + 2} \cdot n^2$ for ${\mathop{\vartriangle}} \geq 2$ and $m \leq \frac{1}{2} \cdot (n^2 + n)$ for ${\mathop{\vartriangle}} = 1$. The latter case is an immediate consequence of a well-known bound by Heller [ Pacific J. Math., 7 (1957), pp. 1351--1364] showing that totally unimodular matrices admit at most $\frac{1}{2} \cdot (n^2 + n)$ distinct rows. Our result extends Heller's bound in the sense that even for ${\mathop{\vartriangle}} = n^{\mathcal{O}(\sfrac{1}{\log\log n})}$, the number $m$ of rows of $A$ is bounded by a polynomial in $n$.

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 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 nontrivial lower bound on the number of integer variables needed in such settings.

We present a strongly polynomial algorithm to solve integer programs of the form max{cT x: Ax≤ b, xεℤn }, for AεℤmXn with rank(A)=n, bε≤m, cε≤n, and where all determinants of (nXn)-sub-matrices of A are bounded by 2 in absolute value. In particular, this implies that integer programs max{cT x : Q x≤ b, xεℤ≥0n}, where Qε ℤmXn has the property that all subdeterminants are bounded by 2 in absolute value, can be solved in strongly polynomial time. We thus obtain an extension of the well-known result that integer programs with constraint matrices that are totally unimodular are solvable in strongly polynomial time.

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 [22] 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 xT Qx 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.

We prove a representation theorem of projections of sets of integer points by an integer matrix $W$. Our result can be seen as a polyhedral analogue of several classical and recent results related to the Frobenius problem. Our result is motivated by a large class of nonlinear integer optimization problems in variable dimension. Concretely, we aim to optimize $f(Wx)$ over a set $\mathcal{F} = P\cap \mathbb{Z}^n$, where $f$ is a nonlinear function, $P\subset \mathbb{R}^n$ is a polyhedron, and $W\in \mathbb{Z}^{d\times n}$. As a consequence of our representation theorem, we obtain a general efficient transformation from the latter class of problems to integer linear programming. Our bounds depend polynomially on various important parameters of the input data leading, among others, to first polynomial time algorithms for several classes of nonlinear optimization problems.

We show that the problem of minimizing a quadratic polynomial with integer coefficients over the integer points in a general two-dimensional rational polyhedron is solvable in time bounded by a polynomial in the input size.

T cells orchestrate the adaptive immune response, making them targets for immunotherapy. Although immunosuppressive therapies prevent disease progression, they also leave patients susceptible to opportunistic infections. To identify novel drug targets, we established a logical model describing T-cell receptor (TCR) signaling. However, to have a model that is able to predict new therapeutic approaches, the current drug targets must be included. Therefore, as a next step we generated the interleukin-2 receptor (IL-2R) signaling network and developed a tool to merge logical models. For IL-2R signaling, we show that STAT activation is independent of both Src- and PI3-kinases, while ERK activation depends upon both kinases and additionally requires novel PKCs. In addition, our merged model correctly predicted TCR-induced STAT activation. The combined network also allows information transfer from one receptor to add detail to another, thereby predicting that LAT mediates JNK activation in IL-2R signaling. In summary, the merged model not only enables us to unravel potential cross-talk, but it also suggests new experimental designs and provides a critical step towards designing strategies to reprogram T cells.

We consider optimizing a nonlinear objective function over a weighted independence system presented by a linear-optimization oracle. We provide an efficient algorithm that determines an r-best solution for nonlinear functions of the total weight of an independent set, where r depends only on certain Frobenius numbers of the individual weights and is independent of the size of the ground set. In contrast, we show that finding an optimal (0-best) solution requires exponential time.

We study the problem of optimizing nonlinear objective functions over matroids presented by oracles or explicitly. Such functions can be interpreted as the balancing of multicriteria optimization. We provide a combinatorial polynomial time algorithm for arbitrary oracle-presented matroids, that makes repeated use of matroid intersection and an algebraic algorithm for vectorial matroids. Our work is partly motivated by applications to minimum-aberration model-fitting in experimental design in statistics, which we discuss and demonstrate in detail.

Cellular decisions are determined by complex molecular interaction networks. Large-scale signaling networks are currently being reconstructed, but the kinetic parameters and quantitative data that would allow for dynamic modeling are still scarce. Therefore, computational studies based upon the structure of these networks are of great interest. Here, a methodology relying on a logical formalism is applied to the functional analysis of the complex signaling network governing the activation of T cells via the T cell receptor, the CD4/CD8 co-receptors, and the accessory signaling receptor CD28. Our large-scale Boolean model, which comprises 94 nodes and 123 interactions and is based upon well-established qualitative knowledge from primary T cells, reveals important structural features (e.g., feedback loops and network-wide dependencies) and recapitulates the global behavior of this network for an array of published data on T cell activation in wild-type and knock-out conditions. More importantly, the model predicted unexpected signaling events after antibody-mediated perturbation of CD28 and after genetic knockout of the kinase Fyn that were subsequently experimentally validated. Finally, we show that the logical model reveals key elements and potential failure modes in network functioning and provides candidates for missing links. In summary, our large-scale logical model for T cell activation proved to be a promising in silico tool, and it inspires immunologists to ask new questions. We think that it holds valuable potential in foreseeing the effects of drugs and network modifications.

This paper focuses on the outer description of the convex hull of all integer solutions to a given system of linear inequalities. It is shown that if the given system contains lower and upper bounds for the variables, then the convex hull can be produced by iteratively generating so‐called mod‐2 cuts only. This fact is surprising and might even be counterintuitive, since many integer rounding cuts exist that are not mod‐2, i.e., representable as the $\{0,\frac{1}{2}\}$ combination of the given constraint system. The key, however, is that in general many more rounds of mod‐2 cut generation are necessary to produce the final description than in the traditional integer rounding procedure.

In this paper we modify Buchberger's S-pair reduction algorithm for computing a Gröbner basis of a toric ideal so as to apply it to an integer program (IP) in inequality form with fixed right-hand sides and fixed upper bounds on the variables. We formulate the algorithm in the original space and interpret the reduction steps geometrically. In fact, three variants of this algorithm are presented, and we give elementary proofs for their correctness. A relationship among these (exact) algorithms, iterative improvement heuristics, and the Kernighan--Lin procedure is established. Computational results are also presented.

In this paper, we investigate separation problems for classes of inequalities valid for the polytope associated with the Steiner tree packing problem, a problem that arises, e.g., in very large-scale integration (VLSI) routing. The separation problem for Steiner partition inequalities is $\mathcal{N P}$-hard in general. We show that it can be solved in polynomial time for those instances that come up in switchbox routing. Our algorithm uses dynamic programming techniques. These techniques are also applied to the much more complicated separation problem for alternating cycle inequalities. In this case, we can compute in polynomial time, given some point y, a lower bound for the gap $\alpha - a^T y$ over all alternating cycle inequalities $a^T x \geq \alpha $. This gives rise to a very effective separation heuristic. A by-product of our algorithm is the solution of a combinatorial optimization problem that is interesting in its own right: find a shortest path in a graph where the “length” of a path is its usual length minus the length of its longest edge.