Interactive Optimization of System Reliability Under Multiple Objectives

This paper considers a multiobjective reliability allocation problem for a series system with time-dependent reliability. The method determines the most preferable reliability allocation and preventive maintenance schedule. The problem is multiobjective nonlinear mixed-integer. The decision making procedure is based on interactive optimization and a nonlinear programming algorithm. The method is illustrated by a numerical example.     

Optimal apportionment of reliability and redundancy in seriessystems under multiple objectives

A multiobjective reliability apportionment problem for a series system with time-dependent reliability is presented. The resulting mathematical programming formulation determines the optimal level of component reliability and the number of redundant components at each stage. The problem is a multiobjective, nonlinear, mixed-integer mathematical programming problem, subject to several design constraints. Sequential unconstrained minimization techniques in conjunction with heuristic algorithms are used to find an optimum solution. A generalization of the problem in view of inherent vagueness in the objective and the constraint functions results in an ill-structured reliability apportionment problem. This multiobjective fuzzy optimization problem is solved using nonlinear programming. The computational procedure is illustrated through a numerical example. The fuzzy optimization techniques can be useful during initial stages of the conceptual design of engineering systems where the design goals and design constraints have not been clearly identified or stated, and for decision making problems in ill-structured situations     

Optimum Integrated Link Scheduling and Power Control for Multihop Wireless Networks

In this paper, a new mathematical programming formulation is developed for minimizing the schedule length in multihop wireless networks based on the optimal joint scheduling of transmissions across multi-access communication links and the allocation of transmit power levels while meeting the requirements on the signal-to-interference-plus-noise ratio at intended receivers. The authors prove that the problem can be represented as a mixed-integer linear programming (MILP) and show that the latter yields a solution that consists of transmit power levels that are "strongly Pareto optimal". It was demonstrated that the MILP formulation can be used effectively to derive optimal scheduling and power levels for networks with as many as 30 designated communication links. The authors show that the MILP formulation can also be effectively solved to provide upper and lower bounds (corresponding to an approximation factor Delta) for the optimum schedule length of networks with as many as 100 designated links. It is proved that the integrated link scheduling and power control problem (ILSP) is NP-complete. Consequently, a heuristic algorithm of polynomial complexity is developed and investigated for solving the problem in a timely and practical manner. The algorithm is based on the properties of a novel interference graph, i.e., the "generalized power-based interference graph", whose "chromatic" and "independence numbers" provide fundamental bounds for the ILSP. It is demonstrated that the frame length of schedules realized by the heuristic scheme resides in the 25th percentile of those attained by the optimal mechanism for randomly generated topologies with as many as 30 designated communication links. Furthermore, it is shown that the algorithm significantly outperforms a corresponding algorithm presented in the literature     

A partitioning algorithm for technoiogy-mapped designs onsingle-chip emulation systems

Reconfigurable single-chip emulation systems were proposed as an alternative to multichip emulation systems. Because they cannot be emulated on a single chip at once, large designs are sliced into partitions that are downloaded and executed sequentially on the same reconfigurable emulation chip. In this paper, we address the problem of partitioning a design on a reconfigurable single-chip emulator under resource constraints. First, we extract an acyclic flow graph of the design to be emulated. Then, we model the problem as an integer linear programming problem (IP) based on the acyclic flow graph of the design where the structure of the assignment and precedence constraints produce a tight formulation. To partition a design, our algorithm uses two distinct steps with different objectives. In the first step, we minimize the number of cycles needed to schedule every look-up table (LUT) in the circuit. Then flip-flops (FFs) are inserted into the appropriate cycles of the schedule in the second step. Experiments are conducted on small- and medium-size circuits from the MCNC Partitioning93 benchmark suite. The obtained results show that our algorithm produces optimal partitioning schedules     

System reliability design with deteriorative components

In constrained optimum system reliability problems, the reliability of each component is usually assumed to be fixed, and the optimal number of redundancies at each stage is determined. However, in real world the component reliability decreases as component deteriorates; i.e. the component reliability is dependent on its age. This paper presents a system reliability optimization problem with deteriorative components. We formulate this problem as a parametric nonlinear integer programming problem where the objective function has a time parameter t. A solution method is proposed for solving it. We believe that this model can provide very useful information for decision makers and reliability designers.     

A note on solving a system reliability problem involving nonlinear constraints

This paper is concerned with maximizing a system reliability function subject to nonlinear constraints. Numerical examples from the literature are handled by a general nonlinear programming algorithm, which can deal with the positive-integer variables of this reliability problem without special difficulties. The computational results presented in this paper suggest that the computer program listed here can be useful as a model for maximizing the system reliability function subject to the nonlinear constraints used here. In addition, because of the general applicability of the nonlinear programming algorithm, other system reliability functions and nonlinear constraints different from the ones used in this paper can also be accommodated.     

An algorithm to solve integer programming problems: An efficient tool for reliability design

In many reliability design problems, the decision variables can only have integer values. The redundancy allocation is an example of one such problem; others include spare parts allocation, or repairmen allocation, which necessitate an integer programming formulation. In other words, integer programming plays an important role in system reliability optimization. In this paper, an algorithm is presented which provides an exact, simple and economical solution to any general class of integer programming problems and thereby offers reliability designers an efficient tool for system design. The algorithm can be used effectively to solve a wide variety of reliability design problems. The scope of use of this algorithm is also indicated and the procedure is illustrated by an example.     

Optimal Multicast Routing and Wavelength Assignment on WDM Ring Networks Without Wavelength Conversion

We consider the multicast routing and wavelength assignment (MC-RWA) problem on WDM bidirectional ring networks without wavelength conversion. We give an integer programming formulation of the problem and propose an algorithm to solve it optimally. The algorithm is based on column generation and branch-and-price. We test the proposed algorithm on randomly generated data and the test results show that the algorithm gives optimal solutions to all of the test problems.     

基于构件的软件测试中测试用例分配优化研究

探讨了软件测试中每个构件软件的可靠性灵敏度已知,而测试资源受约束时,如何合理分配测试用例以提高构件软件可靠性的最优化问题.分析了传统的基于可靠性灵敏度的构件软件可靠性优化方法(RPP策略),在此基础上提出一种考虑测试代价的改进的构件软件可靠性优化方法(RPP-c策略).证明了RPP-c策略中带约束的测试用例最优分配问题是一个NPC问题,给出了动态规划求解方法,从理论上验证了RPP-c策略是最优的.     

Optimal Reliability Allocation by Branch-and-Bound Technique

The paper presents an efficient method for finding the exact optimal solutions of reliability allocation problems that are formulated as an integer nonlinear programming problem generalized to handle nonlinear constraints and nonseparable problems. The method is based on branch-and-bound and developed by considering separation and relaxation techniques.     

A utility-based distributed maximum lifetime routing algorithm for wireless networks

Energy-efficient routing is a critical problem in multihop wireless networks due to the severe power constraint of wireless nodes. Despite its importance and many research efforts toward it, a distributed routing algorithm that maximizes network lifetime is still missing. To address this problem, this paper proposes a novel utility-based nonlinear optimization formulation to the maximum lifetime routing problem. Based on this formulation, a fully distributed localized routing algorithm is further presented, which is proved to converge at the optimal point, where the network lifetime is maximized. Solid theoretical analysis and simulation results are presented to validate the proposed solution.     

A Discrete Filled Function Method for the Design of FIR Filters With Signed-Powers-of-Two Coefficients

In this paper, we consider the optimal design of finite-impulse response (FIR) filters with coefficients expressed as sums of signed powers-of-two (SPT) terms, where the normalized peak ripple (NPR) is taken as the performance measure. This problem is formulated as a mixed-integer programming problem. Based on a transformation between two different integer spaces and the computation of the optimal scaling factor for a given set of coefficients, this mixed integer programming problem is transformed into an equivalent integer programming problem. Then, an efficient algorithm based on a discrete filled function is developed for solving this equivalent problem. For illustration, some numerical examples are solved.     

Application of the surrogate constraints algorithm to optimal reliability design of systems

This paper presents a solution method for the reliability optimization problem of series-parallel systems which is formulated as a mixed integer nonlinear programming problem with multiple constraints. In the solution method, the optimal solution is obtained by solving the surrogate dual problem. Surrogate problems with only one constraint which appear in the optimization process are solved by a technique using dynamic programming. Some computational experiences are shown along with the comparison with an existing approach.     

两跳放大转发中继网络中的ε-全局最优多中继选择策略

研究了并行两跳放大转发中继网络中的多中继选择策略问题。以接收端的信噪比(signal-to-noiseratio,SNR)最大化为目标,该问题首先被规划为0-1非线性整数规划问题,这是一个NP-hard问题,其最优解只可以通过穷举方法得到,但是对于节点数量很大的网络,低效的穷举方法是无法容忍的。基于分支定界(branch-and-bound)框架并结合线性变形放松技术(reformulation-linearization technique,RLT),提出了一种ε-全局最优的多中继选择策略。仿真结果表明该方法能很好地以预定精度ε逼近全局最优解。通过此方法得到的性能可以作为其他算法的参考基准。     

An optimal algorithm for solving partial target coverage problem in wireless sensor networks

This paper deals with the partial target coverage problem in wireless sensor networks under a novel coverage model. The most commonly used method in previous literature on the target coverage problem is to divide continuous time into discrete slots of different lengths, each of which is dominated by a subset of sensors while setting all the other sensors into the sleep state to save energy. This method, however, suffers from shortcomings such as high computational complexity and no performance bound. We showed that the partial target coverage problem can be optimally solved in polynomial time. First, we built a linear programming formulation, which considers the total time that a sensor spends on covering targets, in order to obtain a lifetime upper bound. Based on the information derived in previous formulation, we developed a sensor assignment algorithm to seek an optimal schedule meeting the lifetime upper bound. A formal proof of optimality was provided. We compared the proposed algorithm with the well‐known column generation algorithm and showed that the proposed algorithm significantly improves performance in terms of computational time. Experiments were conducted to study the impact of different network parameters on the network lifetime, and their results led us to several interesting insights. Copyright © 2011 John Wiley & Sons, Ltd.     

EDA算法求解一类特殊的非线性双层规划问题

研究下层为线性规划上层为二次规划的非线性双层规划问题。利用单纯形最优性等价条件和基于正态分布的分布估计算法(EDA)求解该问题的全局最优解。为了提高算法效率,结合种群最优个体,给出了有效的交叉算子。设计算法时,用均匀设计产生初始种群,从而增加种群的多样性。为克服进化算法的弱局部收敛性,文中提出一种新的方法增加算法的局部收敛性。数值试验结果表明,文中提出的算法是有效且快速的。     

Reliability Optimization by 0-1 Programming for a System with Several Failure Modes

Mathematical models for reliability of a redundant system with two classes of failure modes are usually formulated as a nonlinear integer programming (NIP) problem. This paper reformulates the NIP problem into a 0-1 linear programming (ZOLP) problem and a one-to-one correspondence is shown between this NIP problem and the ZOLP problem. A NIP example treated by Tillman is formulated into a ZOLP problem and optimal solutions, identical to Tillman's are obtained by an implicit enumeration method. Calculating the new coefficients of the objective function and the constraints in the ZOLP are straight forward. There are not many constraints or variables in the proposed ZOLP. Consequently, the computation (CPU) time is less.     

A semidefinite programming approach to optimal unambiguous discrimination of quantum states

We consider the problem of unambiguous discrimination between a set of linearly independent pure quantum states. We show that the design of the optimal measurement that minimizes the probability of an inconclusive result can be formulated as a semidefinite programming problem. Based on this formulation, we develop a set of necessary and sufficient conditions for an optimal quantum measurement. We show that the optimal measurement can be computed very efficiently in polynomial time by exploiting the many well-known algorithms for solving semidefinite programs, which are guaranteed to converge to the global optimum. Using the general conditions for optimality, we derive necessary and sufficient conditions so that the measurement that results in an equal probability of an inconclusive result for each one of the quantum states is optimal. We refer to this measurement as the equal-probability measurement (EPM). We then show that for any state set, the prior probabilities of the states can be chosen such that the EPM is optimal. Finally, we consider state sets with strong symmetry properties and equal prior probabilities for which the EPM is optimal. We first consider geometrically uniform (GU) state sets that are defined over a group of unitary matrices and are generated by a single generating vector. We then consider compound GU state sets which are generated by a group of unitary matrices using multiple generating vectors, where the generating vectors satisfy a certain (weighted) norm constraint.