We propose an accelerated gradient-free method with a non-Euclidean proximal operator associated with the p-norm (1 ⩽ p ⩽ 2). We obtain estimates for the rate of convergence of the method under low noise arising in the calculation of the function value. We present the results of computational experiments.
To solve problems of demand management in terms of smart energy systems (Smart grid), we need a mathematical model of active consumer decision-making. Existing models either do not consider important aspects of consumer behavior, or are too complex for use in multi-agent simulation. A mathematical model of an active consumer is proposed, based on which we formulate and solve the problem of optimization of electrical appliances and consumer equipment, as well as determine the loading conditions of self-generation, under which the consumer problem allows simple and effective solution. The proposed approach is illustrated by equipment optimization of a single household.
We present the results of a comparative statistical analysis of the time for solving the asymmetric traveling salesman problem (ATSP) with the branch-and-bound method (without precalculation of the tour) and with a hybrid method. The hybrid method consists of the Lin–Kernighan–Helsgaun approximate algorithm used to calculate the initial tour and the branch-and-bound method. We show that using an approximate solution found with the Lin–Kernighan–Helsgaun algorithm can significantly reduce the search time for the exact solution to the traveling salesman problem using the branch-and-bound method for problems from a certain class. We construct a prediction of the search time for the exact solution by the branchand- bound method and by the hybrid algorithm. A computational experiment has shown that the proportion of tasks solved faster by the hybrid algorithm than by the branch-and-bound method grows with increasing problem dimension.
In this paper, we consider two scheduling problems on a single machine, where a specific objective function has to be maximized in contrast to usual minimization problems. We propose exact algorithms for the single machine problem of maximizing total tardiness 1‖max-ΣT j and for the problem of maximizing the number of tardy jobs 1‖maxΣU j . In both cases, it is assumed that the processing of the first job starts at time zero and there is no idle time between the jobs. We show that problem 1‖max-ΣT j is polynomially solvable. For several special cases of problem 1‖maxΣT j , we present exact polynomial algorithms. Moreover, we give an exact pseudo-polynomial algorithm for the general case of the latter problem and an alternative exact algorithm.
To improve the reliability of data delivery, in Wi-Fi networks stations can reserve for their transmissions periodic time intervals of the same duration in which they are allowed to transmit, while adjacent stations do not have that right. Here there arises the problem of choosing the parameters of reserved intervals that would ensure quality of service requirements for transmitted data in the smallest possible amount of reserved channel time. We consider the data transmission process in periodic intervals with the block acknowledgement policy that lets us reduce the costs by acknowledgement the set of packets with a single service message. We propose a method for mathematical modeling of such a transmission.
In this paper we consider the NP-hard 1|rj|ΣTj scheduling problem, suggesting a polynomial algorithm to find its approximate solution with the guaranteed absolute error. The algorithm employs a metric introduced in the parameter space. In addition, we study the possible application of such an approach to other scheduling problems.
An agent model of crowd (ensemble) behavior in emergencies was presented. This model is distinguished for the allowance for dynamics of each agent from the ensemble under consideration. The crowd effect manifests itself mostly as attraction or repulsion of closely set agents with a probability depending on the agent’s psychological type. Consideration was given to the effects associated with the crowd “turbulence.” Operation of the intelligent rescue agents was simulated. The impact of the configuration of spatial agent allocation on the dynamics of their evacuation in emergencies was analyzed. The influence of the intelligent rescue agents on the system was studied, and an adaptive procedure for training such agents was developed.
The optimality criteria used in the problem of stochastic linear regulator over an infinite time horizon were analyzed. A certain criterion for long-run average and pathwise ergodic were shown to be inefficient with regard for the disturbance factor. Consideration was given to a new criterion of the extended long-run average and its use in the discounted control systems.
We give a survey of approaches for analyzing the sensitivity of non-dominated alternatives to changes in the parameters of partial quasi-orderings that define preferences. Such parameters can include values of importance coefficients for different criteria or boundaries of interval estimates of the degrees of superiority in the importance of some criteria over others, boundaries of intervals of criteria value tradeoffs uncertainty, and others.
The IEEE 802.11s standard of Wi-Fi Mesh networking introduces a novel deterministic channel access mechanism called MCCA. This mechanism allows stations to reserve distinct time intervals for their data transmission. Since each station is informed about their neighbouring stations' reservations, it does not transmit during them leading to less packet losses due to packets collisions. However, to provide QoS (Quality of Service) over an imperfect wireless channel additional packets retransmissions might be needed. That leads to problem of choosing appropriate MCCA reservations parameters. In the paper, we develop an analytical model of QoS provisioning data streaming over a lossy Wi-Fi Mesh network via MCCA. The model can be used to find such reservations parameters for which the channel resource consumption is minimal while QoS requirements are met.
We consider the problem of modeling anomalous diffusions with the Ornstein–Uhlenbeck process with time-varying coefficients. An anomalous diffusion is defined as a process whose mean-squared displacement non-linearly grows in time which is nonlinearly growing in time. We classify diffusions into types (subdiffusion, normal diffusion, or superdiffusion) depending on the parameters of the underlying process. We solve the problem of finding the coefficients of dynamics equations for the Ornstein–Uhlenbeck process to reproduce a given mean-squared displacement function.
After a series of publications of T.E. O’Neil et al. (e.g. in 2010), dynamic programming seems to be the most promising way to solve knapsack problems. Some techniques are known to make dynamic programming algorithms (DPA) faster. One of them is the graphical method that deals with piecewise linear Bellman functions. For some problems, it was previously shown that the graphical algorithm has a smaller running time in comparison with the classical DPA and also some other advantages. In this paper, an exact graphical algorithm (GrA) and a fully polynomial-time approximation scheme based on it are presented for an investment optimization problem having the best known running time. The algorithms are based on new Bellman functional equations and a new way of implementing the GrA.
This paper describes a modified version of an algorithm suggested earlier by the authors for optimizing of ads allocation in sponsored search on the main page of search results in response to user search queries to a web search engine. It is demonstrated that the modification of the algorithm reduces appreciably the searching procedure and the algorithm complexity. And finally, the new algorithm undergoes experimental testing on real data sets provided by Yandex. © 2015, Pleiades Publishing, Ltd.
A computationally efficient method for the design of a suboptimal anisotropic con- troller for discrete descriptor systems based on convex optimization methods is proposed. Nu- merical examples are given.
We show that if preferences can be defined with an additive utility function then decision making models based on the theory of criteria importance can be defined with imprecise probabilities. With this idea, we analyze new approaches to decision making in the theory of criteria importance.
For the process of order (1,1) spatial autoregression, the consistency and asymptotic normality of the sign estimate were established. The relative asymptotic efficiency of the sign estimate relative to least- squares estimate was calculated, and its behavior under various distributions of the renewing field was considered.
This paper demonstrates that most existing voting schemes represent or can be rewritten as weighted games. However, axiomatics for power indices defined on simple games are not directly applied to weighted games, since related operations become ill-posed. The author shows that the majority of axiomatics can be adapted to weighted games. Finally, a series of examples are provided.
Using a simplified multistage bidding model with asymmetrically informed agents, De Meyer and Saley [17] demonstrated an idea of endogenous origin of the Brownian component in the evolution of prices on stock markets: random price fluctuations may be caused by strategic randomization of “insiders.” The model is reduced to a repeated game with incomplete information. This paper presents a survey of numerous researches inspired by the pioneering publication of De Meyer and Saley.