ABSTRACT. We consider the expected runtime of non-elitist evolutionary algorithms (EAs), when they are applied to a family of fitness functions with a plateau of second-best fitness in a Hamming ball of radius r around a unique global optimum. On one hand, using the level-based theorems, we obtain polynomial upper bounds on the expected runtime for some modes of the non-elitist EA based on an unbiased mutation and the bitwise mutation in particular. On the other hand, we show that the EA with fitness proportionate selection is inefficient if the bitwise mutation is used with the standard settings of mutation probability.

ABSTRACT. In this paper we study the inversion of discrete functions associated with some hard combinatorial problems. Inversion of such a function is considered in the form of a special variant of the well-known MaxSAT problem. To solve the latter we apply the previously developed local search method based on the Merging Variables Principle (MVP). The main novelty is that we combine MVP with evolutionary strategies to leave local extrema generated by Merging Variable Hill Climbing algorithm. The results of computational experiments show the effectiveness of the proposed technique in application to inversion of several cryptographic hash functions and to one problem of combinatorial optimization, which is a variant of the Facility Location Problem.

ABSTRACT. Progress in the development of methods of location theory and methods of automatic grouping of objects and data, the most popular of which are based on solving p-median and similar problems (k-means, k-medoid), is mainly aimed at increasing the speed of algorithms, accuracy and stability of their results. For the global search problems in these fields, the researchers' efforts are focused on the development of compromise heuristic algorithms that provide a fairly quick solution with minimal error. The Genetic Algorithms with greedy agglomerative crossover procedure and other special genetic algorithms for the considered problems demonstrate the best values of the objective function (sum of distances or squared distances) for many practically important problems. Traditionally, such algorithms do not use the mutation operator [1, 2]. In this work, we propose new genetic algorithms for the k-means problem (GA-k-means) [2] with an original idea of the mutation operator. The crossover procedure applied to a randomly generated solution is used as the mutation operator. Analogous idea was used in the variable neighborhood search algorithms with special randomized neighborhoods [3]. In this work, we conducted the computational experiments of the classical genetic algorithms for the k-means problem, and the genetic algorithms two types of mutation operators. The first one is known as the Uniform random mutation [4]. In the second case, we considered our Crossover-like mutation. The experiments were conducted on classical data sets from repositories and on the results of non-destructive testing of prefabricated production batches of electronic radio components, carried out in a specialized test center. The comparison results show that the idea of including our new mutation operator in the GA improves significantly the results of the simplest GA for the k-means problem. For the most precise genetic algorithms with greedy agglomerative crossover operators [2], the advantage of our new mutation operator is not so evident; however, it is still statistically significant, especially for larger problems.

1. Alp O., Erkut E., Drezner Z. An Efficient Genetic Algorithm for the p-Median Problem. Annals of Operations Research. 2003, 122: 21-42. DOI:10.1023/A:1026130003508 2. Kazakovtsev L., Antamoshkin A. Genetic Algorithm with Fast Greedy Heuristic for Clustering and Location Problems. Informatica. 2014, 38: 229–240 3. Rozhnov I.P., Orlov V.I., Kazakovtsev L.A. VNS-Based Algorithms for the Centroid-Based Clustering Problem. Facta Universitatis series Mathematics and Informatics. 2019, 34(5): 957-972 3. Kim K.-j., Ahn H. A recommender system using GA K-means clustering in an online shopping market. Expert Systems with Applications. 2008, 34(2):1200-1209

ABSTRACT. Algorithms for finding a minimum of unimodal functions are proposed. Their software implementation in uniform standards within the framework of the library has been completed. Their deep comparative testing was carried out using separable and quasi-separable functions, Chebyshev oscillators, Rosenbrock-Skokov functions and others with the number of variables from 5 to 500 thousand. The areas of their rational employment are identified and the features of convergence are investigated. As a result of a series of computational experiments, we formulated the advantages and disadvantages of the developed algorithms, the most effective software implementations for the studied class of problems have been found.

This work was partly supported by Russian Foundation for Basic Research, grant No 18-07-00587.

ABSTRACT. In this paper, we construct an uncertain penalized semi-infinite optimization problem (USIOP)ρ associated with the uncertain semi-infinite optimization problem (USIOP) by using the exact l1 penalty function method. Then, we show that (USIOP) and (USIOP)ρ attain their robust optimality at the same point. Further, we discuss the robust saddle-point criteria of (USIOP) and established the relationship between the robust saddle-point to (USIOP) and robust minimizer to (USIOP)ρ. Moreover, we give some nontrivial examples which are modeled by the uncertain semi-infinite optimization problem to verified the established results.

ABSTRACT. Further development of an original approach to the equilibrium problem in a linear exchange model and its variations is presented. The conceptual basis of the approach is polyhedral complementarity. The original problem is reduced to a fixed point problem of a piecewise constant point-to-set mapping on the price simplex. The mapping is invertible and a fixed point of the inverse mapping provides the equilibrium prices too. For the model with fixed budgets (Fisher model), the emerging mapping is a potential one and this provides a new reduction of the equilibrium problem to an optimization problem, which differs from the well-known Eisenberg-Gale reduction. The inverse mapping allows us to obtain a dual version of the reduction. The two obtained optimization problems are in duality similar to linear programming problems. The report will present explicit formulations of dual problems for the Fisher model and its two generalizations: a model with spending constraints and a generalized Fisher model. The obtained explicit formulation for the Fisher model makes it possible to clarify the connection of the approach with Eisenberg-Gale result. An optimization problem is also presented for the general linear exchange model.

ABSTRACT. In this paper, we are motivated by two important applications: entropy-regularized optimal transport problem and road or IP traffic demand matrix estimation by entropy model. Both of them include solving a special type of optimization problem with linear equality constraints and objective given as a sum of an entropy regularizer and a linear function. It is known that the state-of-the-art solvers for this problem, which are based on Sinkhorn's method (also known as RSA or balancing method), can fail to work, when the entropy-regularization parameter is small. We consider the above optimization problem as a particular instance of a general strongly convex optimization problem with linear constraints. We propose a new algorithm to solve this general class of problems. Our approach is based on the transition to the dual problem. First, we introduce a new accelerated gradient method with adaptive choice of gradient's Lipschitz constant. Then, we apply this method to the dual problem and show, how to reconstruct an approximate solution to the primal problem with provable convergence rate. We prove accelerated rate both for the absolute value of the primal objective residual and constraints infeasibility. Our method has similar to Sinkhorn's method complexity of each iteration, but is faster and more stable numerically, when the regularization parameter is small. We illustrate the advantage of our method by numerical experiments for the two mentioned applications. We show that there exists a threshold, such that, when the regularization parameter is smaller than this threshold, our method outperforms the Sinkhorn's method in terms of computation time.

ABSTRACT. This paper considers an assessment and evaluation of the pronunciation quality in computer-aided language learning systems. We propose the novel distortion measure for speech processing by using the gain optimization of the symmetrized Itakura-Saito divergence between phonemes. This dissimilarity is implemented in a complete algorithm for pronunciation learning and improvement. At its first stage a user has to achieve a stable pronunciation of all sounds by using phonetic database from an ideal speaker. At the second stage, the recognition of phonemes and their short sequences is carried out to guarantee the distinguishability of learned sounds. Here the training set may contain not only ideal phones but the best sounds of a user obtained at the previous step. Finally, the word recognition accuracy is tested by using deep neural networks fine-tuned on the best words from a user. Experimental study shows that the proposed procedure makes it possible to achieve high efficiency for learning of sounds and their sequences even in the presence of noise in the observed utterance.

ABSTRACT. The securities settlement process consists in delivering securities from one financial actor to another in exchange for payment in currency. Each business day has a night-time settlement (NTS) period when transactions (exchange of cash and/or security for payment) are settled in batches. Banque de France is inter alia in charge of Mathematical Optimization Module (MOM) for the NTS period which is a component of a large European platform. To reduce the number of failed transactions some additional financial features can be triggered, such as partial settlement of eligible transactions and provision of credit (auto-collateralisation mechanism). MOM must settle as many transactions as possible respecting all business constraints and taking advantage of these financial features. Furthermore, MOM execution time is limited, the data size is large (several hundred thousands of transactions over a billion euro) and the number of transactions and their amounts require high numerical precision. In this work we introduce the necessary financial notions, explain the NTS process and formulate it as a discrete optimisation model. We expose heuristic, mixed integer and linear programming algorithmic approaches used to solve this large-scale problem. We present results obtained on production data and discuss some perspectives.

ABSTRACT. The analysis of infinitesimal quantities allows us to expand the function of one variable in a generalized Taylor series without using derivatives. By this algorithm, we expand a function with several variables in an arbitrary direction at a given point. Then we choose arbitrary directions in the polar coordinate system. Coefficients of expanded monomials form the surfaces associated with the selected point. The article gives analytical trigonometric formulas for these surfaces in polar coordinate system. Coefficient surfaces for orders of smallness 1 and 2 play the role of gradients and Hessians. Surfaces for higher orders of smallness act as tensors and are rarely used in optimization methods. A new optimality criterion is formulated using coefficient surfaces.

ABSTRACT. In recent years, sequential optimality conditions are frequently used for convergence of iterative methods to solve nonlinear constrained optimization problems. The sequential optimality conditions do not require any of the constraint qualications. In this paper, We present the necessary sequential complementary approximate Karush Kuhn Tucker (CAKKT) condition for a point to be a solution of a nonlinear optimization problem. The nonlinear optimization problem is associated with the variational inequality problem. We also extend the complementary approximate Karush Kuhn Tucker condition from scalar optimization problem to multiobjective optimization problem and associated with the vector variational inequality problem. Further, we prove that with some extra conditions of convexity and affinity, complementary approximate Karush Kuhn Tucker conditions are sufficient for the variational inequality problem and vector variational inequality problem. Finally, we verify our results via illustrative examples. An example shows that a point which is a solution of variational inequality problem is also a CAKKT point.

ABSTRACT. Interval optimization problems are closely related to the inexact data in real life engineering and economic problems. The talk aims to discuss the KKT optimality conditions for a class of multivalued interval valued fractional optimization problems. The definations of LU-V-invex and LS-V-invex for the considered multivalued fractional interval problem have been introduced. The concept of LU/LS-Pareto optimality for the problem have also been illustrated with adequate examples.

The main purpose of the present article is to study the Karush-Kuhn-Tucker optimality condition for a class of a fractional interval multivalued programming problem. For the solution concept, LU and LS-Pareto optimality are discussed, and some nontrivial examples are illustrated. The concepts of LU-V-invex and LS-V-invex for a fractional interval problem are introduced and using these assumptions, the Karush-Kuhn-Tucker optimality conditions for the problem have been established. Non-trivial examples are discussed throughout to make a clear understanding of the results established.

ABSTRACT. It is proposed an algorithm to construct a decision rule for solving multiclass pattern recognition problems based on using a convex hulls approach. The main idea of the proposed approach is to construct a convex hulls based on subsets of vectors from training sample so that every such a convex hull contains vectors only from one class. We determine special class of multiclass pattern recognition problems where the sequence of classes could be fixed for which convex hull for vectors from every class in this sequence do not contain vectors from the next classes following after this class in sequence. Such a problem, when training sample satisfy conditions mentioned above, is called as convex separable set solvable (CSS-solvable problem). Computational results carried out using proposed approach show that a number of classic pattern recognition problems are CSS-solvable. It is shown that well known Irises Fischer problem is CSS-solvable one. At the same time a decision rule obtained using proposed approach, provides such a classification of the training sample, which corresponds to the best known solution. This non trivial fact allows one to expect a high efficiency of the proposed approach in real applications. The algorithm for constructing the decision rule based on convex hulls approach is proposed in general case when the problem is not CSS-solvable. The computational aspects of constructing decision rule are discussed. For the construction of family of facets of convex hull of set of vectors, the new approach is proposed which eliminates searching the subsets of this set. In the first step it is used well known Gale transformation for sequence of vectors and in the second step is S.N. Chernikov’s method is used to construct (without searching) minimal infeasible systems of an infeasible system of linear inequalities. It was determined in [1] dual relationship between facets of a convex polytop and minimal infeasible systems of a corresponding infeasible system of linear inequalities. It should be also mentioned that applied interest of the obtained results is also in regards to industrial problems as a metallurgical production. One interesting problem in such production is to increase the efficiency of production by reassignment or complete termination of unfavorable technological routes. References [1] Gainanov D.N. Graphs for Pattern Recognition. Infeasible Systems of Linear Inequalities. DeGruyter, 2016. 152 pp. ISBN 978-3-11-048106-8.

ABSTRACT. The interpretation of the biological mechanisms through the systems biology approach involves the representation of the molecular components in an integrated system, namely a network, where the interactions among them are much more informative than the single components. The denition of the dissimilarity between complex biological networks is fundamental to understand dierences between conditions, states, and treatments. It is, therefore, challenging to identify the most suitable distance measures for this kind of analysis. In this work, we aim at testing several measures to dene the distance among sample- and condition-specic metabolic networks. The networks are represented as directed, weighted graphs, due to the nature of the metabolic reactions. We used four dierent case studies and exploited SVM classication to dene the performance of each measure.

ABSTRACT. We consider the multiple line detection problem by using the center-based clustering approach, and propose a new incremental method based on iterative reweighted approach. We prove the convergence theorem, and construct an appropriate algorithm which we test on numerous artificial data sets. Stopping criterion in the algorithm is defined by using the parameters from DBSCAN algorithm. We give necessary conditions for the most appropriate partition, which have been used during elimination of unacceptable center-lines that appear in the output of the algorithm. The algorithm is also illustrated on a real-world image coming from Precision Agriculture.

ABSTRACT. Publications on the two-stage scheduling systems such as two-machine flow shops, job shops and open shops, single machine with coupled tasks, and their various generalisations constitute a significant part of the scheduling literature. Many of these publications consider a limited storage (buffer) or an additional limited resource. The majority of publications on scheduling with a buffer consider the buffer as storage that limits the number of jobs that have completed their first operation and are waiting for the commencement of the second one. The majority of scheduling models with an additional resource assume that the resource is used only during the processing on a machine. Despite numerous possible applications that include, for example, supply chains, multimedia systems and data gathering networks, much less research has been done on the models where the resource (storage space, buffer) is allocated to a job from the start of its first operation till the end of its second operation and where the storage requirement varies from job to job. The talk presents a survey of recent publications on this type of scheduling problems, which includes NP-hardness proofs, particular cases amenable for polynomial-time algorithms, polynomial approximation schemes, and integer programming based algorithms, including for example Lagrangian relaxation.

ABSTRACT. The irregular tiling of polyominoes has applications in different fields, for example, in sampling with blue-noise properties, variety of computer graphics problems such as anti-aliasing, rendering, geometry processing, and engineering problems like phased array antennas design. Our approach considers an Integer Linear Programming formulation of a polyomino tiling. The model for tiling with two kinds of shapes: L-tromino and L-tetromino, is proposed. Computational experiments conducted using IBM ILOG CPLEX package are presented in the paper showing the effectiveness of the proposed approach.

ABSTRACT. We consider the traveling salesperson problem in a directed graph. The pyramidal tours with steps back are an extension of the classic pyramidal tours and form the special class of Hamiltonian tours for which the traveling salesperson problem is solved by dynamic programming in polynomial time. The polytope of pyramidal tours with step-backs PSB(n) is defined as the convex hull of the characteristic vectors of all possible pyramidal tours with step-backs in a complete directed graph. The 1-skeleton of PSB(n) is the graph whose vertex set is the vertex set of PSB(n) and the edge set is the set of geometric edges or one-dimensional faces of PSB(n). We present a linear-time algorithm to verify vertex adjacencies in 1-skeleton of the polytope PSB(n) and estimate the characteristics of 1-skeleton: the diameter is bounded above by 4 and the clique number grows as Θ(n²).

ABSTRACT. We study the proximity of the optimal value of the m-dimensional knapsack problem to the optimal value of that problem with additional restriction that only one coordinate can have a non-zero value. We derive exact and asymptotic formulas for the precision of such approximation. In particular, we prove that the precision tends to 0.59136.../m if n → ∞ and m is fixed. Also, we give the class of the worst multi-dimensional knapsack problems for which the bound is attained. Previously, similar results were obtained only if m = 1.

ABSTRACT. In this study we consider the shortest path problem, where the arc costs are subject to distributional uncertainty. Basically, the decision-maker attempts to minimize her worst-case expected loss over an ambiguity set (or a family) of candidate distributions that are consistent with the decision-maker's initial information. The ambiguity set is formed by all distributions that satisfy prescribed linear first-order moment constraints with respect to subsets of arcs and individual probability constraints with respect to particular arcs.

In contrast to the related studies, our distributional constraints can be designed from incomplete and partially observable data. Under some additional assumptions the resulting distributionally robust shortest path problem (DRSPP) admits equivalent robust and mixed-integer programming (MIP) reformulations. The robust reformulation is shown to be strongly NP-hard, whereas the problem without the first-order moment constraints is proved to be polynomially solvable. We perform numerical experiments to illustrate the advantages of the proposed approach; we also demonstrate that the MIP reformulation of DRSPP can be solved reasonably fast using off-the-shelf solvers.

ABSTRACT. For a reduction in environmental pollution and dependency on petroleum, electric vehicles (EV) present an advantageous alternative to traditionally fossil-fuel powered automobiles. Rapid growth in the number of EVs requires an urgent need to develop an adequate charging station infrastructure to stimulate and facilitate their usage. Due to restricted investments in the development of a sufficient infrastructure, locations have to be chosen deliberately.

In this paper several extensions considering different objectives and various constraints to the deterministic flow refuelling location problem (DFRLP), described by de Vries and Duijzer (2017), are introduced, described and implemented. Furthermore, the model extensions are analysed using randomly generated problem instances. The research shows that, when considering location-dependent costs, results heavily depend on the relation of said cost differences. Tests for different cost scenarios are carried out and policy implications are discussed.

The basic DFRLP, which is proven to be strongly NP-hard, assumes that the availability of a single charging station is sufficient to refuel all flows using it, regardless of the EVs number, which wants to be refuelled there and their distance travelled since the last refuelling process. Furthermore, increasing acceptance of EVs requires the consideration of restricted capacity at charging stations. Capacity is defined by calculating the energy demand at a charging station for each EV and therefore simultaneously taking decisions concerning the placement and size of stations. We also discuss the influence of failure probabilities at potential facility locations while deploying an infrastructure in order to guarantee a minimum path reliability for a certain number of EVs.

ABSTRACT. The linear second-order cone programming problem is considered. For its solution dual Newton's methods are proposed. These methods are constructed with the help of optimality conditions. The nonlinear system of equations, obtained from the optimality conditions and depended only from dual variables, is solved by the Newton method. Under assumption that there exist strictly complementary solutions of both primal and dual problems the local convergence of the methods with super-linear rate is proved.

ABSTRACT. The paper examines an algorithm for finding approximate sparse solutions of convex cardinality constrained optimization problem in Hilbert spaces. The proposed algorithm uses the penalty decomposition approach and solves sub-problems on each iteration approximately. We examine the convergence of the algorithm to a stationary point satisfying necessary optimality conditions. Unlike other similar works, this paper discusses the properties of PD algorithms in infinite-dimensional (Hilbert) space. The results showed that the convergence property obtained in previous works for cardinality constrained optimization in Euclidean space also holds for infinite-dimensional (Hilbert) space. Moreover, in this paper we established a similar result for convex optimization problems with cardinality constraint with respect to a dictionary (not necessarily the basis in H)

ABSTRACT. We suggest a modified descent splitting method for optimization problems having a special decomposable structure. The proposed modification maintains the basic convergence properties but enables one to reduce computational efforts per iteration and to provide computations in a distributed manner. On the one hand, it consists in component-wise choice of descent directions together with a special threshold control. On the other hand, it involves a simple adaptive step-size choice, which takes into account the problem behavior along the iteration sequence. Preliminary computational tests confirm the efficiency of the proposed modification.

ABSTRACT. The general-purpose optimization software has never been more powerful than today. It is universal, customizable, controllable, and enables a user with a variety of tools and features to get better solutions in a shorter time. In this tutorial, we will overview the ingredients of one of the fastest MIP solvers, the Gurobi optimizer, that are relevant in academic studies. The key topics would be the internal organization of the solver, its tuning when solving LPs and MIPs, the most newly added features, and other selected ones.

ABSTRACT. Many systems have to be maintained while the underlying constraints, costs and/or profits change over time. Although the state of a system may evolve during time, a non-negligible transition cost is incurred for transitioning from one state to another. In order to model such situations, Gupta et al. (ICALP 2014) and Eisenstat et al. (ICALP 2014) introduced a multistage model where the input is a sequence of instances (one for each time step), and the goal is to find a sequence of solutions (one for each time step) that are both (i) near optimal for each time step and (ii) as stable as possible. In this talk, we will give a survey of recent results in algorithmic multistage optimization, both in the offline and the online contexts and we will discuss connections with other models taking into account the evolution of data during time.