During the operating lifetime of products, an inspection strategy is discussed to get both censored data and some accurate data embedded in censoring intervals here. To obtain the parameter estimates of lifetime model...
详细信息
During the operating lifetime of products, an inspection strategy is discussed to get both censored data and some accurate data embedded in censoring intervals here. To obtain the parameter estimates of lifetime model, an iterative single-point imputation (SPI) algorithm is proposed under stochastic quantile probabilities, called stochastic quantile-filling augmentation (SOYA). By the algorithm, stochastic conditional quantiles are imputed as the virtual failure time data from doubly transacted distributions in interval-censored intervals;and the virtual right-censored data are obtained by equipartition conditional quantiles in right-censored interval, respectively. It has iterative thoughts of stochastic multiple imputations to obtain the virtual data. And its convergence is verified through the examples both under the criterion of moment estimation (ME) and maximum likelihood estimation (MLE). Especially, closed-form estimates for Weibull distribution and Gamma distribution are given through some transformations. Furthermore, numerical examples and simulations show that the proposed augmentation algorithm performs better on parameter estimations than the iterative SPI algorithm under equipartition quantile probabilities. (C) 2017 Elsevier Ltd. All rights reserved.
Many fundamental NP-hard problems can be formulated as integer linear programs (ILPs). A famous algorithm by Lenstra solves ILPs in time that is exponential only in the dimension of the program, and polynomial in the ...
详细信息
Many fundamental NP-hard problems can be formulated as integer linear programs (ILPs). A famous algorithm by Lenstra solves ILPs in time that is exponential only in the dimension of the program, and polynomial in the size of the ILP. That algorithm became a ubiquitous tool in the design of fixed-parameter algorithms for NP-hard problems, where one wishes to isolate the hardness of a problem by some parameter. However, in many cases using Lenstra's algorithm has two drawbacks: First, the run time of the resulting algorithms is often double-exponential in the parameter, and second, an ILP formulation in small dimension cannot easily express problems involving many different costs. Inspired by the work of Hemmecke et al. (Math Program 137(12, Ser. A):325-341, 2013), we develop a single-exponential algorithm for so-called combinatorial n-fold integer programs, which are remarkably similar to prior ILP formulations for various problems, but unlike them, also allow variable dimension. We then apply our algorithm to many relevant problems problems like Closest String, Swap Bribery, Weighted Set Multicover, and several others, and obtain exponential speedups in the dependence on the respective parameters, the input size, or both. Unlike Lenstra's algorithm, which is essentially a bounded search tree algorithm, our result uses the technique of augmenting steps. At its heart is a deep result stating that in combinatorial n-fold IPs, existence of an augmenting step implies existence of a "local" augmenting step, which can be found using dynamic programming. Our results provide an important insight into many problems by showing that they exhibit this phenomenon, and highlights the importance of augmentation techniques.
We consider -fold -block decomposable integer programs, which simultaneously generalize -fold integer programs and two-stage stochastic integer programs with scenarios. In previous work (Hemmecke et al. in Integer pro...
详细信息
We consider -fold -block decomposable integer programs, which simultaneously generalize -fold integer programs and two-stage stochastic integer programs with scenarios. In previous work (Hemmecke et al. in Integer programming and combinatorial optimization. Springer, Berlin, 2010), it was proved that for fixed blocks but variable , these integer programs are polynomial-time solvable for any linear objective. We extend this result to the minimization of separable convex objective functions. Our algorithm combines Graver basis techniques with a proximity result (Hochbaum and Shanthikumar in J. ACM 37:843-862,1990), which allows us to use convex continuous optimization as a subroutine.
In this paper we generalize N-fold integer programs and two-stage integer programs with AT scenarios to N-fold 4-block decomposable integer programs. We show that for fixed blocks but variable N, these integer program...
详细信息
ISBN:
(纸本)9783642130359
In this paper we generalize N-fold integer programs and two-stage integer programs with AT scenarios to N-fold 4-block decomposable integer programs. We show that for fixed blocks but variable N, these integer programs are polynomial-time solvable for any linear objective. Moreover, we present a polynomial-time computable optimality certificate for the case of fixed blocks, variable N and any convex separable objective function. We conclude with two sample applications, stochastic integer programs with second-order dominance constraints and stochastic integer multi-commodity flows, which (for fixed blocks) can be solved in polynomial time in the number of scenarios and commodities and in the binary encoding length of the input data. In the proof of our main theorem we combine several non-trivial constructions from the theory of Graver bases. We are confident that our approach paves the way for further extensions.
To realize automatic modeling and dynamic simulation of the educational assembling-type robot with open structure, a general dynamic model for the educational assembling-type robot and a fast simulation algorithm are ...
详细信息
To realize automatic modeling and dynamic simulation of the educational assembling-type robot with open structure, a general dynamic model for the educational assembling-type robot and a fast simulation algorithm are put forward. First, the educational robot system is abstracted to a multibody system and a general dynamic model of the educational robot is constructed by the Newton-Euler method. Then the dynamic model is simplified by a combination of components with fixed connections according to the structural characteristics of the educational robot. Secondly, in order to obtain a high efficiency simulation algorithm, based on the sparse matrix technique, the augmentation algorithm and the direct projective constraint stabilization algorithm are improved. Finally, a numerical example is given. The results show that the model and the fast algorithm are valid and effective. This study lays a dynamic foundation for realizing the simulation platform of the educational robot.
暂无评论