main-content

This book constitutes the refereed proceedings of the 9th International Conference on Optimization and Applications, OPTIMA 2018, held in Petrovac, Montenegro, in October 2018.The 35 revised full papers and the one short paper presented were carefully reviewed and selected from 103 submissions. The papers are organized in topical sections on mathematical programming; combinatorial and discrete optimization; optimal control; optimization in economy, finance and social sciences; applications.

### New Perspective on Slack Variables Applications to Singular Optimization Problems

This paper is devoted to a new approach for solving nonlinear programming (NLP) problems for which the Kuhn-Tucker optimality conditions system of equations is singular. It happens when the strict complementarity condition (SCC), a constrained qualification (CQ), and a second-order sufficient condition (SOSC) for optimality is not necessarily satisfied at a solution. Our approach is based on the construction of p-regularity and on reformulating the inequality constraints as equality. Namely, by introducing the slack variables, we get the equality constrained problem, for which the Lagrange optimality system is singular at the solution of the NLP problem in the case of the violation of the CQs, SCC and/or SOSC. To overcome the difficulty of singularity, we propose the p-factor method for solving the Lagrange system. The method has a superlinear rate of convergence under a mild assumption. We show that our assumption is always satisfied under a standard second-order sufficient optimality condition.

Yuri Evtushenko, Vlasta Malkova, Alexey Tret’yakov

### The Nearest Point Theorem for Weakly Convex Sets in Asymmetric Seminormed Spaces

Weakly convex sets in asymmetric seminormed spaces are considered. We prove that any point from some neighborhood of such a set has the unique nearest point in the set. The proof of the nearest point theorem is based on the theorem about the diameter of $$\varepsilon$$ -projection which is also important in approximation theory. The notion of weakly convex sets in asymmetric seminormed spaces generalizes known notions of sets with positive reach, proximal smooth sets, and prox-regular sets. By taking the Minkowski functional of the epigraph of some convex function as a seminorm, the results obtained for weakly convex sets can be applied to weakly convex functions whose graphs are weakly convex sets with respect to this seminorm.

Grigorii E. Ivanov, Mariana S. Lopushanski, Maxim O. Golubev

### A Modified Duality Method for Solving an Elasticity Problem with a Crack Extending to the Outer Boundary

A modified dual method for solving an elasticity problem with a crack extending to the outer boundary is considered. The method is based on a modified Lagrange functional. The convergence of the method is investigated in detail under a natural assumption of $$H^1$$ -regularity of the solution to the crack problem. Basic duality relation for the primal and dual problems is proposed.

Robert Namm, Georgiy Tsoy, Ellina Vikhtenko

### Subgradient Method with Polyak’s Step in Transformed Space

We consider two subgradient methods (methods A and B) for finding the minimum point of a convex function for the known optimal value of the function. Method A is a subgradient method, which uses the Polyak’s step in the original space of variables. Method B is a subgradient method in the transformed space of variables, which uses Polyak’s step in the transformed space. For both methods a proof of the convergence of finding the minimum point with a given accuracy by the value of the function was performed. Examples of ravine convex (smooth and non-smooth) functions are given, for which convergence of method A is slow. It is shown that with a suitable choice of the space transformation matrix method B can be significantly accelerated in comparison with method A for ravine convex functions.

Petro Stetsyuk, Viktor Stovba, Zhanna Chernousova

### Mirror Descent and Constrained Online Optimization Problems

We consider the following class of online optimization problems with functional constraints. Assume, that a finite set of convex Lipschitz-continuous non-smooth functionals are given on a closed set of n-dimensional vector space. The problem is to minimize the arithmetic mean of functionals with a convex Lipschitz-continuous non-smooth constraint. In addition, it is allowed to calculate the (sub)gradient of each functional only once. Using some recently proposed adaptive methods of Mirror Descent the method is suggested to solve the mentioned constrained online optimization problem with an optimal estimate of accuracy. For the corresponding non-Euclidean prox-structure, the case of a set of n-dimensional vectors lying on the standard n-dimensional simplex is considered.

Alexander A. Titov, Fedor S. Stonyakin, Alexander V. Gasnikov, Mohammad S. Alkousa

### Primal-Dual Newton’s Method with Steepest Descent for Linear Programming

The primal-dual method for solving linear programming problems is considered. In order to determine the search directions the non-perturbed system of optimality conditions is solved by Newton’s method. If this system is degenerate, then an auxiliary linear complementarity problem is solved for obtained unique directions. Starting points and all consequent points are feasible. The step-lengths are chosen from the steepest descent approach based on minimization of the dual gap. The safety factor is not introduced, and trajectories are allowed to move along the boundaries of the feasible sets. The convergence of the method at a finite number of iterations is proved.

### Sufficient Conditions of Polynomial Solvability of the Two-Machine Preemptive Routing Open Shop on a Tree

The routing open shop problem with preemption allowed is a natural combination of the metric TSP problem and the classical preemptive open shop scheduling problem. While metric TSP is strongly NP-hard, the preemptive open shop is polynomially solvable for any (even unbounded) number of machines. The previous research on the preemptive routing open shop is mostly focused on the case with just two nodes of the transportation network (problem on a link). It is known to be strongly NP-hard in the case of an unbounded number of machines and polynomially solvable for the two-machine case. The algorithmic complexity of both two-machine problem on a triangular network and a three-machine problem with two nodes are still unknown. The problem with a general transportation network is a generalization of the metric TSP and therefore is strongly NP-hard.We describe a wide polynomially solvable subclass of the preemptive routing open shop on a tree. This class allows building an optimal schedule with at most one preemption in linear time. For any instance from that class optimal makespan coincides with the standard lower bound. Therefore, the result, previously known for the problem on a link, is generalized on a special case on an arbitrary tree. The algorithmic complexity of the general case of the two-machine problem on a tree remains unknown.

Ilya Chernykh

### On Complexity and Exact Solution of Production Groups Formation Problem

The success of a modern enterprize is substantially determined by the effectiveness of staff selection and formation of various kinds of functional groups. Creation of such groups requires consideration of different factors depending on the activity of the groups. The problem of production groups formation, considered in this paper, asks for an assignment of workers to jobs taking into account the implicational constraints. The first result of the paper states the NP-hardness of the problem under consideration. The second result is a branch and bound method, which uses supplementary assignment problems for computing bounds. A software implementation of the algorithm is made, and a computational experiment is carried out, comparing the proposed algorithm with the CPLEX solver on randomly generated input data.

Anton Eremeev, Alexander Kononov, Igor Ziegler

### Time Complexity of the Ageev’s Algorithm to Solve the Uniform Hard Capacities Facility Location Problem

We show that the facility location problem with uniform hard capacities can be solved by the Ageev’s algorithm in $$O(m^3n^2)$$ time, where m is the number of facilities and n is the number of clients. This improves the results $$O(m^5 n^2)$$ of Ageev in 2004 and $$O(m^4n^2)$$ of Ageev, Gimadi, and Kurochkin in 2009.

Edward Kh. Gimadi, Anna A. Kurochkina

### An Exact Algorithm of Searching for the Largest Size Cluster in an Integer Sequence 2-Clustering Problem

A problem of partitioning a finite sequence of points in Euclidean space into two subsequences (clusters) maximizing the size of the first cluster subject to two constraints is considered. The first constraint deals with every two consecutive indices of elements of the first cluster: the difference between them is bounded from above and below by some constants. The second one restricts the value of a quadratic clustering function that is the sum of the intracluster sums over both clusters. The intracluster sum is the sum of squared distances between cluster elements and the cluster center. The center of the first cluster is unknown and determined as the centroid (i.e. as the mean value of its elements), while the center of the second one is zero.The strong NP-hardness of the problem is shown and an exact algorithm is suggested for the case of integer coordinates of input points. If the space dimension is bounded by some constant this algorithm runs in a pseudopolynomial time.

Alexander Kel’manov, Sergey Khamidullin, Vladimir Khandeev, Artem Pyatkin

### NP-hardness of Some Max-Min Clustering Problems

We consider some consimilar problems of searching for disjoint clusters in the finite set of points in Euclidean space. The goal is to maximize the minimum subset size so that the value of each intracluster quadratic variation would not exceed a given constant. We prove that all considered problems are NP-hard even on a line.

Alexander Kel’manov, Vladimir Khandeev, Artem Pyatkin

### Improved Polynomial Time Approximation Scheme for Capacitated Vehicle Routing Problem with Time Windows

The Capacitated Vehicle Routing Problem with Time Windows is the well-known combinatorial optimization problem having numerous valuable applications in operations research. In this paper, following the famous framework by M. Haimovich and A. Rinnooy Kan and technique by T. Asano et al., we propose a novel approximation scheme for the planar Euclidean CVRPTW. For any fixed $$\varepsilon >0$$ , the proposed scheme finds a $$(1+\varepsilon )$$ -approximate solution of CVRPTW in time $$TIME(\mathrm {TSP},\rho ,n)+O(n^2)+O\left( e^{O\left( q\,\left( \frac{q}{\varepsilon }\right) ^3(p\rho )^2\log (p\rho )\right) }\right) ,$$ where q is the given vehicle capacity bound, p is the number of time windows for servicing the customers, and $$TIME(\mathrm {TSP},\rho ,n)$$ is the time needed to find a $$\rho$$ -approximate solution for an auxiliary instance of the metric TSP.

Michael Khachay, Yuri Ogorodnikov

### Piecewise Linear Bounding Functions for Univariate Global Optimization

The paper addresses the problem of constructing lower and upper bounding functions for univariate functions. This problem is of a crucial importance in global optimization where such bounds are used by deterministic methods to reduce the search area. It should be noted that bounding functions are expected to be relatively easy to construct and manipulate with. We propose to use piecewise linear estimators for bounding univariate functions. The rules proposed in the paper enable an automated synthesis of lower and upper bounds from the function’s expression in an algebraic form. Numerical examples presented in the paper demonstrate the high accuracy of the proposed bounds.

Oleg Khamisov, Mikhail Posypkin, Alexander Usov

### The Scalability Analysis of a Parallel Tree Search Algorithm

Increasing the number of computational cores is a primary way of achieving high performance of contemporary supercomputers. However, developing parallel applications capable to harness the enormous amount of cores is a challenging task. Thus, studying the scalability of parallel algorithms (the growth order of the number of processors required to accommodate the growing amount of work, below we give a clear definition of the scalability investigated in our paper) is very important. In this paper we propose a parallel tree search algorithm aimed at distributed parallel computers. For this parallel algorithm, we perform a theoretical analysis of its scalability and show that the achieved scalability is close to the theoretical maximum.

Roman Kolpakov, Mikhail Posypkin

### Minimization of the Weighted Total Sparsity of Cosmonaut Training Courses

The paper is devoted to a cosmonaut training planning problem, which is some kind of resource-constrained project scheduling problem (RCPSP) with a new goal function. Training of each cosmonaut is divided into special courses. To avoid too sparse courses, we introduce a special objective function—the weighted total sparsity of training courses. This non-regular objective function requires the development of new methods that differ from methods for solving the thoroughly studied RCPSP with the makespan criterion. New heuristic algorithms for solving this problem are proposed. Their efficiency is verified on real-life data. In a reasonable time, the algorithms let us find a solution that is better than the solution found with the help of the solver CPLEX CP Optimizer.

Alexander Lazarev, Nail Khusnullin, Elena Musatova, Denis Yadrentsev, Maxim Kharlamov, Konstantin Ponomarev

### Genetic Local Search for Conflict-Free Minimum-Latency Aggregation Scheduling in Wireless Sensor Networks

We consider a Minimum-Latency Aggregation Scheduling problem in wireless sensor networks when aggregated data from all sensors are required to be transferred to the sink. During one time slot (time is discrete) each sensor can either send or receive one message or be idle. Moreover, only one message should be sent by each sensor during the aggregation session, and the conflicts caused by interference of radio waves must be excluded. It is required to find a min-length conflict-free schedule for transmitting messages along the arcs of the desired spanning aggregation tree (AT) with the root in the sink. This problem is NP-hard in a general case, and also remains NP-hard in a case when AT is given. In this paper, we present a new heuristic algorithm that uses a genetic algorithm and contains the local search procedures and the randomized mutation procedure. The extensive simulation demonstrates a superiority of our algorithm over the best of the previous approaches.

Roman Plotnikov, Adil Erzin, Vyacheslav Zalyubovskiy

### Numerical Implementation of the Contact of Optimal Trajectory with Singular Regime in the Optimal Control Problem with Quadratic Criteria and Scalar Control

Previous works by these authors offer the numerical method of successive approximations for developing the solutions of the problem of stabilization of nonlinear systems with standard functional. This paper considers applying this method for studying the problem with singular control. It is achieved by introducing an auxiliary problem. The solution for the auxiliary problem provides a smooth approximation to the solution of the initial problem. The paper presents the algorithms for constructing an approximate solution for the initial problem. It is demonstrated that unlike direct algorithms of optimal control, these algorithms allow registering the saturation point, thus enabling one to register and study singular regimes.

Alexander P. Afanas’ev, Sergei M. Dzyuba, Irina I. Emelyanova, Elena V. Putilina

### On the Stability of the Algorithm of Identification of the Thermal Conductivity Coefficient

The paper is devoted to the inverse problem of determining the thermal conductivity coefficient of substance depending on the temperature. The consideration is based on the first boundary value problem for the non-stationary heat equation. The mean-root-square deviation of the temperature distribution field and the heat flux on the boundary of the domain from the experimental data is used as the cost functional. The algorithm for the numerical solution of the problem based on the modern approach of Fast Automatic Differentiation was proposed by the authors in previous works. In the present paper, a numerical stability analysis of the obtained solutions is carried out. It is shown that the perturbation of the restored thermal conductivity coefficient is of the same order as the perturbation of the experimental data that caused it. Many illustrative examples are presented.

### On the Effectiveness of the Fast Automatic Differentiation Methodology

In this paper, we compare the three approaches for calculating the gradient of a complex function of many variables. The compared approaches are: the use of precise, analytically derived formulas; the usage of formulas derived with the aid of the Fast Automatic Differentiation methodology; the use of standard software packages that implement the ideas of Fast Automatic Differentiation methodology. Comparison of approaches is carried out with the help of a complex function that represents the energy of atoms system whose interaction potential is the Tersoff potential. As a comparison criterion, the computer time required to calculate the gradient of the function is used. The results show the superiority of the Fast Automatic Differentiation methodology in comparison with the approach using analytical formulas. Standard packages compute the function gradient around the same time as using the formula of the Fast Automatic Differentiation methodology.

Alla Albu, Andrei Gorchakov, Vladimir Zubov

### Numerical Damping of Forced Oscillations of an Elastic Beams

The beam oscillations are modeled by the fourth-order hyperbolic partial differential equation. The minimized functional is the energy integral of an oscillating beam. Control is implemented via certain function appearing in the right side of the equation. It was shown that the solution of the problem exists for any given damping time, but with decreasing this time, finding the optimal control becomes more complicated. In this work, numerical damping of beam oscillations is implemented via several fixed point actuators. Computational algorithms have been developed on the basis of the matrix sweep method and the second order Marquardt minimization method. To find a good initial approximation empirical functions with a smaller number of variables are used. Examples of damping the oscillations via a different number of actuators are given. It is shown that the amplitude of the oscillations of any control functions increases with the reduction of the given damping time. Examples of damping the oscillations in the presence of constraints on control functions are given; in this case, the minimum damping time exists. The damping of oscillations is considered also in the case when different combinations of actuators are switched on at different time intervals of oscillation damping.

Andrey Atamuratov, Igor Mikhailov, Nikolay Taran

### Solutions of Traveling Wave Type for Korteweg-de Vries-Type System with Polynomial Potential

This paper deals with the implementation of numerical methods for searching for traveling waves for Korteweg-de Vries-type equations with time delay. Based upon the group approach, the existence of traveling wave solution and its boundedness are shown for some values of parameters. Meanwhile, solutions constructed with the help of the proposed constructive method essentially extend the class of systems, possessing solutions of this type, guaranteed by theory. The proposed method for finding solutions is based on solving a multiparameter extremal problem. Several numerical solutions are demonstrated.

Levon A. Beklaryan, Armen L. Beklaryan, Alexander Yu. Gornov

### The Synthesis of the Switching Systems Optimal Parameters Search Algorithms

The problems of the optimal motion parameters search for generalized models of the dynamical systems are considered. The switching dynamic models taking into account action of non-stationery forces and optimality conditions are studied. The method for designing the dynamical models using polynomial regression is proposed. The optimal analytical solutions for some types of parametric curves are found. The algorithms of the optimal motion parameters search by means of the intelligent control methods are elaborated. The indicated algorithms and the software package allowed to execute a series of computational experiments and to carry out the stability analysis. The prospects of the results development in terms of generalization and modification of the models and the methods are presented. The results and the algorithms can be applied to the problems of automated transport design, robotics, and aircrafts motion control.

Olga Druzhinina, Olga Masina, Alexey Petrov

### Alternative Theorem for Differential Games with Strongly Convex Admissible Control Sets

A linear differential game with strongly convex admissible control sets and a smooth target set is considered. For such a differential game we obtain the alternative theorem. This theorem states that for any initial position either there is a program strategy of pursuer that guarantees the capture or there is a program strategy of evader that guarantees the evasion. This result is based on the commutativity of the Minkowski sum and difference for sets with special properties of strong and weak convexity in a Banach space.

Grigorii E. Ivanov, Maxim O. Golubev

### On Optimal Selection of Coefficients of Path Following Controller for a Wheeled Robot with Constrained Control

Stabilization of motion of a wheeled robot with constrained control resource by means of a continuous feedback linearizing the closed-loop system in a neighborhood of the target path is considered. The problem of selection of the feedback coefficients is set and discussed. In the case of a straight target path, the desired feedback coefficients are defined to be those that result in the partition of the phase plane into two invariant sets of the nonlinear closed-loop system while ensuring the greatest asymptotic rate of the deviation decrease. A hybrid control law is proposed that ensures the desired properties of the phase portrait and minimal overshooting and is stable to noise. The proposed techniques are extended to the case of circular target paths.

Alexander Pesterev

### The Space-Time Representation for Optimal Impulsive Control Problems with Hysteresis

An optimal control problem for a sweeping process driven by impulsive controls is considered. The control system we study is described by both a measure-driven differential equation and a differential inclusion. This system is the impulsive-trajectory relaxation of an ordinary control system with nonlinearity of hysteresis type, in which the hysteresis is modeled by the play operator and considered as a particular case of a nonconvex sweeping process. The concept of a sweeping process for the so-called graph completions of functions of bounded variation, defining the corresponding moving set, is developed. The space-time representation based on the singular space-time transformation and a method to obtain optimality conditions for impulsive processes are proposed. By way of motivation, an example from mathematical economics is considered.

Olga N. Samsonyuk

### Impulsive Relaxation of Continuity Equations and Modeling of Colliding Ensembles

The paper promotes a relatively novel class of multi-agent control systems named “impulsive” continuity equations. Systems of this sort, describing the dynamics of probabilistically distributed “crowd” of homotypic individuals, are intensively studied in the case when the driving vector field is bounded and sufficiently regular. We, instead, consider the case when the vector field is unbounded, namely, affine in a control parameter, which is only integrally constrained. This means that the “crowd” can be influenced by “shock” impacts, i.e., actions of small duration but very high intensity. For such control continuity equations, we design an impulsive relaxation by closing the set of solutions in a suitable coarse topology. The main result presents a constructive form of the relaxed system. A connection of the obtained results to problems of contact dynamics is also discussed along with applications to optimal ensemble control and other promising issues.

Maxim Staritsyn, Nikolay Pogodaev

### Analysis of Indicators of High-Technology Production Using Optimization Models, Taking into Account the Shortage of Working Capital

We present a new approach to an estimate of company’s value in the high-tech sector, based on the results of research of the mathematical model of production, taking into account the crediting of working capital in an unstable demand. The model is formalized in the form of the Bellman equation, which solution gives an estimate of the enterprise value depending on its performance indicators and external economic conditions. The method develops the income approach to an estimate of company’s value and takes into account the specifics of the economic regulation of production in the industry and provides an opportunity for an operative analysis of production indicators when external conditions change. The paper presents the results of analysis of the capitalization dynamics of the large Russian company Kamaz using the developed model. The results of the study of the modified model that takes into account the impact of the accumulated debt burden on the enterprise’s indicators are proposed. The solution of the corresponding Bellman equation makes it possible to estimate the magnitude of the critical debt of the company corresponding to the bankruptcy boundary and the debt accounting parameter for the bankruptcy of the company. In the paper, the properties of the company’s capitalization in terms of a model that takes into account the debt burden and infrastructure constraint are also given.

Damir Alimov, Nataliia Obrosova, Alexander Shananin

### Dynamic Marketing Model: Optimization of Retailer’s Role

We study a vertical control distribution channel in which a manufacturer sells a single kind of good to a retailer. The state variables are the cumulative sales and the retailer’s motivation. The manufacturer chooses wholesale price discount while retailer chooses pass-through. We assume that the wholesale price discount increases the retailer’s sale motivation thus improving sales. In contrast to previous settings, we focus on the maximization of retailer’s profit with respect to pass-through. The arising problem is linear with respect to both cumulative sales and the retailer’s motivation, while it is quadratic with respect to wholesale price discount and pass-through. We obtain a complete description of optimal strategies and optimal trajectories. In particular, we demonstrate that the number of switches for change in the type of optimal policy is no more than one.

### The Berge Equilibrium in Cournot Oligopoly Model

More than a hundred years ago, the first models of oligopolies were described. Modeling of oligopolies continues to this day in many modern papers. The main approach meets the concept of the Nash equilibrium and is actively used in modeling the behavior of players in a competitive market. The exact opposite of such “selfish” equilibrium is the “altruistic” concept of the Berge equilibrium. At the moment, many works are devoted to a Berge equilibrium. However, all of these items are limited to purely theoretical issues, or, in general, to psychological applications. Papers devoted to the study of Berge equilibrium in economic problems were not seen until now. In this paper, the Berge equilibrium is considered in the Cournot oligopoly, and its relationship to the Nash equilibrium is studied. Cases are revealed in which players gain more profit by following the concept of the Berge equilibrium, then by using strategies dictated by the Nash equilibrium.

Konstantin Kudryavtsev, Viktor Ukhobotov, Vladislav Zhukovskiy

### The Model of the Russian Banking System with Indicators Nominated in Rubles and in Foreign Currency

We propose a model of the Russian banking system. It is based on the problem of a macroeconomic agent “bank” which is modeled according to the principles of aggregated description, optimality, and perfect foresight. To derive the equations of the model, we use the original method of relaxation of complementary slackness conditions. The model successfully reproduces main indicators of the banking system, such as total loans, deposits, settlement accounts, reserves and profits nominated both in rubles and in foreign currency.

Nikolai Pilnik, Stanislav Radionov, Artem Yazikov

### Research on the Model of Population Groups Human Capital Dynamics

This article describes the dynamic optimization model with human capital as a group educational characteristic (along with these groups population) and as the main factor of their production. The main feature of this model is inequality in qualification which leads towards the run for the middle as unlinear dynamics of educational effectiveness for different groups. The research of the simulation model in one specific regime allowed to describe two different scenarios. They include the development of the groups and run for the middle dynamics. These results allow stating conceptual usability of the model for real society dynamics description.

Igor G. Pospelov, Ivan G. Kamenev

### Maximization of the Accumulated Extraction in a Gas Fields Model

A continuous dynamic long-term model of the gas fields group is considered. Two problems are set and solved: the problem of maximizing accumulated production for a gas fields group over a fixed period and the problem of maximizing the length of the general “shelf” for fields group. The problems proposed for the study belong to the class of optimal control problems with mixed constraints. The basic mathematical apparatus is Pontryagin’s maximum principle in Arrow’s form, in which Lagrange’s multipliers are applied. The obtained results are analyzed.

Alexander K. Skiba

### Estimation of Multiproduct Models in Economics on the Example of Production Sector of Russian Economy

The model of the real sector of the Russian economy is presented. It allows for the separate description of GDP and its components by expenditure both in constant and in current prices. Unlike standard macroeconomic models, the model proposed considers a set of Trader agents in addition to Producer agent. Traders are based on a set of CES-functions and allow to decompose the statistics available into a set of unobserved components. The Producer is based on a specific production function that performs well for Russian data and works with financial variables, such as credits and bank accounts. In contrary to the standard approach, the model is not linearized to get estimates of model parameters but is estimated directly using a set of nonlinear equations. The optimization is performed numerically and allows to get both series of unobserved model products and their prices and model parameters. The stability of the solution found is checked on simulated data.

Ivan Stankevich, Alexei Ujegov, Sergey Vasilyev

### Optimization of Transmission Systems for Chain-Type Markets

We consider a market for a homogeneous good with a chain-type transmission network. Every node corresponds to a local market with a perfect competition characterized by supply and demand functions. The initial transmission capacity, the cost of the capacity expansion and the unit transmission cost are given for every transmission line. The cost of the capacity expansion includes fixed and variable components. We examine the social welfare optimization problem for such a market. The welfare corresponds to the difference between the total consumption utility and the costs of production, transportation, and expansion of the transmission lines. Due to fixed costs of lines expansion, the problem is in general NP-hard with respect to the number of the nodes. We generalize the concept of supermodularity of the welfare function on the set of expanded lines and propose an algorithm for the solution of the problem. Results of computer simulation confirm the statistical efficiency of the algorithm.

Alexander Vasin, Nikita Tsyganov

### Hypoelastic Stabilization of Variational Algorithm for Construction of Moving Deforming Meshes

We suggest an algorithm for time-dependent mesh deformation based on the minimization of hyperelastic quasi-isometric functional. The source of deformation is time-dependent metric tensor in Eulerian coordinates. In order to attain the time continuity of deformation we suggest stress relaxation procedure similar to hypoelasticity where at each time step special choice of metric in Lagrangian coordinates eliminates internal stresses. Continuation procedure gradually introduces internal stresses back while forcing deformation to follow prescribed Eulerian metric tensor. At each step of continuation procedure functional is approximately minimized using few steps of preconditioned gradient search algorithm. Stress relaxation and continuation procedure are implemented as a special choice of factorized representation of Lagrangian metric tensor and nonlinear interpolation procedure for factors of this metric tensor. Thus we avoid solving time-dependent PDE for mesh deformation and under certain assumption guarantee that deformation from mesh on a one-time level to the next one converges to isometry when time step tending to zero.

### Approximate Coalitional Equilibria in the Bipolar World

We study a discrete model of jurisdiction formation in the spirit of Alesina and Spolaore [1]. A finite number of agents live along a line. They can be divided into several groups. If a group is formed, then some facility is located at its median and every member x of a group S with a median m pays $$\frac{1}{|S|}+|x-m|$$ .We consider the notion of coalitional stability: a partition is stable if no coalition wishes to form a new group decreasing the cost of all members. It was shown by Savvateev et al. [4] that no stable partition may exist even for 5 agents living at 2 points. We now study approximately stable partitions: no coalition wishes to form a new group decreasing all costs by at least $$\epsilon$$ .In this work, we define a relative measure of partition instability and consider bipolar worlds where all agents live in just 2 points. We prove that the maximum possible value of this measure is approximately $$6.2\%$$ .

Andrei Golman, Daniil Musatov