ABSTRACT. In this paper, we propose a novel approach to recovering path relationships in communication networks. The path relationship is one of the key input data which is necessary for network operation and maintenance. We have a continuous network transformation, upgrades, expansions, service allocations, thus the network physical topology and paths relationship are permanently changing with high frequency. Our approach is aimed at recovering the path relationships through flow information of each arc in the network. Getting the flow information is not a big technical problem and its control is included in the basic toolbox for network monitoring. We consider two scenarios which lead us to integer linear programs. The both of them minimize the flow deviation, where in the first one we look for a directed spanning tree (r-arborescence) and, in the second one --- more general origin/destination paths (OD-paths). We propose mixed integer linear programming formulations for both problems. Their feature is that they contain the non-polynomial number of constraints which are considered implicitly by the cutting planes approach. The preliminary computation results showed that the large-scale instances of the first scenario can easily be solved. At the same time, the optimal solutions of second scenario problems can be found only on small- and medium-size instances, which inspires for the further research.

ABSTRACT. In this paper, we discuss the real-world Split Delivery Vehicle Routing Problem with Time Windows (SDVRPTW) for drilling rig routing in Siberia and the Far East. There is a set of objects (exploration sites) that require well-drilling work. Each object includes a known number of planned wells and must be served within a given time interval. Several drilling rigs can operate at the same object simultaneously, but their number must not exceed the number of wells planned for this object. A rig that has started work on a well completes it to the end. The objective is to determine a set of rig routes (including the numbers of assigned wells) to perform all well-drilling requests respecting the time windows that minimizes the total traveling distance. The main difference with traditional SDVRP is that it is the service time that is split, not the demand.

We propose a mixed-integer linear programming (MILP) model for this problem. To find high-quality solutions, we design the Variable Neighborhood Search (VNS) matheuristic. Exact methods are incorporated within a local search to optimize the distribution of well work among the rigs. Time-window constraints are relaxed, allowing infeasible solutions during the search, and evaluation techniques are applied to treat them. Results of computational experiments for the algorithm and a state-of-the-art MILP solver are discussed.

ABSTRACT. We propose a simulation-optimization model for the effective management of emergency medical services (EMS). As the control actions we consider 1) ambulance fleet allocation among existence base stations; 2) various scenarios of assignment of ambulance crews to medical requests. The management quality is assessed by the average time of arrival of ambulances to clients. The assignment scenarios are realized in the simulation part of the model and take into account the changing of request's intensity and network's congestion during the day. We propose the genetic algorithm with a local search to determine the best allocation of ambulances among base stations. We conduct a lot of numerical experiments base on which we form common recommendations for the effective management of EMS.

ABSTRACT. We consider an integral model of developing systems consisting of elements of n age groups. Herewith, system elements are divided into m types depending on their technical characteristics. The mathematical model is presented by a system of Volterra type integral equations with variable integration limits. We consider the developing system since the moment of system origin, so there is no prehistory and for t = 0 all the age groups of the elements are empty. The work continues research carried out for developing systems with prehistory. This vector model is used to describe the development of a large electric power system, in which the equipment of power plants is divided into groups by the types of energy resources, and the stations of each type are divided into age groups by efficiency factors. Based on this model, we set the problem of optimizing the parameters controlling the decommissioning of equipment. The optimization problem is nonlinear because the control parameter is in the lower limits of integration in the objective functional as well as in restrictions. Also, there are restrictions on the phase variable. To solve the problem, we use an algorithm based on the discretization of all the elements of the system. The results of numerical calculations are presented.

ABSTRACT. We consider the parabola method for solving univariate optimization problems. For multivariate problems we use this method as a line search procedure in combination with well known zero-order methods such as coordinate descent method, Hooke and Jeeves method and Rosenbrock method. Comprehensive numerical comparison among obtained versions of zero-order methods is given in the present work. The set of test problems includes nonconvex functions with large amount of local and global optimum points. Zero-order methods combined with parabola method demonstrate high performance and quite frequently find the global optimum even for large problems (up to 100 variables).

ABSTRACT. We consider the problem of global minimization of smooth concave function over a bounded polyhedral set. Two types of cutting planes are used. The first one is the so called second order cutting planes - a modification of the well-known Tuy's cuts proposed by V.P. Bulatov. The second type is concave cuts based on the concave extension proposed by O.V. Khamisov. The second order cuts are performed in n-dimensional space, concave extebsion cuts are constructed in (n+1)-dimensional space. Different geometry of the cuts provides faster convergence to a global minimum. The suggested approach is not a branch-and-bound approach, so we do not have here a branching process. The elaborated method is a cutting plane procedure, though with a quite sofisticated procedure of constructing the cutting planes. Results of the computational testing are given.

ABSTRACT. Facility disruptions or failures may occur due to natural disasters or a deliberate man-made attack. Such an attack is known as interdiction. Recently, facility location problems, addressing intentional strikes against operating facilities and strategies to reduce their impact, have received particular attention. In this paper, we present a new location-interdiction median problem aimed at designing a distribution network which is robust to the worst-case, long-term facility losses. We suppose that there are two players: defender (system designer) and attacker. The defender decides where to locate facilities to minimize the overall cost of supplying the demands of customers. The attacker determines which r facilities to interdict to maximize the cost of serving the customers from the remaining operational facilities. Note that we suppose that the facilities are attacked simultaneously and interdicted facilities become unavailable. We propose bilevel and single-level integer formulations of this problem. For a particular case when the attacker hits a single facility, we develop a fast local search procedure based on implicit enumeration of interdiction strategies. We test our approaches in a series of computational experiments on well-known test problems.

ABSTRACT. Optimization of costly black-box functions is hard. Not only we know next to nothing about their nature, we need to calculate their values in as small number of points as possible. The problem is even more pronounced for pseudo-Boolean black-box functions since it is harder to approximate them. For such functions the local search methods where a neighborhood of a point must be traversed are in a particular disadvantage compared to evolutionary strategies. In the paper we propose several heuristics that make use of the search history to avoid already processed points and prioritize the more promising points from a neighborhood to be processed first. In the experiments involving minimization of an extremely costly pseudo-Boolean black-box function we show that the proposed heuristics significantly improve the performance of a hill climbing algorithm, making it outperform (1+1)-EA with an additional benefit of being more stable.

ABSTRACT. A sufficient issue in studies of economic development is whether economies (countries, regions of a country, etc.) converge to one another in terms of per capita income. There are a number of methodologies to test the convergence hypothesis. The most widespread one is the so-called beta-convergence, implying a negative cross-section correlation between initial per capita income and growth. An alternative methodology is the distribution dynamics analysis that explores the evolution of cross-economy income distribution. Both approaches provide only an aggregated characterization of convergence; it is impossible to reveal among converging economies those with a deviant behavior (e.g., diverging or randomly walking). Methodologies based on time-series analysis make it possible to overcome this problem. They consider time series of the income gap, i.e., the difference of per capita incomes in a pair of economies (one element of the pair can be an aggregate, e.g., the national economy if economies under consideration are country’s regions). One of such methodologies consists in testing the income gaps for stationarity. However, this approach cannot reveal the case of catching-up. In a more general method, time series of income gap are modeled by power-series trends. I find that such a method can yield wrong results because of the overly general representation of the trend. For instance, this is the case when the path of the income gap has a U-shape form with its right end lower than the left end. This paper puts forward an alternative approach, namely, modeling the convergence process by nonlinear asymptotically subsiding trends. A few specific forms of such trends are proposed: log-exponential trend, exponential trend, and fractional trend. A pair of economies is deemed converging if their income gap is stationary about of these trends. To test for stationarity, standard unit root test are applied with non-standard test statistics that are estimated for each kind of the trends. The paper provides examples of empirical application of the proposed method.

ABSTRACT. Previously, the authors proposed a formalization of renewable resources rational use problem based on the representation of an operated system as a discrete dynamic system. In the case of structured ecosystem described by nonlinear binary Leslie's model (binary model has an additional criterion for population structuring in addition to age or developmental stage), despite its non-linearity, it turned out that all optimal controls preserving this system belong to a certain hyperplane. As a development of these results, we obtained the conditions under which the positive boundary of a feasible set with so-called quasi-preserving controls also contain part of some hyperplane. In the process, we used a generalization of classical concept of map irreducibility - the concept of local irreducibility. Statements about the influence of the irreducibility property of discrete dynamical system step operator on the properties of feasible set positive boundary for the optimal exploitation problem under consideration are proved. It is shown that the reducibility of step operator leads to the existence on the positive boundary of controls with partial dominance. In addition, the reducibility of step operator leads to linearity some zone of positive boundary, despite the non-linearity of the step operator. The results obtained make it possible to assess the applicability of the proposed formalization in the specific ecological populations exploitation problems.

ABSTRACT. The procedure for reverse stress testing of credit institutions is considered. In this case, the specifiedfinancial result is selected as the objective function. The stress conditions leading to such a financial result shouldbe determined. The areas of possible application and the concept of implementing reverse stress testing areformulated. The implementation of the macroeconomic reverse stress scenario is discussed, including theformulation of the corresponding mathematical problems. The stages of constructing the inverse stress scenarioleading to a given financial effect are formulated. An example of defining a stress scenario for reverse stresstesting and possible options for implementing the found stress scenario with zero specified financial effect isgiven. Possible directions for further development of the proposed approach are formulated.

ABSTRACT. We consider a strongly NP-hard problem of clustering a finite set of points in Euclidean space into two clusters. In this problem, we find a partition of the input set minimizing the sum over both clusters of the weighted intracluster sums of the squared distances between the elements of the clusters and their centers. The weight factors are the cardinalities of the corresponding clusters and the centers are defined as follows. The center of the first cluster is unknown and determined as the centroid, while the center of the other one is given as input (is the origin without loss of generality). In this paper, we present a polynomial-time exact algorithm for the one-dimensional case of the problem.

ABSTRACT. In the Max k-Colored Clustering Problem we are given an undirected graph G = (V,E). Each edge e of G has a nonnegative weight w(e) and a color c(e)∈C = {1, 2, ..., k}. It is required to assign a color from C to each vertex of G so as to maximize the total weight of edges whose both endpoints have the same color as the color of the edge. Angel et al. show that the problem is strongly NP-hard and present a randomized constant-factor approximation algorithm for solving it. The approximation bound was improved by Ageev and Kononov and Alhamdan and Kononov. We present a modification of the algorithm by Alhamdan and Kononov, which improves on its approximation bound (0.36 instead 0.34).

ABSTRACT. Clustering problems form an important section of data analysis. In these problems one has to partition a given set of objects into several subsets (clusters) basing only on similarity of the objects. In machine learning clustering problems are usually classified as unsupervised learning. Semi-supervised clustering problems are also considered. In these problems some objects are pre-clustered.

We consider the most visual formalization of a version of semi-supervised clustering. It is a special case of a graph clustering problem. In this problem one has to partition a given set of n objects into k clusters (k < n). A collection of k pairwise disjoint nonempty subsets of objects is fixed. No two objects from different subsets of this collection must belong to the same cluster and all objects from any subset must belong to the same cluster. Similarity of objects is determined by an undirected graph. Vertices of this graph are in one-to-one correspondence with objects, and edges connect similar objects. One has to partition the vertices of the graph into pairwise disjoint groups (clusters) minimizing the number of edges between clusters and the number of missing edges inside clusters.

The problem is NP-hard for any fixed k. For k = 2 we present a polynomial time approximation algorithm and prove a performance guarantee of this algorithm.  

ABSTRACT. Graphs invariants have proven to be one of the most important and fruitful concepts in modern Combinatorics and Theoretical Computer Science. Besides being a fascinating study subject for their own sake, they play an important role in the famous graph isomorphism problem. Their success serves as a natural motivation for the following natural question: what are the graph properties that can be deduced from a certain graph invariant? In this talk we will give an overview and will report on recent results concerning two graph invariants: the status sequence of a graph and the graph spectrum.

ABSTRACT. The problem of determining the minimum total service time for identical requirements by parallel devices is considered. A partial order between the requirements is established. The partial order determines the priority in the service. Time is discrete, interrupts are prohibited. With a fixed number of devices, the complexity status of the problem is not known today. Under certain conditions on a priori given directive service time the affine hull of the polytope of the problem is found. The structure of the faces of the polytope is discussed.

ABSTRACT. We consider bicriteria discrete problems in the context of the axiomatic approach of the Pareto set reduction. The degree of the reduction is investigated for various values of the compromise coefficient in the case of one or two elementary information quanta. We construct families of instances with special structures of the Pareto set for such bicriteria problems as set covering problem, customer order scheduling problem and generalized traveling salesman problem. The Pareto set reduction is analyzed for the proposed instances.

ABSTRACT. In this work we show that there are only polynomially many Δ-modular empty lattice simplicies up to the unimodular equivalence relation. Additionally, using classical results of R. Gomory, we give bounds on distance between optimal IP and LP solutions and sparsity level of solutions for simplicies, and some more general classes of polyhedrons. As a special case it affects some variants of knapsack problem polyhedron.

ABSTRACT. We propose a cut-based algorithm for finding all vertices and all facets of the convex hull of all integer points of a polyhedron defined by a system of linear inequalities. Our algorithm DDM Cuts is based on the Gomory cuts and the dynamic version of the double description method. We describe the computer implementation of the algorithm and present the results of computational experiments comparing our algorithm with naive one.

ABSTRACT. In this paper, we apply differential game theory to analyze the problem of pollution control in Eastern Siberia. In doing so, we consider the real data for 2016-2018 years obtained from statistical and accounting reports. The obtained result shows that the cooperation among the major pollutants can be beneficial both for the environment and the companies, especially for those with high levels of pollution.

Air pollution is a major environmental problem that affects everyone in the world. Emissions from large industrial enterprises have a great adverse impact on the environment and the people's quality of life including a climate change. Game theory offers a powerful tool for modeling and analyzing situations where multiple players pursue different but not necessarily opposite goals. In particular, it is well suited for analyzing the ecological management problems in which players (countries, plants) produce some goods while bearing costs due to the emitted pollution). It should be noted that most results on pollution control are aimed at studying transboundary pollution. One particular problem associated with this line of research is that it is difficult to obtain realistic numerical values of the model parameters. Thus, the results turn out to be of more theoretical nature.

In contrast to the mentioned approach we consider local situations that can be modeled with more precision. Furthermore, we hope that the obtained results can be of use when planning local policies aimed at decreasing pollution load in particular regions. Recently, there has been a paper devoted to the pollution control problem of the Irkutsk region of the Russian Federation based on data for 2011, [Tur, Gromova, 2018]. Our contribution extends the results presented in the mentioned paper, moreover, the ecological situation in three cities of Eastern Siberia is considered based on data for 2016.

The active development of industry in cities in Eastern Siberia inevitably leads to environmental problems in the region. Industrial enterprises, consuming a huge amount of natural resources, are powerful sources of pollution. Air pollution is one of the most acute environmental problems in the district, moreover, the bulk of the population lives in areas where concentration of pollutants in the air regularly exceeds the maximum permissible levels. So, over the past few years, Krasnoyarsk, Bratsk, and Shelekhov have become one of those which are in the list of Russian cities with the highest level of air pollution. It is due to the fact that such aluminum plants as Krasnoyarsk, Bratsk, and Irkutsk Aluminum Smelters are located in these cities. We were able to identify all the related parameters on the base of official documents and analyze a realistic model of considered situation.

We describe a problem of the pollution control in the form of linear-quadratic differential game. The Nash equilibrium is found in an open-loop form. Also the cooperative form of the game is considered. The cooperative solution is calculated as the Shapley value. All calculations are based on the real data.

The research was funded by RFBR under the research project 18-00-00727 (18-00-00725).

ABSTRACT. A one-dimensional differential game is considered, in which the payoff is determined by the module of the deviation of the phase variable at a fixed time from the set value, taking into account the periodicity. The first player seeks to minimize the payoff. The goal of the second player is the opposite. For this problem, the price of the game is calculated and optimal player controls are constructed. As an example, we consider the problem of controlling a rotational mechanical system in which the goal of the first player acquires the meaning of minimizing the module of deviation of the angle from the desired state.

This work was funded by the Russian Science Foundation (project no. 19-11-00105).

ABSTRACT. We consider the classical Arrow--Debreu model for a pure exchange economy with multiplicative utilities of its agents. To calculate its equilibrium prices, we present a new iterative algorithm which simulates the simplest intuitive forms of the economic behavior of market agents and converge under very weak assumptions. The algorithm relies on increasing prices for scarce products only. Moderate inflation, accompanying the computational process, plays a positive role in establishing an equilibrium between commodity supply and demand. Schemes have a meaningful economic interpretation. The convergence theorems are proved, and the results of numerical experiments are presented.

ABSTRACT. The paper proposes the concept of a weak Berge equilibrium. Unlike the Berge equilibrium, the moral basis of this equilibrium is the Hippocratic Oath ”First do no harm”. On the other hand, all Berge equilibria are some weak Berge equilibria. The properties of the weak Berge equilibrium have been investigated. The existence of weak Berge equilibrium in mixed strategies has been established for finite games. As example, a Weak Berge equilibria for finite three-person non-cooperative games were computed.

ABSTRACT. This is a survey of recent developments in the computational knot theory. We start with retrospective of well-known results and techniques bringing topological knot theory and graph theory together: knots equivalence, Reidemeister moves, knot diagrams and knot polynomials. Then, we briefly address the complexity of the unknotting problem. We illustrate the difficulty of unknotting on small and insightful examples of knots. The easy unknotting cases, e.g., knot diagrams of treewidth 2, are addressed in details. We wrap up the tutorial posing numerous open questions and introducing new research directions.

ABSTRACT. Applications of convex optimization in machine learning include support vector machines, polyhedral classifiers, deduction of disjunctive and conjunctive normal forms, time-series clustering, image segmentation, different models based on information theory, e.g., those involving Shannon entropy and Kullback-Leibler divergence. Virtually the whole spectrum of standard methods of convex optimization such as the gradient descent, the Frank-Wolfe algorithm, and interior-point methods is used for training deep neural networks. At the same time, some new results in the area of linear programming and convex optimization indicate that there are methodologies beyond the classical approaches which can lead to substantially more efficient machine learning algorithms and better interpretable machine learning models. So in this lecture we will address recent developments in convex optimization and convex analysis, in particular in the context of machine learning.

ABSTRACT. Finding long cycles in graphs is an NP-hard problem. Cycles in hypergraphs can be defined in several natural ways. Since finding long cycles in hypergraphs is hard for all kinds of cycles, it makes sense to consider approximate algorithms and extremal problems on long cycles in hypergraphs. We discuss several such extremal problems, recent progress on them and possible algorithms based on the proofs.