Problem size,parallel architecture,and optimal speedup

The communication and synchronization overhead inherent in parallel processing can lead to situations where adding processors to the solution method actually increases execution time. Problem type, problem size, and architecture type all affect the optimal number of processors to employ. In this paper we examine the numerical solution of an elliptic partial differential equation in order to study the relationship between problem size and architecture. The equation's domain is discretized into n² grid points which are divided into partitions and mapped onto the individual processor memories. We analytically quantify the relationships among grid size, stencil type, partitioning strategy processor execution time, and communication network type. In doing so, we determine the optimal number of processors to assign to the solution (and hence the optimal speedup), and identify (i) the smallest grid size which fully benefits from using all available processors, (ii) the leverage on performance given by increasing processor speed or communication network speed, and (iii) the suitability of various architectures for large numerical problems. Finally, we compare the predictions of our analytic model with measurements from a multiprocessor and find that the model accurately predicts performance.     

Optimal control problem in bond graph formalism

This paper presents a new way to derive an optimal control system for a specific optimisation problem, based on bond graph formalism. The procedure proposed concerns the optimal control of linear time invariant MIMO systems and can deal with both cases of the integral performance index, these correspond to dissipative energy minimization and output error minimization. An augmented bond graph model is obtained starting from the bond graph model of the system associated with the optimal control problem. This augmented bond graph, consisting of the original model representation coupled to an optimizing bond graph, supplies, by its bicausal exploitation, the set of differential-algebraic equations that analytically give the solution to the optimal control problem without the need to develop the analytical steps of Pontryagin’s method. The proof uses the Pontryagin Maximum Principle applied to the port-Hamiltonian formulation of the system.     

On optimal spacecraft damping

The problem of spacecraft damping (damping of initial angular velocity to zero) for a minimal time is studied. Two variants of formulation of the optimization problem are considered; these variants differ in the form of constraints on the control torque. Analytical solution to the formulated problem is obtained in the closed form and numerical expressions for synthesis of optimal angular velocity control program are given. Similar problem of time-optimal angular acceleration of the spacecraft to the given value is also solved. Procedure for determination of the control torque at the initial time instant for the problem of acceleration of the spacecraft to the required angular velocity is presented. Numerical example of solution of the problems of buildup and damping of spacecraft rotation velocity for a minimal time is given.     

Markov控制过程基于性能势的平均代价最优策略

研究了一类离散时间Markov控制过程平均代价性能最优控制决策问题.应用 Markov性能势的基本性质,在很一般性的假设条件下,直接导出了无限时间平均代价模型在紧 致行动集上的最优性方程及其解的存在性定理.提出了求解最优平稳控制策略的迭代算法,并 讨论了这种算法的收敛性问题.最后通过分析一个实例来说明这种算法的应用.     

Applying a finite-horizon numerical optimization method to a periodic optimal control problem

Computing a numerical solution to a periodic optimal control problem can be difficult, especially when the period is unknown. A method of approximating a solution to a stochastic optimal control problem using Markov chains was developed in [Krawczyk, J. B. (2001). A Markovian approximated solution to a portfolio management problem. Information Technology for Economics and Management, 1, http://www.item.woiz.polsl.pl/issue/journal1.htm]. This paper describes the application of that method to a periodic optimal control problem formulated in [Gaitsgory, V. & Rossomakhine, S. (2006). Linear programming approach to deterministic long run average problems of optimal control. SIAM Journal on Control and Optimization, 44(6), 2006-2037]. As a result, approximately optimal feedback rules are computed that can control the system both on and off the optimal orbit.     

基于高斯伪谱法的分区联立动态优化策略

最优控制轨迹通常由不同类型的弧段组成,采用数值方法求解这类问题时,其优化轨迹的不连续性可能导致求解失败,为此基于高斯伪谱法,提出一种分区联立动态优化求解策略.该策略通过对优化时域合理分区,避免了由于控制轨迹不连续而导致的病态优化问题.另外,通过联立求解分区后的优化问题,能够满足各分区间的连接条件,而且可以使用较少的节点获得高质量的优化解.最后以抗生素发酵过程为例验证了所提出算法的有效性.     

Time-Optimal Boundary Control for Systems Defined by a Fractional Order Diffusion Equation

We consider the optimal control problem for a system defined by a one-dimensional diffusion equation with a fractional time derivative. We consider the case when the controls occur only in the boundary conditions. The optimal control problem is posed as the problem of transferring an object from the initial state to a given final state in minimal possible time with a restriction on the norm of the controls. We assume that admissible controls belong to the class of functions L_∞[0, T ]. The optimal control problem is reduced to an infinite-dimensional problem of moments. We also consider the approximation of the problem constructed on the basis of approximating the exact solution of the diffusion equation and leading to a finitedimensional problem of moments. We study an example of boundary control computation and dependencies of the control time and the form of how temporal dependencies in the control dependent on the fractional derivative index.     

G-PaMeLA: A divide-and-conquer approach for joint channel assignment and routing in multi-radio multi-channel wireless mesh networks

The performance of Multi-Radio Multi-Channel Wireless Mesh Networks (MRMC-WMNs) based on the IEEE 802.11 technology depends significantly on how the channels are assigned to the radios and how traffic is routed between the access points and the gateways. In this paper we propose an algorithmic approach to this problem, for which, as far as we know, no optimal polynomial time solutions have been put forward in the literature. The core of our scheme consists of a sequential divide-and-conquer technique which divides the overall Joint Channel Assignment and Routing (JCAR) problem into a number of local optimization sub-problems that are executed sequentially. We propose a generalized scheme called Generalized Partitioned Mesh network traffic and interference aware channeL Assignment (G-PaMeLA), where the number of sub-problems is equal to the maximum number of hops to the gateway, and a customized version which takes advantage of the knowledge of the topology. In both cases each sub-problem is formulated as an Integer Linear Programming (ILP) optimization problem. An optimal solution for each sub-problem can be found by using a branch-and-cut method. The final solution is obtained after a post-processing phase, which improves network connectivity. The divide-and-conquer technique significantly reduces the execution time and makes our solution feasible for an operational WMN. With the help of a detailed packet level simulation, the G-PaMeLA technique is compared with several state-of-the-art JCAR algorithms. Our results highlight that G-PaMeLA performs much better than the others in terms of packet loss rate, collision probability and fairness among traffic flows.     

Cut-and-solve: An iterative search strategy for combinatorial optimization problems

Branch-and-bound and branch-and-cut use search trees to identify optimal solutions to combinatorial optimization problems. In this paper, we introduce an iterative search strategy which we refer to as cut-and-solve and prove optimality and termination for this method. This search is different from traditional tree search as there is no branching. At each node in the search path, a relaxed problem and a sparse problem are solved and a constraint is added to the relaxed problem. The sparse problems provide incumbent solutions. When the constraining of the relaxed problem becomes tight enough, its solution value becomes no better than the incumbent solution value. At this point, the incumbent solution is declared to be optimal. This strategy is easily adapted to be an anytime algorithm as an incumbent solution is found at the root node and continuously updated during the search.Cut-and-solve enjoys two favorable properties. Since there is no branching, there are no “wrong” subtrees in which the search may get lost. Furthermore, its memory requirement is negligible. For these reasons, it has potential for problems that are difficult to solve using depth-first or best-first search tree methods.In this paper, we demonstrate the cut-and-solve strategy by implementing a generic version of it for the Asymmetric Traveling Salesman Problem (ATSP). Our unoptimized implementation outperformed state-of-the-art solvers for five out of seven real-world problem classes of the ATSP. For four of these classes, cut-and-solve was able to solve larger (sometimes substantially larger) problems. Our code is available at our websites.     

Pontryagin’s maximum principle in optimal control problems of orientation of a spacecraft

Pontryagin’s maximum principle is used for solution of topical problems of spacecraft motion control. The dynamic optimal control problem of space orientation of a spacecraft from an arbitrary initial to a given final angular position with minimization of the turning time is studied in detail. The solution to the formulated problem is obtained and numerical expressions for synthesis of optimal control program are given. Results of mathematical simulation of the dynamics of motion of a spacecraft at optimal control are presented; these results demonstrate practical feasibility of the developed control algorithm.     

Regional Optimal Control Problem Governed by Distributed Bi-linear Hyperbolic Systems

This paper considers the regional bi-linear control problem of an important class of hyperbolic systems. The objective is to bring the state solutions at time T close to a desired observations w ^d only on a sub-region ω along the spatial domain Ω. We prove the existence of solution by minimizing sequence method. The adjoint system of this problem is introduced and used to characterize the optimal control. A numerical approach is developed and illustrated successfully by simulations.     

Warranty servicing for discretely degrading items with non-zero repair time under renewing warranty

This paper considers a repair-replacement strategy for a special class of discretely degrading and repairable products under renewing free replacement warranty. Each product may experience N different working states with different exponential hazard functions, before the warranty contract expires. Once the item enters working state i (i = 1, 2, … , N), it can either fail or move to any of the subsequent working states with different probabilities, given that a transition has been made. In the former case, the best rectification action, replacement or minimal repair, regarding the failure status, i.e., the product degradation level at the failure time and the remaining warranty time, should be conducted to put the item into operation. It is assumed that replacement of the faulty item occurs instantly and the product warranty is renewed, but non-zero repair time has been included in the model. We derive the optimal replacement-repair policy to minimize the manufacturer’s expected warranty servicing cost per item sold. The Adomian decomposition method is used to find an analytic approximate solution for a special case with two working states. For N > 2, a simulation based optimization method has been developed to analyze the expected warranty cost. Some numerical examples in each section are given to clearly demonstrate the application of this model.     

Towards Fast Vickrey Pricing using Constraint Programming

Ensuring truthfulness amongst self-interested agents bidding against one another in an auction can be computationally expensive when prices are determined using the Vickrey–Clarke–Groves (VCG) mechanism. This mechanism guarantees that each agent's dominant strategy is to tell the truth, but it requires solving n+ 1 optimization problems when the overall optimal solution involves n agents. This paper first examines a case-study example demonstrating how Operations Research techniques can be used to compute Vickrey prices efficiently. In particular, the case-study focuses on the Assignment Problem. We show how, in this case, Vickrey prices can be computed in the same asymptotic time complexity as that of the original optimization problem. This case-study can be seen as serving a pedagogical role in the paper illustrating how Operations Research techniques can be used for fast Vickrey pricing. We then propose a Constraint Programming approach that can be used in a more general context, where nothing is assumed about the nature of the constraints that must be satisfied or the structure of the underlying problem. In particular, we demonstrate how nogood learning can be used to improve the efficiency of constraint-based Vickrey pricing in combinatorial auctions.     

基于种群多样性模糊控制的粒子群算法

关于优化粒子群算法问题,针对标准粒子群算法前期收敛速度过快,后期容易陷入局部最优解的问题,提出一种种群多样性模糊控制的粒子群算法。为了控制种群多样性的变化,提高算法跳出局部最优解的性能,在算法中加入模糊控制器和位置跳变策略,通过控制参数的变化来控制粒子的速度、位置和种群多样性的变化,使算法从全局探测平稳过渡到局部开采。仿真结果表明,改进算法能有效避免陷入局部最优解,且对高维函数优化时效果更为明显,是一种高效的优化算法。     

Population-based optimization of cytostatic/cytotoxic combination cancer chemotherapy

This article studies the suitability of modern population based algorithms for designing combination cancer chemotherapies. The problem of designing chemotherapy schedules is expressed as an optimization problem (an optimal control problem) where the objective is to minimize the tumor size without compromising the patient’s health. Given the complexity of the underlying mathematical model describing the tumor’s progression (considering two types of drugs, the cell cycle and the immune system response), analytical and classical optimization methods are not suitable, instead, stochastic heuristic optimization methods are the right tool to solve the optimal control problem. Considering several solution quality and performance metrics, we compared three powerful heuristic algorithms for real-parameter optimization, namely, CMA evolution strategy, differential evolution, and particle swarm pattern search method. The three algorithms were able to successfully solve the posed problem. However, differential evolution outperformed its counterparts both in quality of the obtained solutions and efficiency of search.     

Numerical Solution of Optimal Control Problems with Constant Control Delays

We investigate a class of optimal control problems that exhibit constant exogenously given delays in the control in the equation of motion of the differential states. Therefore, we formulate an exemplary optimal control problem with one stock and one control variable and review some analytic properties of an optimal solution. However, analytical considerations are quite limited in case of delayed optimal control problems. In order to overcome these limits, we reformulate the problem and apply direct numerical methods to calculate approximate solutions that give a better understanding of this class of optimization problems. In particular, we present two possibilities to reformulate the delayed optimal control problem into an instantaneous optimal control problem and show how these can be solved numerically with a state-of-the-art direct method by applying Bock’s direct multiple shooting algorithm. We further demonstrate the strength of our approach by two economic examples.      

Optimal Capture of a Tumbling Object in Orbit Using a Space Manipulator

This paper introduces an optimal capture strategy for a manipulator based on a servicing spacecraft to approach an arbitrarily rotating object, such as a malfunctioning satellite or a piece of orbital debris, for capturing with minimal impact to the robot’s base spacecraft. The method consists of two steps. The first step is to determine an optimal future time and the target object’s corresponding motion state for the robot to capture the tumbling object, so that, at the time when the gripper of the robot intercepts the target the very first instant, the resulting impact or disturbance to the attitude of the base spacecraft will be minimal. The second step is to control the robot to reach the tumbling object at the predicted optimal time along an optimal trajectory. The optimal control problem is solved with random uncertainties in the initial and final boundary conditions. Uncertainties are introduced because sensor and estimation errors inevitably exist in the first step, i.e., determination process of the initial and final boundary conditions. The application of the method is demonstrated using a dynamics simulation example.     

Optimal fault detection for linear discrete time-varying systems

This paper deals with the problem of observer-based fault detection for linear discrete time-varying (LDTV) systems. A problem formulation is first proposed to address the optimization of the fault detection filter (FDF) design, which is expressed in terms of maximizing a finite horizon H_∞/H_∞ or H₋/H_∞ performance index. This formulation can be applied to FDF design of LDTV systems subject to l₂-norm bounded unknown inputs or stochastic noise sequences. It is shown that a unified optimal solution to the FDF can be obtained by solving the discrete time Riccati equation and the optimal FDF is not unique. A numerical example is given to illustrate the proposed method.