343 results on '"APPROXIMATION algorithms"'
Search Results
52. An improved approach for determination of index positions on CNC magazines with cutting tool duplications by integrating shortest path algorithm.
- Author
-
Baykasoğlu, Adil and Ozsoydan, Fehmi Burcin
- Subjects
INDEXING ,CUTTING tools ,METAHEURISTIC algorithms ,APPROXIMATION algorithms ,MATHEMATICAL optimization ,COMBINATORIAL optimization ,SIMULATED annealing - Abstract
Optimisation of automatic tool changer (ATC) indexing problem, where cutting tools are allocated to the stations on a turret magazine of a CNC machine, is one of the challenging problems in machining. The aim of the problem is to minimise the total indexing time of ATC. This problem becomes even more challenging if duplication of cutting tools is allowed and a bidirectional ATC is used. The problem has a unique feature which has not been stressed yet by other researchers, that is, although ATC indexing (master problem) is the main optimisation problem, objective function evaluation of this problem is a standalone optimisation problem (sub problem) indeed. Although an approximation algorithm does not guarantee optimality for the master problem, the subproblem must be solved optimally; otherwise, deficiencies arising from ill-defined objective function might be encountered. Considering this interesting future, a novel methodology, which employs a shortest path algorithm, is developed. Thus, the subproblem of this complicated problem can be optimally solved. Moreover, two metaheuristics, based on threshold accepting and descent first improvement greedy methodologies, are proposed for generating efficient solutions. Finally, several benchmarking instances are generated and solved to test the proposed algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
53. Two-machine routing open shop on a tree: instance reduction and efficiently solvable subclass.
- Author
-
Chernykh, I. D. and Lgotina, E. V.
- Subjects
- *
RETAIL store openings , *APPROXIMATION algorithms , *ROUTING algorithms , *TREES - Abstract
We consider two-machine routing open shop problem on a tree. In this problem, a transportation network with a tree-like structure is given, and each node contains some jobs to be processed by two mobile machines. Machines are initially located in the predefined node called the depot, have to traverse the network to perform their operations on each job (and each job has to be processed by both machines in arbitrary order), and machines have to return to the depot after performing all the operations. The goal is to construct a feasible schedule for machines to process all the jobs and to return to the depot in shortest time possible. This problem is known to be NP-hard even in the case when the transportation network consists of just two nodes. We propose an instance reduction procedure which allows to transform any instance of the problem to a simplified instance on a chain with limited number of jobs. The reduction considered preserves the standard lower bound on the optimum. We describe four possible outcomes of this procedure and prove that in three of them the initial instance can be solved to the optimum in linear time, thus introducing a wide polynomially solvable subclass of the problem considered. Our research can be used as a foundation to construct efficient approximation algorithms for the two-machine routing open shop on a tree. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
54. A generic framework for approximation analysis of greedy algorithms for star bicoloring.
- Author
-
Juedes, David W. and Jones, Jeffrey S.
- Subjects
- *
GREEDY algorithms , *JACOBIAN matrices , *SPARSE matrices , *INDEPENDENT sets , *APPROXIMATION algorithms , *COLUMNS , *AUTOMATIC differentiation - Abstract
This paper presents a generic framework for the design and comparison of polynomial-time approximation algorithms for MINIMUM STAR BICOLORING. This generic framework is parameterized by algorithms which produce sequences of distance- 2 independent sets. As our main technical result we show that, when the parameterized algorithm produces sequences of distance- 2 independent sets that remove at least Ω (n ϵ) edges during each step, the generic framework produces a polynomial-time approximation algorithm for MINIMUM STAR BICOLORING that is always at least O (n 1 − ϵ / (1 + ϵ) ) of optimal. Under the generic framework, we model two algorithms for MINIMUM STAR BICOLORING from the literature: Complete Direct Cover (CDC) [Hossain and Steihaug, Computing a sparse Jacobian matrix by rows and columns, Optim. Methods Softw. 10 (1998), pp. 33–48] and ASBC [Juedes and Jones, Coloring Jacobians revisited: A new algorithm for star and acyclic bicoloring, Optim. Methods Softw. 27(1–3) (2012), pp. 295–309]. We apply our main result to show approximation upper bounds of O (n 3 / 4) and O (n 2 / 3) , respectively, for these two algorithms. Our approximation upper bound for CDC is the first known approximation analysis for this algorithm. In addition to modelling CDC and ASBC, we use the generic framework to build and analyze three new O (n 2 / 3) approximation algorithms for MINIMUM STAR BICOLORING: MAX-NEIGHBORHOOD, MAX-RATIO c , and LOCAL-SEARCH-k. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
55. GLS and VNS based heuristics for conflict-free minimum-latency aggregation scheduling in WSN.
- Author
-
Plotnikov, Roman, Erzin, Adil, and Zalyubovskiy, Vyacheslav
- Subjects
- *
METAHEURISTIC algorithms , *SPANNING trees , *APPROXIMATION algorithms , *HEURISTIC algorithms , *UNDIRECTED graphs , *NP-hard problems , *HEURISTIC - Abstract
We consider a conflict-free minimum latency data aggregation problem that occurs in different wireless networks. Given a network that is presented as an undirected graph with one selected vertex (a sink), the goal is to find a spanning aggregation tree rooted in the sink and to define a conflict-free aggregation minimum length schedule along the arcs of the tree directed to the sink. Herewith, at the same time slot, each element of the network can either send or receive at most one message. Only one message should be sent by each network element during the whole aggregation session, and the conflicts caused by signal interference should be excluded. This problem is NP-hard and remains NP-hard even in the case when the aggregation tree is given. Therefore, the development of efficient approximation algorithms is very important for this problem. In this paper, we present new heuristic algorithms based on genetic local search and variable neighbourhood search metaheuristics. We conducted an extensive simulation that demonstrates the superiority of our algorithms compared with the best of the previous approaches. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
56. Inner approximation algorithm for solving linear multiobjective optimization problems.
- Author
-
Csirmaz, Laszlo
- Subjects
- *
APPROXIMATION algorithms , *ALGORITHMS , *LINEAR programming - Abstract
Benson's outer approximation algorithm and its variants are the most frequently used methods for solving linear multiobjective optimization problems. These algorithms have two intertwined parts: single-objective linear optimization on one hand, and a combinatorial part closely related to vertex enumeration on the other. Their separation provides a deeper insight into Benson's algorithm, and points toward a dual approach. Two skeletal algorithms are defined which focus on the combinatorial part. Using different single-objective optimization problems yields different algorithms, such as a sequential convex hull algorithm, another version of Benson's algorithm with the theoretically best possible iteration count, and the dual algorithm of Ehrgott et al. [A dual variant of Benson's 'outer approximation algorithm' for multiple objective linear programming. J Glob Optim. 2012;52:757–778]. The implemented version is well suited to handle highly degenerate problems where there are many linear dependencies among the constraints. On problems with 10 or more objectives, it shows a significant increase in efficiency compared to Bensolve – due to the reduced number of iterations and the improved combinatorial handling. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
57. Minimum point-overlap labelling*.
- Author
-
Higashikawa, Yuya, Imai, Keiko, Shiraga, Takeharu, Sukegawa, Noriyoshi, and Yokosuka, Yusuke
- Subjects
- *
APPROXIMATION algorithms , *LABELS , *MAXIMA & minima , *RECTANGLES , *ALGORITHMS - Abstract
In an application of map labelling to air-traffic control, labels should be placed with as few overlaps as possible since labels include important information about airplanes. Motivated by this application, de Berg and Gerrits (Comput. Geom. 2012) proposed a problem of maximizing the number of free labels (i.e. labels not intersecting with any other label) and developed approximation algorithms for their problem under various label-placement models. In this paper, we propose an alternative problem of minimizing a degree of overlap at a point. Specifically, the objective of this problem is to minimize the maximum of λ (p) over p ∈ R 2 , where λ (p) is defined as the sum of weights of labels that overlap with a point p. We develop a 4-approximation algorithm by LP-rounding under the 4-position model. We also investigate the case when labels are rectangles with bounded height/length ratios. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
58. Research on reducing fuzzy test sample set based on heuristic genetic algorithm.
- Author
-
Wang, Zhihua, Cheng, Manman, and Wang, Yongjian
- Subjects
HEURISTIC algorithms ,GENETIC algorithms ,FUZZY algorithms ,SCALABILITY ,APPROXIMATION algorithms - Abstract
Fuzzy testing is the most effective method for vulnerability mining, which can deal with complex programmes better than other vulnerability mining techniques and has strong scalability. However, in the large-scale vulnerability analysis test, the fuzzy test input sample set faces the challenges of low quality, high repeatability and low availability etc. Therefore, this paper studies the input sample set and proposes heuristic genetic algorithm. By using 0–1 matrix, the genetic algorithm is improved with a consideration of practical problems and the execution path for sample set is selected and compressed through approximation algorithm, thus obtaining a smallest sample set and accelerating the efficiency of fuzzy test. Experimental results show that the proposed method is effective. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
59. Inference for an exponentiated half logistic distribution with application to cancer hybrid censored data.
- Author
-
Z. Raqab, Mohammad, Bdair, Omar M., K. Rastogi, Manoj, and Al-aboud, Fahad M.
- Subjects
- *
CENSORING (Statistics) , *SURVIVAL analysis (Biometry) , *APPROXIMATION algorithms , *MAXIMUM likelihood statistics , *COMPUTER simulation - Abstract
In this paper, based on hybrid censored sample from a two parameter exponentiated half logistic distribution, we consider the problem of estimating the unknown parameters using frequentist and Bayesian approaches. Expectation-Maximization, Lindley's approximation and Metropolis-Hastings algorithms are used for obtaining point estimators and corresponding confidence intervals for the shape and scale parameters involved in the underlying model. Data analyses involving the survival times of patients suffering from cancer diseases and treated radiotherapy and/or chemotherapy have been performed. Finally, numerical simulation study was conducted to assess the performances of the so developed methods and conclusions on our findings are reported. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
60. Vector scheduling with rejection on two machines.
- Author
-
Dai, Bingfei and Li, Weidong
- Subjects
- *
ONLINE algorithms , *APPROXIMATION algorithms , *POLYNOMIAL approximation , *POLYNOMIAL time algorithms , *DYNAMIC programming , *PRODUCTION scheduling , *SCHEDULING - Abstract
In this paper, we study the problem of vector scheduling with rejection on two identical parallel machines, where the objective is to minimize the sum of maximum load over all dimensions and machines and the total penalty cost. We present a 3-approximation algorithm and a 2.54-approximation algorithm based randomized rounding for the general case. When the number of dimensions is fixed, we design a fully polynomial time approximation scheme based on dynamic programming. Finally, we design an online algorithm with competitive ratio 1.62d, where d is the number of dimensions. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
61. Scheduling unrelated machines with two types of jobs.
- Author
-
Vakhania, Nodari, Hernandez, Jose Alberto, and Werner, Frank
- Subjects
PRODUCTION scheduling ,PRODUCTION control ,SCHEDULING ,JOB shops ,SETUP time ,LINEAR programming ,APPROXIMATION algorithms ,MACHINE theory - Abstract
In this paper, we consider the problem of scheduling a set of jobs having only two possible processing times on a set of unrelated parallel machines. This problem is a generalisation of the much more common problem of scheduling equal-length jobs on identical machines. Such a situation may occur in the production of two different types of products. First, we show that an earlier open problem of scheduling jobs with two possible processing times and on unrelated machines with the objective to minimise the makespan can be polynomially solved by an algorithm consisting of two phases. A slight modification of this algorithm yields an absolute worst-case error of for the case of two arbitrary processing times and ,. Thus, for practical problems of a large size with two types of products and two possible processing times, the approximation algorithm generates schedules very close to an optimal one. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
62. An evolutionary algorithm for the robust maximum weighted independent set problem.
- Author
-
Klobučar, Ana and Manger, Robert
- Subjects
EVOLUTIONARY algorithms ,INDEPENDENT sets ,ALGORITHMS ,COMPUTATIONAL complexity ,ROBUST optimization ,APPROXIMATION algorithms - Abstract
This work deals with the robust maximum weighted independent set problem, i.e. finding a subset of graph vertices that are not adjacent to each other and whose sum of weights is as large as possible. Uncertainty in problem formulation is restricted to vertex weights and expressed explicitly by a finite set of scenarios. Three criteria of robustness are considered: absolute robustness (max-min), robust deviation (min-max regret), and relative robustness (relative min-max regret). Since the conventional maximum weighted independent set problem is already NP-hard, finding the exact solution of its robust counterpart should obviously have a prohibitive computational complexity. Therefore, we propose an approximate algorithm for solving the considered robust problem, which is based on evolutionary computing and on various crossover and mutation operators. The algorithm is experimentally evaluated on appropriate problem instances. It is shown that satisfactory solutions can be obtained for any of the three robustness criteria in reasonable time. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
63. Nonparametric relative recursive regression estimators for censored data.
- Author
-
Slaoui, Yousri
- Subjects
- *
STOCHASTIC approximation , *APPROXIMATION algorithms , *CENTRAL limit theorem - Abstract
In this paper, we propose a relative recursive regression estimator for censored data defined by the stochastic approximation algorithm to deal with the presence of outliers or when the response is usually positive. We give the central limit theorem and the strong pointwise convergence rate for our proposed nonparametric relative recursive estimators under some mild conditions. We finally developed a second generation plug-in bandwidth selection procedure. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
64. Makespan minimisation on parallel batch processing machines with non-identical job sizes and release dates.
- Author
-
Ozturk, Onur, Espinouse, Marie-Laure, Mascolo, MariaDi, and Gouin, Alexia
- Subjects
BATCH processing ,PRODUCTION scheduling ,HEURISTIC algorithms ,LINEAR programming ,APPROXIMATION algorithms ,WASHING machines - Abstract
The problem we study in this paper arises from the washing step of hospital sterilisation services. Washers in the washing step are capable of handling more than one medical device set as long as their capacity is not exceeded. The medical device set sizes and arrival times to the sterilisation service may be different, but they all have the same washing duration. Thus, we model the washing step as a batch scheduling problem where medical device sets are treated as jobs with non-identical sizes and release dates, but equal processing times. The main findings we present in this paper are the following. First, we study two special cases for which polynomial algorithms are presented. We then develop a 2-approximation algorithm for the general problem. Finally, we develop a MILP model and compare it with another MILP model from the literature. Computational results show that our MILP model outperforms the model from the literature. [ABSTRACT FROM PUBLISHER]
- Published
- 2012
- Full Text
- View/download PDF
65. Minimizing the expected time to detect a randomly located lost target using 3-dimensional search technique.
- Author
-
Caraballo, Tomás, Anwar Teamah, Abd El-Moneim, and El-Bagoury, Abd Al-Aziz Hosni
- Subjects
- *
GAUSSIAN distribution , *SEARCH theory , *APPROXIMATION algorithms , *MODEL theory , *STATISTICS - Abstract
This paper considers a new model in search theory to find a randomly located target in the 3-dimensional space. An approximation algorithm that facilitates searching procedures for searchers or robots is presented. The expected time to detect the target is also proved. The statistical analysis by calculating the optimal search strategy which minimizes the time to detect the target, assuming trivariate standard normal distribution is provided, and the technique by flowcharts is designed as well. The effectiveness of this strategy is illustrated by introducing an application from real world. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
66. Bandwidth selector for nonparametric recursive density estimation for spatial data defined by stochastic approximation method.
- Author
-
Bouzebda, Salim and Slaoui, Yousri
- Subjects
- *
NONPARAMETRIC estimation , *CENTRAL limit theorem , *KERNEL (Mathematics) , *BANDWIDTHS , *STOCHASTIC approximation , *APPROXIMATION algorithms , *DENSITY - Abstract
In this article we propose an automatic selection of the bandwidth of the recursive kernel density estimators for spatial data defined by the stochastic approximation algorithm. We showed that, using the selected bandwidth and the stepsize which minimize the MWISE (Mean Weighted Integrated Squared Error), the recursive estimator will be quite similar to the nonrecursive one in terms of estimation error and much better in terms of computational costs. In addition, we obtain the central limit theorem for the nonparametric recursive density estimator under some mild conditions. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
67. Semi-Average Sampling for Shift-Invariant Signals in a Mixed Lebesgue Space.
- Author
-
Jiang, Yingchun and Kou, Junke
- Subjects
- *
SIGNAL sampling , *IRREGULAR sampling (Signal processing) , *SUBSPACES (Mathematics) , *APPROXIMATION algorithms , *SPACE , *FUNCTIONALS - Abstract
This article mainly studies the nonuniform and semi-average sampling of time-varying shift-invariant signals living in a mixed Lebesgue space L p , q (R d + 1) , under the condition that the generator φ of the shift-invariant subspace belongs to a hybrid-norm space of mixed form depending on the orders p and q. First, the sampling stability for two kinds of semi-average sampling functionals is established. Then, we give the corresponding iterative approximation projection algorithms with exponential convergence for recovering the time-based shift-invariant signals from the semi-average samples. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
68. Approximation algorithms for scheduling C-benevolent jobs on weighted machines.
- Author
-
Yu, Ge and Jacobson, Sheldon H.
- Subjects
- *
ONLINE algorithms , *APPROXIMATION algorithms , *COMPUTER scheduling , *GREEDY algorithms , *DETERMINISTIC algorithms , *INFINITY (Mathematics) - Abstract
This article considers a new variation of the online interval scheduling problem, which consists of scheduling C-benevolent jobs on multiple heterogeneous machines with different positive weights. The reward for completing a job assigned to a machine is given by the product of the job value and the machine weight. The objective of this scheduling problem is to maximize the total reward for completed jobs. Two classes of approximation algorithms are analyzed, Cooperative Greedy algorithms and Prioritized Greedy algorithms, with competitive ratios provided. We show that when the weight ratios between machines are small, the Cooperative Greedy algorithm outperforms the Prioritized Greedy algorithm. As the weight ratios increase, the Prioritized Greedy algorithm outperforms the Cooperative Greedy algorithm. Moreover, as the weight ratios approach infinity, the competitive ratio of the Prioritized Greedy algorithm approaches four. We also provide a lower bound of 3/2 and 9/7 for the competitive ratio of any deterministic algorithm for scheduling C-benevolent jobs on two and three machines with arbitrary weights, respectively. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
69. Data-driven satisficing measure and ranking.
- Author
-
Huang, Wenjie
- Subjects
STOCHASTIC approximation ,APPROXIMATION algorithms ,RISK assessment - Abstract
We propose a computational framework for real-time risk assessment and prioritising for random outcomes without prior information on probability distributions. The basic model is built based on satisficing measure (SM) which yields a single index for risk comparison. Since SM is a dual representation for a family of risk measures, we consider problems constrained by general convex risk measures and specifically by conditional value-at-risk. Starting from offline optimisation, we apply sample average approximation technique and argue the convergence rate and validation of optimal solutions. In online stochastic optimisation case, we develop primal-dual stochastic approximation algorithms respectively for general risk constrained problems, and derive their regret bounds. For both offline and online cases, we illustrate the relationship between risk ranking accuracy with sample size (or iterations). [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
70. A budgeted maximum multiple coverage model for cybersecurity planning and management.
- Author
-
Zheng, Kaiyue, Albert, Laura A., Luedtke, James R., and Towle, Eli
- Subjects
- *
GREEDY algorithms , *APPROXIMATION algorithms , *KNAPSACK problems , *INTERNET security , *CYBER intelligence (Computer security) , *COMPUTER crime prevention - Abstract
This article studies how to identify strategies for mitigating cyber-infrastructure vulnerabilities. We propose an optimization framework that prioritizes the investment in security mitigations to maximize the coverage of vulnerabilities. We use multiple coverage to reflect the implementation of a layered defense, and we consider the possibility of coverage failure to address the uncertainty in the effectiveness of some mitigations. Budgeted Maximum Multiple Coverage (BMMC) problems are formulated, and we demonstrate that the problems are submodular maximization problems subject to a knapsack constraint. Other variants of the problem are formulated given different possible requirements for selecting mitigations, including unit cost cardinality constraints and group cardinality constraints. We design greedy approximation algorithms for identifying near-optimal solutions to the models. We demonstrate an optimal (1–1/e)-approximation ratio for BMMC and a variation of BMMC that considers the possibility of coverage failure, and a 1/2-approximation ratio for a variation of BMMC that uses a cardinality constraint and group cardinality constraints. The computational study suggests that our models yield robust solutions that use a layered defense and provide an effective mechanism to hedge against the risk of possible coverage failure. We also find that the approximation algorithms efficiently identify near-optimal solutions, and that a Benders branch-and-cut algorithm we propose can find provably optimal solutions to the vast majority of our test instances within an hour for the variations of the proposed models that consider coverage failures. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
71. A randomised algorithm for computing static-output-feedbacks for large-scale systems.
- Author
-
Peretz, Y. and Wu, W.
- Subjects
- *
ALGORITHMS , *SEARCH algorithms , *APPROXIMATION algorithms - Abstract
A randomised algorithm is proposed for computing globally optimal static-output-feedbacks for large-scale systems. The algorithm is based on the Ray-Shooting Method and involves some heuristics to accelerate the search. We also improve the basic Ray-Shooting Algorithm and make the search in the controller parameter-space (which generally, is much more smaller than the certificate parameter-space), thus enabling its efficient use for large-scale systems. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
72. Simultaneous distribution and sizing optimization for stiffeners with an improved genetic algorithm with two-level approximation.
- Author
-
Chen, Shenyan, Dong, Tianshan, and Shui, Xiaofang
- Subjects
- *
APPROXIMATION algorithms , *TOPOLOGY - Abstract
This article presents an improved genetic algorithm with two-level approximation (GATA) to optimize the distribution and size of stiffeners simultaneously. A novel optimization model of stiffeners, including two kinds of design variables, is established. The first level approximation problem transforms the original implicit problem to an explicit problem which involves the topology and size variables. Then, a genetic algorithm (GA) addresses the mixed variables. The individuals in the GA are coded by topology variables, and when calculating an individual's fitness, the second level approximation problem is embedded to optimize the size variables. Considering the stiffeners' optimization, several aspects of the initial GATA are updated, including the relationship between two kinds of variables, the weight and its sensitivity calculation and the GA strategy, to optimize the stiffeners' size and distribution simultaneously. Numerical examples show that the improved GATA is effective in optimizing the stiffened shells' topology and size variables simultaneously. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
73. The multi-resource agent bottleneck generalised assignment problem.
- Author
-
Karsu, Özlem and Azizoğlu, Meral
- Subjects
BOTTLENECKS (Manufacturing) ,PRODUCTION scheduling ,COMPUTER simulation of production scheduling ,LINEAR programming ,APPROXIMATION algorithms ,BRANCH & bound algorithms - Abstract
In this study, we consider the multi resource agent bottleneck generalised assignment problem. Our aim is to minimise the maximum load over all agents. We take our motivation from an assignment problem faced in heating, ventilating and air conditioning sector. We study the linear programming (LP) relaxation of the problem. We use the optimal LP relaxation solutions in our branch and bound algorithm while defining bounding and branching schemes. We find that our branch and bound algorithm returns optimal solutions to the problems with up to 60 jobs when the number of agents is 5, and up to 30 jobs when the number of agents is 10, in less than 20 minutes. To find approximate solutions, we define a tabu search algorithm and α approximation algorithm. Our computational results have revealed that both algorithms can find high quality solutions to large sized instances very quickly. To the best of our knowledge our study is the first reported attempt to solve the problem. We hope our study fills an important gap in the literature. [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
74. A scatter search heuristic for maximising the net present value of a resource-constrained project with fixed activity cash flows.
- Author
-
Vanhoucke, Mario
- Subjects
HEURISTIC algorithms ,COMPUTER algorithms ,APPROXIMATION algorithms ,CASH flow ,PRODUCTION scheduling ,TIME management - Abstract
In this paper, we present a meta-heuristic algorithm for the resource-constrained project scheduling problem with discounted cash flows. We assume fixed payments associated with the execution of project activities and develop a heuristic optimisation procedure to maximise the net present value of a project subject to the precedence and renewable resource constraints. We investigate the use of a bi-directional generation scheme and a recursive forward/backward improvement method from literature and embed them in a meta-heuristic scatter search framework. We generate a large dataset of project instances under a controlled design and report detailed computational results. The solutions and project instances can be downloaded from a website in order to facilitate comparison with future research attempts. [ABSTRACT FROM AUTHOR]
- Published
- 2010
- Full Text
- View/download PDF
75. Permutation flowshop scheduling with simple linear deterioration.
- Author
-
Sun, Lin-Hui, Ge, Chen-Chen, Zhang, Wei, Wang, Ji-Bo, and Lu, Yuan-Yuan
- Subjects
- *
APPROXIMATION algorithms , *PERMUTATIONS , *LOGARITHMS , *PRODUCTION scheduling , *SCHEDULING - Abstract
This article addresses permutation flowshop scheduling problems with simple linear deterioration. The objectives are to minimize logarithm of the makespan, total logarithm of the completion time, total weighted logarithm of the completion time, and the sum of the quadratic job logarithms of the completion times. Approximation algorithms and their worst-case bounds are presented and analysed. Branch-and-bound algorithms are also proposed to solve the problems optimally. Computational experiments are performed to illustrate the algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
76. Using Approximation Algorithms to Build Evidence Factors and Related Designs for Observational Studies.
- Author
-
Karmakar, Bikram, Small, Dylan S., and Rosenbaum, Paul R.
- Subjects
- *
SCIENTIFIC observation , *POLYNOMIAL time algorithms , *OPERATIONS research , *APPROXIMATION algorithms , *EVIDENCE , *AIR bag restraint systems , *SYSTEM analysis - Abstract
Observational or nonrandomized studies of treatment effects are often constructed with the aid of polynomial-time algorithms that optimally form matched treatment-control pairs or matched sets. Because each observational comparison may potentially be affected by bias, investigators often reinforce a single comparison with an additional comparison that is unlikely to be affected by the same biases, for instance using multiple control groups or evidence factors or control + instrument designs. Use of two comparisons affected by different biases may detect bias if the two comparisons disagree, or may show that two comparisons with different weakness concur in their conclusions. Even this simplest addition—a second comparison—creates design problems without polynomial-time solutions. Faced with a problem that no polynomial-time algorithm can solve, a so-called approximation algorithm is a type of compromise: it provides a solution in polynomial time that is provably not much worse than the unattainable optimal solution. Building upon existing techniques for related problems in operations research, we develop an approximation algorithm for minimum distance matching with near-fine balance for three comparison groups. This algorithm is a practical approach to most observational designs that add a second comparison. The method is applied to an observational study of the effects of side airbags on injury severity in the U.S. Fatality Analysis Reporting System. For many car makes and models, side airbags were initially unavailable, then later available as optional equipment for an additional fee, then still later provided as standard equipment. Within sets matched for make and model of car, for safety belt use, for direction of impact, and other covariates, we compare crashes in these three periods, where each comparison has different limitations. The method is implemented in the R package approxmatch, whose example reproduces some of the calculations. for this article are available online. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
77. String-averaging incremental stochastic subgradient algorithms.
- Author
-
Oliveira, R. M., Helou, E. S., and Costa, E. F.
- Subjects
- *
STOCHASTIC approximation , *CONVEX programming , *ALGORITHMS , *STOCHASTIC programming , *APPROXIMATION algorithms , *CONVEX functions , *RANDOM sets - Abstract
We present a method to solve constrained convex stochastic optimization problems when the objective is a finite sum of convex functions. Our method is based on Incremental Stochastic Subgradient Algorithms and String-Averaging techniques, with an assumption that the subgradient directions are affected by random errors in each iteration. Our analysis allows the method to perform approximate projections onto the feasible set in each iteration. We provide convergence results for the case where a diminishing step-size rule is used. We test our method in a large set of random instances of a stochastic convex programming problem and we compare its performance with the robust mirror descent stochastic approximation algorithm proposed in Nemirovski et al. (Robust stochastic approximation approach to stochastic programming, SIAM J Optim 19 (2009), pp. 15741609). [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
78. Order Reduction Techniques via Routh Approximation: A Critical Survey.
- Author
-
Choudhary, Amit Kumar and Nagar, Shyam Krishna
- Subjects
- *
APPROXIMATION algorithms , *UNCERTAIN systems , *ORDER - Abstract
Routh Approximation is believed to witness tremendous usage in deriving the reduced models from their higher equivalents. Order reduction is a critical field of interest for researchers or control engineers dealing with practical and physical systems of higher order. Reason for the popularity of Routh Approximation among other reduction methodologies is its strength of computational simplicity, ease of access and the promise to retain the model stability. This paper accomplishes a survey of the available Routh Approximation algorithms in their varied configuration since five decades. Last survey report based on Routh Approximation was cited in late seventies as discussed in the paper. One prime reason for the outcome of this paper is the problem met by the authors during their own work for analysing varied configuration of Routh Approximation for order reduction. Many times, the arrangement, stated or performed, seemed to be already in existence. Thus, the paper would be helpful to the researchers working in the area of order reduction and have prime focus on the utility of Routh Approximation. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
79. On approximations of the Euler-Peano scheme for multivalued stochastic differential equations.
- Author
-
Wu, Jing and Zhang, Mingbo
- Subjects
- *
STOCHASTIC differential equations , *EULER acceleration , *PEANO axioms , *APPROXIMATION algorithms , *LIPSCHITZ spaces , *KOLMOGOROV complexity - Abstract
It is known that a unique strong solution exists for multivalued stochastic differential equations under the Lipschitz continuity and linear growth conditions. In this paper we apply the Euler-Peano scheme to show that existence of weak solution and pathwise uniqueness still hold when the coefficients are random and satisfy one-sided locally Lipschitz continuous and an integral condition (i.e. Krylov's conditions put forward in On Kolmogorov's equations for finite-dimensional diffusions, Stochastic PDE's and Kolmogorov Equations in Infinite Dimensions (Cetraro, 1998), Lecture Notes in Math., 1715, Springer, Berlin, 1999, pp. 1-63). When the coefficients are nonrandom and possibly discontinuous but only satisfy some integral conditions, the sequence of solutions of the Euler-Peano scheme converges weakly, and the limit is a weak solution of the corresponding MSDE. As a particular case, we obtain a global semi-flow for stochastic differential equations reflected in closed, convex domains. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
80. Asymptotic expansion for forward-backward SDEs with jumps.
- Author
-
Fujii, Masaaki and Takahashi, Akihiko
- Subjects
- *
JUMPING , *STOCHASTIC differential equations , *APPROXIMATION algorithms , *POISSON processes , *BROWNIAN motion - Abstract
This work provides a semi-analytic approximation method for decoupled forward-backward SDEs (FBSDEs) with jumps. In particular, we construct an asymptotic expansion method for FBSDEs driven by the random Poisson measures with σ-finite compensators as well as the standard Brownian motions around the small-variance limit of the forward SDE. We provide a semi-analytic solution technique as well as its error estimate for which we only need to solve essentially a system of linear ODEs. In the case of a finite jump measure with a bounded intensity, the method can also handle state-dependent and hence non-Poissonian jumps, which are quite relevant for many practical applications. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
81. On bootstrap testing inference in cure rate models.
- Author
-
Loose, Laís H., Valença, Dione Maria, and Bayer, Fábio Mariano
- Subjects
- *
STATISTICAL bootstrapping , *PARAMETER estimation , *APPROXIMATION algorithms , *RESAMPLING (Statistics) , *SIMULATION methods & models - Abstract
Survival models deal with the time until the occurrence of an event of interest. However, in some situations the event may not occur in part of the studied population. The fraction of the population that will never experience the event of interest is generally called cure rate. Models that consider this fact (cure rate models) have been extensively studied in the literature. Hypothesis testing on the parameters of these models can be performed based on likelihood ratio, gradient, score or Wald statistics. Critical values of these tests are obtained through approximations that are valid in large samples and may result in size distortion in small or moderate sample sizes. In this sense, this paper proposes bootstrap corrections to the four mentioned tests and bootstrap Bartlett correction for the likelihood ratio statistic in the Weibull promotion time model. Besides, we present an algorithm for bootstrap resampling when the data presents cure fraction and right censoring time (random and non-informative). Simulation studies are conducted to compare the finite sample performances of the corrected tests. The numerical evidence favours the corrected tests we propose. We also present an application in an actual data set. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
82. An Improved Method for ASEP Evaluation over Fading Channels Based on Q-Function Approximation.
- Author
-
Markovic, Aleksandar V., Peric, Zoran H., Panic, Stefan R., Spalevic, Petar C., and Prlincevic, Bojan P.
- Subjects
- *
RADIO transmitter fading , *APPROXIMATION algorithms , *MODULATION theory , *ERROR probability , *MATHEMATICAL bounds - Abstract
In this paper, capitalizing on novely introduced interval approximation of Q-function, we have presented simple and tight approximation for the evaluation of the average symbol error probability (ASEP) over fading channels. First, comparison to other known Q-function closed-form approximations has been performed, and it has been shown that accuracy improvement has been achieved by using proposed interval approximation in whole range of input values. Further, it has been shown that by using proposed approximation, values of ASEP for some applied modulation formats could be efficiently and accurately evaluated when transmission over fading channels is observed. Also has been shown that than by using proposed approximation, ASEP measures are bounded more closely than by using other known Q-function closed-form approximations. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
83. Reliability Evaluation of IEC 61850 Process Bus Architecture for Protection Function.
- Author
-
Mo, Jun and Tan, Jiancheng
- Subjects
- *
ARCHITECTURE , *RELIABILITY in engineering , *BUILDING protection , *APPROXIMATION algorithms , *REDUNDANCY in engineering , *USB technology - Abstract
The complex redundancy architecture of IEC 61850 process bus brings difficulties to the reliability analysis of digital protection system. An approximation method can be considered for the reliability analysis of protection system. This article analyses the weakness of conventional reliability approximation algorithms in the aspects of calculation accuracy, and then presents a disjoint path set (DPS)-based approximation method which is simple and practical. The sampled value (SV) and generic-object-oriented substation event (GOOSE) are adopted as the basic function to build the protection function model. The digital protection system is expressed as a single-input multiple-output (SIMO) model which is more suitable for describing distributed protection function. A case of the line protection in a 3/2 connection system is analyzed to demonstrate the validity of the proposed method and model. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
84. A new complex approach towards approximate inverse and generalized Radon transform.
- Author
-
Li, Wei and Wang, Jinping
- Subjects
- *
MATHEMATICAL complexes , *INVERSE problems , *APPROXIMATION algorithms , *GENERALIZED integrals , *RADON transforms - Abstract
In this paper, we first consider the framework of Sobolev spaces and derive analytically a reconstruction algorithm by means of the residue theorem of complex analysis, the approximate inverse, Gaussian mollifier and integral equations. And we successfully extend Natterer’s results to the generalized Radon transform with non-uniform attenuation. Finally, we investigate the smoothing properties of the generalized Radon transform. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
85. The Wild Goose Chase Problem.
- Author
-
Gard, Andrew
- Subjects
- *
PROBABILITY theory , *ARTIFICIAL intelligence , *CRYSTAL structure , *ROBUST control , *ALGORITHMS , *APPROXIMATION algorithms - Abstract
The classical pursuit problem considers the path traced by a point in space as it charges directly toward a moving target. But what if the target has more lofty goals than mere escape? To what degree can it control the path taken by its pursuer? We prove that the pursuer can be led to any point in
without being allowed to close more than an arbitrarily small distance en route. [ABSTRACT FROM AUTHOR] - Published
- 2018
- Full Text
- View/download PDF
86. Computing the Shapley value in allocation problems: approximations and bounds, with an application to the Italian VQR research assessment program.
- Author
-
Lupia, Francesco, Mendicelli, Angelo, Ribichini, Andrea, Scarcello, Francesco, and Schaerf, Marco
- Subjects
- *
ASSIGNMENT problems (Programming) , *GAME theory , *APPROXIMATION algorithms , *MATHEMATICAL bounds , *ALGORITHMS - Abstract
In allocation problems with indivisible goods, money compensation is used to distribute worth in a fair way. Coalitional games provide a formal mathematical framework to model such problems, and the Shapley value is a solution concept widely used to realise a fair distribution. To overcome its intractability, we describe how to simplify allocation problems and we propose algorithms for computing lower bounds and upper bounds of the Shapley value that can be combined with approximation algorithms. The proposed techniques have been implemented and tested on a real-world application of allocation problems, namely, the Italian research assessment program known as VQR. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
87. On Minty variational principle for nonsmooth vector optimization problems with generalized approximate convexity.
- Author
-
Gupta, Pooja and Mishra, S. K.
- Subjects
- *
NONSMOOTH optimization , *APPROXIMATION algorithms , *MATHEMATICAL optimization , *NUMERICAL analysis , *PROBLEM solving - Abstract
In this paper, we consider a nonsmooth vector optimization problem involving locally Lipschitz generalized approximate convex functions and find some relations between approximate convexity and generalized approximate convexity. We establish relationships between vector variational inequalities and nonsmooth vector optimization problem using the generalized approximate convexity as a tool. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
88. Robust confidence regions for the semi-parametric regression model with responses missing at random.
- Author
-
Bindele, Huybrechts F., Abebe, Asheber, and Meyer, Nicole K.
- Subjects
- *
MONTE Carlo method , *REGRESSION analysis , *WILCOXON signed-rank test , *ROBUST control , *APPROXIMATION algorithms - Abstract
In this paper, a regression semi-parametric model is considered where responses are assumed to be missing at random. From the empirical likelihood function defined based on the rank-based estimating equation, robust confidence intervals/regions of the true regression coefficient are derived. Monte Carlo simulation experiments show that the proposed approach provides more accurate confidence intervals/regions compared to its normal approximation counterpart under different model error structure. The approach is also compared with the least squares approach, and its superiority is shown whenever the error distribution in the simulation study is heavy tailed or contaminated. Finally, a real data example is given to illustrate our proposed method. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
89. Some properties of the exponential polynomials.
- Author
-
Brychkov, Yu. A.
- Subjects
- *
POLYNOMIALS , *APPROXIMATION algorithms , *COMPLEX variables , *CRYSTAL structure , *EXPONENTIAL functions - Abstract
Representations, differentiation formulas, series expansions and other relations for the exponential polynomials
are given. [ABSTRACT FROM AUTHOR] - Published
- 2018
- Full Text
- View/download PDF
90. Extension and approximation of <italic>m</italic>-subharmonic functions.
- Author
-
Åhag, Per, Czyż, Rafał, and Hed, Lisa
- Subjects
- *
SUBHARMONIC functions , *FUNCTION algebras , *DIRICHLET problem , *APPROXIMATION algorithms , *TOPOLOGY - Abstract
Let
be a bounded domain, and let f be a real-valued function defined on the whole topological boundary. The aim of this paper is to find a characterization of the functions f which can be extended to the inside to am -subharmonic function under suitable assumptions on. We shall do so using a function algebraic approach with focus on m -subharmonic functions defined on compact sets. We end this note with some remarks on approximation ofm -subharmonic functions. [ABSTRACT FROM AUTHOR]- Published
- 2018
- Full Text
- View/download PDF
91. Approximation of convex bodies by multiple objective optimization and an application in reachable sets.
- Author
-
Lizhen Shao, Fangyuan Zhao, and Yuhao Cong
- Subjects
- *
MULTIDISCIPLINARY design optimization , *CONVEX programming , *CONVEX bodies , *APPROXIMATION algorithms , *PROBLEM solving - Abstract
In this paper, we focus on approximating convex compact bodies. For a convex body described as the feasible set in objective space of a multiple objective programme, we show that finding it is equivalent to finding the non-dominated set of a multiple objective programme. This equivalence implies that convex bodies can be approximated using multiple objective optimization algorithms. Therefore, we propose a revised outer approximation algorithm for convex multiple objective programming problems to approximate convex bodies. Finally, we apply the algorithm to solve reachable sets of control systems and use numerical examples to show the effectiveness of the algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
92. Outer-approximation algorithms for nonsmooth convex MINLP problems.
- Author
-
Delfino, A. and de Oliveira, W.
- Subjects
- *
APPROXIMATION algorithms , *STOCHASTIC convergence , *NONSMOOTH optimization , *MIXED integer linear programming , *PROBLEM solving , *CONVEX functions - Abstract
In this work, we combine outer-approximation (OA) and bundle method algorithms for dealingwithmixed-integer non-linear programming (MINLP) problems with nonsmooth convex objective and constraint functions. As the convergence analysis of OA methods relies strongly on the differentiability of the involved functions, OA algorithms may fail to solve general nonsmooth convex MINLP problems. In order to obtain OA algorithms that are convergent regardless the structure of the convex functions, we solve the underlying OA's non-linear subproblems by a specialized bundle method that provides necessary information to cut off previously visited (non-optimal) integer points. This property is crucial for proving (finite) convergence of OA algorithms. We illustrate the numerical performance of the given proposal on a class of hybrid robust and chanceconstrained problems that involve a random variable with finite support. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
93. Alternative GMM estimators for spatial regression models.
- Author
-
Breitung, Jörg and Wigger, Christoph
- Subjects
SPACE in economics ,GENERALIZED method of moments ,PARAMETER estimation ,APPROXIMATION algorithms ,ROBUST control - Abstract
Using approximations of the score of the log-likelihood function, we derive moment conditions for estimating spatial regression models, starting with the spatial error model. Our approach results in computationally simple and robust estimators, such as a new moment estimator derived from the first-order approximation obtained by solving a quadratic moment equation, and performs similarly to existing generalized method of moments (GMM) estimators. Our estimator based on the second-order approximation resembles the GMM estimator proposed by Kelejian and Prucha in 1999. Hence, we provide an intuitive interpretation of their estimator. Additionally, we provide a convenient framework for computing the weighting matrix of the optimal GMM estimator. Heteroskedasticity robust versions of our estimators are also proposed. Furthermore, a first-order approximation for the spatial autoregressive model is considered, resulting in a computationally simple method of moment estimator. The performance of the considered estimators is compared in a Monte Carlo study. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
94. Feasible algorithm for linear mixed model for massive data.
- Author
-
Zhao, Yanyan
- Subjects
- *
ALGORITHMS , *PARAMETERS (Statistics) , *APPROXIMATION algorithms , *LINEAR statistical models , *BIG data - Abstract
This article studies computation problem in the context of estimating parameters of linear mixed model for massive data. Our algorithms combine the factored spectrally transformed linear mixed model method with a sequential singular value decomposition calculation algorithm. This combination solves the operation limitation of the method and also makes this algorithm feasible to big dataset, especially when the data has a tall and thin design matrix. Our simulation studies show that our algorithms make the calculation of linear mixed model feasible for massive data on ordinary desktop and have same estimating accuracy with the method based on the whole data. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
95. Approximation algorithms in partitioning real-time tasks with replications.
- Author
-
Lin, Jian (Denny), Cheng, Albert M. K., and Gercek, Gokhan
- Subjects
- *
APPROXIMATION algorithms , *FAULT-tolerant computing , *REAL-time computing , *MULTIPROCESSORS , *HEURISTIC algorithms - Abstract
Today is an era where multiprocessor technology plays a major role in designs of modern computer architecture. While multiprocessor systems offer extra computing power, it also opens a new range of opportunities to improve fault-robustness. This paper focuses on a problem of achieving fault-tolerance using replications in real-time, multiprocessor systems. In the problem, multiple replicas, or copies, of a computing task are executed on distinct processors to resist potential processor failures and computing faults. Two greedy, approximation heuristics, named Worst Fit Increasing K-Replication and First Fit Increasing K-Replication, are studied to maximise the number of real-time tasks assigned on a system with identical processors, respecting to the tasks’ replicating and timely requirements. Worst case performance is analysed by using an approximation ratio between the algorithms and an optimal solution. We mathematically prove that the ratios of using both algorithms are infinitely close to 2. Simulations are performed on a large set of testing cases which can be used to bring to light the average performance of using the algorithms in practice. The results show that both heuristic algorithms provide simple but fast and effective solutions to solve the problem. Assigning real-time tasks to a multiprocessor system with replications. [ABSTRACT FROM PUBLISHER]
- Published
- 2018
- Full Text
- View/download PDF
96. Approximation of Non-Lipschitz SDEs by Picard Iterations.
- Author
-
Baptiste, Julien, Grepat, Julien, and Lepinette, Emmanuel
- Subjects
APPROXIMATION algorithms ,LIPSCHITZ spaces ,PICARD number ,PRICING ,DIFFERENTIAL equations - Abstract
In this article, we propose an approximation method based on Picard iterations deduced from the Doléans-Dade exponential formula. Our method allows to approximate trajectories of Markov processes in a large class, e.g., solutions to non-Lipchitz stochastic differential equation. An application to the pricing of Asian-style contingent claims in the constant elasticity of variance model is presented and compared to other methods of the literature. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
97. Model reduction by iterative error system approximation.
- Author
-
Antoulas, A. C., Benner, Peter, and Feng, Lihong
- Subjects
- *
APPROXIMATION theory , *ITERATIVE methods (Mathematics) , *LINEAR systems , *REDUCED-order models , *APPROXIMATION algorithms - Abstract
The analysis of a posteriori error estimates used in reduced basis methods leads to a model reduction scheme for linear time-invariant systems involving the iterative approximation of the associated error systems. The scheme can be used to improve reduced-order models (ROMs) with initial poor approximation quality at a computational cost proportional to that for computing the original ROM. We also show that the iterative approximation scheme is applicable to parametric systems and demonstrate its performance using illustrative examples. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
98. Approximation of optimal filter for Ornstein–Uhlenbeck process with quantised discrete-time observation.
- Author
-
Bania, Piotr and Baranowski, Jerzy
- Subjects
- *
APPROXIMATION algorithms , *ORNSTEIN-Uhlenbeck process , *QUANTUM Hall effect , *DISCRETE-time systems , *GALERKIN methods - Abstract
Quantisation of signals is a ubiquitous property of digital processing. In many cases, it introduces significant difficulties in state estimation and in consequence control. Popular approaches either do not address properly the problem of system disturbances or lead to biased estimates. Our intention was to find a method for state estimation for stochastic systems with quantised and discrete observation, that is free of the mentioned drawbacks. We have formulated a general form of the optimal filter derived by a solution of Fokker–Planck equation. We then propose the approximation method based on Galerkin projections. We illustrate the approach for the Ornstein–Uhlenbeck process, and derive analytic formulae for the approximated optimal filter, also extending the results for the variant with control. Operation is illustrated with numerical experiments and compared with classical discrete-continuous Kalman filter. Results of comparison are substantially in favour of our approach, with over 20 times lower mean squared error. The proposed filter is especially effective for signal amplitudes comparable to the quantisation thresholds. Additionally, it was observed that for high order of approximation, state estimate is very close to the true process value. The results open the possibilities of further analysis, especially for more complex processes. [ABSTRACT FROM PUBLISHER]
- Published
- 2018
- Full Text
- View/download PDF
99. Optimal robust control of nonlinear time-delay systems: Maintaining low operating errors during feedback outages.
- Author
-
Choi, Ho–Lim and Hammer, Jacob
- Subjects
- *
OPTIMAL control theory , *ROBUST control , *NONLINEAR control theory , *TIME delay systems , *FEEDBACK control systems , *ERROR analysis in mathematics , *APPROXIMATION algorithms - Abstract
The problem of maintaining low operating errors during feedback outages is considered for a class of nonlinear systems with time-delays in the input channel. It is shown that there are optimal controllers that keep operating errors below a specified bound for the longest time possible. Furthermore, it is shown that optimal performance can be approximated as closely as desired by using bang-bang controllers – controllers that are relatively easy to calculate and implement. [ABSTRACT FROM PUBLISHER]
- Published
- 2018
- Full Text
- View/download PDF
100. Performance recovery of a class of uncertain non-affine systems with unmodelled dynamics: an indirect dynamic inversion method.
- Author
-
Yi, Bowen, Lin, Shuyi, Yang, Bo, and Zhang, Weidong
- Subjects
- *
FEEDBACK control systems , *PERFORMANCE evaluation , *APPROXIMATION algorithms , *ROBUST control , *MATHEMATICAL proofs - Abstract
This paper presents an output feedback indirect dynamic inversion (IDI) approach for a class of uncertain nonaffine systems with input unmodelled dynamics. Compared with previous approaches to achieve performance recovery, the proposed method aims at dealing with a broader class of nonaffine-in-control systems with triangular structure. An IDI state feedback law is designed first, in which less knowledge of the model plant is needed compared to earlier approximate dynamic inversion methods, thus yielding more robust performance. After that, an extended high-gain observer is designed to accomplish the task with output feedback. Finally, we prove that the designed IDI controller is equivalent to an adaptive proportional-integral (PI) controller, with respect to both time response equivalence and robustness equivalence. The conclusion implies that for the studied strict-feedback non-affine systems with unmodelled dynamics, there always exits a PI controller to stabilise the systems. The effectiveness and benefits of the designed approach are verified by three examples. [ABSTRACT FROM PUBLISHER]
- Published
- 2018
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.