检索结果-内蒙古大学图书馆

Pattern-based heuristic for the cell formation problem in group technology

学校读者我要写书评

暂无评论

Pattern-based heuristic for the cell formation problem in gr...

作者： Batsyn, Mikhail Bychkov, Ilya Goldengorin, Boris Pardalos, Panos Sukhov, Pavel Laboratory of Algorithms and Technologies for Network Analysis The National Research University Higher School of Economics 136 Rodionova Street Nizhny Novgorod Russian Federation 603093 Russia Center of Applied Optimization University of Florida 401 Weil Hall 116595 Gainesville FL 32611-6595 United States

ISBN: (纸本)9781461455738

In this chapter we introduce a new pattern-based approach within the linear assignment model with the purpose to design heuristics for a combinatorial optimization problem (COP). We assume that the COP has an additive (separable) objective function and the structure of a feasible (optimal) solution to the COP is predefined by a collection of cells (positions) in an input file. We define a pattern as a collection of positions in an instance problem represented by its input file (matrix). We illustrate the notion of pattern by means of some well-known problems in COP, among them are the linear ordering problem (LOP) and cell formation problem (CFP), just to mention a couple. The CFP is defined on a Boolean input matrix, the rows of which represent machines and columns - parts. The CFP consists in finding three optimal objects: a block-diagonal collection of rectangles, a row (machines) permutation, and a column (parts) permutation such that the grouping efficacy is maximized. The suggested heuristic combines two procedures: the pattern-based procedure to build an initial solution and an improvement procedure to obtain a final solution with high grouping efficacy for the CFP. Our computational experiments with the most popular set of 35 benchmark instances show that our heuristic outperforms all well-known heuristics and returns either the best known or improved solutions to the CFP. © Springer Science+Business Media New York 2013.

关键词： Cytology

Preferences prediction using a gallery of mobile device based on scene recognition and object detection

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Savchenko, Andrey A.V. Demochkin, K.V. Grechikhin, I.S. HSE University Laboratory of Algorithms and Technologies for Network Analysis Nizhny Novgorod Russia St. Petersburg Department of Steklov Institute of Mathematics Samsung-PDMI Joint AI Center St. Petersburg Russia

In this paper user modeling task is examined by processing a gallery of photos and videos on a mobile device. We propose novel engine for user preference prediction based on scene recognition, object detection and facial analysis. At first, all faces in a gallery are clustered and all private photos and videos with faces from large clusters are processed on the embedded system in offline mode. Other photos may be sent to the remote server to be analyzed by very deep models. The visual features of each photo are obtained from scene recognition and object detection models. These features are aggregated into a single user descriptor in the neural attention block. The proposed pipeline is implemented for the Android mobile platform. Experimental results with a subset of Photo Event Collection, Web Image Dataset for Event Recognition and Amazon Fashion datasets demonstrate the possibility to process images very efficiently without significant accuracy degradation. The source code of Android mobile application is publicly available at https://***/hse-asavchenko/*** Codes 68T10 Copyright © 2019, The Authors. All rights reserved.

关键词： Object recognition

Heuristic for maximizing grouping efficiency in the cell formation problem 1

学校读者我要写书评

暂无评论

6th International Conference on network analysis, NET 2016

作者： Bychkov, Ilya Batsyn, Mikhail Pardalos, Panos M. Laboratory of Algorithms and Technologies for Network Analysis National Research University Higher School of Economics 136 Rodionova Street Nizhny Novgorod603093 Russia Center for Applied Optimization University of Florida 401 Weil Hall P.O. Box 116595 Gainesville32611-6595 United States

ISBN: (数字)9783319568294

ISBN: (纸本)9783319568287

In our paper, we consider the Cell Formation Problem in Group Technology with grouping efficiency as an objective function. We present a heuristic approach for obtaining high-quality solutions of the CFP. The suggested heuristic applies an improvement procedure to obtain solutions with high grouping efficiency. This procedure is repeated many times for randomly generated cell configurations. Our computational experiments are performed for popular benchmark instances taken from the literature with sizes from 10×20 to 50×150. Better solutions unknown before are found for 23 instances of the 24 considered. The preliminary results for this paper are available in Bychkov et al. (Models, algorithms, and technologies for network analysis, Springer, NY, vol. 59, pp. 43–69, 2013, [7]). © Springer International Publishing AG 2017.

关键词： Benchmarking

Detection of Sensitive Textual Information in User Photo Albums on Mobile Devices

学校读者我要写书评

暂无评论

Detection of Sensitive Textual Information in User Photo Alb...

IEEE Region 8 International Conference on Computational technologies in Electrical and Electronics Engineering, SIBIRCON

作者： Evgeny Myasnikov Andrey Savchenko Samara University Samara Russia Laboratory of Algorithms and Technologies for Network Analysis National Research University Higher School of Economics Nizhny Novgorod Russia

关键词：

An efficient exact model for the cell formation problem with a variable number of production cells

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Bychkov, Ilya Batsyn, Mikhail Laboratory of Algorithms and Technologies for Network Analysis National Research University Higher School of Economics 136 Rodionova Nizhniy Novgorod603093 Russia

The Cell Formation Problem has been studied as an optimization problem in manufacturing for more than 90 years. It consists of grouping machines and parts into manufacturing cells in order to maximize loading of cells and minimize movement of parts from one cell to another. Many heuristic algorithms have been proposed which are doing well even for large-sized instances. However, only a few authors have aimed to develop exact methods and most of these methods have some major restrictions such as a fixed number of production cells for example. In this paper we suggest a new mixed-integer linear programming model for solving the cell formation problem with a variable number of manufacturing cells. The popular grouping efficacy measure is used as an objective function. To deal with its fractional nature we apply the Dinkelbach approach. Our computational experiments are performed on two testsets: The first consists of 35 well-known instances from the literature and the second contains 32 instances less popular. We solve these instances using CPLEX software. Optimal solutions have been found for 63 of the 67 considered problem instances and several new solutions unknown before have been obtained. The computational times are greatly decreased comparing to the state-of-Art approaches. Copyright © 2017, The Authors. All rights reserved.

关键词： Cellular manufacturing

Hyperplanes Avoiding Problem and Integer Points Counting in Polyhedra

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Dakhno, Grigorii Gribanov, Dmitry Kasianov, Nikita Kats, Anastasiia Kupavskii, Andrey Kuz’min, Nikita Laboratory of Discrete and Combinatorial Optimization Moscow Institute of Physics and Technology Institutsky lane 9 Moscow region Dolgoprudny141700 Russia Laboratory of Algorithms and Technologies for Network Analysis HSE University 136 Rodionova Ulitsa Nizhny Novgorod603093 Russia

In our work, we consider the problem of computing a vector 6 x ∈ n of minimum k·kp-norm such that ax 6= a0, for any vector (a, a0) from a given finite set A ⊆ n. In other words, we search for a vector of minimum norm that avoids a given finite set of hyperplanes, which is natural to call as the Hyperplanes Avoiding Problem. This problem naturally appears as a subproblem in Barvinok-type algorithms for counting integer points in polyhedra. More precisely, it appears when one needs to evaluate certain rational generating functions in an avoidable critical point. We show that: 1. With respect to k·k1, the problem admits a feasible solution x with kxk1 ≤ (m + n)/2, where m = |A|, and show that such solution can be constructed by a deterministic polynomial-time algorithm with O(n · m) operations. Moreover, this inequality is the best possible. This is a significant improvement over the previous randomized algorithm, which computes x with a guaranty kxk1 ≤ n · m. The original approach of A. Barvinok can guarantee only kxk1 = O((n · m)n). To prove this result, we use a newly established algorithmic variant of the Combinatorial Nullstellensatz;2. The problem is NP-hard with respect to any norm k·kp, for p ∈ (R≥1 ∪{∞});3. As an application, we show that the problem to count integer points in a polytope P = {x ∈ Rn : Ax ≤ b}, for given A ∈ m×n and b ∈ Qm, can be solved by an algorithm with O(ν2·n3·∆3) operations, where ν is the maximum size of a normal fan triangulation of P, and ∆ is the maximum value of rank-order subdeterminants of A. It refines the previous state-of-the-art O(ν2 · n4 · ∆3)-time algorithm. As a further application, it provides a refined complexity bound for the counting problem in polyhedra of bounded codimension. More specifically, it improves the computational complexity bound for counting the number of solutions in the Unbounded Subset-Sum problem. Copyright © 2024, The Authors. All rights reserved.

关键词： Rational functions

Reliability of MST identification in correlation-based market networks

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Kalyagin, Valeriy A. Koldanov, A.P. Koldanov, P.A. National Research University Higher School of Economics Laboratory of Algorithms and Technologies for Network Analysis 136 Rodionova street Nizhny Novgorod603093 Russia

Maximum spanning tree (MST) is a popular tool in market network analysis. Large number of publications are devoted to the MST calculation and it's interpretation for particular stock markets. However, much less attention is payed in the literature to the analysis of uncertainty of obtained results. In the present paper we suggest a general framework to measure uncertainty of MST identification. We study uncertainty in the framework of the concept of random variable network (RVN). We consider different correlation based networks in the large class of elliptical distributions. We show that true MST is the same in three networks: Pearson correlation network, Fechner correlation network, and Kendall correlation network. We argue that among different measures of uncertainty the FDR (False Discovery Rate) is the most appropriated for MST identification. We investigate FDR of Kruskal algorithm for MST identification and show that reliability of MST identification is different in these three networks. In particular, for Pearson correlation network the FDR essentially depends on distribution of stock returns. We prove that for market network with Fechner correlation the FDR is non sensitive to the assumption on stock's return distribution. Some interesting phenomena are discovered for Kendall correlation network. Our experiments show that FDR of Kruskal algorithm for MST identification in Kendall correlation network weakly depend on distribution and at the same time the value of FDR is almost the best in comparison with MST identification in other networks. These facts are important in practical *** Codes 68T37, 62-07, C44 © 2021, CC BY.

关键词： Random variables

Comparison of statistical procedures for Gaussian graphical model selection

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Grechikhin, Ivan S. National Research University Higher School of Economics Laboratory of Algorithms and Technologies for Network Analysis 136 Rodionova St Nizhny Novgorod603093 Russia

Graphical models are used in a variety of problems to uncover hidden structures. There is a huge number of different identification procedures, constructed for different purposes. However, it is important to research different properties of such procedures and compare them in order to find out the best procedure or the best use case for some specific procedure. In this paper, some statistical identification procedures are compared using different measures, such as Type I and Type II errors, ROC AUC. Copyright © 2017, The Authors. All rights reserved.

关键词： Statistical methods

A study of distributionally robust mixed-integer programming with Wasserstein metric: on the value of incomplete data

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Ketkov, Sergey S. Laboratory of Algorithms and Technologies for Networks Analysis HSE University Rodionova st. 136 Nizhny Novgorod603093 Russia Department of Business Administration University of Zurich Zurich8032 Switzerland

This study addresses a class of linear mixed-integer programming (MILP) problems that involve uncertainty in the objective function parameters. The parameters are assumed to form a random vector, whose probability distribution can only be observed through a finite training data set. Unlike most of the related studies in the literature, we also consider uncertainty in the underlying data set. The data uncertainty is described by a set of linear constraints for each random sample, and the uncertainty in the distribution (for a fixed realization of data) is defined using a type-1 Wasserstein ball centered at the empirical distribution of the data. The overall problem is formulated as a three-level distributionally robust optimization (DRO) problem. First, we prove that the three-level problem admits a single-level MILP reformulation, if the class of loss functions is restricted to biaffine functions. Secondly, it turns out that for several particular forms of data uncertainty, the outlined problem can be solved reasonably fast by leveraging the nominal MILP problem. Finally, we conduct a computational study, where the out-of-sample performance of our model and computational complexity of the proposed MILP reformulation are explored numerically for several application domains. © 2023, CC BY-NC-ND.

关键词： Probability distributions