View: session overviewtalk overview
Session manager Pavel Sorokovikov
10:00  Solving smooth minmin and minmax problems by mixed oracle algorithms PRESENTER: Egor Gladin ABSTRACT. In this paper, we consider two types of problems that have some similarity in their structure, namely, minmin problems and minmax saddlepoint problems. Our approach is based on considering the outer minimization problem as a minimization problem with an inexact oracle. This inexact oracle is calculated via the inexact solution of the inner problem, which is either minimization or a maximization problem. Our main assumptions are that the problem is smooth and the available oracle is mixed: it is only possible to evaluate the gradient w.r.t. the outer block of variables which corresponds to the outer minimization problem, whereas for the inner problem only zerothorder oracle is available. To solve the inner problem we use accelerated gradientfree method with zerothorder oracle. To solve the outer problem we use either an inexact variant of Vaydya's cuttingplane method or a variant of accelerated gradient method. As a result, we propose a framework that leads to nonasymptotic complexity bounds for both minmin and minmax problems. Moreover, we estimate separately the number of first and zerothorder oracle calls which are sufficient to reach any desired accuracy. 
10:20  Nonconvex optimization in digital predistortortion of signal PRESENTER: Aleksandr Maslovskiy ABSTRACT. In this paper we give some observation of applying modern optimization methods for functionals describing digital predistortion (DPD) of signals with orthogonal frequency division multiplexing (OFDM) modulation. The DPD functionals modeling the behavior of power amplifier are based on A VinnerHammerstain model. To achieve better DPD performance we consider state of the art optimization methods and strategies, which are used to optimize modern neural networks: various start initializations, which allow to get more global optimization minimum; different modern methods, which are applied for optimization of nonconvex functions (Neural Networks); different methodologies/techniques of learning rate changing, which allow to change optimization step and get highperformance of DPD model. To obtain the results of this research, we use different DPD functions and signals with OFDM modulation. To compare the performance of functions we use Normalized mean squared error (NMSE) as a criterion of checking results. Through this study, we selected best optimization methods, strategies of learning rate changing and start initialization, which increase the performance of the investigated models. 
10:40  Modification of the intersectoral balance method PRESENTER: Anastasiya Rassokha ABSTRACT. The intersectoral balance method is a tool for mediumterm economic analysis. It is used to identify industries that act as drivers of economic growth, to analyze the mechanisms of shock propagation, and to assess the consequences of economic sanctions. The classical version of the method, based on the model of W. Leontief, is built on the hypothesis of the constancy of the norms of output costs. Since the 90ies of XX century, the changing nature of economic growth, globalization of the world economy, priority development of the service sector have adversely affected the implementation of the basic hypothesis Leontief models and have stimulated the development of models that account for substitution of production factors. The paper develops a mathematical apparatus for mediumterm analysis based on models of interindustry balance with production functions from the class of functions with constant elasticity of substitution (CES). The developed approach is based on the use of the Yang transform to construct a dual convex programming problem for calculating Lagrange multipliers to interindustry balance ratios that model price indices for industry products. The paper also sets the task of model identification. The method is tested on the Russian statistical data. 
11:00  Choice of Optimal Order when Merging DifferentType Aircraft Flows as Mixed Integer Programming Problem PRESENTER: Arseniy Spiridonov ABSTRACT. In the paper, the problem of aircraft flows merging is considered, which arises at the point of joining two or more air routes. It is assumed that the aircraft may be of different types. This results in their different parameters: safety interval between them, different intervals for varying the arrival instants, different costs for maneuvering, etc. The problem has two subtasks: the choice of the optimal order of the aircraft in the gathered queue and the assignment of the optimal arrival instants for the chosen order. Both subtasks are solved simultaneously by means of mixedinteger programming methods. Numerical simulation results are given for model examples. 
Session manager Maxim Zharkov
10:00  Approximation Algorithms for TwoBar Charts Packing Problem. Theory PRESENTER: Stepan Nazarenko ABSTRACT. In TwoBar Charts Packing Problem, it is necessary to pack the set of bar charts consisting of two bars each into the unitheight strip of minimal length. When packing, it is allowed to move bars vertically within the strip, but it is forbidden to change the order and separate the chart's bars. Earlier, for this problem, which is a generalization of the Bin Packing Problem, several approximation algorithms with guaranteed estimates were proposed. However, these algorithms build a nearoptimal solution. This fact inspired us to conduct a numerical experiment in which the approximate solutions are compared to each other and with the optimal one. We build the optimal solution by the CPLEX package by solving the BLP, which we have proposed in our previous papers. The results of the simulation make up the content of this paper. 
10:20  Approximation Algorithms for TwoBar Charts Packing Problem. Simulation PRESENTER: Gregory Melidi ABSTRACT. In TwoBar Charts Packing Problem, it is necessary to pack the set of bar charts consisting of two bars each into the unitheight strip of minimal length. When packing, it is allowed to move bars vertically within the strip, but it is forbidden to change the order and separate the chart's bars. Earlier, for this problem, which is a generalization of the Bin Packing Problem, several approximation algorithms with guaranteed estimates were proposed. However, these algorithms build a nearoptimal solution. This fact inspired us to conduct a numerical experiment in which the approximate solutions are compared to each other and with the optimal one. We build the optimal solution by the CPLEX package by solving the BLP, which we have proposed in our previous papers. The results of the simulation make up the content of this paper. 
10:40  Analysis of optimal solutions to the problem of a single machine with preemption PRESENTER: Servakh Vladimir ABSTRACT. The problem of single machine with equal length of jobs and the preemption is considered. The optimization criterion is the weighted average time completion of jobs. The properties of the problem are investigated. An algorithm for constructing a finite set of schedules containing an optimal solution is proposed. 
11:00  Selfadjusting genetic algorithm with greedy agglomerative crossover for continuous pmedian problems PRESENTER: Lev Kazakovtsev ABSTRACT. The continuous pmedian problem is a classical global optimization model used both for finding optimal locations of facilities on a plane, and as a clustering model. The problem is to find p points (medians) such that the sum of the distances from known demand points to the nearest median is minimal. Such a clustering model is less sensitive to "outliers" (separately located demand points that are not included in any cluster), compared with models such as kmeans. This feature is important for such clustering problems as groupping highlyreliable electronic devices into homogeneous production batches. Many heuristic approaches were proposed for this NPhard problem. The genetic algorithms with a greedy agglomerative crossover operator are some of the most accurate heuristic methods. However, such a crossover operator is computationally expensive which limits its applicability for largescale problems. A parameter of this operator (parameter r) determinates the efficiency of the whole genetic algorithm. Moreover, the optimal value of this parameter is hardly predictable based on numerical parameters of the problem such as the numbers of demand points and medians. We investigate its influence on the result of the algorithm, and also propose a simple procedure for adjusting the algorithm parameter. The advantages of the selfadjusting algorithm are shown for problems with a data volume of up to 2,000,000 objects. 
Session manager Stepan Sorokin
10:00  The problem of optimizing the supply route and choosing the location of gas treatment units PRESENTER: Lyudmila Som ABSTRACT. We consider the following problem of a gas production company. There is a gasbearing region with natural gas fields. The produced gas must be delivered to the main pipelines by laying a network of pipelines from fields to main pipelines (supply route). Before the gas enters the main pipeline, it must be processed in a gas treatment unit. Gas treatment units have to be located in some fields. The goal is to minimize the total cost of laying pipelines and placing gas treatment units. We propose a mathematical model of this problem in the form of a mixedinteger linear programming problem. Based on this mathematical model, we present the results of the free solver PULP on real data from a wellknown gas company. Also, we present a hybrid metaheuristic algorithm based on the local search, variable neighborhood search, and greedy algorithm. The main idea of the hybrid algorithm is the separation of gas processing and supply. First of all, we define the gas processing locations. Then we build the supply tree. The use of metaheuristics can significantly reduce the complexity of each stage. The study was carried out within the framework of the state contract of the Sobolev Institute of Mathematics (project no. 031420190014) 
10:20  Dixit–Stiglitz–Krugman Model with Investments in R&D ABSTRACT. We study a monopolistic competition model in the open economy case. The utility of consumers is additively separable. The producers can choose the technology (R&D) endogenously. We examine the local comparative statics of market equilibrium with respect to transport cots (of iceberg type). Early, we find the following preliminary result: increasing transport cost has opposite impacts on the mass of firms and productivity. In the present paper, we study, mainly, the local comparative statics w.r.t. transport costs for the case of autarky (the very big transport costs). For the case of linear production costs, the known (and counterintuitive!) result is that the social welfare increases near autarky. We generalize this result for the model with investments in R&D, this is the main result of the paper. 
10:40  Monopolistic Competition Model: the Case of International Trade between Several Countries PRESENTER: Igor Bykadorov ABSTRACT. We study the market equilibrium in international trade monopolistic competition model a'la DixitStiglitzKrugman with homogeneous firms. The utility of consumers is additively separable. The only production factor is labor. The concrete functional form of subutility function is assumed unknown. Thus, it is not possible to get the equilibrium in closed form. Earlier, for the case of international trade between two countries, we examined the local symmetric comparative statics of equilibrium variables with respect to transport costs of iceberg type. In the present paper, we develop the previous results in the case of international trade between more than two countries. The main attention we pay to the cases of free trade (the very small transport costs) and autarky (the very big transport costs). For autarky, we consider the different cases of preautarky. 
11:00  Retailing in Monopolistic Competition Model with Entrance Fee PRESENTER: Igor Bykadorov ABSTRACT. We study the monopolistic competition models a'la DixitStiglitz with vertical market interaction of several manufacturers, a retailer, and consumers. The utility is OttavianoTabuchiThisse type. The cost functions of manufacturers and of retailers are linear. Earlier we provided Stackelberg equilibrium under the leadership of retailer; study the consequences, on social welfare and the consumer surplus. In the present paper, we develop the model by introducing the entrance fee for manufacturers.

Session manager Pavel Sorokovikov
11:40  Weakly supervised learning using manifold regularization and lowrank matrix representation PRESENTER: Vladimir Berikov ABSTRACT. We solve a weakly supervised regression problem. Under ''weakly" we understand that for some training points the labels are known, for some unknown and for others uncertain due to presence of random noise or other reasons such as lack of resources. The solution process requires to optimize a certain objective function (the loss function), which combines manifold regularization and lowrank matrix decomposition techniques. These lowrank approximations allow us to speed up all matrix calculations and reduce storage requirements. This is especially crucial for large datasets. Ensemble clustering is used for obtaining the coassociation matrix which we consider as the similarity matrix. Utilization of these techniques allows us to increase the quality and stability of the solution. In the numerical section, we study the proposed method on artificial data sets using MonteCarlo modeling. 
12:00  Machine Learning Algorithms of Relaxation Subgradient Method with Space Extension PRESENTER: Lev Kazakovtsev ABSTRACT. In relaxation subgradient minimization methods, a descent direction is constructed based on information about the subgradients obtained at the iteration. This direction forms an obtuse angle with all subgradients in the neighborhood of the current minimum, and minimization along this direction allows us to go beyond this neighborhood and eliminate the method looping effects. Algorithms of this type have a broad practical use due to their fast convergence and the ability to minimize nonconvex functions, for example, when estimating the parameters of mathematical models with nonsmooth regularization. The idea of optimizing the space extension parameter choice in accordance with the current state of the search can be applied to create new algorithms. We formulate the problem of the descent direction search as a problem of solving systems of inequalities, and propose an algorithm with space extension for solving them. This algorithm is close to the iterative least squares method. With relatively low computational costs per iteration, the proposed algorithm has a high convergence rate and is efficient in the absence of convexity and smoothness. Therefore, in terms of applicability and computational efficiency, it complements the wellknown minimization methods based on quadratic or piecewise linear models. In addition, we present an example of the implementation of such an algorithm, which confirms the effectiveness of theoretical constructions. Theoretical analysis of the learning algorithm with space extension allowed us to identify the components of the algorithm and replace them, which enables us, depending on the situation, to use increased values of the extension parameter. On this basis, a theoretically new learning method with space extension and the corresponding subgradient method for solving problems of minimizing nonsmooth functions were developed and substantiated. Our computational experiment confirms the efficiency of the proposed relaxation subgradient method. 
12:20  Kmeans clustering via a nonconvex optimization approach PRESENTER: Anton Ushakov ABSTRACT. Clustering is one of the basic tasks in machine learning and data mining. Euclidean minimumsumofsquares clustering problem is probably the most common clustering model. It consists in finding $k$ cluster centers or representatives so as the sum of squared Euclidean distances from a set of points and their closest centers is minimized. The problem is known to be nonconvex and NPhard even in the planner case. In this paper, we propose a new DC programming approach to the problem. First, we cast the original nonconvex problem as a continuous optimization problem with the objective function represented as a DC function. We then devise a solution algorithm, resting upon the global optimality conditions and global search scheme for DC minimization problems proposed by A.S. Strekalovsky. We implement the developed algorithm and compare it with kmeans clustering algorithms on generated datasets. 
12:40  Computational techniques for investigating lowpotential Gupta clusters of extremely large dimensions PRESENTER: Pavel Sorokovikov ABSTRACT. The paper considers the problem of finding lowenergy metallic Gupta clusters, which reduces to the global minimization of the multiextremal potential function. We propose algorithms and computational techniques for the study of these atomicmolecular clusters. Problems with a small, a medium, and a large number of atoms are investigated to check the performance of the developed methods. System computational experiments were performed to search for a global minimum in the Gupta model of extremely large dimensions (from 126 to 156 atoms). The authors are not aware of other works in which the results of computations for clusters of the specified number of atoms are given. 
13:00  On one variant of (1+1)Evolutionary Algorithm using merging variables PRESENTER: Alexander Semenov ABSTRACT. In this paper we describe a new evolutionary strategy. It is based on the common (1+1) random mutation scheme which was augmented with metaheuristic technique named merging variables principle, that was proposed by us in previous works. We show that the new variant of (1+1)EA has asymptotically lower worst case estimation than the original (1+1)EA. In the experimental part we conduct comparison of the proposed strategy with several known variants of (1+1)EA and demonstrate its practical applicability on several hard variants of MaxSAT problem. 
Session manager Maxim Zharkov
11:40  On the robust capacitated facility location and design problem with elastic demand PRESENTER: Tatyana Levanova ABSTRACT. In the capacitated facility location and design problem with elastic demand a new Company planes to open service facilities. The Company fights with a Competitor for a serviced share of all customer demand. This share varies elastically depending on the location and design of the facilities being opened. In this formulation, customer demand is known and assumed to be unchanged. However, in realworld situations, when planning for a certain period of time, the demand changes, and instead of exact values, its estimates can be given. Therefore, robust placement problems have appeared that take this fact into account. In this paper, we formulate a new robust model of the capacitated facility location and design problem with elastic demand. A problemspecified version of the annealing simulation algorithm is developed. To organize the search for a solution, new types of neighborhoods are constructed. The results of computational experiments are performed. 
12:00  Threshold robustness in the drilling rig routing problem PRESENTER: Igor Kulachenko ABSTRACT. We consider the realworld Drilling Rig Routing Problem (DRRP) in an uncertain environment. There is a set of objects that are exploration sites requiring welldrilling work. Each object includes a known number of wells that need to be drilled within a given time interval, and it is allowed to partition the set of wells so that several drilling rigs perform the required work. In the real world, unforeseen circumstances can affect drilling time, and that, if disregarded, can lead to a disruption of the work plan. Thus, in this problem, we maximize the error in the drilling time estimates when there is still a set of routes and schedules for a fleet of drilling rigs to perform all welldrilling requests in time with total traveling costs no more than a given threshold. It is a socalled threshold robustness approach. In this research, we propose an integer linear programming model for the DRRP with uncertainties and a method based on Adaptive Large Neighborhood Search (ALNS). Computational results for our algorithm and a stateoftheart MILP solver are presented. 
12:20  Mimimizing Total Completion Time in Multiprocessor Job Systems with Energy Constraint PRESENTER: Yulia Kovalenko ABSTRACT. We consider the problem of scheduling multiprocessor jobs to minimize the total completion time under the given energy budget. Each multiprocessor job requires more than one processor at the same moment of time. Processors may operate at variable speeds. Running a job at a slower speed is more energy efficient, however it takes longer time and affects the performance. The complexity of both parallel and dedicated versions of the problem is investigated. We propose approximation and exact algorithms for various particular cases. In our algorithms, initially a sequence of jobs and their processing times are calculated and then a feasible solution is constructed using listtype scheduling rule. 
12:40  Local search heuristic for the parallel machine scheduling with transport robots PRESENTER: Alexander Yuskov ABSTRACT. We consider a new scheduling problem originated from the order picking at an automatic warehouse. We have a finite set of orders. Each order consists of a set of items. All items are stored in pallets at the automatic flat warehouse. Each order should process through the picking station where items are extracted from pallets and packing in a box. We have some parallel picking machines and some parking places for pallets. Each machine can use all pallets at the parking places at the same time. Each pallet should be bringing from the automatic warehouse to the picking station and return back by a transport robot. The number of robots is limited. Our goal is to minimize makespan. We design a local search heuristic to tackle the problem. Feasible solutions are coded by a permutation of items. The decoder procedure creates a corresponding active schedule for parallel machines taking into account the limited number of transport robots. Computational experiments for real data of a big electronic device warehouse indicate the high efficiency of the approach. 
13:00  Exact algorithms for the threelevel pricing problem and its generalization PRESENTER: Lyudmila Som ABSTRACT. Stackelberg's game of three players is considered. There are the leader company, the follower company, and their clients. First, the leader sets own price for his facilities, then the follower chooses the optimal price for products for his facilities, taking into account the leader's choice. After that, each client chooses where to purchase a unit of goods in such a way that their transport and purchase costs are minimal. The product is purchased only if the client's budget allows it. The goal of the game is to find the price vector at which the leader's income will be the maximum. Two problem statements are considered: when mill pricing is at the first level, uniform pricing is at the second level, and vice versa. In the levels with mill pricing, the choice of the optimal facility location of enterprises has been added. The problems under consideration are a generalization of the problems discussed earlier ([1], [2]). To solve the generalized case, it is proposed to extend the existing exact algorithms that have proved to be the best for these problems. The algorithm is based on decomposition for the problem with uniform pricing for the leader and mill pricing for the follower. And the algorithm is based on projecting lowerlevel variables onto the upper one for the second problem. The results of a computational experiment are presented. The study was carried out within the framework of the state contract of the Sobolev Institute of Mathematics (project no. 031420190014) 
Session manager Maxim Staritsyn
11:40  Bilevel models of sociallyoriented strategic planning in the natural resource sector PRESENTER: Artem Panin ABSTRACT. This article continues the author’s research into cooperation between public and private investors in the resource region. Unlike previous works, here an attempt was made to explicitly take into account the interests of the local population. This work aims to analyze the partnership mechanisms in terms of efficiency, using the gametheoretical Stackelberg model. Such mechanisms determine the economic policy of the state and play an important role for addressing a whole range of issues related to the strategic management of the natural resource sector in Russia. Models are formulated as bilevel mathematical programming problems with two optimization criteria at the upper level. Effective solution algorithms based on metaheuristics and allowing solving largedimensional problems will be developed. This opens up the possibility of practical study on the real data of the properties of Stackelberg equilibrium, which determines the design of the mechanism for the formation of economic policy, clearly taking into account the interests of the local population. The simulation results will allow not only to assess the impact of various factors on the effectiveness of the generated subsoil development program but also to formulate the basic principles that should guide the state in the strategic management process. This work is supported by Russian Foundation for Basic Research (projects numbers 20–010–00151 and 19–410–240003). 
12:00  Finding Better Precoding in Massive MIMO using Optimization Approach PRESENTER: Evgeny Bobrov ABSTRACT. In this paper, we consider the precoding problem for wireless MIMO systems. This task is crucial for modern cellular 5G networks. The optimal precoding matrix is determined by a special hard to solve nonconvex constrained optimization problem. That is why in practice heuristic algorithms for precoding are mainly used, such as MaximalRatio Transmission or ZeroForcing. In this paper, we propose to find precoding matrix using optimization of spectral efficiency in special families of matrices. We are testing the proposed approach in several scenarios generated using Quadriga  an open source software for generating realistic radio channel impulse response. Our method shows monotonic improvement over heuristic methods with reasonable computation time. 
12:20  Optimal control approach for dengue control using wMel and wMelPop strains of Wolbachia PRESENTER: Olga Vasilieva ABSTRACT. We propose a dengue transmission model of SIR(S)SI type that accounts for two sexstructured mosquito populations: the wild mosquitoes (males and females that are Wolbachiafree), and those deliberately infected with either wMel or wMelPop strain of Wolbachia symbiotic bacterium. Laboratory experiments have revealed that Wolbachia induces the inhibition of the dengue virus inside the mosquitoes which leads to a considerable reduction of dengue morbidity in human populations. Wolbachiabased biocontrol of dengue operates by releases of Wolbachiainfected mosquitoes seeking to crush the populations of wild insects. In the present study, we bring forth the methodology capable of providing quantitative estimations of the three key metrics of Wolbachiabased biocontrol when the initial size of the wild mosquito population can be fairly assessed. The proposed methodology stems from the optimal control approach for the design of straindependent optimal release programs that can be characterized by the following three quantifications: (a) optimal time of effective releases; (b) a total number of Wolbachiacarrying insects to be massreared, and (c) the estimated number of human infections to be prevented. Additionally, our discussion is also focused on the costeffectiveness of two Wolbachia strains, wMel and wMelPop, that are usually employed for Wolbachiabased dengue control. 
12:40  Feedback Maximum Principle for a Class of Linear Continuity Equations Inspired by Optimal Impulsive Control PRESENTER: Maxim Staritsyn ABSTRACT. We consider an optimal control problem for a linear continuity equation in the space of probability measures, subject to additonal integral constraint on control. The latter establishes a connection of the addressed model with the framework of impulsive control. Dynamical systems in the space of measures are used to model (infinite) ensembles of microscopic individuals (agents) driven by a common vector field. The control is a function of time variable only, i.e., it is common for all the individuals. For the case, when the agents do not interact one with another, we present a necessary optimality condition of the type of feedback minimum principle (FMP), which employs the constructions of Pontryagin's Maximum Principle (PMP) for designing an ensemblefeedback control. We give an example showing that FMP can be used to discard nonoptimal PMP extrema, and discuss the algorithmic feature of FMP, which implies its realization as an iterative numeric algorithm for optimal impulsive control. 
13:00  Agentbased mathematical model of COVID19 propagation in Novosibirsk region: optimization and forecasting PRESENTER: Mariia Sosnovskaia ABSTRACT. During the last year the pandemic of COVID19 affected 192 countries with over 100 million confirmed people. There was determined seven SARSCoV2 strains and created a lot of vaccines and mathematical models that needed to be investigated in short and long terms. The simulation of different scenarios of epidemy propagation in Novosibirsk region depend on interventions and vaccination procedure can be used for developing of effective programs for control the epidemy. We propose the updated agentbased mathematical model of COVID19 propagation in Novosibirsk region based on COVASIM software [1]. At the first step of modeling data analysis using machine learning approach is carried out. It allows to determine the correlated datasets and find some features that used in modeling procedure. At the second step unknown model parameters that depend on intervention dates such as reproduction number, number of asymptomatic patients, etc. are calibrated using additional measurements about number of daily confirmed, tested, death cases as well as statistic information about disease. We use OPTUNA [2] optimization approach for minimization the misfit function and identifiability analysis for regularization [3]. At the third step we analyze different scenarios of COVID19 propagation depend on interventions and vaccination [4]. This work is supported by the Russian Science Foundation (project no. 187110044) and the Council for Grants of the President of the Russian Federation (project no. МК4994.2021.1.1). References: [1] C. C. Kerr, R. M. Stuart, D. Mistry, R. G. Abeysuriya, G. Hart, K. Rosenfeld, P. Selvaraj, R. C. Nunez,B. Hagedorn, L. George, A. Izzo, A. Palmer, D. Delport, C. Bennette, B. Wagner, S. Chang, J. A. Cohen,J. PanovskaGriffiths, M. Jastrzebski, A. P. Oron, E. Wenger, M. Famulare, D. J. Klein. Covasim: an agentbased model of covid19 dynamics and interventions, medRxiv (2020). DOI: 10.1101/2020.05.10.20097469. [2] A hyperparameter optimization framework optuna, https://optuna.org/. [3] Krivorotko O.I., Andornaya D.V., Kabanikhin S.I. Sensitivity analysis and practical identifiability of some mathematical models in biology. Journal of Applied and Industrial Mathematics. 2020; 14:115–130. DOI: 10.1134/S1990478920010123. [4] Krivorotko O.I., Kabanikhin S.I., Zyatkov N.Yu., Prikhodko A.Yu., Prokhoshin N.M., Shishlenin M.A. Mathematical modeling and forecasting of COVID19 in Moscow and Novosibirsk region. Siberian Journal of Numerical Mathematics. 2020; 23(4):395–414. DOI: 10.15372/SJNM20200404 
Session manager Anton Ushakov
15:00  Novel scenarios and old challenges: Discrete Optimization at various Huawei technologies ABSTRACT. In my talk, I will introduce several mathematical directions from the domain of Discrete Optimization and Operational Research and having importance in different technologies researched by Mathematical Modeling Laboratory at Huawei. There are no engineering prerequisites required, and my target is to show many opportunities to do mathematical research with an impact on technologies. 
15:40  A column generation based heuristic for a temporal bin packing problem PRESENTER: Alexey Ratushnyi ABSTRACT. We introduce a new temporal bin packing problem that originated from cloud computing. We have a finite set of items. For each item, we know an arriving time, processing time, and two weights (CPU, RAM). Some items we call large. Each bin (server) has two capacities and is divided into two identical parts (left and right). A regular item can be placed in one of them. A large item is divided into two identical parts and placed in both parts of a bin. Our goal is to pack all items into the minimum number of bins. For this NPhard problem, we design a heuristic that is based on column generation to get lower and upper bounds. Preliminary computational experiments for real test instances indicate a small gap between the bounds. The average relative error is at most 0.5% for one week planning horizon and about 50000 items. The average running time is 24 seconds for a personal computer. 
16:00  Fast Heuristic Algorithms for the Multiple Strip Packing Problem PRESENTER: Igor Vasilyev ABSTRACT. In this paper we address the socalled twodimensional Multiple Strip Packing Problem (MSPP). Given a set of rectangles and a set of strips, each strip has a predefined width, the problem is to find a feasible packing of all the rectangles into the strips so as the maximal height of the packing over all the strips is minimized. A packing is feasible if all the rectangles are placed into the strips and not overlapped. In case of only one strip, the problem is widely known as the Strip Packing Problem (SPP). Many effective constructive heuristics for SPP are based on the socalled skyline representation of a packing pattern. We generalized this approach for the case of multiple strips and developed a randomized local search, which embeds the proposed skyline heuristic to compute the objective value for a packing. We also introduced the twodimensional level multiple strip packing problem and developed some levelbased constructive heuristics. We report computational results on reallife problem instances arisen in an application of MSPP in scheduling computing jobs on multiple Spark computer clusters. 
16:20  Adaptive Regularized ZeroForcing Beamforming in Massive MIMO with MultiAntenna Users PRESENTER: Evgeny Bobrov ABSTRACT. Modern wireless cellular networks use massive multipleinput multipleoutput (MIMO) technology. This involves operations with an antenna array at a base station that simultaneously serves multiple mobile devices that also use multiple antennas on their side. For this, various Beamforming and Detection techniques are used, allowing each user to receive the signal intended for him from the base station. There is an important class of linear Precoding called Regularized ZeroForcing (RZF). In this work, we propose a special kind of regularization matrix with different regularization for different UE (Adaptive RZF), using singular values of multiantenna users. Proposed algorithm has a simple analytical formula and is provided with theoretical study and asymptotic behavior. We also show the results in comparison with other linear Precoding algorithms on simulations with the Quadriga channel model. The proposed approach leads to a significant increase in quality with the same computation time as in the baseline methods. 
16:40  Simple Shortest Path Problem with MustPass Nodes: a problemspecific BranchandBound algorithm PRESENTER: Michael Khachay ABSTRACT. The Shortest Simple Path Problem with MustPass Nodes (SSPPMPN) is the wellknown combinatorial optimization problem having numerous applications in operations research. In this paper, we show that this problem remains intractable even in the case of any fixed number of nodes to visit. Our main result is the novel problemspecific branchandbound algorithm for this problem. We prove its high performance by a numerical evaluation carried out on the reallife benchmark dataset 'Rome99' taken from the 9th DIMACS Implementation (shortest paths) Challenge. The results show that the proposed algorithm outperforms the wellknown solver Gurobi equipped with the best known MILP models both in obtained accuracy and execution time. 
17:00  Constructive heuristics for automatic warehouse scheduling PRESENTER: Ivan Davydov ABSTRACT. We consider a reallife problem that arises in an industrial process of a big electronic device manufacturer. A warehouse, which stores the finished products is involved in the orders packing and delivery process. Each order should process through two stages to be prepared for delivery. During the first stage, picking, the ordered goods have to be extracted from the storage. During the second stage, these goods have to be packed into the boxes and transferred to the delivery service. The problem is to arrange the schedule and the way the orders have to process through the stages, in order to maximize the throughput of the warehouse. We propose a set of constructive heuristics and hybrid approaches for this problem and discuss the results of computational experiments on real data, provided by the Huawei company. 
17:20  Conclusions and Discussion 
Session manager Alexander Stolbov