Criticality analysis of activity networks under interval uncertainty

This paper reconsiders the Project Evaluation and Review Technique (PERT) scheduling problem when information about task duration is incomplete. We model uncertainty on task durations by intervals. With this problem formulation, our goal is to assert possible and necessary criticality of the different tasks and to compute their possible earliest starting dates, latest starting dates, and floats. This paper combines various results and provides a complete solution to the problem. We present the complexity results of all considered subproblems and efficient algorithms to solve them.     

Fast routing computation on InfiniBand networks

The InfiniBand architecture has been proposed as a technology both for communication between processing nodes and I/O devices, and for interprocessor communication. Its specification defines a basic management infrastructure that is responsible for subnet configuration and fault tolerance. Each time a topology change is detected, new forwarding tables have to be computed and uploaded to devices. The time required to compute these tables is a critical issue, due to application traffic is negatively affected by the temporary lack of connectivity. In this paper, we show the way to integrate several routing algorithms, in order to combine their advantages. In particular, we merge a new proposal, characterized by its high computation speed but low efficiency, with a traditional one, slower but more efficient. Our goal is to provide new routes in a short period of time, minimizing the degradation mentioned before, and maintaining, at the same time, high network performance.     

Engineering computation under uncertainty - Capabilities of non-traditional models

This paper provides a review of various non-traditional uncertainty models for engineering computation and responds to the criticism of those models. This criticism imputes inappropriateness in representing uncertain quantities and an absence of numerically efficient algorithms to solve industry-sized problems. Non-traditional uncertainty models, however, run counter to this criticism by enabling the solution of problems that defy an appropriate treatment with traditional probabilistic computations due to non-frequentative characteristics, a lack of available information, or subjective influences. The usefulness of such models becomes evident in many cases within engineering practice. Examples include: numerical investigations in the early design stage, the consideration of exceptional environmental conditions and socio-economic changes, and the prediction of the behavior of novel materials based on limited test data. Non-traditional uncertainty models thus represent a beneficial supplement to the traditional probabilistic model and a sound basis for decision-making. In this paper non-probabilistic uncertainty modeling is discussed by means of interval modeling and fuzzy methods. Mixed, probabilistic/non-probabilistic uncertainty modeling is dealt with in the framework of imprecise probabilities possessing the selected components of evidence theory, interval probabilities, and fuzzy randomness. The capabilities of the approaches selected are addressed in view of realistic modeling and processing of uncertain quantities in engineering. Associated numerical methods for the processing of uncertainty through structural computations are elucidated and considered from a numerical efficiency perspective. The benefit of these particular developments is emphasized in conjunction with the meaning of the uncertain results and in view of engineering applications.     

Adaptive stabilization of minimum phase plant under Lipschitz uncertainty

Consideration was given to the problem of adaptive stabilization of the minimum phase plant under Lipschitz uncertainty and bounded external disturbance with unknown upper bound. The proposed adaptive stabilization algorithm is based on the recurrent set estimation of the unknown plant parameters, Lipschitz uncertainty, and the upper bound of the external disturbance and includes the online verification of the control plant model.     

不确定条件下的质量交换网络综合

基于现有的质量交换网络综合方法,同时考虑不确定因素对于综合过程的影响,提出了不确定条件下质量交换网络综合的两步综合法。该方法首先确定网络结构,然后以年度总费用为综合目标,对设备尺寸和操作参数进行随机优化,并讨论了两种不同的随机模型的优化：期望值模型与机会约束模型。采用遗传算法和蒙特卡洛随机模拟相结合对上述随机优化模型进行求解。实例计算表明了这一综合方法的合理性以及算法的可行性。     

Maximum compatibility method for data fitting under interval uncertainty

For the linear regression model, the data-fitting problem under the interval uncertainty of the data is studied. As an estimate of the linear function parameters, it is proposed to take their values that deliver the maximum for the so-called recognizing functional of the parameter set compatible with the data (the maximum compatibility method). The properties of the recognizing functional, its interpretation, and the properties of the estimates obtained using the maximum compatibility method are investigated. The relationships to other data analysis methods are discussed, and a practical electrochemistry problem is solved.     

Fast symbolic computation of the worst-case delay in tandem networks and applications

Computing deterministic performance guarantees is a defining issue for systems with hard real-time constraints, like reactive embedded systems. In this paper, we use burst-rate constrained arrivals and rate-latency servers to deduce tight worst-case delay bounds in tandem networks under arbitrary multiplexing. We present a constructive method for computing the exact worst-case delay, which we prove to be a linear function of the burstiness and latencies; our bounds are hence symbolic in these parameters. Our algorithm runs in quadratic time in the number of servers. We also present an application of our algorithm to the case of stochastic arrivals and server capacities. For a generalization of the exponentially bounded burstiness (EBB) model, we deduce a polynomial-time algorithm for stochastic delay bounds that strictly improve the state-of-the-art separated flow analysis (SFA) type bounds.     

Solvability of interval linear equations and data analysis under uncertainty

Consideration was given to the problem of recognizing the solvability (nonemptiness of the solution set) of an interval systems of linear equations. A method based on the so-called recognizing functional of the solution set was proposed to solve it. A new approach to data processing under interval uncertainty based on the unconstrained maximization of the recognizing functional (“maximal consistency method”) was presented as an application, and its informal interpretations were described     

A modified Benders decomposition method for efficient robust optimization under interval uncertainty

The goal of robust optimization problems is to find an optimal solution that is minimally sensitive to uncertain factors. Uncertain factors can include inputs to the problem such as parameters, decision variables, or both. Given any combination of possible uncertain factors, a solution is said to be robust if it is feasible and the variation in its objective function value is acceptable within a given user-specified range. Previous approaches for general nonlinear robust optimization problems under interval uncertainty involve nested optimization and are not computationally tractable. The overall objective in this paper is to develop an efficient robust optimization method that is scalable and does not contain nested optimization. The proposed method is applied to a variety of numerical and engineering examples to test its applicability. Current results show that the approach is able to numerically obtain a locally optimal robust solution to problems with quasi-convex constraints (≤ type) and an approximate locally optimal robust solution to general nonlinear optimization problems.     

On private computation in incomplete networks

Suppose that some parties are connected by an incomplete network of reliable and private channels. The parties cooperate to execute some protocol. However, the parties are curious—after the protocol terminates each party tries to learn information from the communication it heard. We say that a function can be computed privately in a network if there is a protocol in which each processor learns only the information implied by its input and the output of the function (in the information theoretic sense). The question we address in this paper is what functions can be privately computed in a given incomplete network. Every function can be privately computed in two-connected networks with at least three parties. Thus, the question is interesting only for non two-connected networks. Generalizing results of (Bläser et al. in J. Cryptol, 19(3): 341–357, 2006), we characterize the functions that can be computed privately in simple networks—networks with one separating vertex and no leaves. We then deal with private computations in arbitrary non two-connected networks: we reduce this question to private computations of related functions on trees, and give some sufficient conditions and necessary conditions on the functions that can be privately computed on trees.     

New Approximation Assisted Multi-objective collaborative Robust Optimization (new AA-McRO) under interval uncertainty

Existing collaborative optimization techniques with multiple coupled subsystems are predominantly focused on single-objective deterministic optimization. However, many engineering optimization problems have system and subsystems that can each be multi-objective, constrained and with uncertainty. The literature reports on a few deterministic Multi-objective Multi-Disciplinary Optimization (MMDO) techniques. However, these techniques in general require a large number of function calls and their computational cost can be exacerbated when uncertainty is present. In this paper, a new Approximation-Assisted Multi-objective collaborative Robust Optimization (New AA-McRO) under interval uncertainty is presented. This new AA-McRO approach uses a single-objective optimization problem to coordinate all system and subsystem multi-objective optimization problems in a Collaborative Optimization (CO) framework. The approach converts the consistency constraints of CO into penalty terms which are integrated into the system and subsystem objective functions. The new AA-McRO is able to explore the design space better and obtain optimum design solutions more efficiently. Also, the new AA-McRO obtains an estimate of Pareto optimum solutions for MMDO problems whose system-level objective and constraint functions are relatively insensitive (or robust) to input uncertainties. Another characteristic of the new AA-McRO is the use of online approximation for objective and constraint functions to perform system robustness evaluation and subsystem-level optimization. Based on the results obtained from a numerical and an engineering example, it is concluded that the new AA-McRO performs better than previously reported MMDO methods.     

Managing uncertainty and discontinuous condition numbers in geometric computation

We consider operations on subdivision surfaces under the strict robustness requirement that these floating-point computations return an object with the same topological form as the true solution. The problems involved may however be ill-conditioned, and defined in terms of uncertain data, and even supplementary interval arithmetic may not ensure robustness. Trapping mechanisms are therefore proposed to resolve this difficulty.     

Augmenting predictive with oblivious routing for wireless mesh networks under traffic uncertainty

Traffic routing is central to the utility and scalability of wireless mesh networks. Many recent routing studies have examined this issue, but generally they have assumed that the demand is constant and given in advance. On the contrary, wireless traffic studies have shown that demand is highly variable and difficult to predict, even when aggregated at access points.There are several approaches for handling volatile traffic. On one hand, traffic may be modeled in real-time with a dynamic routing based upon forecasted traffic demand. On the other hand, routing can be made with the focus towards maximally unbalanced demand, such that the worst-case performance is contained (known as oblivious routing). The first approach can perform competitively when traffic can be forecasted with accuracy, but may result in unbounded worst-case performance when forecasts go wrong. It is an open question how these two approaches would compare with each other in real networks and if possible at all, whether a benchmark could be defined to guide the selection of the appropriate routing strategy.To answer the above open question, this paper conducts a systematic comparison study of the two approaches based on the extensive simulation study over a variety of network scenarios with real-world traffic trace. It identifies the key factors of the network topology and traffic profile that affect the performance of each routing strategy. A series of metrics are examined with varying powers of forecasting whether predictive routing or oblivious routing will perform better. Following the guidelines defined by these metrics, we present an adaptive strategy which augments the performance of the predictive routing with the worst-case bound provided by the oblivious routing through adaptive selection of routing strategies based on the degree of traffic uncertainty.     

Robust stabilizing inventory control in supply networks under uncertainty of external demand and supply time-delays

A synthesis problem of the robust inventory control strategy for supply networks under uncertain bounded demand and uncertainty of supply time-delays and with presence of asymmetric constraints on states and controls is considered. Control is constructed based on the invariant ellipsoid method as a linear non-stationary feedback with respect to deviation of the current stock level from the chosen safety level. Solvability conditions of the synthesis problem are stated in the form of linear matrix inequalities and are reduced to solving semi-definite programming and one-dimensional convex optimization problems. The resulting control strategy ensures suppression of influence of intervalbounded external demand and robust stabilization of the closed-loop system. Control of the supply network of three nodes is considered as an example.     

New concepts for activity float in resource-constrained project management

The concepts of float and critical path are central to analyzing activity networks in project management. In resource-constrained projects, schedule multiplicity makes it difficult to calculate float and identify critical activities accurately. In this work, new concepts of float and critical activity are developed to ascertain critical activities more precisely without reference to activity start and end times in specific schedules. The notions of float, group float, float set, negative float and zero critical activity are introduced, which the project manager can use to deal more effectively with critical activities, duration uncertainty, activity buffering, and resource allocation than the currently available tools in literature. For practical implementation, algorithms are provided and tested to calculate the new measures on the PSPLIB benchmark instances, specifically the J30, J60 and J120 test sets, for the resource constrained project management, illustrating the effectiveness of the proposed concepts in helping to identify flexibility in scheduling activities.     

Approximating minimum independent dominating sets in wireless networks

We present the first polynomial-time approximation scheme (PTAS) for the Minimum Independent Dominating Set problem in graphs of polynomially bounded growth which are used to model wireless communication networks.The approach presented yields a robust algorithm, that is, it accepts any undirected graph as input, and returns a (1+ε)-approximate minimum independent dominating set, or a certificate showing that the input graph does not satisfy the bounded growth property.