Representing data via vectors and matrices and optimizing spectral objectives such as determinants, and traces of naturally associated matrices is a standard paradigm that is utilized in multiple areas including machine learning, statistics, convex geometry, location problems, allocation problems, and network design problems. In this talk, we will look at many of these applications with a focus on the determinant objective. We will then give algorithms for these problems that build on classical matroid intersection algorithms.

Lemke and Howson proposed in 1964 a pivot-based algorithm for solving bimatrix games. The year after, Lemke proposed a closely related algorithm for solving a large class of linear complementarity problems. Although Todd extended the Lemke algorithm to oriented matroids in 1984, the extension of the Lemke—Howson algorithm to oriented matroids has not yet been addressed in the literature. Actually, achieving such an extension requires solving a few issues. One of them is to propose a relevant definition of Nash equilibria for oriented matroids. Another one is more challenging, namely finding the counterpart of the following preliminary operation of the classical Lemke—Howson algorithm: the translation of the payoff matrices so as to make them positive. In this work, we show how to overcome these challenges and extend the Lemke—Howson algorithm to oriented matroids. A few applications are discussed, such as a strengthening of a theorem by McLennan and Tourky, a combinatorial interpretation of the orientation of the pivot step in the classical version, and the localization of tropical bimatrix games in the class PPAD. Joint work with Xavier Allamigeon and Stéphane Gaubert.

The multi-depot vehicle scheduling problem (MDVSP) is a principal planning challenge for transit agencies. We introduce a novel approach to MDVSP by incorporating service reliability through chance-constrained programming (CCP), targeting the pivotal issue of travel time uncertainty and its impact on transit service quality. We propose an exact branch-and-cut (B&C) scheme to solve our CCP model. We present several cut-generation procedures that exploit the underlying problem structure and analyze the relationship between the obtained cut families. Additionally, we design a Lagrangian-based heuristic to handle large-scale instances reflective of real-world transit operations. Our approach partitions the set of trips, each subset leading to a subproblem that can be efficiently solved with our B&C algorithm, and then employs a procedure to combine the subproblem solutions to create a vehicle schedule that satisfies all the planning constraints of the MDVSP. Our empirical evaluation demonstrates the superiority of our stochastic variant in achieving cost-effective schedules with reliable service guarantees compared to alternatives commonly used by practitioners, as well as the computational benefits of our methodologies.

We propose an approach to graph sparsification based on the idea of preserving the smallest k eigenvalues and eigenvectors of the Graph Laplacian. This is motivated by the fact that small eigenvalues and their associated eigenvectors tend to be more informative of the global structure and geometry of the graph than larger eigenvalues and their eigenvectors. The set of all weighted subgraphs of a graph G that have the same first k eigenvalues (and eigenvectors) as G is the intersection of a polyhedron with a cone of positive semidefinite matrices. We discuss the geometry of these sets and deduce the natural scale of k. Various families of graphs illustrate our construction.

We investigate the semigroup of integer points inside a convex cone. We extend classical results in integer linear programming to integer conic programming. We show that the semigroup associated with nonpolyhedral cones can sometimes have a notion of finite generating set with the help of a group action. We show this is true for the cone of positive semidefinite matrices (PSD) and the second-order cone (SOC). Both cones have a finite generating set of integer points, similar in spirit to Hilbert bases, under the action of a finitely generated group. We also extend notions of total dual integrality, Gomory-Chvatal closure, and Caratheodory rank to integer points in arbitrary cones.

The field of mixed-integer nonlinear optimization has advanced significantly over the past three decades. Yet, even small instances of many nonconvex optimization problems involving the Euclidean norm are beyond the capabilities of modern codes. Although these models arise from applications as diverse as molecular energy minimization, object packing, and facility location, they often share specific features which lead to computational intractability. In this presentation, we identify these features, introduce new algorithms to address them, and present numerical results showing the impact of our techniques. This is joint work with Anatoliy Kuznetsov.