In many applications, when building regression models, it is important to account for the presence of outliers, i.e., corrupted input data points resulting, e.g., from recording errors. Problems consisting in simultaneously performing linear regression and discarding outliers may be formulated as mixed-integer optimization problems which involve cubic terms, each given by the product of a binary variable and a quadratic term of the continuous variables. This can be notably illustrated with the least trimmed squares problem, which consists in minimizing some given number of squared residuals, and is known to be both NP-hard and hard to approximate.
Existing approaches in the literature typically rely on the linearization of the cubic terms using big-M constraints. However the latter lead to weak relaxations and poor performance in practice. In this work, we derive stronger second-order conic relaxations not involving big-M constraints. Our computational experiments indicate that the proposed formulations are several orders of magnitude faster than existing big-M formulations in the literature for this problem.

Optimization over trained machine learning models has applications including verification, minimizing neural acquisition functions, and integrating a trained surrogate into a larger decision-making problem. We formulate and solve optimization problems constrained by trained graph neural networks (GNNs). For the classical GNN architectures considered in this talk, optimizing over a GNN with a fixed graph is equivalent to optimizing over a dense neural network. Thus, we study the case where the input graph is not fixed, implying that each edge is a decision variable, and develop two mixed-integer optimization formulations. To circumvent the symmetry issue caused by graph isomorphism, we propose two types of symmetry-breaking constraints, and provide a proof that adding these constraints will not remove all symmetric solutions. As a byproduct, a graph indexing algorithm is constructed to yield an indexing satisfying these constraints. To test our symmetry-breaking strategies and optimization formulations, we consider an application in optimal molecular design.

Semidefinite Programming (SDP) is a powerful technique to compute tight lower bounds for Optimal Power Flow (OPF) problems. Even using clique decomposition techniques, semidefinite relaxations are still computationally demanding. However, there are many different clique decompositions for the same SDP problem and they are not equivalent in terms of computation time. In this paper, we propose a new strategy to compute efficient clique decompositions with a clique merging heuristic. This heuristic is based on two different estimates of the computational burden of an SDP problem: the size of the problem and an estimation of a per-iteration cost for a state-of-the-art interior-point algorithm. We compare our strategy with other algorithms on MATPOWER instances and we show a significant decrease in solver time. In the last part of the talk we present recent developments on how to incorporate machine learning techniques to automatically identify effective clique decompositions.