A Penalty Branch-and-Bound Method for Mixed-Binary Linear Complementarity Problems

Linear complementarity problems (LCPs) are an important modeling tool for many practically relevant situations but also have many important applications in mathematics itself. Although the continuous version of the problem is extremely well studied, much less is known about mixed-integer LCPs (MILCPs) in which some variables have to be integer-valued in a solution. In particular, … Read more

Distributionally Robust Fair Transit Resource Allocation During a Pandemic

This paper studies Distributionally robust Fair transit Resource Allocation model (DrFRAM) under Wasserstein ambiguity set to optimize the public transit resource allocation during a pandemic. We show that the proposed DrFRAM is highly nonconvex and nonlinear and is, in general, NP-hard. Fortunately, we show that DrFRAM can be reformulated as a mixed-integer linear programming (MILP) … Read more

Cardinality Minimization, Constraints, and Regularization: A Survey

We survey optimization problems that involve the cardinality of variable vectors in constraints or the objective function. We provide a unified viewpoint on the general problem classes and models, and give concrete examples from diverse application fields such as signal and image processing, portfolio selection, or machine learning. The paper discusses general-purpose modeling techniques and … Read more

Second-Order Conic and Polyhedral Approximations of the Exponential Cone: Application to Mixed-Integer Exponential Conic Programs

Exponents and logarithms exist in many important applications such as logistic regression, maximum likelihood, relative entropy and so on. Since the exponential cone can be viewed as the epigraph of perspective of the natural exponential function or the hypograph of perspective of the natural logarithm function, many mixed-integer nonlinear convex programs involving exponential or logarithm … Read more

An Algorithm-Independent Measure of Progress for Linear Constraint Propagation

Propagation of linear constraints has become a crucial sub-routine in modern Mixed-Integer Programming (MIP) solvers. In practice, iterative algorithms with tolerance-based stopping criteria are used to avoid problems with slow or infinite convergence. However, these heuristic stopping criteria can pose difficulties for fairly comparing the efficiency of different implementations of iterative propagation algorithms in a … Read more

Inductive Linearization for Binary Quadratic Programs with Linear Constraints: A Computational Study

The computational performance of inductive linearizations for binary quadratic programs in combination with a mixed-integer programming solver is investigated for several combinatorial optimization problems and established benchmark instances. Apparently, a few of these are solved to optimality for the first time. Citationpreprint (no internal series / number): University of Bonn, Germany June 11, 2021ArticleDownload View … Read more

Single-neuron convexifications for binarized neural networks

Binarized neural networks are an important class of neural network in deep learning due to their computational efficiency. This paper contributes towards a better understanding of the structure of binarized neural networks, specifically, ideal convex representations of the activation functions used. We describe the convex hull of the graph of the signum activation function associated … Read more

Shapes and recession cones in mixed-integer convex representability

Mixed-integer convex representable (MICP-R) sets are those sets that can be represented exactly through a mixed-integer convex programming formulation. Following up on recent work by Lubin et al. (2017, 2020) we investigate structural geometric properties of MICP-R sets, which strongly differentiate them from the class of mixed-integer linear representable sets (MILP-R). First, we provide an … Read more

A Computational Status Update for Exact Rational Mixed Integer Programming

The last milestone achievement for the roundoff-error-free solution of general mixed integer programs over the rational numbers was a hybrid-precision branch-and-bound algorithm published by Cook, Koch, Steffy, and Wolter in 2013. We describe a substantial revision and extension of this framework that integrates symbolic presolving, features an exact repair step for solutions from primal heuristics, … Read more

Strong Optimal Classification Trees

Decision trees are among the most popular machine learning models and are used routinely in applications ranging from revenue management and medicine to bioinformatics. In this paper, we consider the problem of learning optimal binary classification trees with univariate splits. Literature on the topic has burgeoned in recent years, motivated both by the empirical suboptimality … Read more