The multi-armed bandit problem has been extensively studied within the context of sequential decision-making, finding numerous applications across diverse fields such as finance, online advertising, and healthcare. This survey aims to provide an overview of recent advancements, emerging topics, and novel applications related to multi-armed bandits. We focus on highlighting key developments that are particularly relevant to the operations research and optimization communities. By offering a comprehensive background on the subject, our survey serves as a valuable resource for researchers seeking new areas of exploration. Additionally, we present selected real-world problem statements to illustrate practical implications and potential future directions for further investigation.
We consider optimization of a smooth function of non-negative normalized vectors, generally of different dimensions. The iterative process is based on a multiplicative gradient step with projections onto unit simplices. The convergence of this process is proven. Application of this approach to stochastic matrix factorization problems leads to EM-like algorithms. This allows us to develop an optimizational theory of probabilistic topic modeling of large text collections that is much more elegant than the Bayesian inference commonly used in this area. Multi-objective additive regularization uniformly describes hundreds of topic models previously introduced in terms of Bayesian learning. We propose a new attention topic model that operates on sequential text rather than on a ``bag of words’’ representation like classical topic models. Our approach is a step towards bringing together gradient optimization methods for training neural large language models and probabilistic topic models, providing prospects for the development of a large class of neural topic models.
Let G be a simple graph. Imagine placing pebbles on the vertices of this graph. We can represent this arrangement (configuration) by a function that assigns a number of pebbles to each vertex. The weight of this configuration is simply the total number of pebbles placed on all the vertices. A pebbling step involves taking two pebbles from one vertex and moving one of them to an adjacent vertex. A solvable configuration is one where it's possible to move pebbles around the graph using these steps to place at least one pebble on any chosen vertex. A t-restricted pebbling configuration limits the number of pebbles on any single vertex to a maximum of t. The t-restricted optimal pebbling number is the smallest total number of pebbles needed to achieve a solvable arrangement while adhering to this t limit. This paper characterizes graphs where the 2-restricted optimal pebbling number is 5. Also, we characterize the trees of order n that are the improved upper bound of the 2-restricted optimal pebbling number for them. Finally, we study the 2-restricted optimal pebbling number of some grid graphs, corona and neighborhood corona of two specific graphs.
Finding one or more solutions to a general system of nonlinear equations (SNE) is a computationally hard problem with many applications in sciences and engineering. First, we will briefly discuss classical approaches for addressing (SNE).
Then, we will discuss the various ways that a SNE can be transformed into an optimization problem, and we will introduce techniques that can be utilized to search for solutions to the global optimization problem that arises when the most common reformulation is performed. We will present computational results using state of the art heuristics.
Fighting with invasive biological species presents an outstanding problem in many regions of the Globe. The scientific literature on the relevant mathematical models is steadily growing. Reviewing some basic mathematical approaches and taking as basic examples the propagation of ticks (and thus tick-borne diseases) and of Hogweed we develop heterogeneous diffusion models for the analysis of their evolution. Our aim is to derive some quantitative predictions about the efficiency of various methods dealing with undesired expansion and hence to suggest effective schedules for applying these methods. We shall report some results in this direction.
This talk is focused on a class of bilevel optimization problems, arising from zero-sum Stackelberg games. There are two players, a leader who acts first, and a follower, who decides afterwards. The leader takes interdiction actions to maximize (minimize) the minimum cost (the maximum profit) that the follower can obtain by solving its optimization problem. More precisely, the follower deals with a classical combinatorial optimization problem, while the leader is trying to modify the original input of the problem under some constraints so that the best response of the follower is as bad as possible. There is rich literature in this line of research. We will briefly review the basic settings and previous work, followed by recent results we have achieved in knapsack, network connectivity and maximum coverage.
A proper coloring f of a graph is equitable if the sizes of any two color classes of f differ by at most 1. When k divides n, an equitable k-coloring of an n-vertex graph G corresponds to finding k vertex-disjoint complete (n/k)-vertex subgraphs in the complement of G. Among applications of equitable coloring and similar notions are scheduling in communication systems, construction timetables, mutual exclusion scheduling problem, and round-a-clock scheduling. Results on equitable coloring also have interesting consequences in extremal combinatorics and graph theory, mostly in complementary form. The problem of finding an equitable k-coloring of a graph is NP-complete for every k > 2. The goal of the talk is to survey known results and unsolved problems on equitable coloring and its variations, in particular, on equitable list coloring. We also introduce and discuss equitable DP-coloring of graphs.
The main difficulty of multicriterial optimization is the absence of a unique concept of a solution, which is a result of uncertainty of the initial problem. There exist a number of different concepts of a solution, they are based on a proper preference relations or on transformations of the corresponding vector problem into a scalar optimization problem. The talk describes some relationships between different preference relations such as Pareto and lexicographic preferences, which enable one to create simple iterative methods for finding a solution. Next, relationships between linear convolution and sequential concessions method may enable one to select a suitable Pareto-optimal solution.
The tutorial is dedicated to the memory of my teacher Valery Shevchenko, who instilled in me a love for all mathematics, especially, ILP.
The problem of finding upper and lower bounds for the number of vertices and faces of the convex hull of integer points in a polyhedron is considered. The problem has a history of almost half a century and has been solved from the point of view of obtaining asymptotics only for the number of vertices with a fixed dimension. Recently, an approach to obtaining bounds for the number of edges has been found. A review of these results and methods will be given, and open problems will be formulated.
Spatial graphs are embeddings of graphs in a 3D space with edges realized by curves. Even if a graph has a simple combinatorial structure, it can be embedded in a topologically complicated way. Two spatial graphs are said to be topologically equivalent if one can be moved to the other by a continuous deformation of a space.
Spatial graphs are relevant mathematical objects to describe both combinatorial and topological properties of various 3D systems, from biological to engineering. In particular, for the identification and optimization of spatial topologies in the design of 3D engineering systems.
We will discuss recent results on spatial graphs, their invariants and applications.
We are developing a solver for mixed integer linear programming (MILP) problems. It was recently registered in the Unified Register of Russian Computer Programs and Databases, registry entry No. 27562 of 11.04.2025. The implementation for linear programs includes an interior point method, primal and dual simplex methods, including for large scale problems up to 1,000,000 variables and more. We have also developed a separate LU factorization specifically for our methods. The approach to solving MILP problems is based on a variant of the branch-and-bound method, and includes a specialized pre-solving phase (including symmetry detection), cuts to improve relaxation, and specialized methods for determining integer feasible points such as feasibility pump. The solver is used in practice to solve a more complex variant of the vehicle routing problem with time windows (VRPTW), where the meta-algorithm uses the solver and produces a solution to the problem with very good performance: a problem with 788 orders and 98 couriers in Moscow is solved in less than a minute.
In large scale GTS delivery projects, we usually face systematical optimization, considering many phases and sub-systems. As a rule, the system is heterogeneous, simultaneously including black-box subsystem, large scale MIP subsystem, dynamic programming subsystem and others. We propose several decomposition and multi-level efficient large scale optimization algorithms, which integrated Large Neighborhood Search, Black Box Optimization Methods, Mathematical Programming Techniques to solve these challenging problems.
AI Website Creator