38 citations · 129 across the 25 of their papers we have counts for
30 papers
Computing Equilibria in Integer Programming Games with Shared Constraints
Bainian Hao, Hyunwoo Lee, Robert Hildebrand +1
We develop a cutting-plane algorithm for computing pure Nash equilibria in finite integer games with shared constraints, where a deviation may be feasible against one opponent prof…
Hidden Convexity via Symmetric Displacement Covers: Mixed-Integer Quadratic Programming and Integer Cubic Programming in Fixed Dimension
Cinar Ari, Robert Hildebrand
We give exact polynomial-time algorithms in fixed dimension for mixed-integer quadratic programming over arbitrary rational polyhedra and for integer cubic programming over bounded…
Bounded Integer Quadratic Programming through Parallelepiped Covers and Discrete Convic Optimization
Cinar Ari, Robert Hildebrand
We give an exact algorithm for minimizing an arbitrary rational quadratic polynomial over the integer points of a bounded rational polyhedron $\{x : Ax \le b\…
Integer Maximization over Balls: Hardness and Exact Algorithms
Cinar Ari, Robert Hildebrand
We study the problem of maximizing a linear function over the integer points of an origin-centered ball, which we call \BallIPp{p}. For every fixed integer , we pro…
Curvature batching for integer and mixed-integer quadratic programming
Cinar Ari, Robert Hildebrand
We give an explicit algorithm for integer quadratic programming with running time , where is the number of variables, bounds the absolute en…
Optimal triangulations for piecewise linear approximations of non-convex variable products
Robert Burlacu, Lukas Hager, Robert Hildebrand
We show optimal triangulations for piecewise linear (PWL) approximations of indefinite quadratic functions over the plane. Optimal triangulations have minimum triangle density whil…
Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. IV. The General Unimodular Two-Dimensional Case
Robert Hildebrand, Matthias Köppe, Luze Xu
We study an abstract setting for cutting planes for integer programming called the infinite group problem. In this abstraction, cutting planes are computed via cut generating funct…
Optimizing Representation in Redistricting: Dual Bounds for Partitioning Problems with Non-Convex Objectives
Jamie Fravel, Robert Hildebrand, Nicholas Goedert +2
We investigate optimization models for the purpose of computational redistricting. Our focus is on nonconvex objectives for estimating expected Black Representatives and Political…
Continuous Equality Knapsack with Probit-Style Objectives
Jamie Fravel, Robert Hildebrand, Laurel Travis
We study continuous, equality knapsack problems with uniform separable, non-convex objective functions that are continuous, antisymmetric about a point, and have concave and convex…
Compact mixed-integer programming relaxations in quadratic optimization
Ben Beach, Robert Hildebrand, Joey Huchette
We present a technique for producing valid dual bounds for nonconvex quadratic optimization problems. The approach leverages an elegant piecewise linear approximation for univariat…
Complexity, Exactness, and Rationality in Polynomial Optimization
Daniel Bienstock, Alberto del Pia, Robert Hildebrand
We focus on rational solutions or nearly-feasible rational solutions that serve as certificates of feasibility for polynomial optimization problems. We show that, under some separa…
An Approximate Method for the Optimization of Long-Horizon Tank Blending and Scheduling Operations
Benjamin Beach, Robert Hildebrand, Kimberly Ellis +1
We address a challenging tank blending and scheduling problem regarding operations for a chemical plant. We model the problem as a nonconvex MIQCP, then approximate this model as a…
A Flexible Job Shop Scheduling Representation of the Autonomous In-Space Assembly Task Assignment Problem
Joshua Moser, Julia Hoffman, Robert Hildebrand +1
As in-space exploration increases, autonomous systems will play a vital role in building the necessary facilities to support exploration. To this end, an autonomous system must be…
Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. VII. Inverse semigroup theory, closures, decomposition of perturbations
Robert Hildebrand, Matthias Köppe, Yuan Zhou
In this self-contained paper, we present a theory of the piecewise linear minimal valid functions for the 1-row Gomory-Johnson infinite group problem. The non-extreme minimal valid…
Binary Extended Formulations
Sanjeeb Dash, Oktay Gunluk, Robert Hildebrand
We analyze different ways of constructing binary extended formulations of mixed-integer problems with bounded integer variables and compare their relative strength with respect to…
Minimal cut-generating functions are nearly extreme
Amitabh Basu, Robert Hildebrand, Marco Molinaro
We study continuous (strongly) minimal cut generating functions for the model where all variables are integer. We consider both the original Gomory-Johnson setting as well as a rec…
Extension Complexity Lower Bounds for Mixed-Integer Extended Formulations
Robert Hildebrand, Robert Weismantel, Rico Zenklusen
We prove that any mixed-integer linear extended formulation for the matching polytope of the complete graph on vertices, with a polynomial number of constraints, requires $Ω(\s…
Sublinear Bounds for a Quantitative Doignon-Bell-Scarf Theorem
Stephen R. Chestnut, Robert Hildebrand, Rico Zenklusen
The recent paper "A quantitative Doignon-Bell-Scarf Theorem" by Aliev et al. generalizes the famous Doignon-Bell-Scarf Theorem on the existence of integer solutions to systems of l…
Mixed Integer Reformulations of Integer Programs and the Affine TU-dimension of a Matrix
Jörg Bader, Robert Hildebrand, Robert Weismantel +1
We study the reformulation of integer linear programs by means of a mixed integer linear program with fewer integer variables. Such reformulations can be solved efficiently with mi…
An FPTAS for Minimizing Indefinite Quadratic Forms over Integers in Polyhedra
Robert Hildebrand, Robert Weismantel, Kevin Zemmer
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 rationa…
Note on the Complexity of the Mixed-Integer Hull of a Polyhedron
Robert Hildebrand, Timm Oertel, Robert Weismantel
We study the complexity of computing the mixed-integer hull of a polyhedron . Given an inequality description, with on…
Light on the Infinite Group Relaxation
Amitabh Basu, Robert Hildebrand, Matthias Köppe
This is a survey on the infinite group problem, an infinite-dimensional relaxation of integer linear optimization problems introduced by Ralph Gomory and Ellis Johnson in their gro…
Minimizing Cubic and Homogeneous Polynomials over Integers in the Plane
Alberto Del Pia, Robert Hildebrand, Robert Weismantel +1
We complete the complexity classification by degree of minimizing a polynomial over the integer points in a polyhedron in . Previous work shows that optimizing a quad…
Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. III. Foundations for the k-Dimensional Case with Applications to k=2
Amitabh Basu, Robert Hildebrand, Matthias Köppe
We develop foundational tools for classifying the extreme valid functions for the k-dimensional infinite group problem. In particular, (1) we present the general regular solution t…