9 papers
Neural Network Verification as Piecewise Linear Optimization: Formulations for the Composition of Staircase Functions
Tu Anh-Nguyen, Joey Huchette
We present a technique for neural network verification using mixed-integer programming (MIP) formulations. We derive a \emph{strong formulation} for each neuron in a network using…
Modeling Combinatorial Disjunctive Constraints via Junction Trees
Bochuan Lyu, Illya V. Hicks, Joey Huchette
We introduce techniques to build small ideal mixed-integer programming (MIP) formulations of combinatorial disjunctive constraints (CDCs) via the independent branching scheme. We p…
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…
The Convex Relaxation Barrier, Revisited: Tightened Single-Neuron Relaxations for Neural Network Verification
Christian Tjandraatmadja, Ross Anderson, Joey Huchette +3
We improve the effectiveness of propagation- and linear-optimization-based neural network verification algorithms with a new tightened convex relaxation for ReLU neurons. Unlike pr…
Contextual Reserve Price Optimization in Auctions via Mixed-Integer Programming
Joey Huchette, Haihao Lu, Hossein Esfandiari +1
We study the problem of learning a linear model to set the reserve price in an auction, given contextual information, in order to maximize expected revenue from the seller side. Fi…
A geometric way to build strong mixed-integer programming formulations
Joey Huchette, Juan Pablo Vielma
We give an explicit geometric way to build mixed-integer programming (MIP) formulations for unions of polyhedra. The construction is simply described in terms of spanning hyperplan…