View: session overviewtalk overview

13:00 | Integer Programming Approach to the Data Traffic Paths Recovering Problem PRESENTER: Igor Vasilyev 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 ( |

13:20 | A Matheuristic for the Drilling Rig Routing Problem PRESENTER: Igor Kulachenko 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. |

13:40 | A Simulation-Optimization Model for the Effective Management of Emergency Medical Services PRESENTER: Natalia Shamray 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. |

13:00 | Optimization Problem in the Integral Model of Developing Systems in the Vector Case PRESENTER: Evgeniia Markova 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. |

13:20 | Parabola Method in Combination with Zero-Order Methods 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). |

13:40 | A Double Cuts Method in Concave Programming PRESENTER: Oleg Khamisov 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. |

14:00 | Locating Facilities Under Deliberate Disruptive Attacks PRESENTER: Anton Ushakov 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 |

14:20 | Improving Effectiveness of Neighborhood-Based Algorithms for Optimization of Costly Pseudo-Boolean Black-Box Functions PRESENTER: Oleg Zaikin 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. |

14:00 | Nonlinear Models of Convergence 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. |

14:20 | About Some Properties of a Feasible Set of Optimal Ecosystems Exploitation Problem for Nonlinear Binary Leslie Model PRESENTER: Alexander Smirnov 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. |

14:40 | The Inverse Problem of Stress Testing the Credit Organizations PRESENTER: Ellina Emelyanova 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. |

14:00 | Exact Algorithm for the One-Dimensional Quadratic Euclidean Cardinality-Weighted 2-Clustering Problem PRESENTER: Anna Panasenko 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. |

14:20 | A 0.3622-Approximation Algoritm for the Maximum K-Edge-Colored Clustering Problem PRESENTER: Alexander Ageev ABSTRACT. In the Max |

14:40 | An Approximation Algorithm for a Semi-Supervised Graph Clustering Problem PRESENTER: Alexander Morshinin 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 ( The problem is NP-hard for any fixed k. For |

17:00 | On the Polytope of Schedules of Servicing Time of Identical Claims by Parallel Devices PRESENTER: Ruslan Simanchev 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. |

17:20 | The Pareto Set Reduction in Bicriteria Discrete Problems PRESENTER: Aleksey Zakharov 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. |

17:40 | New Properties of Δ-Modular Simlicies PRESENTER: Dmitriy Gribanov 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. |

18:00 | How to Find the Convex Hull of All Integer Points in a Polyhedron? PRESENTER: Sergey Semenov 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. |

17:00 | A Pollution Control Problem for the Aluminum Production in Eastern Siberia: Differential Game Approach PRESENTER: Ekaterina Gromova 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). |

17:20 | On a One-Dimensional Differential Game with a Non-Convex Terminal Payoff PRESENTER: Igor' Izmest'Ev 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). |

17:40 | On Iterative Methods for Searching Equilibrium in Pure Exchange Economy with Multiplicative Utilities of Its Agents 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. |

18:00 | Weak Berge Equilibrium PRESENTER: Konstantin Kudryavtsev 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. |