ABSTRACT. A class of discrete-continuous control systems described by differential equations with piecewise constant controls is considered. Conditions for nonlocal improvement and control optimality are constructed in the form of fixed point problems in the control space. This representation of conditions makes it possible to apply and modify the well-known theory and methods of fixed points for constructing iterative algorithms for solving the considered discrete-continuous optimal control problems. The proposed iterative algorithms have the property of nonlocality of successive control approximations and the absence of a procedure for the parametric search for an improving approximation at each iteration, which is characteristic of known standard gradient-type methods. Based on the proposed approach, new necessary conditions for control optimality are constructed, which strengthen the known conditions of optimality. Conditions for the convergence of relaxation sequences of controls obtained based on the constructed sufficient conditions for nonlocal improvement of control are derived. Illustrative examples of improving admissible controls and obtaining optimal controls by fixed-point methods are given. This work was supported by the Russian Foundation for Basic Research, project 18-41-030005.

ABSTRACT. A new approach to optimization of state-quadratic optimal control problems with terminal constraints based on the sequential solution of control improvement problems in the form of special boundary value problems is considered. The developed approach for improving the admissible controls is based on the formulas for the functional increment without the remainder of the expansions. Such formulas make it possible to avoid the laborious operation of parametric variation to improve control, which ultimately leads to increased efficiency of the developed optimization procedures. The nonlocality of improving control is achieved by solving a special boundary value problem, which is much simpler than the boundary value problem of the maximum principle. To solve the boundary-value improvement problem, an iterative algorithm is constructed with the fulfillment of all terminal constraints at each iteration, based on the known perturbation principle. The proposed approach allows to formulate new necessary optimality conditions that strengthen the known maximum principle in the class of problems under consideration, and makes it possible to strictly improve non-optimal controls that satisfy the maximum principle. The comparative efficiency of the considered nonlocal methods with the known methods is illustrated by numerical calculations of model examples. The work was supported by RFBR, project No. 18-41-030005.

ABSTRACT. An approach to modeling the development strategies of electric power systems based on an integral model of developing systems is considered. The model includes a non-classical Volterra equation of the first kind, which describes the balance between the desired level of electricity consumption and the input generating capacities. The capacities are divided into several age groups with different indicators of the effectiveness of their functioning. We study the case when the moment of the system origin coincides with the beginning of the modeling. The prospect of using two methods of describing age boundaries to solving the optimization problem for the lifetime of the base equipment of real-life objects of electric power systems is considered.

ABSTRACT. The aim of this study, is to present the fractional model of energy supply-demand system (ES-DS) based on the Caputo-Fabrizio derivative. For the first time, the existence and uniqueness of solution of the fractional model of ES-DS are proved. This model is based on four important functions, energy resources demand (ERD) x1, energy resource supply (ERS) x2, energy resource import (ERI) x3 and renewable energy resources (RER) x4 that we will discuss on two regions Russian far east and eastern Siberia. Moreover, the homotopy analysis method and the Laplace transforms (HATM) are applied to solve the mentioned model. Instead of applying the floating point arithmetic (FPA), we will use the CESTAC method and the CADNA library which are based on the discrete stochastic arithmetic (DSA). Using this method instead of showing the accuracy of the results by the traditional absolute error or residual error, we will apply a novel condition. Based on the CESTAC method and the CADNA library, we can find the optimal approximation, the optimal error and some of numerical instabilities which they are the main novelties of this study. Applying the obtained numerical results, we can forecast the rate of energy supply and demand for spacial interval of time.

ABSTRACT. In the Hitting Set problem, one is given a collection of sets and has to find a minimum-cardinality set intersecting all sets in the input collection. In applications with noisy data (like feature selection, genome-wide association studies, and optimal medication), one is rather interested in Multiple Hitting Set, where the solution has to intersect each input set a given number of times. In 1998, Weihe presented a data reduction algorithm for Hitting Set that turned out effective in practise. We observe that Weihe's algorithm actually computes linear-size problem kernels for Hitting Set parameterized by the Dilworth number of the incidence graph and thus initiate parameterized complexity studies with respect to the Dilworth number: it was introduced by Foldes and Hammer in 1978 and is bounded from above by the neighborhood diversity, which is frequently studied in the context of parameterized complexity theory. We generalize Weihe's kernelization to Multiple Hitting Set and speed it up using matrix multiplication, allowing for sequentual subquadratic-time implementations and parallel implementations using NC1 circuits. We experimentally compare the data reduction effect of our kernelization and additional data reduction rules for Multiple Hitting Set to those derived by Moscato et al. in the context of feature selection and cancer medication applications.

ABSTRACT. The Hierarchical Chinese Postman Problem is finding a shortest traversal of all edges of a graph respecting precedence constraints given by a partial order on classes of edges. We show that the special case with connected classes is NP-hard even on orders decomposable into a chain and an incomparable class. For the case with linearly ordered (possibly disconnected) classes, we get 5/3-approximations and fixed-parameter algorithms by transferring results from the Rural Postman Problem.

ABSTRACT. Dealing with NP-hard problems, kernelization is a fundamental notion for polynomial-time data reduction with performance guarantees: in polynomial time, a problem instance is reduced to an equivalent instance with size upper-bounded by a function of a parameter chosen in advance. Kernelization for weighted problems particularly requires to also shrink weights. Marx and Végh [ACM Trans. Algorithms 2015] and Etscheid et al. [J. Comput. Syst. Sci. 2017] used a technique of Frank and Tardos [Combinatorica 1987] to obtain polynomial-size kernels for weighted problems, mostly with additive goal functions. We characterize the function types that the technique is applicable to, which turns out to contain many non-additive functions. Using this insight, we systematically obtain kernelization results for natural problems in graph partitioning, network design, facility location, scheduling, vehicle routing, and computational social choice, thereby improving and generalizing results from the literature.

ABSTRACT. We present a new bi-level linear integer programming model for the strategic planning of the public-private partnership. In this model, we need to select and schedule some ecological, infrastructure, and production projects within a finite planning horizon. Two players, the leader (government) and the follower (private companies) make own decisions sequentially under the budget constraints. The players try to maximize own total profits. We claim that this bi-level problem is $\sum^p_2$-hard in cooperative and non-cooperative cases. To find near-optimal solution, we design a stochastic tabu search metaheuristic according to the upper level variables. The optimal solution for the lower level is obtained by CPLEX solver. To reduce the running time, we use randomized flip and move neighborhoods. To evaluate the neighboring solutions, we solve the lower level problem approximately. Computational results for real world instances for the Transbaikalian polymetallic fields and comparison with a matheuristic based on the high point relaxation are discussed.

ABSTRACT. We consider a variant of the offline Dial-a-Ride problem with a single server where each request has a source, destination, and a prize earned for serving it. The goal for the server is to serve requests within a given time limit so as to maximize the total prize money. We consider the variant where prize amounts are uniform which is equivalent to maximizing the number of requests served. This setting is applicable when all rides may have equal importance such as paratransit services. We first prove that the \textsc{segmented best path} ($\sbp$) algorithm from~\cite{atmos17} is a 4-approximation. We then show that no polynomial-time algorithm can be guaranteed to serve the optimal number of requests, even when the time limit for the algorithm is augmented by any constant factor $c \ge 1$. We present an algorithm, $k$-Sequence, that repeatedly serves the fastest set of $k$ remaining requests, and provide upper and lower bounds on its performance. We show $k$-Sequence has approximation ratio at most $2+\lceil \lambda\rceil/k$ and at least $1 + \lambda/k$, where $\lambda$ denotes the ratio between the maximum and minimum distances in the graph, and that $1 + \lambda/k$ is tight when $1 + \lambda/k \ge k$. Thus, for the case of $k=1$, i.e., when the algorithm repeatedly serves the quickest request, it has approximation ratio $1+\lambda$, which is tight for all $\lambda$. We also show that even as $k$ grows beyond the size of $\lambda$, the ratio never improves below $9/7$.

ABSTRACT. We consider the gas transmission network operating on the territory of the Russian Federation. This network includes gas fields, gas consumers, nodal compressor stations, underground gas storages, which, depending on the given scenario of the system operation, can act as gas sources or gas consumers. The nodes are connected by means of gas pipelines. Because natural gas is used in heat and power engineering and electricity, the gas transmission network may be exposed to terrorist threats, and the actions of intruders may be directed both at gas production facilities and gas pipelines. To simulate intruders attacks, a model of the attacker-defender type was proposed. In this model, the defender, represented by the system operator, solves the problem of finding the maximum flow to meet the needs of gas consumers. The attacker, in turn, attempts to minimize the maximum flow in the gas transmission network by excluding either nodes or gas pipelines. Gas transmission networks in Russia and Europe are very extensive, ramified, and have many bridges and reserve gas pipelines. Therefore, to inflict maximum damage to the system, attacks on cliques, that is, on several interconnected objects, are modeled. The article presents the results of test calculations, in which we identify the most significant combinations of objects in the gas transmission network in terms of the potential threat from terrorist attacks.

ABSTRACT. The main purpose of quotas is to limit emissions for facilities that have a negative impact on the environment. When calculating emission quotas, it is necessary to solve a nonlinear programming problem with a nonlinear objective function and linear constraints. Variables of the problem are emission reduction coefficients for objects that have a negative impact on the environment. Constraints of the problem are determined by the admissibility of the emission contributions from objects to the concentration of pollutants in the air at the locations of quotas. As a rule, the number of constraints of this problem is significantly less than the number of variables (the problem can include up to 10,000 variables and 1,000 linear constraints). In this regard, it seems relevant to use the theory of duality for the purposes of substantive analysis and simplification of computational methods for problem solving. We suggest the transition from primal to dual nonlinear programming. As a result, we gain a nonsmooth problem of unconstrained minimization of a much smaller order, and the solution can be obtained by effective subgradient minimization methods with an alteration in the space metric. We propose an effective method for solving the problem of emission quotas to be determined, and confirm its efficiency by a computational experiment on both test and applied data. The explicit form of the dependence of primal and dual variables is useful for the analysis of the solution and the selection of the object priority parameters by an expert.

ABSTRACT. In this paper, we study the properties of a penalty method in solving one of the non-convex constrained quadratic programming problem. The problem has an application in radiophysics while it is required to maximize directed radiation using phased antenna arrays. The objective function of the problem is defined by a positive semi-definite (n x n)-matrix, with the size n that equals doubled number of emitters in the antenna array. Every constraint is defined by an (n x n)-matrix that has two identical positive eigenvalues and two identical non-negative eigenvalues, the rest of the eigenvalues are equal to zero. The number of constraints is n. In the current work the problem is reduced to an unconstraint problem using the exterior point method. The properties of the problem were studied with different quadratic programming methods. In the computational experiments, solving algorithms were applied to the unconstrained problem formulation using the penalty function. Global optimality of the obtained solutions is established using BARON package. Results of solving unconstrained problem formulation are compared. Also, there was performed a number of experiments to study how the result is changing with radio-frequency and counterweight density rise for some models that find a practical application. It is established that the objective function in many local optima has the same value that corresponds to the same solution in the physical sense. An experimental analysis of the stability of the local optima under small variations of the input data was carried out.

ABSTRACT. This paper addresses the optimistic statement of one class of bilevel optimization problems (BOPs) with a nonconvex lower level. Namely, we study BOPs with a convex quadratic objective function at the upper level and with a bimatrix game at the lower level. It is known that the problem of finding a Nash equilibrium point in a bimatrix game is equivalent to the special nonconvex optimization problem with a bilinear structure. Nevertheless, we can replace such a lower level with its optimality conditions and transform the original bilevel problem into a single-level nonconvex optimization problem. Then we apply the original Global Search Theory (GST) for general d.c. optimization problems and the Exact Penalization Theory to the resulting problem. After that, a special method of local search, which takes into account the structure of the problem under consideration, is developed.

ABSTRACT. We consider two problems of finding the best approximations of convex compact sets in three-dimensional Euclidean space. The first is the construction of an external approximation - a covering, and the second is the construction of an internal approximation - a packing. The elements of both approximations are balls whose radii are equal to the product of the common parameter r by the individual positive coefficient for each ball. The optimality criterion in solving the first problem is the minimization of the parameter r, and for the second one, it is the maximization of r. The key element of the iterative algorithm is the partitioning of the set M into the areas of influence of points from the current array. These areas are generalized Dirichlet zones. Then we find a new point for each zone. For the first problem, it is the Chebyshev center of the region, and for the second one, it is the point where the Euclidean distance to the boundary of the zone reaches its maximum. Besides, we use the methods of subgradient descent and ascent. The preliminary results of the computational experiment are presented and discussed.

ABSTRACT. The paper considers the agent scheduling problem in a multi-skill call center. This problem consists of maximizing the service quality under constraints on the total labor cost of the agents. The mathematical formulation of the problem is suggested and shown to be NP-hard.  Also, a mixed-integer linear programming (MIP) model is proposed for the problem. A genetic algorithm is developed taking into account the specific features of the problem. The data series with different numbers of agents are generated, and an experimental comparison of the results of the genetic algorithm and the MIP solutions found by the CPLEX solver is carried out. The computational experiment has shown practically acceptable accuracy of the solutions obtained by the genetic algorithm and applicability of this algorithm to problems of large dimensions.

ABSTRACT. In this report we consider an ambiguity-averse multi-stage network game between a user and an attacker. The arc costs are assumed to be random variables that satisfy prescribed first-order moment constraints for some subsets of arcs and individual probability constraints for some particular arcs. The user aims at minimizing its expected loss by traversing between two fixed nodes in the network. By observing user's decisions, the attacker reveals to the user a partial information about the distribution of the arc costs. In contrast to most of the previous studies in literature, the user can dynamically adjust the decisions at each node of its path. We propose a multi-stage robust reformulation of the distributionally robust shortest-path problem. We employ a finite adaptability approach to approximate the multi-stage formulation with a sequence of linear mixed-integer programming problems. We interpret adaptive decisions of the user in the context of repeated interactions between the decision-makers, where the user sequentially refines the first-order moment constraints. Finally, the relevance of the proposed approach is illustrated with numerical experiments, where the arc costs are estimated dynamically by leveraging Bluetooth sensors.

ABSTRACT. It is known that there is no EPTAS for the $m$-dimensional knapsack problem unless $W[1] = FPT$. It is true already for the case, when $m = 2$. But an FPTAS still can exist for some other particular cases of the problem.

In this note we show that the $m$-dimensional knapsack problem with a $\Delta$-modular constraints matrix admits an FPTAS with the arithmetical complexity $$O(T_{LP} \cdot (1/\varepsilon)^{m+5} \cdot (4m)^{2m + 5} \cdot \Delta),$$ where $T_{LP}$ is the linear programming complexity bound. In particular, for fixed $m$ the arithmetical complexity bound becomes $$ O(n \cdot (1/\varepsilon)^{m+5} \cdot \Delta). $$

ABSTRACT. The paper considers the problem of scheduling software modules on a multi-core processor, taking into account the limited bandwidth of the data bus and the precedence constraints and precedence constraints between the modules. Two problem formulations with different levels of problem-specific detail are suggested and both shown to be NP-hard. A mixed integer linear programming (MIP) model is proposed for the first problem formulation, and a greedy algorithm is developed for the second one. An experimental comparison of the results of the greedy algorithm and the MIP solutions found by CPLEX solver is carried out. Modifications of both problem formulations for the case of uncertainty in the input data are considered and experimentally evaluated.

ABSTRACT. A Hamiltonian decomposition of a regular graph is a partition of its edge set into Hamiltonian cycles. The problem of finding edge-disjoint Hamiltonian cycles in a given regular graph has many applications in combinatorial optimization and operations research. Our motivation for this problem comes from the field of polyhedral combinatorics, as a sufficient condition for vertex nonadjacency in the 1-skeleton of the traveling salesperson polytope can be formulated as the Hamiltonian decomposition problem in a 4-regular multigraph.

In our approach, the algorithm starts by solving the relaxed 2-matching problem, then iteratively generates subtour elimination constraints for all subtours in the solution and solves the corresponding ILP-model to optimality. The procedure is enhanced by the local search heuristic based on chain edge fixing and cycle merging operations. In the computational experiments, the iterative ILP algorithm showed comparable results with the previously known heuristics on undirected multigraphs and significantly better performance on directed multigraphs.

ABSTRACT. We consider a leader-follower model for competitive location in a discrete space. In the model, two firms compete by opening their facilities to capture customers' demand. One of the firms, called the leader, is assumed to make its decision first when the set of customers and competitor's operational parameters are uncertain. The leader considers a finite set of environment realizations or scenarios, describing key customers' and competitor's parameters.

In each of the scenarios, the leader anticipates an optimal reaction of the competitor firm, called the follower. The follower is assumed to decide when the demand scenario is revealed. It optimizes the location of its facilities and aims to maximize profit.

Customers' behavior is modeled by a binary rule, where a customer chooses a single serving facility. This facility must be more preferable than any competitor's one. The leader sets target values of the profit for each of the scenarios and considers these values when computing a regret component of the objective function. The leader's problem can be formalized as a bi-level mixed-integer programming problem with multiple lower-level problems. We suggest a branch-and-cut procedure starting from a high-point relaxation of the problem and enriches the set of constraints with additional inequalities generated via auxiliary optimization problem finding the strongest cut for a bilevel infeasible solution.

ABSTRACT. Diffusion-logistic mathematical model based on partial differential equation (PDE) describes the process of information dissemination in social networks [1] that play an important role in the dissemination of information. The initial boundary value problem for this model is characterized by the PDE coefficients, boundary and the initial condition (source), which affect the predictive properties of the model. The source parameters are unknown or can be rough estimated. To control and predict the response of users to information, it is necessary to determine the initial data using additional measurements about number of involved users in fixed time (inverse problem) [2]. The inverse problem is reduced to the problem of minimizing the misfit function and is solved using a combination of the particle swarm method and the Nelder-Mead method as well as gradient descent method (GDM), fast gradient method (FGM) [3]. The integral formula of the gradient of the misfit function is reduced via the solution of corresponding adjoint problem. It is shown that the convergence of the GDM requires more than 100 times more iterations than the FGM. At the same time, the combined method gives a slightly more accurate result, but it takes 10 times more time to find a solution. This work is supported by the Russian Science Foundation (project no. 18-71-10044) and the Council for Grants of the President of the Russian Federation (project no. МК-4994.2021.1.1).

References: [1] Wang H., Wang F., Xu K. Modeling information diffusion in online social networks with partial differential equations. 2013. arXiv: 1310.0505. [2] Kabanikhin S.I. Definitions and examples of inverse and ill-posed problem. Journal of Inverse and Ill-Posed Problems. 2008. 16(4): 317-357. DOI: 10.1515/JIIP.2008.019. [3] Gasnikov A., Nesterov Yu. Universal fast gradient method for stochastic composit optimization problems. Comp. Math. & Math. Phys. 2018. 58(1): 51-68. DOI: 10.1134/S0965542518010050.

ABSTRACT. Nowadays in Russia a strong growth in consumer lending is taking place. During 2017-2019 the part of consumer loans in the total mass of loans was 57%. In Russia, the fight against poverty is one of the national goals, which determines the relevance of research and mathematical modeling of the debt burden on the population. We analyze the debt burden using the database of the Russian Longitudinal Monitoring Survey – Higher School of Economics (RLMS-HSE), which includes data from 2838 households from 38 constituent entities of the Russian Federation. The households are divided into those which are inclined to take loans and those which do not need credits. Using a modified Ramsey model, it is possible to reproduce the dynamics of consumer loans, money supply, consumptions and the dynamics of deposits over the last decade. The most expected forecasts are presented in accordance with the level of population income loss.

ABSTRACT. Dynamic cooperative games on networks are considered. This is a relatively new class of dynamic games. In our previous paper (Petrosyan and Yeung in 2020) differential cooperative games on the networks were discussed in a special case when the payoffs of players depend only upon their actions and actions of direct neighbors in the network. Here we investigate dynamic games but in the more general setting when a player’s payoff depends upon payoffs of all players with whom he is connected in the network. In cooperative network games when constructing characteristic function, it is supposed that left out players can cut connections with those who decide to form a coalition. This gives the possibility to essentially simplify the methods for the calculation of characteristic functions. Based on this idea new characteristic function is proposed which generates a time-consistent dynamic Shapley Value for a class of dynamic network games under consideration (Shapley in 1953, E. Gromova in 2016). The characteristic function features include the property that the worth of coalitions is derived in the process of cooperation along the cooperative trajectory, and the marginal contributions of individual players are evaluated based on their cooperative actions. It is necessary to mention that the time-consistency property of the characteristic function has not been shared by existing characteristic functions in differential games. Also, it is the first time that the worth of coalitions is measured under the process of cooperation instead of under min-max confrontation or Nash non-cooperative stance. It is proved that the cooperative dynamic game is convex, which means that the core of the game is not empty and the Shapley Value belongs to the core.

ABSTRACT. Inverse problems arise in many applications in science and engineering. The term “inverse problem” is generally understood as the problem of finding a specific physical property, or properties, of the medium under investigation, using indirect measurements. In general, an inverse problem aims at recovering the unknown parameters of a physical system that produces the observations and/or measurements. Such problems are usually ill-posed. This is often solved via two approaches: a Bayesian approach which computes a posterior distribution of the models given prior knowledge and the regularized data fitting approach which chooses an optimal model by minimizing an objective taking into account both fitness to data and prior knowledge. Optimization plays an important role in solving many inverse problems. Indeed, the task of inversion often either involves or is fully cast as a solution to an optimization problem. In this talk, we discuss current state-of-the-art optimization methods widely used in inverse problems. We then survey recent related advances in addressing similar challenges in problems faced by the machine learning community and discuss their potential advantages for solving inverse problems.

ABSTRACT. Classification and Regression Trees are very powerful Machine Learning tools. Their design expressed as an optimization problem enables us to obtain excellent accuracy performance, and, at the same time, to have some control on important issues such as sparsity, explainability or fairness. In this talk, some recent advances in the field and future research lines will be discussed.

ABSTRACT. Maximum spanning tree (MST) is a popular tool in network analysis. Large number of publications are devoted to the MST calculation and it's interpretation in market network analysis. However, much less attention is paidd in the literature to the estimation of uncertainty of obtained results. In the present paper we suggest a general framework to measure uncertainty of MST identification. First we consider the problem in the framework of the concept of random variable network. We measure uncertainty of MST by the risk function of the associated multiple decision statistical procedure (Kruskal algorithm). We discuss different measures of association and different loss functions used in binary classification. We choose an appropriate loss function and show that for Pearson correlation network the risk function of Kruskal algorithm essentially depends on distribution. We prove that for alternative measure of association (sign similarity network) the risk function of Kruskal algorithm is non sensitive to the assumption on distribution for any loss functions. For another popular measure of association, tau-Kendall correlation, we show that the risk function of Kruskal algorithm weakly depend on distribution. This facts are important in practical applications.

ABSTRACT. In this contribution, Lipschitz Global Optimization problems are considered. Namely, we focus our attention on problems with an objective function which satisfies the Lipschitz condition on the search interval and on problems where the first derivative of the objective function satisfies the Lipschitz condition. In particular, in these problems the function we optimize is supposed to be multiextremal on the search domain, its analytical representation is unknown and even one its evaluation is a computationally expensive procedure. New promising approaches, called Local Tuning techniques, allowing one to accelerate the search, are described. We construct methods which tune their behavior to that of the objective function using adaptive estimates of local Lipschitz constants in different areas of the search region. Numerical experiments confirm the advantages of the considered techniques. All the methods were tested both on the traditional computers and on the Infinity Computer allowing one to compute exact numerical derivatives.

References 1. Kvasov D.E., Mukhametzhanov M.S., Nasso M.C., Sergeyev Ya.D. (2020), On Acceleration of Derivative-Free Univariate Lipschitz Global Optimization Methods, Sergeyev Y., Kvasov D. (eds) Numerical Computations: Theory and Algorithms. NUMTA 2019. Lecture Notes in Computer Science, Springer, Cham, 11974:413-421. 2. Lera D. Sergeyev Ya.D. (2013), Acceleration of univariate global optimization algorithms working with Lipschitz functions and Lipschitz first derivatives, SIAM Journal on Optimization, 23(1), 508-529. 3. Sergeyev Ya.D., Mukhametzhanov M.S., Kvasov D.E. and Lera D. (2016), Derivative-free local tuning and local improvement techniques embedded in the univariate global optimization. Journal of Optimization Theory and Applications, Vol. 171(1), 186-208. 4. Sergeyev Ya.D., Nasso M.C., Mukhametzhanov M.S., Kvasov D.E., Novel local tuning techniques for speeding up one-dimensional algorithms in expensive global optimization using Lipschitz derivatives, Journal of Computational and Applied Mathematics, Volume 383, February 2021, 113134.

ABSTRACT. The report explores the mathematical basis of the original polyhedral complementarity approach, proposed by the author for finding economic equilibrium in linear exchange model and its various variations. The math- ematical fundamental base of the approach is a special class of piecewise constant multivalued mappings on the simplex in Rn, generated by a pair of polyhedral complexes in duality. For regular mappings arising in the study of the Fisher model, their potentiality was proved. This allowed us to propose very simple algorithms for finding fixed points. More complex are the quasiregular mappings generated by the general exchange model. These mappings are not potential mappings. Two algorithms are proposed for such mappings. The proposed finite algorithm can be considered as an analogue of Lemke’s method for linear complementarity problem with positive principal minors of the restriction matrix (class P). At each step of the process, it is required to solve a general linear system. The proposed iterative algorithm is based on the approximation of the original mapping by regular mappings and is free from this drawback. The convergence of the process with the speed of a geometric progression has been proved under non-limiting conditions

ABSTRACT. Distributed optimization methods are actively researched by optimization community. Due to applications in distributed machine learning, modern research directions include stochastic objectives, reducing communication frequency and time-varying communication network topology. Recently, an analysis unifying several centralized and decentralized approaches to stochastic distributed optimization was developed in Koloskova et al. (2019). In this work, we employ a Catalyst framework and accelerate the rates of Koloskova et al. (2019) in the case of low stochastic noise.

ABSTRACT. The paper deals with a set of identical requirements processing schedules for parallel machines. The conditions of precedence are set, interrupts are prohibited, time is discrete. This set of schedules is the set of feasible solutions to a number of optimization problems which are determined by various objective functions. For instance, such as minimizing the total processing time, minimizing the weighted sum of processing time. The paper proposes the set of all schedules as a family of subsets of a finite set and defines the schedule polytope as the convex hull of incidence vectors. The report deals with the affine hull and polyhedral relaxation of the scheduling polytope. Polyhedral relaxation includes nonnegativity constraints, constraints as to the number of machines, and precedence constraints. Using the bH-basis technique, the work shows that constraints for nonnegativity generate facets of the scheduling polytope. Necessary conditions for facet constraints as to the number of machines and precedence constraints are found.

ABSTRACT. We consider the maximizing the minimum processor delay game with uniformly related processors and linear externalities. A set of jobs is to be assigned to a set of processors with different delay functions depending on their own loads and also loads on other processors. Jobs choose processors to minimize their own delays. The social payoff of a schedule is the minimum delay among all processors, i.e. cover. For the case of two processors in this model the Nash equilibrium existence is proven and the expression for the Price of Anarchy is obtained. Also we show that the Price of Anarchy is limited in contrast to the initial model without externalities.

ABSTRACT. We consider the intractable problem of finding several edge-disjoint spanning trees of a given diameter on an edge-weighted random graph. Earlier, the authors have implemented an asymptotically optimal approach for this problem in the case of directed graphs. The direct use of this result for the case of undirected graphs turned out to be impossible due to the emergence in this case of problems, which are associated with the summation of dependent random variables. In this work we give the polynomial time algorithm with conditions of asymptotic optimality for the case of undirected graphs.

ABSTRACT. The knapsack problem with additional constraints generalizing standard conflict and forcing constraints is studied. The problem is reduced to optimization on 2-level Boolean sets (2LSs), and a series of linear programs are solved on the sets yielding their solution or an upper bound of the objective function value. Three mathematical models of the problem as a continuous quadratic program are built, which allows solving the problem by semidefinite, Lagrangian dual bound, polynomial optimization, Branch and Bound, and other methods. One of them uses representability of a 2LS as an intersection of a polytope and an ellipsoid. For solving the original problem in this setting, a polyhedral-ellipsoid method is developed and adapted.

ABSTRACT. We discuss a class of tightly feasible MILP for which branch-and-bound is ineffective. We consider its hardness, evaluate the probability that randomly generated instances are feasible, and introduce a heuristic solution method based on the old idea of reformulating binary variables to continuous while introducing a linear complementarity constraint. We show the extent of the computational advantage, under a time limit, of our heuristic with respect to a state-of-the-art branch-and-bound implementation.

ABSTRACT. The problem of combinatorial optimization occurs in many areas of life, such as planning, delivery, routing, etc. Accurate methods for solving problems of this type require large computational and time costs, which is unacceptable for real-life problems, when often solutions need to be obtained dynamically. Thus, approaches for solving large scale problems that are close to optimal in a relatively short time are particularly important and relevant. In this article, we consider the problem statement described in the competition ROADEF/EURO challenge 2020 dedicated to maintenance planning optimization problem in collaboration with RTE (https://www.roadef.org/challenge/2020/en/). First of all, the main task is to build an optimal maintenance schedule for the high voltage transmission network to ensure delivery and supply of electricity. To solve this problem we use several suboptimization methods to find a good maintenance schedule that would be consistent with all work-related constraints and would take into account the risk assessment. There are many algorithms that can solve this optimization problem such as Genetic algorithms [1], evolutionary strategies (CMA-ES [1]), swarm intelligence algorithms (Particle Swarm Optimization [2], Ant Colony Optimization [3]), exact integer algorithms (Branch and Bound, Branch and Cut [4]), random search (Simulated Annealing [5]) and local search methods (Variable Neighborhood Search [6]). To achieve these goals, it is very important to use the best methods available nowadays. For this reason, we used the CMA-VNS [7] algorithm after analyzing the results of the Combinatorial Black Box Optimization Competition ( https://web.mst.edu/~tauritzd/CBBOC/GECCO2015 ). The algorithm is hybrid and consists of Bipop CMA-ES and VNS algorithms that makes it possible to obtain solutions with zero penalty function and close to minimal objective function in an admissible time. Other popular algorithms are carried out to compare with our solution to prove the efficiency of this approach. For the algorithm implementation the Python 3 was used.

[1] - Seyedali Mirjalili. Genetic Algorithm. Evolutionary Algorithms and Neural Networks, 2019, Volume 780, ISBN : 978-3-319-93024-4 [2] - Sylverin Kemmoé Tchomté, Michel Gourgand, Particle swarm optimization: A study of particle displacement for solving continuous and combinatorial optimization problems, International Journal of Production Economics, Volume 121, Issue 1, September 2009, Pages 57-67, DOI: https://doi.org/10.1016/j.ijpe.2008.03.015 [3] - Курейчик В. М., Кажаров А. А. Муравьиные алгоритмы для решения транспортных задач. Известия Российской академии наук. Теория и системы управления., 2010 [4] - Писарук Н. Н. Исследование операций. Минск, БГУ, 2017 [5] - V. Granville, M. Krivanek and J. Rasson, "Simulated Annealing: A Proof of Convergence" in IEEE Transactions on Pattern Analysis \& Machine Intelligence, vol. 16, no. 06, pp. 652-656, 1994. DOI: 10.1109/34.295910 [6] - Hansen, Pierre & Mladenovic, Nenad. (2001). Variable neighborhood search: Principles and applications. European Journal of Operational Research. 130. 449-467. 10.1016/S0377-2217(00)00100-4 [7] - Fan Xue and Geoffrey Q Shen. Design of an efficient hyper-heuristic algorithm CMA-VNS for combinatorial black-box optimization problems. In Proceedings of GECCO ’17 Companion, Berlin, Germany, July 15-19, 2017, 6 pages. DOI: http://dx.doi.org/10.1145/3067695.3082054

ABSTRACT. The single-bidder rate is a commonly used proxy of corruption in public procurement, but ipso facto this is not evidence of a corrupt auction, but an uncompetitive auction. And while an uncompetitive auction could arise due to a corrupt procurer attempting to conceal the transaction, but it could also be a result of geographic isolation, monopolist presence, or other structural factors. In this paper, we use positive-unlabelled classification to attempt to separate public procurement auctions in the Russian Federation into auctions that are probably fair, and those that are suspicious.

ABSTRACT. The paper investigates a contractual approach and studies economies with non-convex production. The contractual theory developed in (Marakulin, 2003, 2011) for exchange and in (Marakulin, 2014) for production economies is modified and adapted to the models with non-convex and non-smooth production sector. We clarify an appropriate notion of the web of contracts, their dominance by coalitions, the partial break of contracts, etc. A generalized notion of marginal contractual allocation (called K-marginal fuzzy contractual) is introduced and used in equilibrium analysis together with marginal cost pricing (MCP-equilibrium) that is applied in literature instead of Walrasian equilibrium for production economies with increasing returns to scale. We analyze marginal pricing rules that can be specified as Clark’s derivative and similar ones. The equivalence between MCP-equilibria and K-marginal fuzzy contractual allocations (K is a convex cone) presents the main result. It can be viewed as a theoretical substantiation of the concept of MCP-equilibrium in non-convex economies. The work develops a contractual approach as a universal way for perfect competition modeling.

ABSTRACT. A one-dimensional discrete game problem with a given endpoint is considered. A terminal set is a union of an infinite number of disjoint segments of equal length. This terminal set has the meaning of the neighborhood of the desired state of the system, taking into account the periodicity. It is believed that one breakdown is possible, which leads to a change in the dynamics of the controlled process. The breakdown time is not known in advance. The first player's control is based on the principle of minimizing the guaranteed result. The opposite side is the second player and the moment of the breakdown. In this talk, we have found sufficient termination conditions under which the first player can lead the phase vector at a given moment of time to the terminal set for any control of the second player and any moment of breakdown. The guaranteed control of the first player is constructed. As an example, we consider the problem of controlling a rotational mechanical system with disturbance and possible breakdown. This work was funded by the Russian Science Foundation (project no. 19-11-00105).

ABSTRACT. In the Capacitated Geometric 1-Median problem, we are given n points in multidimensional real space and an integer m, the goal is to locate a new point in space (center) and choose m of the input points to minimize the sum of the Euclidean distances from the center to the chosen points. We suggest an "almost exact" polynomial-time algorithm for this problem in the case of fixed space dimension and describe an approximation scheme PTAS for the general case. On the other hand, we prove that Capacitated Geometric 1-Median is strongly NP-hard and does not admit approximation schemes FPTAS unless P=NP.