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. Cardinality function counts the number of nonzero elements of its input. It acts naturally as a loss function in many machine learning applications. Cardinality optimization has attracted much attention and seen significant progress over the past few years. Composite cardinality function is the cardinality function compounded with affine mappings and hence has a capability of modelling even a wider range of applications. Therefore, Composite Cardinality Optimization (CCOPT) is fundamental. Unlike the cardinality function, whose discontinuous regions are subspaces, composite cardinality has discontinuous regions being the unions of polyhedral sets of exponentially many. This imposes a significant challenge in both developing optimization theory and algorithms. This talk introduces a newly proposed stationary duality for CCOPT and demonstrates its numerical implications.

Abstract. Decision-dependent information discovery (DDID) tackles optimization under uncertainty in settings where the decision maker may investigate the realization of selected uncertain parameters, thereby reducing the overall level of uncertainty. DDID can be modeled as a three-stage robust optimization problem: (i) select a subset of parameters to query, (ii) an adversary reveals the values of the queried parameters, and (iii) compute a minimum-cost feasible solution to the resulting robust problem, where the unqueried parameters remain uncertain. We discuss several reformulations and complexity results for this challenging problem class. In particular, we show how to derive MILP reformulations—possibly non-compact—when uncertainty affects only the cost coefficients. We illustrate our reformulations and algorithms numerically on the selection problem, the orienteering problem, and the spanning tree problem.

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. 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. We introduce the Unsplittable Transshipment Problem in directed graphs with multiple sources and sinks. An unsplittable transshipment routes given supplies and demands using at most one path for each source-sink pair. Although they are a natural generalization of single source unsplittable flows, unsplittable transshipments raise interesting new challenges and require novel algorithmic techniques. As our main contribution, we give a nontrivial generalization of a seminal result of Dinitz, Garg, and Goemans (1999) by showing how to efficiently turn a given transshipment $x$ into an unsplittable transshipment $y$ with $y_a < x_a + d_{\max}$ for all arcs $a$, where $d_{\max}$ is the maximum demand (or supply) value. Further results include bounds on the number of rounds required to satisfy all demands, where each round consists of an unsplittable transshipment that routes a subset of the demands while respecting arc capacity constraints.

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. Pruning and quantization are key techniques for reducing the compute and memory requirements of Large Language Models (LLMs). State-of-the-art post-training methods operate layer-wise, minimizing a per-layer reconstruction error on a small calibration dataset. For pruning, this gives rise to the mask selection problem: finding a binary mask that determines which weights to keep – a cardinality-constrained binary quadratic program that is NP-hard in general. For quantization, a closely related problem arises where each weight must be mapped to a discrete grid point. Existing methods often rely on greedy heuristics that make independent per-weight decisions, effectively ignoring weight interactions. This talk presents a unified local optimization framework that encompasses both pruning and quantization. Across modern GPT architectures, the proposed methods reduce the per-layer compression error by up to 80% over existing approaches, with consistent improvements in perplexity and downstream accuracy.

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

Abstract. This talk studies the inverse optimal transport (IOT) problem under Bregman regularization. We first investigate the fundamental theoretical properties of the model and establish well-posedness results, including existence, uniqueness up to equivalence classes, and stability, under mild structural assumptions on the cost matrix. In addition, we will discuss the numerical algorithms for solving this inverse problem with single and multiple observations.

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. 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. In the context of symmetric integer programs (at least) it is interesting to maximize a linear functional over the integer vectors whose circulant matrix is non-singular. The feasible region turns out to be (the integer points) in a union of linear subspaces. This talk will explain the connections with invariant subspaces and semisimple spaces. It will also consider what kinds of model are most effective for this problem with modern solvers.

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. Learning in dynamical systems is a fundamental challenge underlying modern sequence modeling. Despite extensive study, efficient algorithms with formal guarantees for general nonlinear systems have remained elusive. This talk presents a provably efficient framework for learning in any bounded and Lipschitz nonlinear dynamical system, establishing the first sublinear regret guarantees in a dimension-free setting. Our approach combines Koopman lifting, Luenberger observers, and, crucially, spectral filtering to show that nonlinear dynamics are learnable. These insights motivate a new neural architecture, the Spectral Transform Unit (STU), which achieves state-of-the-art performance on language modeling, dynamical system, and differential equation benchmarks.

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

Abstract. In the current landscape of machine learning, where foundation models must navigate imperfect real-world conditions such as noisy data and unexpected inputs, ensuring their trustworthiness through rigorous benchmarking, safety-focused finetuning, and robust reasoning is more critical than ever. In this talk, I will focus on three recent research advancements that collectively advance these dimensions, offering a comprehensive approach to building trustworthy foundation models. For benchmarking, I will introduce CounterAnimal, a dataset designed to systematically evaluate CLIP’s vulnerability to realistic spurious correlations, revealing that scaling models or data quality can mitigate these biases, yet scaling data alone does not effectively address them. Transitioning to finetuning, we delve deep into the process of unlearning undesirable model behaviours. We propose a general framework to examine and understand the limitations of current unlearning methods and suggest enhanced revisions for more effective unlearning. Furthermore, addressing reasoning, we investigate the reasoning robustness under noisy rationales by constructing the NoRa dataset and propose contrastive denoising with noisy chain-of-thought, a method that markedly improves denoising-reasoning capabilities by contrasting noisy inputs with minimal clean supervision.

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. 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. 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 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. 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. 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. I will provide an overview of the needs in optimization and machine learning in a developing country such as Vietnam.

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. Integer programs lie at the heart of combinatorial optimization, yet it is in general computationally intractable. This talk gives an overview on the latest progress in designing efficient (fixed-parameter tractable) algorithms for subclasses of integer programs. We will highlight the main algorithmic techniques that enable these results and examine the complexity-theoretic bounds that separate the tractable from the intractable.

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. 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.