Abstract. We contribute to a better understanding of the class of functions that can be represented by a neural network with ReLU activations and a given architecture. Using techniques from mixed-integer optimization, polyhedral theory, and tropical geometry, we provide a mathematical counterbalance to the universal approximation theorems which suggest that a single hidden layer is sufficient for learning any function. In particular, we investigate whether the class of exactly representable functions strictly increases by adding more layers (with no restrictions on size). As a by-product of our investigations, we settle an old conjecture about piecewise linear functions by Wang and Sun [ IEEE Trans. Inform. Theory, 51 (2005), pp. 4425–4431] in the affirmative. We also present upper bounds on the sizes of neural networks required to represent functions with logarithmic depth.

We contribute to a better understanding of the class of functions that is represented by a neural network with ReLU activations and a given architecture. Using techniques from mixed-integer optimization, polyhedral theory, and tropical geometry, we provide a mathematical counterbalance to the universal approximation theorems which suggest that a single hidden layer is sufficient for learning tasks. In particular, we investigate whether the class of exactly representable functions strictly increases by adding more layers (with no restrictions on size). This problem has potential impact on algorithmic and statistical aspects because of the insight it provides into the class of functions represented by neural hypothesis classes. However, to the best of our knowledge, this question has not been investigated in the neural network literature. We also present upper bounds on the sizes of neural networks required to represent functions in these neural hypothesis classes.

Given a subset $S$ of $\mathbb{R}^d$, the Helly number $h(S)$ is the largest size of an inclusionwise minimal family of convex sets whose intersection is disjoint from $S$. A convex set is $S$-free if its interior contains no point of $S$. The parameter $f(S)$ is the largest number of maximal faces in an inclusionwise maximal $S$-free convex set. We study the relation between the parameters $h(S)$ and $f(S)$. Our main result is that $h(S)\le (d+1)f(S)$ for every nonempty proper closed subset $S$ of $\mathbb{R}^d$. We also study the Helly number of the Cartesian product of two discrete sets.

We show that the problem of finding the simplex of largest volume in the convex hull of n points in ℚd can be approximated with a factor of O(log d) d/2 in polynomial time. This improves upon the previously best known approximation guarantee of d(d–1)/2 by Khachiyan. On the other hand, we show that there exists a constant c > 1 such that this problem cannot be approximated with a factor of cd, unless P = NP. Our hardness result holds even if n = O(d), in which case there exists a d-approximation algorithm that relies on recent sampling techniques, where is again a constant. We show that similar results hold for the problem of finding the largest absolute value of a subdeterminant of a d × n matrix.

We introduce the reverse Chvátal--Gomory rank $r^*(P)$ of an integral polyhedron $P$, defined as the supremum of the Chvátal--Gomory ranks of all rational polyhedra whose integer hull is $P$. A well-known example in dimension two shows that there exist integral polytopes $P$ with $r^*(P)=+\infty$. We provide a geometric characterization of polyhedra with this property in every dimension, and investigate upper bounds on $r^*(P)$ when this value is finite.

Given an integral polyhedron $P\subseteq\mathbb{R}^n$ and a rational polyhedron $Q\subseteq\mathbb{R}^n$ containing the same integer points as $P$, we investigate how many iterations of the Chvátal--Gomory closure operator have to be performed on $Q$ to obtain a polyhedron contained in the affine hull of $P$. We show that if $P$ contains an integer point in its relative interior, then such a number of iterations can be bounded by a function depending only on $n$. On the other hand, we prove that if $P$ is not full-dimensional and does not contain any integer point in its relative interior, then no finite bound on the number of iterations exists.

We derive a new upper bound on the diameter of the graph of a polyhedron P = {x ∈ Rn : Ax ≤ b}, where A ∈ Zm×n. The bound is polynomial in n and the largest absolute value of a sub-determinant of A, denoted by Δ. More precisely, we show that the diameter of P is bounded by O(Δ2 n4 log nΔ). If P is bounded, then we show that the diameter of P is at most O(Δ2 n3.5 log nΔ).

The purpose of this erratum is to correct the computational results reported in [M. Di Summa and L. A. Wolsey, SIAM J. Discrete Math., 24 (2010), pp. 853–875].

Here we study the discrete lot-sizing problem with an initial stock variable and an associated variable upper bound constraint. This problem is of interest in its own right, and is also a natural relaxation of the constant capacity lot-sizing problem with upper bounds and fixed charges on the stock variables. We show that the convex hull of solutions of the discrete lot-sizing problem is obtained as the intersection of two simpler sets, one a pure integer set and the other a mixing set with a variable upper bound constraint. For these two sets we derive both inequality descriptions and polynomial-size extended formulations of their respective convex hulls. Finally we carry out some limited computational tests on single-item constant capacity lot-sizing problems with upper bounds and fixed charges on the stock variables in which we use the extended formulations derived above to strengthen the initial mixed-integer programming formulations.

We consider the mixing set with flows: $s+x_t \geq b_t, x_t \leq y_t {\rm for} 1 \leq t \leq n; s \in \R^1_+, x \in \R^n_+, y \in \Z^n_+.$ It models a “flow version” of the basic mixing set introduced and studied by Günlük and Pochet [Math. Program., 90 (2001), pp. 429–457], as well as the most simple stochastic lot‐sizing problem with recourse. More generally it is a relaxation of certain mixed integer sets that arise in the study of production planning problems. We study the polyhedron defined as the convex hull of the above set. Specifically we provide an inequality description, and we also characterize its vertices and rays.