An algorithm is a formal procedure that describes how to solve a problem. For instance, the simplex algorithm in Chapter 2 takes as input a linear program in standard equality form and either returns an optimal solution, or detects that the linear program is infeasible or unbounded. Another example is the shortest path algorithm in Chapter 3.1. It takes as input a graph with distinct vertices s, t and nonnegative integer edge lengths, and returns an st-path of shortest length (if one exists).

The two basic properties we require for an algorithm are: correctness and termination. By correctness, we mean that the algorithm is always accurate when it claims that we have a particular outcome. One way to ensure this is to require that the algorithm provides a certificate, i.e. a proof, to justify its answers. By termination, we mean that the algorithm will stop after a finite number of steps.

In Section A.1, we will define the running time of an algorithm; we will formalize the notions of slow and fast algorithms. Section A.2 reviews the algorithms presented in this book and discusses which ones are fast and which ones are slow. In Sections A.3 and A.4 we discuss the inherent complexity of various classes of optimization problems and discuss the possible existence of classes of problems for which it is unlikely that any fast algorithm exists. We explain how an understanding of computational complexity can guide us in the design of algorithms.

Broadly speaking, optimization is the problem of minimizing or maximizing a function subject to a number of constraints. Optimization problems are ubiquitous. Every chief executive officer (CEO) is faced with the problem of maximizing profit given limited resources. In general, this is too general a problem to be solved exactly; however, many aspects of decision making can be successfully tackled using optimization techniques. This includes, for instance, production, inventory, and machine-scheduling problems. Indeed, the overwhelming majority of Fortune 500 companies make use of optimization techniques. However, optimization problems are not limited to the corporate world. Every time you use your GPS, it solves an optimization problem, namely how to minimize the travel time between two different locations. Your hometown may wish to minimize the number of trucks it requires to pick up garbage by finding the most efficient route for each truck. City planners may need to decide where to build new fire stations in order to efficiently serve their citizens. Other examples include: how to construct a portfolio that maximizes its expected return while limiting volatility; how to build a resilient tele-communication network as cheaply as possible; how to schedule flights in a cost-effective way while meeting the demand for passengers; or how to schedule final exams using as few classrooms as possible.

Suppose that you are a consultant hired by the CEO of the WaterTech company to solve an optimization problem.

Using a single symmetric relay feedback test, a method is proposed to identify all the three parameters of a first order plus time delay (FOPTD) model. On identifying a higher order dynamics system by an FOPTD model, the conventional method identifies a negative time constant (Li et al., 1991) due to the error in neglecting higher order dynamics in the system output. In the present work, all the parameters of an FOPTD model are estimated with adequate accuracy. Four simulation examples are given. The estimated model parameters of an FOPTD model are compared with those obtained by Li et al. (1991) and also those with the exact model parameters of the system. The performance of the controller designed on the identified model is compared with that identified by Li et al. (1991) and with that of the actual process. The method gives results close to that of the actual system. Simulation results for stable and unstable systems are given.

Introduction

Identification of transfer function models from experimental data is essential for model based controller design. Often derivation of a rigorous mathematical model is difficult due to the complex nature of chemical processes. Hence, system identification is a valuable tool to identify low order models, based on the input-output data. The relay feedback is a single-shot experiment and the magnitude of oscillations can be varied. From the principal harmonics approximation, the ultimate gain (Ku) and ultimate frequency (ωu) are found.

Yu (1999) introduced the saturation relay feedback test for determining the ultimate gain and ultimate frequency of the system that are required for the design of PI/PID controllers. In the present chapter, two modifications are proposed to improve the efficiency of the saturation relay feedback test, especially for systems with a large dead time. In the first method, the safety factor is corrected based on the ideal relay feedback test. In the second method, higher order harmonics are included in the analysis of ideal relay. Simulation results are given to show the improvement of the proposed method over that of the Yu (1999) method for an FOPTD system and for a higher order system. The method is also compared with that proposed by Luyben (2001) for identifying the FOPTD model parameters.

Introduction

Li et al. (1991) pointed out that the error in estimation of ultimate gain ranges from -18% to +27% (with respect to the theoretical value) in ideal relay feedback test. To reduce the error in the estimation of ultimate gain, Yu (1999) suggested the saturation relay feedback test. In this method, the ultimate gain estimated from the ideal relay feedback test is multiplied with a safety factor to get slope of the saturation relay and the saturation relay feedback test is conducted to get better results for the ultimate gain and frequency.

The method proposed by Yu (1999) gave accurate results for small D/τ ratio (generally D/τ < 2).

Use of genetic algorithm for the tuning of decentralized and centralized controllers reported by Sadasivarao and Chidambaram (2003) is reviewed. The knowledge of the system is used to improve the search of genetic algorithms. All the loops are first tuned independently using the Ziegler–Nichols method or synthesis method. The detuning factors of 1.5 and 2 are used to get the range of the controller parameters. In this way, the unstable region (i.e., those settings that make the closed loop system unstable) is reduced from the region of search. The method is applied to a two input and two output distillation column model, given by Wood and Berry (1973). The knowledge-based genetic algorithm is converged faster than the method proposed by Vlachos et al. (1999).

Introduction

Many industrial control problems are of multi-input and multi-output (MIMO) in nature. The conventional multi-loop single-input and single-output (SISO) control systems are still used in industry because the formulation of MIMO control systems is not as straightforward. Centralized control scheme and decentralized control scheme are the two methods available for the control of such multivariable systems. In decentralized control system, single loop controllers are designed for each of the loops. Many methods are proposed for the design of decentralized controllers in the literature. Balachandran and Chidambaram (1996) compared BLT method, sequential design method and the method of inequalities for the design of decentralized controllers, and proved that the method of inequalities gave better performances than the other two methods.

Using a single relay feedback test, a method is proposed to identify all the five parameters of an unstable second order plus time delay model with a zero (SOPTDZ):

Gp = kp(1±τ1s) exp(-Ds)/[(τ2s±1)(τ3s-1)]. In the present work, three simulation examples are given (delay system with one unstable pole, one stable pole and a negative zero; delay system with one unstable pole, one stable pole and a positive zero; delay system with two unstable poles and one negative zero). All the five parameters of the SOPTDZ model are estimated with adequate accuracy. Performance of the controller designed for the identified model is compared with that of the controller designed on the actual transfer function model. The method gives a closed loop performance closer to that of the actual system. The methods are given for an asymmetric relay test. A simulation example of a third order non-linear CSTR system is also given.

Introduction

Identification of transfer function models from experimental data is essential for model-based controller design. Often derivation of a mathematical model is difficult due to the complex nature of chemical processes. Hence system identification is a valuable tool to identify models based on input-output data.

Luyben (1987) suggested the use of relay testing for identifying a transfer function model. Using the values of ku and ωu in the phase angle and amplitude criteria for first order plus time delay (FOPTD) model, we get two equations relating the three parameters (kp, τand D).

The system with one or more right half plane transmission (RHPT) zero is generally called as a non-minimum phase system. In this chapter, two methods of designing multivariable controllers for the systems with RHPT zeros are compared (Reddy et al., 2006). The methods used are decoupled internal model controller (IMC) (Wang et al., 2002) and a simple tuning method (Davison, 1976). In decoupled IMC method (Wang et al., 2002), controller design procedure is developed with the help of a model reduction theorem. Davison (1976) proposed a simple tuning method, which is based on the inverse of the steady-state gain matrix [G(0)]. Previously the method was applied to multivariable minimum phase systems only. In the present work, Davison method is applied to systems with multivariable right half plane zero. The decoupled IMC method (Wang et al., 2002) involves some complex calculations in designing the controllers whereas the Davison method (1976) is simple to apply. Simulation results are given for the following 2 × 2 transfer function matrix of the systems: (i) four-tank system, a benchmark example of multivariable system (Johansson, 2000) (ii) system (Morari et al., 1987) with individual and multivariable transmission zero at s = 1 (iii) binary distillation column (Wang et al., 2002). The performance comparisons are given by the sum of IAE values based on response and interaction both for servo and regulatory problems. The simple tuning method gives an improved performance.

Identification of transfer function models of a system is required for an improved tuning of controllers. Several methods have been reported in the literature for identification of transfer function models with two, three and four parameters (pure delay system, first order plus time delay (FOPTD), second order plus time delay (SOPTD), etc.) using relay feedback approach. In this section, the basics of conventional relay feedback method and modifications in the original autotuning method are reviewed for single-input single-output systems. Excellent reviews on relay tuning methods are given by Yu (1999, 2006), Hang et al. (2002) and Wang et al. (2003). Methods of designing PI/PID controllers based on the transfer function models are also briefly reviewed.

Relay Feedback Method

Åström and Hägglund (1984) suggested the use of an ideal (on–off) relay (Fig. 1.1) to generate a sustained oscillation in the closed loop. For positive gain process, on–off relay is defined by u = umax if e ≥ 0, and u = umin, if e < 0. For negative gain processes, on–off relay is defined by u = umin, if e ≥ 0, and u = umax if e < 0. Amplitude (a) and period of oscillation (pu) are noted from the sustained oscillation. This is a closed loop method for identification of transfer function models. The method is based on the observation that when an open loop output lags the input by π radians, the closed loop system may oscillate (Fig. 1.2) with a period Pu.

The present chapter is concerned with simultaneous relay autotuning of cascade controllers. Traditionally, autotuning procedures for cascade controllers are applied using a sequential, one-loop-at-a-time method. Saraf et al. (2003) proposed a simultaneous method of the relay tuning of series cascade control system. In this method, they assumed the principal harmonic analysis of relay oscillations. This results in error in calculation of the ultimate gains. The higher order harmonics are to be considered in the analysis of simultaneous relay tuning of series and parallel cascade control systems. Using improved ultimate gains, the inner loop (PI) and outer loop (PID) controllers are designed by the Ziegler–Nichols(Z-N) tuning method. The improved performance of the control is compared with the principal harmonic analysis reported by Saraf et al. (2003)

Introduction

Hang et al. (1994) proposed a sequential relay autotuning of series cascade control of stable systems. In this method, the outer loop is open. The on–off relay is used in the inner loop and the value of ku is obtained from 4h/(πa0). The controllers in the inner loop are tuned using the Ziegler–Nichols tuning formulae. With the inner loop under PI control action, the relay test is repeated for the outer loop.

Simultaneous relay tuning method is required whenever the system is to be kept under a closed loop in order to reduce the effect of disturbances or when the open loop system is unstable.

To design proportional plus integral (PI)/PID controllers, the ultimate values of the controller gain (ku) and frequency of oscillation (ωu) should be known. The conventional Ziegler and Nichols continuous cycling method requires a large number of experiments to calculate these values. Åström and Hägglund (1984) suggested the use of ideal relay to generate closed loop oscillations. The ultimate gain and ultimate frequency can be found in a single-shot experiment. However, the method is still approximate because of the use of the principal harmonics approximation. Li et al. (1991) reported that for an open loop, stable first order plus time delay (FOPTD) system, an error of -18% to 27% is obtained in the calculation of ku. Yu (1999) suggested a saturation feedback test to get better results for the ultimate gain and frequency. However, Yu (1999) did not report any result for large values of delay-to-time constant ratio.

An SOPTD model can incorporate higher order process dynamics better than an FOPTD model. The controller designed on the basis of the SOPTD model gives a better closed loop response than the one designed on an FOPTD model. It is better to have an SOPTD model with equal time constants since only three parameters are to be identified. Li et al. (1991) showed that the conventional analysis of the relay autotune method for an SOPTD model with equal time constants gives -11% to 27% error in the calculation of ku.