TY - INPR A1 - Giannakopoulos, Yiannis A1 - Hahn, Johannes T1 - Discrete Single-Parameter Optimal Auction Design N2 - We study the classic single-item auction setting of Myerson, but under the assumption that the buyers' values for the item are distributed over "finite" supports. Using strong LP duality and polyhedral theory, we rederive various key results regarding the revenue-maximizing auction, including the characterization through virtual welfare maximization and the optimality of deterministic mechanisms, as well as a novel, generic equivalence between dominant-strategy and Bayesian incentive compatibility. Inspired by this, we abstract our approach to handle more general auction settings, where the feasibility space can be given by arbitrary convex constraints, and the objective is a linear combination of revenue and social welfare. We characterize the optimal auctions of such systems as generalized virtual welfare maximizers, by making use of their KKT conditions, and we present an analogue of Myerson's payment formula for general discrete single-parameter auction settings. Additionally, we prove that total unimodularity of the feasibility space is a sufficient condition to guarantee the optimality of auctions with integral allocation rules. Finally, we demonstrate this KKT approach by applying it to a setting where bidders are interested in buying feasible flows on trees with capacity constraints, and provide a combinatorial description of the (randomized, in general) optimal auction. Y1 - 2024 ER - TY - INPR A1 - Göß, Adrian A1 - Burlacu, Robert A1 - Martin, Alexander T1 - Parabolic Approximation & Relaxation for MINLP N2 - We propose an approach based on quadratic approximations for solving general Mixed-Integer Nonlinear Programming (MINLP) problems. Specifically, our approach entails the global approximation of the epigraphs of constraint functions by means of paraboloids, which are polynomials of degree two with univariate quadratic terms, and relies on a Lipschitz property only. These approximations are then integrated into the original problem. To this end, we introduce a novel approach to compute globally valid epigraph approximations by paraboloids via a Mixed-Integer Linear Programming (MIP) model. We emphasize the possibility of performing such approximations a-priori and providing them in form of a lookup table, and then present several ways of leveraging the approximations to tackle the original problem. We provide the necessary theoretical background and conduct computational experiments on instances of the MINLPLib. As a result, this approach significantly accelerates the solution process of MINLP problems, particularly those involving many trigonometric or few exponential functions. In general, we highlight that the proposed technique is able to exploit advances in Mixed-Integer Quadratically-Constrained Programming (MIQCP) to solve MINLP problems. KW - mixed-integer nonlinear programming KW - mixed-integer linear programming KW - quadratic approximation KW - global optimization Y1 - 2025 ER - TY - INPR A1 - Hildebrand, Robert A1 - Göß, Adrian T1 - Complexity of Integer Programming in Reverse Convex Sets via Boundary Hyperplane Cover N2 - We study the complexity of identifying the integer feasibility of reverse convex sets. We present various settings where the complexity can be either NP-Hard or efficiently solvable when the dimension is fixed. Of particular interest is the case of bounded reverse convex constraints with a polyhedral domain. We introduce a structure, Boundary Hyperplane Cover, that permits this problem to be solved in polynomial time in fixed dimension provided the number of nonlinear reverse convex sets is fixed. Y1 - ER - TY - INPR A1 - Göß, Adrian A1 - Martin, Alexander A1 - Pokutta, Sebastian A1 - Sharma, Kartikey T1 - Norm-induced Cuts: Optimization with Lipschitzian Black-box Functions N2 - Optimal control problems usually involve constraints which model physical states and their possible transitions. These are represented by ordinary or partial differential equations (ODEs/PDEs) which add a component of infinite dimension to the problem. In recent literature, one method to simulate such ODEs/PDEs are physics-informed neural networks. Typically, neural networks are highly non-linear which makes their addition to optimization problems challenging. Hence, we leverage their often available Lipschitz property on a compact domain. The respective Lipschitz constants have to be computed only once and are accessible thereafter. We present a method that, based on this property, iteratively adds cuts involving the violation of the constraints by the current incumbent and the Lipschitz constant. Hereby, the “shape” of a cut depends on the norm used. We prove the correctness of the method by showing that it either returns an optimal solution when terminating or creates a sequence with optimal accumulation points. This is complemented by a discussion about the termination in the infeasible case, as well as an analysis of the problem complexity. For the analysis, we show that the lower and upper iteration bound asymptotically coincide when the relative approximation error goes to zero. In the end, we visualize the method on a small example based on a two-dimensional non-convex optimization problem, as well as stress the necessity of having a globally optimal oracle for the sub-problems by another example. KW - Global Optimization KW - Lipschitz Optimization KW - Black-box Optimization KW - Derivative-free Optimization Y1 - ER - TY - INPR A1 - Thürauf, Johannes A1 - Grübel, Julia A1 - Schmidt, Martin T1 - Adjustable Robust Nonlinear Network Design under Demand Uncertainties N2 - We study network design problems for nonlinear and nonconvex flow models under demand uncertainties. To this end, we apply the concept of adjustable robust optimization to compute a network design that admits a feasible transport for all, possibly infinitely many, demand scenarios within a given uncertainty set. For solving the corresponding adjustable robust mixed-integer nonlinear optimization problem, we show that a given network design is robust feasible, i.e., it admits a feasible transport for all demand uncertainties, if and only if a finite number of worst-case demand scenarios can be routed through the network. We compute these worst-case scenarios by solving polynomially many nonlinear optimization problems. Embedding this result for robust feasibility in an adversarial approach leads to an exact algorithm that computes an optimal robust network design in a finite number of iterations. Since all of the results are valid for general potential-based flows, the approach can be applied to different utility networks such as gas, hydrogen, or water networks. We finally demonstrate the applicability of the method by computing robust gas networks that are protected from future demand fluctuations. KW - Robust Optimization KW - Nonlinear Flows KW - Potential-based Networks KW - Demand Uncertainties KW - Mixed-integer Nonlinear Optimization Y1 - 2024 ER -