ABSTRACT. We consider the following concept. A set C in d-dimensional real space is said to be a (1+ε)-collection for a set X if C contains (1+ε)-approximations of all the points of space with respect to the Euclidean distances to all the elements of X. A (1+ε)-collection provides a universal method for finding approximate solutions of geometric center-based problems where it is required to choose points in space (centers) minimizing an arbitrary continuity-type function which depends on the distances from the input points to the centers. In fact, one may reduce an original geometric problem to its discrete version where all the centers belong to a (1+ε)-collection for the input set. As was shown recently, for every fixed ε>0 and any finite set in high-dimensional space, there exists a (1+ε)-collection which consists of a polynomial number of points and can be constructed in polynomial time. We suggest an algorithm which gives a better upper bound for the cardinality of (1+ε)-collections and obtain the first lower bound for this cardinality in the worst case. Also, we show that the cardinality of (1+ε)-collections for some sets of points can not be polynomial in the case of ℓ∞ distances.

ABSTRACT. Distance between two vertices is the number of edges of a shortest path connecting them in a graph G. The transmission of a vertex v is the sum of distances from v to all the other vertices of G. A half of the sum of vertex transmissions gives the Wiener index that has found important applications in chemistry. The number of different vertex transmissions is known as Wiener complexity of a graph. A graph is called transmission irregular if it has the largest possible Wiener complexity over all graphs of a given order, i.e., vertices of the graph have pairwise different transmissions. It was shown that almost all graphs are not transmission irregular. The following problem was posed in [1]: find infinite families of transmission irregular graphs among trees, 2-connected graphs and regular graphs. In this report, we present infinite families of transmission irregular graphs in the following classes: trees of even order, 2-connected graphs, cubic and quartic graphs [2-5]. This work is supported by the Russian Foundation for Basic Research (project number 19-01-00682). [1] Alizadeh Y., Klavžar S. On graphs whose Wiener complexity equals their order and on Wiener index of asymmetric graphs. Appl. Math. Comput. 2018. Vol. 328. P. 113-118. [2] Dobrynin A.A. On 2-connected transmission irregular graphs. J. Appl. Industrial Math. 2018. Vol. 12. N. 4. P. 642-647. [3] Dobrynin A.A. Infinite family of 2-connected transmission irregular graphs. Appl. Math. Comput. 2019. Vol. 340. N. 1. P. 1-4. [4] Dobrynin A.A. Infinite family of transmission irregular trees of even order. Discrete Math. - 2019. Vol. 342. N. 1. P. 74-77. [5]. Dobrynin A.A. Infinite family of 3-connected cubic transmission irregular graphs. Discrete Appl. Math. 2019. Vol. 257. P. 151-157.

ABSTRACT. An edge k-colouring of a multigraph is acyclic if every colour class induces a forest. An edge k-colouring is covering if every vertex is incident with edges of all k colours. The celebrated Nash-Williams Theorem states that a multigraph has an acyclic edge k-colouring iff for every vertex subset X, the number of edges in the induced subgraph G[X] does not exceed k(|X|-1) ( we call this Nash-Williams condition) . The results of Gupta say that every graph with minimum degree at least k+1 has a covering edge k-colouring. We present a new proof of Nash-Williams Theorem which allows to obtain the following result about edge colourings that are acyclic and covering simultaneously: if a mutigraph has a cover k-colouring and satisfies Nash-Williams condition, then it has an acyclic covering edge k-colouring. As a colollary, we get the following combination of Nash-Williams and Gupta Theorems: every graph with minimum degree at least k+1 satisfying Nash-Williams condition has an acyclic covering edge k-colouring.

The work is supported by RFBR (projects 18-01-00353 and 18-01-00747).

ABSTRACT. Investigations on the existence problems for non-additive analogs of the standard core in case of unbalanced TU cooperative games, initiated in (Vasilev V., 1978), attracted additional attention about twenty years later. Listing the most important results in this field, let us mention the notion of polynomial core in itself, rediscovered independently for the finite number of players in (Grabish M, 1997) and called k-additive core in the modern literature (see, e.g., (Grabish M., Miranda P., 2009)). It is worth to note also intensive study of the structure of k-core polytopes (including description of their faces), k-core and another optimality solutions interconnections. One of the interesting recent results seems to be a constructive proof of the non-emptyness of 2-additive core of finite cooperative game, presented in this paper. As to the infinite games, we propose ordered vector space methods (Vasilev V., 1998). A main tool for analyzing k-additive core is well-known Ky-Fan theorem on a linear system of inequalities in a normed linear space. Approach applied consists of linearization of the initial non-additive core-existence problem by "embedding" it into an appropriate tenzor power of suitable normed space.

ABSTRACT. We establish a theorem that equilibria in an exchange economy can be described as allocations that are stable under the possibilities: (i) agents can partially and asymmetrically break current contracts, after that (ii) a new mutually beneficial contract can be concluded in a coalition of a size not more than 1 plus the maximum number of products that are not indifferent to the coalition members. The presented result generalizes previous ones on a Pareto improvement in an exchange economy with l commodities that require the active participation of no more than l+1 traders. This concerned with Pareto optimal allocations, but we also describe equilibria. Thus according to the contractual approach to arrive at equilibrium only coalitions of constrained size can be applied that essentially raise the confidence of contractual modeling.

ABSTRACT. We study the market equilibrium in international trade monopolistic competition model a’la Dixit-Stiglitz-Krugman with homogeneous firms. The utility of consumers are additive separable. Transport costs are of iceberg type. The only production factor is labor. The concrete functional form of sub-utility function is assumed unknown. Thus, it is not possible to get the equilibrium in closed form. We examine the local symmetric comparative statics of consumption, prices, firm’s masses and firm’s sizes with respect to transport costs. For linear production costs, the results about equilibria near free trade and autarky are known. We show that many of these results are true for the case of non-linear production costs.

ABSTRACT. We study the coupled-task single machine scheduling problem with equal exact delays and makespan as the objective function. It is known that the problem cannot be approximated with a factor better than 1.25 unless P=NP. In this paper we present a 2.5-approximation algorithm for the general case of this problem, which significantly improves the best previously known approximation bound 3 established in our previous paper. The algorithm runs in time O(n log n) where n is the number of jobs.

ABSTRACT. Network flow optimization method is successfully applied to the railways crew assignment and scheduling problem. The problem if formulated as to find a crew for every locomotive (possibly attached to train) schedule segment. Loco schedule segments are the projections of the known loco schedules to the crew operational domains. The limitation is that in the end of the working shift the crew must return to its original work start point (so-called home depot). A special network is constructed based upon these schedule segments represented as the graph edges. The assignment to the segment is performed as the resource unit (representing single crew) passes thru the corresponding network edge. The control over the route of each crew is maintained thru special finite automaton representing the crew working cycle phases as its states, and working phase changes as state transitions. At the same moment, the network edges themselves (at least some of them) represent crew working state transitions. So the network edge permeability in respect to an arbitrary resource unit is effectively controlled by the crew automaton associated with it: the edge is open if the automaton (in its current state) allows for the corresponding crew working state change. The problem is solved at the enterprise level for the freight train transportation flow over the Eastern Operational domain of the Russian Railways for the operating planning horizon of six hours.

ABSTRACT. The multiprocessor scheduling problem is defined as follows: tasks have to be executed on several parallel identical processors. For each task we know release time, processing time and delivery time. At most one job can be processed at a time, but all jobs may be simultaneously delivered. Preemption on processors is not allowed. The objective is to minimize the time, by which all tasks are delivered. Scheduling tasks among parallel processors is a NP-hard problem in the strong sense. The best known approximation algorithm is Jackson's algorithm, which generates the list schedule by giving priority to the ready job with the largest delivery time. This algorithm generates no delay schedules. We define an IIT (inserted idle time) schedule as a feasible schedule in which a processor is kept idle at a time when it could begin processing a task. The paper proposes the approximation inserted idle time algorithm for the multiprocessor scheduling. It is proved that deviation of this algorithm from the optimum is smaller then twice the largest processing time. To illustrate the efficiency of our approach we compared two algorithms on randomly generated sets of jobs.

ABSTRACT. In this paper, we generalize the approach Gasnikov et. al, 2017 that allows solving (stochastic) convex optimization problems with inexact gradient-free oracle to convex-concave saddle-point problem. The proposed approach works at least the best existing approaches. But for special set-up (simplex type constraints and closeness of Lipschitz constants in 1 and 2 norms) our approach reduces n/(ln n) times the required number of oracle calls (function calculations).

ABSTRACT. We consider an interesting class of composite optimizaton problems with gradient dominance condition [1] and introduce corresponding analogues of the recently prposed concept of inexact oracle [2]. Some adaptive gradient methods are proposed for the considered class of problems. Partially, the objective function and its gradient can be given inexactly. The adaptive choice of the parameters is performed during the operation of the method with respect to both the Lipschitz constant of the gradient and a value corresponding to the error of the gradient and the objective function. The linear convergence of the method is justified up to a value associated with the errors. Estimations for the quality of solution with relative accuracy are obtained and discussed.

1. Karimi H., Nutini J., Schmidt M. Linear сonvergence of gradient and proximal-gradient methods under the Polyak–Lojasiewicz condition // Machine Learning and Knowledge Discovery in Databases / eds. B. Berendt etc. Cham: Springer, 2016. P. 795–811. (Lecture Notes in Computer Science; vol. 9851).

2. Devolder O., Glineur F., Nesterov Yu. First-order methods of smooth convex optimization with inexact oracle. // Math. Program. 2014. Vol. 146, no. 1–2. P. 37–75.

ABSTRACT. This article is devoted to the application of the method of optimal matrix correction of linear programming problems to classification problems. The solution to the problem of recognizing patterns with intersecting classes by the method of separating hyperplane is considered. The original problem is reduced to the problem of a correction of a pair of dual linear programming problems with respect to the Euclidean matrix norm. The results of computational experiments confirming the effectiveness of the proposed method are presented.

ABSTRACT. We study the monopolistic competition model a'la Dixit-Stiglitz with vertical market interaction of several manufacturers, a retailer, and consumers. The utility is Ottaviano-Tabuchi-Thisse type. The cost functions of manufacturers and of the retailer are linear. We provide Stackelberg equilibrium under the leadership of the retailer and study the consequences on social welfare and the consumer surplus, the application the taxes of Pigouvian type. It turns out that the best choice for the social welfare and the consumer surplus is not to tax but subsidize the retailer.

ABSTRACT. We study a monopolistic competition model in the open economy case. The utility of consumers are additive separable. The producers can choose technology (R&D) endogenously. We examine the local comparative statics of market equilibrium with respect to transport cots (of iceberg type). Our main finding is the following: increasing trade cost has opposite impacts on mass of firms and productivity. Moreover, we study the cases of small trade costs and symmetric (on numbers of consumers) countries.

ABSTRACT. This paper addresses the coordination of interaction between various types of consumers and a load serving entity to manage electricity consumption by using the adverse selection model from the contract theory. We propose a method of stimulating different consumers to load curve optimization. Each consumer has its utility function, which determines the necessary amount of electricity at any given time period (hour). LSE company is described by a cost function. The goal of our work is to form tariffs so that it is beneficial for the consumer to reduce the peak load (load shifting from a peak time of the day), reducing the costs for the entire electric power system. Earlier, the problem of formed tariffs for two types of consumers (“high” and “low”) was considered [1]. In this work, we have a larger number of types of consumers and we assume that the principal (LSE) is not fully informed of the "intermediate" consumer. It is shown that the relative number of consumers of the "intermediate" type in the market has a significant impact on the tariffs and the efficiency of the resulting equilibrium according to the criterion of maximizing welfare. The tariffs providing a separating equilibrium are determined. We use the pricing scheme that implies the change in electricity prices depending on the electricity consumption by all consumers during every hour so that all consumers have financial incentive.

1. Aizenberg, N. ,Voropai, N. The interaction of consumers and load serving entity to manage electricity consumption // Communications in Computer and Information Science. - 2019. - Vol. 19. - No. 1090. - Pp. 147-162.: Mathematical Optimization Theory and Operations Research, 18th International Conference, MOTOR 2019, Ekaterinburg, Russia, July 8 - 12, 2019.

ABSTRACT. The loss of dispersal connections between habitat patches may destabilize the populations in a patched ecological network. This work studies the stability of the populations when one or more communication links get removed. An example is finding the alignment of a highway through a patched forest containing a network of metapopulations in the patches. This problem is modeled as that of finding a stable cut of the graph induced by the metapopulations network, where nodes represent the habitat patches and the weighted edges model the dispersal between the habitat patches. A reaction-diffusion system on the graph models the dynamics of the predator-prey system over the patched ecological network. The graph Laplacian’s Fiedler value which indicates the well-connectedness of the graph, is shown to affect the stability of the metapopulations. We show that when the Fiedler value is sufficiently large, the removal of edges without destabilizing the dynamics of the network is possible. We give an exhaustive graph partitioning procedure, which is suitable for smaller networks and uses as criterion both the local and globalstability of populations in the partitioned networks. An heuristic graph bisection algorithm that preserves the preassigned lower bound for the Fiedler value is proposed for larger networks and illustrated with examples.

Joint work with W. Vikram Bhatt and Dinesh Kumar

ABSTRACT. This article continues the research of the authors into cooperation between public and private investors in the natural resource sector. This work aims to analyze the partnership mechanisms in terms of efficiency, using the game-theoretical Stackelberg model. Such mechanisms determine the investment 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. For bilevel mathematical programming problems, the computational complexity will be evaluated and effective solution algorithms based on metaheuristics and allowing solving large-dimensional 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 forming investment policies. 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 management process. This work is supported by Russian Foundation for Basic Research (projects numbers 20–010–00151 and 19–410–240003).

ABSTRACT. When solving application problems, it is often necessary to choose a solution that is acceptable not only for the current source data but also remains acceptable when changing this data within a sufficiently wide range. In recent years, a new direction of research in this area has arisen, which is based on the idea of transforming the formulation. For a given set of input data of the problem to the maximum, instead of maximizing income, in the new formulation, we will maximize the region of the input data of the problem close to the selected example, for which there is a solution that leads to income not less than the specified threshold. This article proposes the new implementation of this idea for the bilevel pricing problems based on the idea of the stability radius (proposed in the works of V. Leontiev). Consider the following Stackelberg game. There are a company and its potential clients. First the company prices at own facilities for a homogeneous product. After that, each client chooses the facility in which the minimum of its costs is achieved. The cost consists of purchase and transportation prices. At the same time, clients can make a purchase only if their budget allows it. The goal is to establish prices at which the maximum profit of the company is achieved. Take an arbitrary feasible solution. Let F be the objective function value of this solution. The value R is called the stability radius, if for any r not exceeding R, the problem in which each budget is reduced by non-negative r has a solution with a value of at least F. In the stability analysis problem we need to find the largest stability radius. We discuss the computational complexity and algorithm solution of the stability analysis problem for three different pricing strategies.

ABSTRACT. We consider a model to defend the edges of a supply network. Vertices of the network represent consumers and suppliers of a resource while the edges correspond to supply channels allowing to transport the resource with no capacity limitations or delays. A network's defender aims to commit its limited budget to protect some edges and minimize the damage from the failure of a part of unprotected ones. The damage is computed as a total resource deficit appearing after the worst-case failure. The defender's problem belongs to a family of "defender-attacker" models. We formulate it as a minimax mixed-integer programming problem. To find its optimal solution, we develop two cut-generation procedures relying on a reformulation of the model into a mixed-integer programming problem with a large number of constraints.

ABSTRACT. This article proposes the Stackelberg game of three types of players: the company-leader, the company-follower and their potential customers (clients). Companies set prices at their own facilities for a homogeneous product sequentially. After that, each customer chooses the facility in which the minimum of its costs is achieved. The cost consists of purchase and transportation prices. At the same time, clients can make a purchase only if their budget allows it. The goal is to establish prices at which the maximum profit of the company-leader is achieved. We assume that the company-leader is limited by the mill pricing strategy when the company sets prices at each facility. Moreover, the company-follower uses the uniform pricing strategy, i.e. she sets a single price for all facilities.

We discuss the new solution algorithm of the three-level pricing problem. The idea of the algorithm based on problem reformulation. Let us try to guess the optimal company-follower price and, after that, find the right optimal solution of the company-leader. Thus we reformulate the problem as a mixed-integer linear programming problem with a non-polynomial number of constraints and variables and solve it by the branch-and-bound algorithm. The results of a computational experiment are presented.

References:

[1] A. V. Gubareva, A. A. Panin, A. V. Plyasunov, L. V. Som, On a three-level competitive pricing problem with uniform and mill pricing strategies, J. Appl. Industr. Math.13:1,(2019) 54–64.

ABSTRACT. The paper is devoted to the multiple covering problem by circles of two types. The number of circles of each class is given as well as a ratio radii. The circle covering problem is usually studied in the case when the distance between points is Euclidean. We assume that the distance is determined using some particular metric, which, generally speaking, is not Euclidean. The numerical algorithm is suggested and implemented. It based on an optical-geometric approach, which is developed by the authors in recent years and previously used only for circles of an equal radius. The results of a computational experiment are presented and discussed.

ABSTRACT. We consider stochastic programming problems with probabilistic criterion. The probability function is defined as the probability that a loss function does not increase a given level. When the probability function is maximized, the problem of constructing level sets of the probability function arises. Two methods to construct level sets are suggested. The first method is based on inner approximations of the level sets. These approximations are obtained by the confidence method known in stochastic programming. The second method is based on statistical estimation of the probability functions. Results obtained by the suggested methods are compared.

ABSTRACT. This work addresses the numerical solution of fractional programs with quadratic functions in the ratios. Instead of considering a sum-of-ratios problem directly, we developed an efficient global search algorithm, which is based on two approaches. The first one adopts a reduction of the fractional minimization problem to the solution of an equation with an optimal value of the d.c. minimization problem with a vector parameter. The second approach is based on the reduction of the sum-of-ratios problem to the optimization problem with nonconvex (d.c.) constraints. Thus, we show how fractional programs can be solved by applying the Global Search Theory of d.c. optimization proposed by A.S. Strekalovsky. The global search algorithm developed for sum-of-ratios problems was tested on two series of test examples with quadratic functions in the numerators and denominators of the ratios. The first one is generated by summing of pairs of separable fractions with affine functions. The second series is constructed using the idea proposed by L.N. Vicente and P.H. Calamai. The numerical experiments demonstrated that the algorithm for fractional programs performs well when solving rather complicated quadratic sum-of-ratios problems with up to 300 variables or 1000 terms in the sum.

ABSTRACT. Social networks represent a new phenomenon of our life. The growing popularity of social networks in the Web dates back to 1995 when American portal Classmates.com was launched. This project facilitated the soon appearance of online social networks (SixDegrees, LiveJournal, LinkedIn, MySpace, Facebook, Twitter, YouTube, and others) in the early 2000s. In Russia, the most popular networks are VKontakte and Odnoklassniki. Social networks are visualized using social graphs. Graph theory provides main analysis tools for social networks. In particular, by calculating centrality measures for nodes and edges one may detect active participants (members) of a social network. We use for the analysis of social networks game-theoretic approach. We propose a new concept of the betweenness centrality for weighted graphs using the methods of cooperative game theory. The characteristic function is determined by special way for different coalitions (subsets of the graph). The betweenness centrality is determined as the Myerson value. The results of computer simulations for some examples of networks, in particular, for the popular social network “VKontakte”, as well as the comparing with the PageRank method are presented. Then we apply game-theoretic methods for community detection in networks. Finally, for approaches based on potential games we suggest a very efficient computational scheme using Gibbs sampling.

ABSTRACT. We study a form of capacity mechanism that combines capacity and supply auctions. We characterize how participants bid in this auction and show that, on a pay-as-bid basis, an equilibrium behavior gives Vickrey-Clarke-Groves (VCG) profits and achieves efficient outcomes when there is submodularity, which is in stark contrast with what in the existing literature — at equilibrium VCG payments achieve truthful bids and efficiency. We also provide some necessary and sufficient conditions for submodularity.