ABSTRACT. We study the following scheduling problem for a warehouse which consists of some identical buildings. Each building has rooms with known capacity. Each room has one type of product or empty. Each building has two gates. One gate is for the loading/unloading trailers, another one is for two forklifts from the central zone (production line). We know when each pallet becomes available from the central zone. Outbound trailers come to pick some pallets; inbound trailers come to put away some pallets. We know the arrival time for each trailer and its processing time. We present scheduling of the central zone as a sequence of inbound virtual trailers that work by no-wait rule. Our goal is to assign all trailers to buildings and find scheduling for service all the inbound/outbound trailers with the minimal total waiting time. To solve the problem, we design a mixed-integer linear program for the case all trailers are serviced by the FIFO rule for each building. Gurobi software can find an optimal solution for small instances in this case. For real-world instances, we design a genetic algorithm. Assignment for virtual trailers is used as a coding sequence. The multi-agent system for inbound/outbound trailers is applied as a decoding procedure. Computational results for The Nederland logistic company with 6 buildings, 50 products, and 90 trailers are discussed.

ABSTRACT. We consider a real-life problem which arise in an industrial process of big electronic device manufacturer. An warehouse, which stores the finished products is involved into the orders packing and delivery process. Each order should process through two stages to be prepared for delivery. During the first stage, picking, the ordered goods have to be extracted from the storage. During the second stage these goods have to be packed into the boxes and transferred to the delivery service. The problem is to arrange the schedule and the way the orders have to process through the stages, in order to maximize the throughput of the warehouse. We propose a set of constructive heuristics for this problem and discuss the results of computational experiments.

ABSTRACT. Suppose that an oil and gas field consists of clusters in each of which an investor can develop at most one project. During the implementation of a particular project, all characteristics are known, including annual production volumes, necessary investment volumes, and profit. The total amount of investments that the investor spends on developing the field during the entire planning period we know. It is required to determine which projects to implement in each cluster, so that, within the total amount of investments, the profit for the entire planning period is maximum.

The problem under consideration is NP-hard. However, it is solved by dynamic programming with pseudopolynomial complexity. But in practice, there are additional constraints that do not allow solving the problem with acceptable accuracy at a reasonable time. Such restrictions, in particular, are annual production volumes. In this paper, we considered only the upper constraints that are dictated by the pipeline capacity. For the investment optimization problem with such additional restrictions, we obtain qualitative results, propose approximate algorithms, and investigate their properties. Based on the results of a numerical experiment, we conclude that the developed algorithms build a solution close (in terms of the objective function) to the optimal one.

ABSTRACT. The work considers the problem of minimizing a sum of linear ratios over a convex compact set. By assigning all the numerators and denominators to new variables, we introduce an auxiliary sum of ratios problem. In the new problem, the feasible set is an image, that is a result of a linear transformation of the feasible set of the initial problem. We propose an iterative two-step procedure to find a solution of the initial problem. The first step is a branch-and-bound-type algorithm to solve the new problem. This algorithm is based on support functions. The second step includes a preimage reconstruction for a solution obtained at the previous step. The proposed procedure gives the most benefit when the number of ratios is smaller than the number of variables in the initial problem. Results of a computational experiment are also presented.

ABSTRACT. In this paper we experimentally check a hypothesis, that dual problem to discrete entropy regularized optimal transport problem poses strong convexity on certain compact set. We present a numerical estimation technique of parameter of strong convexity and show that such an estimate increase performance of an accelerated alternating minimization algorithm for strongly convex functions applied to the considered problem.

ABSTRACT. In this paper, we present a new Hyperfast Second-Order Method with convergence rate O(N^-5) up to a logarithmic factor for the convex function with Lipshitz third derivative. This method based on two ideas. The first comes from the superfast second-order scheme of Yu. Nesterov (CORE Discussion Paper 2020/07, 2020). It allows implementing the third-order scheme by solving subproblem using only the second-order oracle. This method converges with rate O(N^-4). The second idea comes from the work of Kamzolov et al. (arXiv:2002.01004). It is the inexact near-optimal third-order method. In this work, we improve its convergence and merge it with the scheme of solving subproblem using only the second-order oracle. As a result, we get convergence rate O(N^-5) up to a logarithmic factor. This convergence rate is near-optimal and the best known up to this moment.

ABSTRACT. Let ω be a proposition that may be either true or false, and let E be the population of experts. The purpose of our study is to offer a definition of the collective probability of ω = 1 (as a "physical'' parameter, not only as a measure in an abstract model) together with an operational method for its effective elicitation from E. For this, we revise and employ various ideas (and propose new ones as well) from probability interpretations, non-standard expected utility theories, statistical inference, and studies in prediction markets.

ABSTRACT. The onboard equipment for space applications meets increased requirements in terms of reliability and durability of the electronic components. To ensure the quality of the electronic component base, specialized test centers conduct many tests, including destructive physical analysis (DPA). The condition for the applicability of destructive tests for the entire production batch is its uniformity according to the characteristics of the raw materials. Idea of this paper is to compare various models for solving the problem of automatic grouping of electric radio products into homogeneous production batches, based on the k-means model [1, 2]. This work proposes the optimization model of automatic grouping based on the k-means model with the Mahalanobis metric.This model uses training (parameterization) procedure for the Mahalanobis metric by calculating the averaged covariance matrix for the training sample. In the work we investigate the application of the k-means method to the task of automatically grouping devices, each of which contains of a large number of measured parameters, using various measures of distances: Euclidean, Manhattan, Mahalanobis [3]. In some cases, when solving the problem of automatic grouping, we have a sample whose composition is known. This sample can serve as a training (parametrizing) sample, according to which it is possible to calculate the average covariance matrix for a homogeneous production batch using the Mahalanobis distance. A new clustering model based on k-means with a Mahalanobis distance and the averaged covariance matrix is proposed. In this study, we conduct the computational experiments to solve the problem of automatic grouping of electronic radio components according to their non-destructive testing using various optimization models based on the k-means model. For comparison of the results, we use the Rand index [4]. As a result, the model of automatic grouping of products into homogeneous production batches based on the k-means model with the Mahalanobis distance and the averaged (weighted average) covariance matrix gives the highest accuracy by the Rand index. Moreover, in this model, unlike other models, the clustering problem results with better objective function values (less sum of squared distances) have better Rand index values.

References

1. MacQueen J. 1967: Some methods for classification and analysis of multivariate observations. Proc. Fifth Berkeley Symp. Math. Stat. Probab. Vol. 1 pp. 281–97 2. Kazakovtsev L., Antamoshkin A. 2014: Genetic Algorithm with Fast Greedy Heuristic for Clustering and Location Problems. Informatica 38(3). pp 229-240. 3. De Maesschalck R, Jouan-Rimbaud D, Massart D L 2000: The Mahalanobis distance. ChemIntell Lab Syst 50(1). pp 1–18. doi: 10.1016/S0169-7439(99)00047-7 4. Rand W. M. 1971: Objective criteria for the evaluation of clustering methods. Journal of the American Statistical Association. 66 (336). pp 846–50

ABSTRACT. Well-known and widely applied k-means clustering heuristic is used for solving Minimum Sum-of-Square Clustering (MSSC) problem. In solving large size problems, there are two major drawbacks of this technique: (i) since it has to process the large input dataset, it has heavy computational costs and (ii) it has a tendency to converge to one of the local minima of poor quality. In order to reduce the computational complexity, we propose a clustering technique that works on portions of the entire dataset in a stream like fashion. The algorithm evaluates dynamically parameters of clusters from sequential data portions (batches) by aggregating corresponding SS estimates. Promising results are reported on instances from the literature and synthetically generated data with several milions of entities.