To confirm that the expressive power of ReLU neural networks grows with their depth, the function $F_n = \max (0,x_1,\ldots,x_n )$ has been considered in the literature. A conjecture by Hertrich, Basu, Di Summa, and Skutella [NeurIPS 2021] states that any ReLU network that exactly represents $F_n$ has at least $\lceil \log_2 (n+1) \rceil$ hidden layers. The conjecture has recently been confirmed for networks with integer weights by Haase, Hertrich, and Loho [ICLR 2023]. We follow up on this line of research and show that, within ReLU networks whose weights are decimal fractions, $F_n$ can only be represented by networks with at least $\lceil \log_3 (n+1) \rceil$ hidden layers. Moreover, if all weights are $N$-ary fractions, then $F_n$ can only be represented by networks with at least $\Omega( \frac{\ln n}{\ln \ln N})$ layers. These results are a partial confirmation of the above conjecture for rational ReLU networks, and provide the first non-constant lower bound on the depth of practically relevant ReLU networks.

Abstract Partial inverse combinatorial optimization problems are bilevel optimization problems in which the leader aims to incentivize the follower to include respectively not include given sets of elements in the solution of their combinatorial problem. If the sets of required and forbidden elements define a complete follower solution and the follower problem is solvable in polynomial time, then the inverse combinatorial problem is also solvable in polynomial time. In contrast, partial inverse problems can be NP-complete when the follower problem is solvable in polynomial time. This applies e.g. to the partial inverse min cut problem. In this paper, we consider partial inverse combinatorial optimization problems in which weights can only be increased. Furthermore, we assume that the lower-level combinatorial problem can be solved as a linear program. In this setting, we show that the partial inverse shortest path problem on a directed acyclic graph is NP-complete. Moreover, the partial inverse assignment problem is NP-complete. Both results even hold if there is only one required arc or edge, respectively. For solving partial inverse combinatorial optimization problems with only weight increases, we present a novel branch-and-bound scheme that exploits the difference in complexity between complete inverse and partial inverse versions of a problem. For both primal heuristics and node relaxations, we use auxiliary problems that are basically complete inverse problems on similar instances. Branching is done on follower variables. We test our approach on partial inverse shortest path, assignment and min cut problems, and computationally compare it to an MPCC reformulation as well as a decomposition scheme.

Abstract. With every family of finitely many subsets of a finite-dimensional vector space over the Galois-field with two elements we associate a cyclic transversal polytope. It turns out that those polytopes generalize several well-known polytopes that are relevant in combinatorial optimization, among them cut polytopes as well as stable set and matching polytopes. We introduce the class of lifted odd-set inequalities and prove results demonstrating their strength. In particular, we show that they suffice to describe cyclic transversal polytopes if the union of the sets in the family has rank at most two. We also describe extended formulations for cyclic transversal polytopes and introduce a special relaxation hierarchy for them.

Abstract We propose an exact global solution method for bilevel mixed-integer optimization problems with lower-level integer variables and including nonlinear terms such as, e.g., products of upper-level and lower-level variables. Problems of this type are extremely challenging as a single-level reformulation suitable for off-the-shelf solvers is not available in general. In order to solve these problems to global optimality, we enhance an approximative projection-based algorithm for mixed-integer linear bilevel programming problems from the literature to become exact under one additional assumption. This assumption still allows for discrete and continuous leader and follower variables on both levels, but forbids continuous upper-level variables to appear in lower-level constraints and thus ensures that a bilevel optimum is attained. In addition, we extend our exact algorithm to make it applicable to a wider problem class. This setting allows nonlinear constraints and objective functions on both levels under certain assumptions, but still requires that the lower-level problem is convex in its continuous variables. We also discuss computational experiments on modified library instances.

Abstract In the field of autonomous driving, traffic‐light‐controlled intersections are of special interest. We analyze how much an optimized coordination of vehicles and infrastructure can contribute to efficient transit through these bottlenecks, depending on traffic density and certain regulations of traffic lights. To this end, we develop a mixed‐integer linear programming model to describe the interaction between traffic lights and discretized traffic flow. It is based on a microscopic traffic model with centrally controlled autonomous vehicles. We aim to determine a globally optimal traffic flow for given scenarios on a simple, but extensible, urban road network. The resulting models are very challenging to solve, in particular when involving additional realistic traffic‐light regulations such as minimum red and green times. While solving times exceed real‐time requirements, our model allows an estimation of the maximum performance gains due to improved communication and serves as a benchmark for heuristic and decentralized approaches.

Abstract Solving mixed-integer nonlinear optimization problems (MINLPs) to global optimality is extremely challenging. An important step for enabling their solution consists in the design of convex relaxations of the feasible set. Known solution approaches based on spatial branch-and-bound become more effective the tighter the used relaxations are. Relaxations are commonly established by convex underestimators, where each constraint function is considered separately. Instead, a considerably tighter relaxation can be found via so-called simultaneous convexification, where convex underestimators are derived for more than one constraint function at a time. In this work, we present a global solution approach for solving mixed-integer nonlinear problems that uses simultaneous convexification. We introduce a separation method that relies on determining the convex envelope of linear combinations of the constraint functions and on solving a nonsmooth convex problem. In particular, we apply the method to quadratic absolute value functions and derive their convex envelopes. The practicality of the proposed solution approach is demonstrated on several test instances from gas network optimization, where the method outperforms standard approaches that use separate convex relaxations.