View: session overviewtalk overview

16:20 | Integer Linear Programming in Solving the Problem on Pour at the Mixing Department of the Steel Making Production PRESENTER: Varvara Rasskazova ABSTRACT. One of the most important stage of the steel making production is the preparation of the cast iron at the mixing department. The main problems at this stage are timely delivery of the cast iron to the convertor shop floor, as well as satisfaction of chemical requirements with respect to production orders. To satisfy chemical requirements one need to provide an optimal logistic process at mixing department. Indeed, for timely delivery of the cast iron to the convertor shop floor, there needs either prepare a cast iron with high quality by mixing with corresponding proportions, or provide preliminary processing of the cast iron using a special machine, which also needs an additional time resourses. Thus there occures an optimisation problem with complex objective of unloading railway carriages for ongoing delivery of cast iron from the furnace shop floor to the mixing department, as well as provide a mixing process with respect to constraints on both the weight of ladles and requirements on chemical quality corresponding to production orders. To solve a problem above there proposed an integer linear programming model, which corresponds in full to thechnological specific of mixing department processes at the steel making production. The powerful and effectiveness of the proposed model is proof by full-scale computational experiments on real-world data from mixing department of the convertor shop floor № 2 of the Novolipetsk Metallurgical Enterprise. |

16:35 | Genetic algorithm for the variable-sized vector bin-packing problem with limited number of bins ABSTRACT. In this paper, we consider a generalization of the well-known bin packing problem, in which several types of bins are given and the number of bins of each type is limited. Unlike the classic bin packing problem, this variant is not well represented in the literature, although it has a considerable practical value. For solving this problem, a genetic algorithm is proposed. It is based on a new representation scheme that uses first fit decreasing algorithm for decoding genotipes to solutions. The computational evaluation on the test instances have shown a competitive performance Variable sized bin packing \and Limited number of bins \and Genetic algorithm.of the proposed approach comparing to the heuristic algorithm previously known from the literature and Gurobi solver. |

16:50 | Uncertainty of clustering algorithms in random variables networks ABSTRACT. Cluster analysis is a powerful tool in network science and it is well developed in many directions. However, the uncertainty analysis of clustering algorithms is still not sufficiently investigated in the literature. Probabilistic approach to robust clustering based on the theory of labeled random point processes was proposed in (Dalton at al, 2018). In the present paper we propose to study uncertainty of clustering algorithms within the framework of the random variable network model (Kalyagin at al, 2020). This model can be considered as generalization of various network models: gene expression network, brain network, climate observation network, and stock market network. Random variables network model is a complete weighted graph, where the nodes are associated with components of a random vector X, and weights of edges are given by pair wise correlations between these components. Our research question is the following: given a sample of observations of the random vector X, and a clustering algorithm, evaluate uncertainty of identification of clusters by this algorithm in associated random variable network model. We use the concept of reference or true network and the concept of sample network (Kalyagin at al, 2020). Associated cluster structures will be called reference and sample cluster structures. Uncertainty of identification of the cluster structure will be measured by expected value of loss related with error of identification. To measure this loss we compare reference and sample cluster structures with the use of popular RAND index (this index measure a difference of two partitions of the set of nodes of graph). We study uncertainty of different clustering algorithms including single linkage hierarchical algorithm, spectral clustering algorithm, and others. Finally, we discuss an impact of uncertainty of clustering on portfolio optimization in stock market network (Tola at al., 2008). References: 1. Dalton LA, Benalcázar ME, Dougherty ER (2018) Optimal clustering under uncertainty. PLoS ONE 13(10): e0204627 2. Kalyagin V. A., Koldanov A. P., Koldanov P.A., Pardalos P.M. (2020) Statistical analysis of graph structures in random variable networks, Springer Brief in Optimization, Springer. 3. Tola, V., Lillo, F., Gallegati, M., & Mantegna, R. N. (2008). Cluster analysis for portfolio optimization. Journal of Economic Dynamics and Control, 32(1), 235-258. |

17:05 | Metaheuristic Approach to Spectral Reconstruction of Graphs ABSTRACT. Characterization of a graph by its spectrum is a very attractive research problem that has numerous applications. It is shown that the graph is not necessarily uniquely determined by its spectrum in the most general case, i.e., there could be several non-isomorphic graphs corresponding to the same spectrum. All such graphs are called cospectral. However, in most of the cases, it is important to find at least one graph whose spectrum is equal to a given constant vector. This process is called Spectral Reconstruction of Graph (SRG) and it is known as one of the most difficult optimization problems. We address the SRG problem by the metaheuristic methods, more precisely, by Basic Variable Neighborhood Search (BVNS) and improvement-based Bee Colony Optimization (BCOi) methods. The resulting heuristics are called SRG-BVNS and SRG-BCOi, respectively. Both methods are implemented in such a way to take into account the graph properties defined by its spectrum. We compare the performance of the proposed methods with each other and with the results obtained by other approaches from the relevant literature on the reconstruction of some well-known graphs. |

17:20 | Variable Neighborhood Search for Multi-label Feature Selection ABSTRACT. With the growing dimensionality of the data in many real-world applications, feature selection is becoming an increasingly important preprocessing step in multi-label classification. Finding a smaller subset of the most relevant features can significantly reduce resource consumption of model training, and in some cases, it can even result in a model with higher accuracy. Traditionally, feature selection has been done by employing some statistical measure to determine the most influential features, but in recent years, more and more metaheuristics have been proposed to tackle this problem more effectively. In this paper, we propose using the Basic Variable Neighborhood Search (BVNS) algorithm to search for the optimal subset of features, combined with a local search method based on mutual information. The algorithm can be considered a hybrid between the wrapper and filter methods, as it uses statistical knowledge about features to reduce the number of examined solutions during the local search. We compared our approach against Ant Colony Optimization (ACO) and Memetic Algorithm (MA), using the K-nearest neighbors classifier to evaluate solutions. The experiments conducted using three different metrics on a total of four benchmark datasets suggest that our approach outperforms ACO and MA. |

17:35 | Performance Evaluation of Genetic Algorithm Based on Idempotent Algebra Methods for RCPSP ABSTRACT. This paper considers the problem of scheduling an investment project with constrained resources and the criterion of maximizing the net present value. All resources in the model are represented in monetary form. The project budget, as well as income from the reinvestment of profits are the source of cost coverage. We propose a modification of the previously developed genetic algorithm based on the methods of idempotent algebra to solve the problem. The paper shows that the RCSP problem can be formulated in terms of zero-one linear programming; therefore, to find its exact solution, the IBM ILOG CPLEX software package is used. Since this problem is NP-hard, as the number of model variables increases, the capabilities of the CPLEX package are limited. Under these conditions, it is advisable to use a genetic algorithm. Computational experiments were carried out to prove the effectiveness of the genetic algorithm. The results of the work of the modified genetic algorithm are analyzed depending on the initial data of the model, as well as, in comparison with the CPLEX package. Such parameters of the algorithm as the number of activities, the characteristics of cash flows, the size of the population, and the number of generations are taken into account. The algorithm has demonstrated high performance in finding exact solutions to the problem. |

17:50 | Approach to Text Data Clustering Based on Molecular Chemical Reactions ABSTRACT. Text data clustering is one of the problems of information retrieval. The purpose of cluster analysis of text data is to detect groups of semantically similar documents among a collection of given text data without predefined categories (characteristics) of grouping. In the literature, there are many scientific approaches to text data clustering, for example, the k-means local search algo-rithm is widely used. The paper proposes an algorithm for clustering text data using the k-means algorithm combined with molecular chemical reactions. By molecular structure we mean a possible solution to text data clustering, by op-timizing the molecular chemical reactions we mean optimizing the results of text data clustering (search for a global optimal solution). The solution obtained with k-means is used as an initial molecular structure solution to optimize chemical reactions in combination with k-means by generating new solutions: single-molecule collision, single-molecule decomposition, intermolecular collision, and intermolecular synthesis. The computational experiment showed the comparative efficiency of the proposed algorithm, taking into account numerical metrics: accuracy, precision, recall, and F-measure. |

18:05 | A faster algorithm for counting of the integer points in $\Delta$-modular polyhedra ABSTRACT. Let $\PC$ be a polyhedron, defined by a system $A x \leq b$, where $A \in \ZZ^{m \times n}$, $\rank(A) = n$, and $b \in \ZZ^{m}$. In the Integer Feasibility Problem, we need to decide whether $\PC \cap \ZZ^n = \emptyset$ or to find some $x \in \PC \cap \ZZ^n$ in the opposite case. Currently, its state of the art algorithm, due to \cite{DadushDis,DadushFDim} (see also \cite{Convic,ConvicComp,DConvic} for more general formulations), has the complexity bound $O(n)^n \cdot \poly(\phi)$, where $\phi = \size(A,b)$. It is a long-standing open problem to break the $O(n)^n$ dimension-dependence in the complexity of ILP algorithms. We show that if the matrix $A$ has a small $l_1$ or $l_\infty$ norm, or $A$ is sparse and has bounded elements, then the integer feasibility problem can be solved faster. More precisely, we give the following complexity bounds \begin{gather*} \min\{\|A\|_{\infty}, \|A\|_1\}^{5 n} \cdot 2^n \cdot \poly(\phi),\\ \bigl( \|A\|_{\max} \bigr)^{5 n} \cdot \min\{\colSparse(A),\rowSparse(A)\}^{3 n} \cdot 2^n \cdot \poly(\phi). \end{gather*} Here $\|A\|_{\max}$ denotes the maximal absolute value of elements of $A$, $\colSparse(A)$ and $\rowSparse(A)$ denote the maximal number of nonzero elements in columns and rows of $A$, respectively. We present similar results for the integer linear counting and optimization problems. Additionally, we apply the last result for multipacking and multicover problems on graphs and hypergraphs, where we need to choose a minimal/maximal multiset of vertices to cover/pack the edges by a prescribed number of times. For example, we show that the stable multiset and vertex multicover problems on simple graphs admit FPT-algorithms with the complexity bound $2^{O(|\VC|)} \cdot \poly(\phi)$, where $\VC$ is the vertex set of a given graph. |

18:20 | Application of the second-order optimization methods to the stochastic programming problems with quantile function ABSTRACT. We consider the application of the second-order optimization algorithms for stochastic optimization problems with the quantile function as the objective function. To apply these methods, we consider approximations of the probability and quantile functions and their derivatives. The idea of the approximation lies in the replacement of the Heaviside function with the sigmoid function. Previously we showed that approximated probability and quantile functions along with their derivatives converge to the exact ones. Furthermore, it has been shown that the usage of the first-order and second-order optimization methods for problems with the probability function as a criterion leads to a good approximation of the optimal control vector and the optimal value of the target function. In this research, the direct formulas for the second-order derivatives of the approximated quantile function with respect to the elements of the control vector are provided. Also, we consider some numerical examples of problems with quantile function as a criterion. The proof of convergence of the second-order derivatives is not considered in this research. Possible applications of such approximations include the development of the new numerical algorithms for solving stochastic optimization problems, and new algorithms to determine the surface level of the quantile function. |