DO x ML

Abstract. For nearly decomposable nonlinear mixed binary programs, we propose a hierarchy of relaxations that preserve decomposability. The first level coincides with the classical Lagrangian relaxation, while higher levels yield progressively tighter bounds, culminating in a strong dual. We analyze the quality of these bounds for various types of problems.

Abstract. Geoffrion’s theorem is a fundamental result from mathematical programming assessing the quality of Lagrangian relaxation, a standard technique to get bounds for integer programs. An often implicit condition is that the set of feasible solutions is finite or described by rational linear constraints. However, we show through concrete examples that the conclusion of Geoffrion’s theorem does not necessarily hold when this condition is dropped. We then provide sufficient conditions ensuring the validity of the result even when the feasible set is not finite and cannot be described using finitely-many rational linear constraints. Joint work with Santanu Dey and Diego A. Morán R.

Abstract. In this talk, we present new mathematical models and methods to solve the problem of finding optimal risk scores. In particular, unlike in the literature, we optimize at the same time the scores and the thresholds for continuous features.

Abstract. The Debreu-Koopmans theorem (1982) shows that if a separable function $h(x_{1}, \ldots, x_{n}) = \sum^{n}{i=1} h{i} (x_{i})$ is quasiconvex, then at most one $h_{i}$ might be nonconvex and, as a consequence, when all components $h_{i}$ are quasiconvex, $h$ is not quasiconvex and it is not known to which class of functions $h$ belongs, giving rise to the Debreu-Koopmans problem. In this talk, we introduce the class of (strongly) star quasiconvex functions, and we prove that $h$ is (strongly) star quasiconvex if and only if all components $h_{i}$ are (strongly) star quasiconvex and, as a consequence, we solve the Debreu-Koopmans problem. This result has strong implications in economic theory, since it formally bridges classical diversification theory with behavioral economics, as it implies that separable $S$-shaped value (Sigmoid) functions from Prospect Theory are star quasiconvex. Finally, and if the time allows us, we present potential applications in economics and block-coordinate optimization.

Abstract. When both the objective and the feasible region are smooth and strongly convex, the Frank-Wolfe (FW) algorithm admits uniform $\mathcal{O}(1/\sqrt{\varepsilon})$ guarantees. However, it has remained unclear whether strong convexity of the constraint set alone can yield uniformly faster convergence, independent of the optimizer’s location. In this talk, I present a lower bound of $\Omega(1/\sqrt{\varepsilon})$ that matches existing upper bounds and rules out such uniform acceleration. The analysis is driven by a computational framework that systematically generates worst-case FW trajectories on a canonical problem, making the algorithm’s dynamics explicit and providing a principled mechanism for establishing tight lower bounds.

Abstract. A T-curve of degree $d$ is given by a regular unimodular triangulation of $d \cdot \Delta_2$ together with a sign distribution on its lattice points. By Viro’s Patchworking Theorem, this determines the ambient isotopy type (a.k.a. real scheme) of a smooth real plane projective algebraic curve of the same degree. We present a near-quadratic time algorithm for extracting that isotopy type from the triangulation and the signs. Through a GPU-accelerated implementation, this allows one to compute billions of real schemes per second, enabling exhaustive enumeration at scale. This algorithm was essential for our recent construction of all 121 real schemes of degree seven by T-curves. This is joint work with Zoe Geiselmann, Michael Joswig, Lars Kastner, Konrad Mundinger, Sebastian Pokutta, Marcel Wack, and Max Zimmer.

Abstract. We will discuss the complexity of static and adjustable robust optimization whenever the feasibility and uncertainty sets are polytopes, polyhedrons, or integer representable sets. We start with the decision version of the classical min-max robust optimization and illustrate how these problems can be in P, NP, coNP, and $\Sigma_2^p$, depending on the setting. We then turn to two-stage linear robust optimization as well problems with decision-dependent uncertainty sets. We will discuss connections with bilevel optimization and show how decision-dependence often leads to problems outside of the polynomial hierarchy.

Abstract. Recent advances in drone technology have stimulated intensive research on the joint routing of drones and conventional vehicles, as exemplified by the Flying Sidekick Traveling Salesman Problem (FSTSP), where a truck and a drone cooperate to serve customers. Building on the carrier–vehicle literature, Klaučo et al. proposed a mixed-integer second-order cone programming (MISOCP) model for a generalized carrier–vehicle problem and extended it to the Generalized Carrier–Vehicle Traveling Salesman Problem (GCVTSP), in which the fast vehicle may visit multiple targets between take-off and landing. However, their formulation for the fixed-order generalized carrier–vehicle subproblem admits a relatively weak SOCP relaxation, leading to large branch-and-bound trees and long computation times. In this work, we derive an alternative formulation that significantly tightens the SOCP relaxation while preserving the original problem structure. Computational experiments show that the strengthened model yields substantial speed-ups when solving generalized carrier–vehicle instances to optimality. For the GCVTSP, we propose an exact double-ended branch-and-bound algorithm and a heuristic scheme that exploits the improved relaxation. This is a joint work with Wenxuan Dong.

Abstract. Inventory Routing Problems (IRPs) jointly determine multi-period replenishment quantities and vehicle routes, balancing inventory holding and stockout penalties against transportation costs. The problem is fundamentally difficult: delivery quantities are discrete, decisions propagate over long planning horizons through inventory dynamics, and routing feasibility constraints tightly couple customers across each day. These structural interactions make IRPs significantly more complex than classical vehicle routing or lot-sizing problems in isolation. This talk presents a line of work on scalable algorithms for both deterministic and stochastic IRPs. For deterministic settings, the speaker introduces a metaheuristic framework centered on Hybrid Genetic Search (HGS), enriched with problem-specific routing improvement operators and a destroy-and-repair mechanism tailored to delivery quantities. The repair phase leverages dynamic programming routines that evaluate multi-period inventory trajectories and stockout penalties while explicitly accounting for route detours and vehicle capacity interactions. This tight integration of routing and inventory evaluation enables consistent high-quality solutions across standard benchmark instances and produces numerous new best-known results. The discussion then extends to stochastic IRPs with uncertain customer demand. To capture uncertainty while preserving tractability, a rolling-horizon reformulation into a two-stage stochastic optimization model is adopted. Current-day routing and service decisions are optimized by anticipating expected downstream recourse costs under multiple demand scenarios. The primary scalability challenge lies in evaluating large scenario sets efficiently. To address this, a matrix-based dynamic programming framework with GPU-friendly structure is developed to accelerate multi-scenario cost evaluation through parallelized state transitions. This approach enables large-scale scenario analysis and substantially improves computational efficiency, making stochastic IRP planning viable for real-world, high-dimensional applications.

Abstract. Momentum based optimizers are central to a wide range of machine learning applications. These typically rely on an Exponential Moving Average (EMA) of gradients, which decays exponentially the present contribution of older gradients. This accounts for gradients being local linear approximations which lose their relevance as the iterate moves along the loss landscape. This work questions the use of a single EMA to accumulate past gradients and empirically demonstrates how this choice can be sub-optimal: a single EMA cannot simultaneously give a high weight to the immediate past, and a non-negligible weight to older gradients. Building on this observation, we propose AdEMAMix, a simple modification of the Adam optimizer with a mixture of two EMAs to better take advantage of past gradients. Our experiments on language modeling and image classification show – quite surprisingly – that gradients can stay relevant for tens of thousands of steps. They help to converge faster, and often to lower minima: e.g., a 1.3B parameter AdEMAMix LLM trained on 101B tokens performs comparably to an AdamW model trained on 197B tokens (+95%). Moreover, our method significantly slows-down model forgetting during training. Our work motivates further exploration of different types of functions to leverage past gradients, beyond EMAs.

Abstract. Distributionally Robust (DR) optimization aims to certify worst-case risk within a Wasserstein uncertainty set. Current certifications typically rely either on global Lipschitz bounds, which are often conservative, or on local gradient information, which provides only a first-order approximation. We introduce a novel geometric framework based on the least concave majorants of the growth rate function. Our proposed concave certificate establishes a tight bound of DR risk that remains applicable to non-Lipschitz and non-differentiable losses. We extend this framework to complexity analysis, introducing a deterministic bound that complements standard statistical generalization bound. Furthermore, we utilize this certificate to bound the gap between adversarial and empirical Rademacher complexity, demonstrating that dependencies on input diameter, network width, and depth can be eliminated. For practical application in deep learning, we introduce the adversarial score as a tractable relaxation of the concave certificate that enables efficient and layer-wise analysis of neural networks. We validate our theoretical results in various numerical experiments on classification and regression tasks on real-world data.

Abstract. Branch-and-cut is arguably the most effective algorithm to solve large scale mixed-integer optimization problems in practice. In spite of tremendous progress in both the mathematical underpinnings and the computational insights required to deploy branch-and-cut in practice, several aspects of this important algorithm remain poorly understood. In particular, several crucial decisions (e.g., cutting plane or branching variable selection) that need to be made during the execution of branch-and-cut lack a satisfactory foundation, and clear recipes are difficult to formulate given the wide diversity of instances that these algorithms need to tackle. This has led several researchers to explore data driven, machine learning tools to help guide these decisions. The philosophy is simple: the decisions that work well for a given sample of instances should have good performance on a larger class of instances, assuming the sample is “representative” of the larger class. In this talk, we explore the foundational principles that formalize this idea, focusing on two issues: 1) The size of the sample required for high quality performance on unseen instances, and 2) Pitfalls to avoid when selecting a particular machine learning paradigm for branch-and-cut. Both these lines of investigations uncover insights into mixed-integer optimization which we believe are useful beyond the principled use of machine learning for branch-and-cut.

Abstract. Neural networks with ReLU activation play a central role in modern machine learning. We study structural properties of the piecewise-linear functions they represent, highlighting connections to polyhedral theory, mixed-integer optimization, tropical geometry, and computational complexity.

We discuss recent progress on the expressive power of ReLU networks, focusing on lower bounds for the depth required to represent piecewise-linear functions. We then consider the computational complexity of analyzing ReLU networks, including deciding injectivity, surjectivity, and verification properties. Our results show that these problems are computationally intractable in general, revealing fundamental limitations of algorithmically understanding and verifying neural networks. The talk is based on joint work with Christoph Hertrich, Amitabh Basu, Marco Di Summa, Vincent Froese, and Moritz Grillo.

Abstract. The current wave of artificial intelligence is transforming industry, society, and science at an unprecedented pace. Yet, this progress comes with rapidly increasing energy demands, raising urgent sustainability concerns. This lecture begins by examining the limitations of today’s predominantly digital AI systems, focusing on their inherent energy inefficiency and fundamental computational constraints. These challenges underscore the need to rethink the foundations of AI computing. We then turn to neuromorphic computing, an emerging paradigm inspired by biological neural systems. By leveraging analog hardware and spiking neural networks, it offers a path toward dramatically more energy-efficient AI. We will highlight recent advances and delve into the mathematical foundations of spiking neural networks, showcasing our results on expressivity, training, and generalization, and their implications for sustainable intelligent systems.

Abstract. We propose a globally converging cutting-plane algorithm for solving stochastic mixed-integer programs (SMIP) with general mixed-integer state variables. We show that Lagrangian cuts in a lifted space with binary variables added can asymptotically approximate the value function. We also propose enhanced Lagrangian cuts, which strengthen the vanilla Lagrangian cut and yield good geometric properties. In the process of generating enhanced Lagrangian cuts, we employ a collection of computational techniques to guarantee cut validity and reuse information from previous iterations. Machine learning techniques are shown to accelerate the process of obtaining a good candidate cut coefficient. Extensive computational experiments on power system operations, vehicle routing problems, and a crew scheduling problem demonstrate the effectiveness of our proposed methodology in solving large-scale, multistage stochastic mixed-integer optimization problems.

Abstract. The problem of optimal trade execution is to find the trading rate that minimizes the cost of liquidating an inventory of stock by a given time $T$ in the presence of market impact costs. We consider the case of linear price impact when the drift and permanent price impact parameters are constant but unknown to the trader and formulate a Bayesian control formulation where the prior is updated using return data generated during the trade. Since the trading decision affects both cost and data, there is a tradeoff between exploration and exploitation which is fully characterized by the optimal policy. This problem is difficult to solve because the Hamilton-Jacobi-Bellman (HJB) dynamic programming equation has no explicit solution and is computationally intractable due to the curse of dimensionality. To isolate the exploration and exploitation components of the optimal trade, we consider an asymptotic expansion in the regime where the noise in the return is large. The zeroth-order (“exploitation”) term is the solution of the original (Almgren-Chriss) trade execution problem with uncertain parameters replaced by their prior means, while the first-order (“exploration”) term captures the tradeoff between the temporary price impact cost, the cost of using inventory for exploration, and the value of resolving uncertainty about the drift and the price impact. Both terms in the expansion are easy to compute: there is an explicit expression for the zeroth-order term while the exploration adjustment is the solution of a system of linear ordinary differential equations. Our analysis shows an intuitive but non-trivial dependence of optimal exploration on inventory and horizon and illustrates a new approach to exploration over finite horizons.

Abstract. In this talk, we deal with a perturbation analysis of singular SDP with a finite nonzero duality gap. Both of primal (P) and dual (D) are weakly feasible under this condition. We denote by $V_p$ and $V_d$ the optimal values of (P) and (D), respectively. Even there exists a finite nonzero duality gap between the original (P) and (D), i.e., $V_p > V_d$, there always exists “arbitrary small perturbation” which would make both perturbed (P) and (D) strongly feasible so that they have a common optimal value. Thus, the optimal value function of (P) and (D) has a complicated structure sensitive to perturbation. We denote by $v$ the common optimal value of perturbed (P) and (D), which is a function of perturbation. Recently, we established that $v$ has the directional limit when perturbation is reduced to zero, converging to a value in the interval $[V_d, V_p]$. More strongly, we could show that there exists a continuous one-to-one mapping between the set of directions of perturbation and the interval $[V_d, V_p]$ if the singularity degree of (P) and (D) is one. This beautiful property does not hold any more if the singularity degree is greater than one. We discuss how this result can be extended to nonzero finite nonzero duality gap SDPs when singularity degree is two.

Abstract. We propose new methods to accelerate the estimation of flow models.

Abstract. The presence of symmetries is one of the central structural features that make some integer programs challenging for state-of-the-art solvers. In this work, we study the efficacy of Linear Programming (LP) hierarchies in the presence of symmetries. Our main theorem unveils a connection between the algebraic structure of these relaxations and the geometry of the initial integer-empty polytope. We show that under $(k + 1)$-transitive symmetries - a measure of the underlying symmetry in the problem - the corresponding relaxation at level $k$ of the hierarchy is non-empty if and only if the initial polytope intersects all $(n - k)$-dimensional faces of the hypercube. In particular, the hierarchies of Sherali-Adams, Lovász-Schrijver, and the Lift-and-Project closure are equally effective at detecting integer emptiness. Our result provides a unifying, group-theoretic characterization of the poor performance of LP-based hierarchies, and offers a simple procedure for proving lower bounds on the integrality gaps of symmetric polytopes under these hierarchies. Joint work with V. Verdugo (PUC Chile), J. Verschae (PUC Chile), and M. Villagra (Columbia University).

Abstract. A variable change reduces the problem of trying to find an SOS (Sum Of Squares of polynomials) decomposition of a PSD (Positive Semi-Definite) 4-ary 4-ic (4-variate homogeneous polynomial of degree 4) $f$ to the one of trying to find it for a 4-ary 4-ic of the form $f(x,y,z,w) = aw^2 + 2bw + c$, where $a,b,c$ are 3-ary forms of degrees 2, 3, 4 respectively. While $f$ need not be an SOS, all the examples of $f$ we know can be made SOS by multiplying by $a$ — and $af = (ax+b)^2 + ac - b^2$ is obtained by the usual square extraction. It is tempting to conjecture that the (PSD) discriminant of $f$, the 3-ary 6-ic $ac - b^2$, is an SOS. We present counterexamples to this conjecture. The conjecture that $af$ is SOS for any PSD $f = aw^2 + 2bw + c$ still stands.

Abstract. By analogy to the terminology of curved exponential families in statistics, we define curved Bregman divergences as Bregman divergences restricted to non-affine parameter subspaces and sub-dimensional Bregman divergences when the restrictions are affine. A common example of curved Bregman divergence is the cosine dissimilarity between normalized vectors: a curved squared Euclidean divergence. We prove that the barycenter of a finite weighted set of parameters under a curved Bregman divergence amounts to the right Bregman projection onto the non-affine subspace of the barycenter with respect to the full Bregman divergence, and interpret a generalization of the weighted Bregman centroid of $n$ parameters as a $n$-fold sub-dimensional Bregman divergence. We demonstrate the significance of curved Bregman divergences with several examples: (1) symmetrized Bregman divergences, (2) pointwise symmetrized Bregman divergences, and (3) the Kullback-Leibler divergence between circular complex normal distributions. We explain how to reparameterize sub-dimensional Bregman divergences on simplicial sub-dimensional domains. We then consider monotonic embeddings to define representational curved Bregman divergences and show that the $\alpha$-divergences are representational curved Bregman divergences with respect to $\alpha$-embeddings of the probability simplex into the positive measure cone. As an application, we report an efficient method to calculate the intersection of a finite set of $\alpha$-divergence spheres.

Abstract. Redundancy removal in high performance LP solvers is typically done by pre-solver heuristics, as it doesn’t usually make sense to solve multiple LPs as a preprocessing step. Sometimes we really want the minimum description, e.g. when the correctness of our algorithm depends on it, or when the desired computation is much more expensive than solving a single LP. In principle Clarkson’s 1994 algorithm is an attractive tool for this task. In practice the bound of “$m$ LPs with $s$ rows” (where $s$ is the output size) leaves a lot of room for variation, especially when dealing with the simplex method. In this talk I’ll discuss a recent exact arithmetic implementation of Clarkson’s algorithm, and compare the performance with the (even) more traditional algorithm using the same lrslib LP solver. I’ll focus on the impact of various kinds of hot start, and discuss the symbolic (lexicographic) perturbation and preprocessing needed to handle the highly degenerate (as in multiple constraints tight at a vertex) inputs common in combinatorial optimization. This is joint work with David Avis.

Abstract. Recently, Fenchel-Young losses have been introduced to learn links used notably in generalized linear models: they are nonnegative convex losses that vanish on the link; recently introduced Fitzpatrick losses share the same properties. We introduce a broader class of losses that we call representation losses, as they come from the theory of representations of monotone operators. Each representation loss comes with its own enlargement of the link, from which one can deduce geometrical minimizers guarantees to the fitted data. Within representation losses, we distinguish the so-called sharpened Fenchel-Young losses. This subclass of losses are target-dependent Fenchel-Young losses whose link enlargement is controlled by means of a sharpener. Our approach offers perspectives to control geometrical minimizer guarantees to the fitted data when designing a loss.

Abstract. How can we find and apply the best optimization algorithm for a given problem? This question is as old as mathematical optimization itself, and is notoriously hard: even special cases such as finding the optimal learning rate for gradient descent, are nonconvex in general. In this talk we will discuss a dynamical systems approach to this question. We start by discussing an emerging paradigm in differentiable reinforcement learning called “online nonstochastic control”. The new approach applies techniques from online convex optimization and convex relaxations to obtain new methods with provable guarantees for classical settings in optimal and robust control. We then show how this methodology can yield global guarantees for learning the best algorithm in certain cases of stochastic and online optimization. No background is required for this talk, but relevant material can be found in this text on online control and paper on meta optimization.

Abstract. We survey various techniques imported from convex optimization and aimed at accelerating the training of large language models.

Abstract. Training deep neural networks gives rise to large-scale non-convex optimization problems that are often highly sensitive to step-size and hyperparameter choices. We present the Additively Preconditioned Trust-Region Strategy (APTS), a parallel nonlinear optimization method inspired by nonlinear domain decomposition techniques for PDEs and trust-region methods for globalization. The method is based on a decomposition of the parameter space into subspaces, on which local nonlinear subproblems are defined. These subproblems yield local nonlinear corrections that are combined into a global trial step, which can be interpreted as an additive nonlinear preconditioner for the underlying minimization problem. Global convergence is achieved by embedding this step into a trust-region framework, where the full objective is evaluated to determine step acceptance and update the trust-region radius. This stabilization mechanism significantly reduces sensitivity to hyperparameter tuning. We further introduce a non-monotone variant of APTS using a windowed acceptance criterion, allowing controlled non-monotonicity to improve step acceptance in highly non-convex landscapes. Numerical results for purely data based neural network training on standard benchmarks and for PINNs demonstrate the robustness and effectiveness of the proposed approach.

Abstract. Recent progress in quasi-Newton analysis has renewed interest in BFGS methods with explicit global performance guarantees. In this talk, we highlight two complementary advances in modern BFGS research, spanning theory-driven acceleration and noise-robust practice. First, we introduce a generalized eigenpair-based BFGS scheme that explicitly minimizes a strict Hessian-approximation accuracy measure at each iteration, yielding non-asymptotic global superlinear convergence with a doubly-exponential rate. Second, we consider optimization with noisy objective values and propose a regularized quasi-Newton method with a noise-aware relaxation of the Armijo sufficient-decrease test; the method retains the standard $O(\varepsilon^{-2})$ global complexity for reaching first-order stationary points.

Abstract. We establish strong connections between two fundamental nonlinear 0/1 optimization problems coming from the area of experimental design, namely maximum entropy sampling and 0/1 D-Optimality. The connections are based on maps between instances, and we analyze the behavior of these maps. Using these maps, we transport basic upper-bounding methods between these two problems, and we are able to establish new domination results and other inequalities relating various basic upper bounds. Further, we establish results relating how different branch-and-bound schemes based on these maps compare. Additionally, we observe some surprising numerical results, where bounding methods that did not seem promising in their direct application to real-data MESP instances, are now useful for MESP instances that come from 0/1 D-Optimality.

Abstract. We study cut-generating functions in the setting of the Gomory–Johnson group relaxations for integer programming. We address an open question: whether every facet (extreme function) for a finite cyclic group relaxation injects into the space of extreme functions for the infinite group problem. Specifically, we show that any piecewise linear minimal function with rational breakpoints in 1/qZ and rational values at these breakpoints can be approximated by piecewise linear two-slope extreme functions while preserving all function values on 1/qZ. As a corollary, every extreme function for the finite group problem on 1/qZ is the restriction of a continuous piecewise linear two-slope extreme function for the infinite group problem, with breakpoints on a refinement 1/(Mq)Z. Combined with Gomory’s master theorem, this establishes that the infinite group problem indeed serves as the correct master problem for facets of one-row group relaxations. This is a joint work with Matthias Koeppe.

Abstract. The chain of thought is fundamental in Transformers, which is to perform step-by-step reasoning. Besides what intermediate steps work, the order of these steps critically affects the difficulty of the reasoning. This talk presents a novel task of unraveling chain of thought - reordering decoder input tokens to a learning-friendly sequence for Transformers to learn arithmetic tasks. The proposed pipeline first trains a Transformer on a mixture of target sequences arranged in different orders and then identifies benign orders as those with fast loss drops in the early stage. As the search space grows factorially with sequence length, we propose a two-stage hierarchical approach for inter- and intra-block reordering. Experiments on four order-sensitive arithmetic tasks show that our method identifies a learning-friendly order out of a few billion candidates. Notably, on the multiplication task, it recovered the reverse-digit order reported in prior studies.

Abstract. Social networks have become central platforms for word-of-mouth diffusion in marketing, e-commerce, and public health, elevating the importance of designing effective influence maximization strategies under limited resources. However, conventional influence maximization studies largely neglect the majority illusion, a cognitive bias where local neighborhood observations create a false impression of global consensus, potentially misleading both decision-makers and individuals about the true level of adoption. This research investigates how to schedule seed activations to not only maximize overall influence but also to control majority-illusion nodes, thereby improving the perceptual fidelity of diffusion outcomes in social networks. The problem is formulated as the Majority Illusion Influence Maximization Scheduling (MIB) problem, modeled through a two-stage mixed-integer programming framework under the Linear Threshold diffusion model. In Phase I, the model selects and schedules seed nodes over a finite planning horizon to maximize the number of activated nodes subject to seeding budget and timing constraints. Phase II then preserves the influence level achieved in Phase I while explicitly minimizing the number of majority-illusion nodes, thus balancing diffusion reach and perceptual accuracy. To explore structural interventions, an extended network design variant, MID, further incorporates edge modification decisions to study how network structure shapes both activation patterns and illusion phenomena. Due to the NP-hard nature and large-scale complexity of MIB, exact solutions via mixed-integer programming are tractable only for relatively small networks. To enhance scalability, three algorithmic approaches are developed: a fast greedy heuristic (GR), a genetic algorithm (GA), and a rolling horizon (RH) algorithm that decomposes the planning horizon into overlapping time windows. Hybrid warm-start strategies are also designed to feed heuristic solutions into the exact solver, accelerating convergence on medium-sized instances. Computational experiments are conducted on SNAP ego-Twitter networks with sizes ranging from 50 to 2000 nodes under different seeding budgets. Results show that RH consistently provides the best trade-off between solution quality and computation time, matching optimal mixed-integer solutions on 300-node instances with about 12% of the runtime and yielding up to 3.7 and 32 times better solutions than the exact model’s incumbent for 800- and 2000-node cases within the same time limit.

Abstract. We present a general framework for finding good feasible solutions, or improving incumbent solutions, to quadratically constrained quadratic programs (QCQPs) by using mixed-integer linear programs (MIPs) arising from variable discretizations. An adaptive algorithm iteratively updates the parameters of the discretized model by creating finer discretizations around the incumbent point. Our method complements existing algorithms for adaptive updates of MIP relaxations of QCQPs. We use a graph neural network (GNN) approach to leverage the intrinsic graph structure of QCQPs, and Bayesian optimization to jointly tune the parameters of GNN and adaptive algorithm. Computational experiments performed on specific types of QCQPs exhibit improved solution quality by 25% over the standard adaptive method and by 60% over a state-of-the-art global solver.

Abstract. In this talk, given two convex sets, we present a facial reduction algorithm that either decides that the sets do not intersect or finds minimal faces of each set containing the intersection. This can be leveraged to construct duals of convex programs that always afford strong duality even when constraint qualifications fail. Along the way, we introduce our notions of niceness of convex sets and vertical niceness of convex functions which allow us to simplify the theory. This is a joint work with Ying Lin (University of Hong Kong) and Tianxiang Liu (University of Tsukuba).

Abstract. Multivariate statistical process control techniques have been widely used for online monitoring in various applications. However, when monitoring high-dimensional processes, practical resource constraints such as limited data transmission bandwidth, number of sensors, and sensor battery life often restrict our ability to collect observations from all data streams. In this paper, we propose a neural network-based adaptive sampling strategy for monitoring high-dimensional processes. To adaptively select data streams for observation, it is essential to dynamically assess the importance of each stream. Accordingly, we propose learning an importance function through a neural network. By incorporating domain knowledge of process monitoring, a monotonic neural network is constructed. A key challenge in training this network is the lack of ground truth for importance assessment. To address this challenge, we simulate training data and design a novel loss function. Compared to existing adaptive sampling strategies, our method does not rely on heuristic techniques and offers enhanced scalability. With the proposed adaptive sampling strategy, a generic monitoring scheme is then developed for the monitoring of high-dimensional processes. We have conducted thorough numerical simulations and a case study, which demonstrate that our method significantly reduces detection delays and increases the likelihood of observing shifted data streams.

Abstract. In this talk we present a random-subspace Frank–Wolfe algorithm for smooth convex optimization over uniformly convex compact domains. The method replaces the full linear minimization oracle by a low-dimensional oracle restricted to a randomly sampled subspace, substantially reducing the cost per iteration. We show that several known convergence guarantees for the classical Frank–Wolfe method extend to this randomized low-dimensional method.

Abstract. The standard formulation of reinforcement learning assumes that an agent observes an immediate reward at each time step and aims to maximize the cumulative sum of these rewards. In practice, however, providing well-defined immediate rewards at every time step is often difficult, and simple summation is not always an appropriate means of aggregating reward signals. In this talk, I present an overview of our recent research that addresses these challenges.

Abstract. We consider the problem of minimizing a difference-of-convex objective over a nonlinear conic constraint. We assume that the cone is closed, convex and pointed with a nonempty interior, and the support function of a compact base of its dual cone admits a so-called majorizing smoothing approximation. These conditions are satisfied by widely studied cones such as the nonnegative orthants and the cone of positive semidefinite matrices. We reformulate the conic constraint equivalently as a single inequality constraint involving the aforementioned support function, and adapt the moving balls approximation (MBA) method for its solution. In essence, in each iteration of our algorithm, we approximate the support function by a smooth approximation function and apply one MBA step. The subproblems that arise in our algorithm always involve only one single inequality constraint. We design explicit rules to evolve the smooth approximation functions from iteration to iteration and establish the global iteration complexity for obtaining an approximate Karush-Kuhn-Tucker point. In addition, in the convex setting, we establish convergence of the sequence generated, and study its local convergence rate under a standard Hölderian growth condition. This is a joint work with Nung-sing Sze and Jiefeng Xu.

Abstract. The talk will survey recent algorithmic advancements in projection-free (e.g., the Frank-Wolfe method) methods with a focus on novel complexity bounds for convex models with sparse solutions.

Abstract. The higher-order correlation clustering problem for a graph $G$ and costs associated with cliques of $G$ consists in finding a clustering of $G$ so as to minimize the sum of the costs of those cliques whose nodes all belong to the same cluster. To tackle this NP-hard problem in practice, local search heuristics have been proposed and studied in the context of applications. Here, we establish partial optimality conditions for cubic correlation clustering, i.e., for the special case of at most 3-cliques. We define and implement algorithms for deciding these conditions and examine their effectiveness numerically, on two data sets.

Abstract. Deep equilibrium networks, also know as implicit models, are extensions of classical layered networks where the hidden feature vector is obtained as the solution of a fixed-point equation, instead of a finite recursion. Such models can be represented in a “state-space” form that bears a striking resemblance to the familiar state-space representation of LTI systems in control. This in turn opens the door to many opportunities and connections to optimization and control. In this talk, I will present an overview of such models, emphasizing representation, well-posedness and composition. Then I will present a few use cases, including the inversion of neural networks (for data augmentation purposes) and constrained neural control of dynamical systems.

Abstract. Selecting the single best winner in an election can be difficult, sometimes even impossible. In this talk, I will show that selecting just six winners is always sufficient to achieve a majority approval: they form what is known as a Condorcet winning set. I will also discuss how this number can be reduced for a natural class of instances that are metrically embeddable. Finally, I will also present algorithms for finding the optimal committee under various Thiele rules. These are joint works with an amazing set of coauthors: Moses Charikar, Prasanna Ramakrishnan, Ulrike Schmidt-Kraepelin, Krzysztof Sornat, Bernhard von Stengel, Adrian Vetta, and Kangning Wang.

Abstract. We prove a strongly polynomial bound on the circuit diameter of polyhedra, resolving the circuit analogue of the polynomial Hirsch conjecture. Specifically, we show that the circuit diameter of a polyhedron $P = {x \in \mathbb{R}^n : Ax = b, x \geq 0}$ with $A \in \mathbb{R}^{m \times n}$ is $O(m^2 \log m)$. Our construction yields monotone circuit walks, giving the same bound for the monotone circuit diameter. The circuit diameter, introduced by Borgwardt, Finhold, and Hemmecke (SIDMA 2015), is a natural relaxation of the combinatorial diameter that allows steps along circuit directions rather than only along edges. All prior upper bounds on the circuit diameter were only weakly polynomial. Finding a circuit augmentation algorithm that matches this bound would yield a strongly polynomial time algorithm for linear programming, resolving Smale’s 9th problem.

Abstract. In many applications, an optimization model is solved repeatedly after small simultaneous changes to the objective coefficients, right-hand sides, and constraint matrix. In this work, we show how to obtain computationally convenient and reliable dual bounds for bounded linear and mixed-integer linear programs under general perturbations. We present worst-case guarantees on the gap between the true value function and the proposed dual bound, which are linear in the size of the perturbations under mild assumptions. For the MIP setting, we revisit the Schrage & Wolsey idea of reusing a nominal branch-and-bound tree, combining it with node-level dual information, to derive dual bounds that are practical to evaluate. We conclude with numerical results on classic OR and power systems problems and future directions. This is joint work with Santanu S. Dey and Fabian Badilla Mera.

Abstract. We introduce a direct polynomial reduction from BLP to DGP1 that reduces instance size increase in the target problem with respect to the existing chain BLP $\to$ SAT $\to$ 3SAT $\to$ DGP1 based on existing literature. Based on this reduction, we can “model” any problem in NP by means of the DGP1. We therefore present a set of methods for solving DGP1 instances: exact, leading to certificates for YES instances; relaxed, leading to bounds on an error function for NO instances; and heuristic, based on continuous optimization methods.

Abstract. There have been a number of recent results on the complexity of computing parameters on polyhedra. We consider the monotone eccentricity of a vertex v of a polytope. This is the largest number of pivots required to reach an optimal vertex starting from v. We study a polytope introduced by Frieze and Teng derived from the exact partition problem. We show that Frieze and Teng’s result on the complexity of computing lower bounds on diameters of exact partition polytopes extends to show that computing monotone eccentricity is also NP-Hard and in fact D^P-hard. The Frieze-Teng construction is an appealing and approachable object that was advertised as being a simple polytope. This turns out not to be quite true in general, but we are nevertheless able to show the complexity results hold for simple polytopes. This is joint work with K. Narayanan.

Abstract. Magic squares are a fascinating mathematical challenge that has intrigued mathematicians for centuries. Given a positive (and possibly large) integer $n$, one of the main challenges that still remains is to find, within a computational time, a magic square of order $n$, that is, a square matrix of order $n$ with unique integers from $a_{\min}$ to $a_{\max}$, such that the sum of each row, column, and diagonal equals a constant. In this work, we first present an integer constraint satisfaction problem for constructing a magic square of order $n$. Nonetheless, the solution time of this problem grows exponentially as the order increases. To overcome this limitation, we also propose an approach that constructs magic squares depending on whether $n$ is odd, singly even, or doubly even. Moreover, we provide a proof of the correctness of this novel approach. Our numerical results show that our method can construct magic squares of order up to 70000 in less than 140 seconds, demonstrating its efficiency and scalability.

Abstract. In this talk, I am going to present recent progress of fair division as well as open questions.

Abstract. The duality between optimization and sampling provides a powerful mathematical framework for exploring complex probability measures and highly non-convex landscapes. In this talk, we examine this relationship in both directions and show how ideas from one domain can be used to overcome fundamental limitations in the other. We begin with the direction from optimization to sampling. By formulating stochastic optimal control as an optimization problem over path-space measures, we derive a new trust-region-based approach for sampling from high-dimensional, multimodal target distributions. This perspective enables principled control of exploration and improves robustness in challenging sampling settings. We then reverse the viewpoint and use diffusion-based sampling techniques to address global optimization problems. We introduce a non-convex optimization method that combines controlled diffusion dynamics with temperature tempering. Through systematic benchmarking, we analyze the failure modes of classical first-order optimizers and traditional MCMC approaches such as Simulated Annealing. Our results show that leveraging diffusion dynamics leads to improved scaling behavior and more reliable escape from local minima in highly multimodal objectives.