Optimal discrete-valued control computation

In this paper, we consider an optimal control problem in which the control takes values from a discrete set and the state and control are subject to continuous inequality constraints. By introducing auxiliary controls and applying a time-scaling transformation, we transform this optimal control problem into an equivalent problem subject to additional linear and quadratic constraints. The feasible region defined by these additional constraints is disconnected, and thus standard optimization methods struggle to handle these constraints. We introduce a novel exact penalty function to penalize constraint violations, and then append this penalty function to the objective. This leads to an approximate optimal control problem that can be solved using standard software packages such as MISER. Convergence results show that when the penalty parameter is sufficiently large, any local solution of the approximate problem is also a local solution of the original problem. We conclude the paper with some numerical results for two difficult train control problems.     

A computational method for free terminal time optimal control problem governed by nonlinear time delayed systems

This paper considers a free terminal time optimal control problem governed by nonlinear time delayed system, where both the terminal time and the control are required to be determined such that a cost function is minimized subject to continuous inequality state constraints. To solve this free terminal time optimal control problem, the control parameterization technique is applied to approximate the control function as a piecewise constant control function, where both the heights and the switching times are regarded as decision variables. In this way, the free terminal time optimal control problem is approximated as a sequence of optimal parameter selection problems governed by nonlinear time delayed systems, each of which can be viewed as a nonlinear optimization problem. Then, a fully informed particle swarm optimization method is adopted to solve the approximate problem. Finally, two free terminal time optimal control problems, including an optimal fishery control problem, are solved by using the proposed method so as to demonstrate its applicability.     

Modified Legendre–Gauss–Radau Collocation Method for Optimal Control Problems with Nonsmooth Solutions

A new method is developed for solving optimal control problems whose solutions are nonsmooth. The method developed in this paper employs a modified form of the Legendre–Gauss–Radau orthogonal direct collocation method. This modified Legendre–Gauss–Radau method adds two variables and two constraints at the end of a mesh interval when compared with a previously developed standard Legendre–Gauss–Radau collocation method. The two additional variables are the time at the interface between two mesh intervals and the control at the end of each mesh interval. The two additional constraints are a collocation condition for those differential equations that depend upon the control and an inequality constraint on the control at the endpoint of each mesh interval. The additional constraints modify the search space of the nonlinear programming problem such that an accurate approximation to the location of the nonsmoothness is obtained. The transformed adjoint system of the modified Legendre–Gauss–Radau method is then developed. Using this transformed adjoint system, a method is developed to transform the Lagrange multipliers of the nonlinear programming problem to the costate of the optimal control problem. Furthermore, it is shown that the costate estimate satisfies one of the Weierstrass–Erdmann optimality conditions. Finally, the method developed in this paper is demonstrated on an example whose solution is nonsmooth.

     

A multigrid method for constrained optimal control problems

We consider the fast and efficient numerical solution of linear-quadratic optimal control problems with additional constraints on the control. Discretization of the first-order conditions leads to an indefinite linear system of saddle point type with additional complementarity conditions due to the control constraints. The complementarity conditions are treated by a primal-dual active set strategy that serves as outer iteration. At each iteration step, a KKT system has to be solved. Here, we develop a multigrid method for its fast solution. To this end, we use a smoother which is based on an inexact constraint preconditioner.We present numerical results which show that the proposed multigrid method possesses convergence rates of the same order as for the underlying (elliptic) PDE problem. Furthermore, when combined with a nested iteration, the solver is of optimal complexity and achieves the solution of the optimization problem at only a small multiple of the cost for the PDE solution.     

Constrained optimization problems using multiplier methods

A modified multiplier method for optimization problems with equality constraints is suggested and its application to constrained optimal control problems described. For optimal control problems with free terminal time, a gradient descent technique for updating control functions as well as the terminal time is developed. The modified multiplier method with the simplified conjugate gradient method is used to compute the solution of a time-optimal control problem for a V/STOL aircraft.     

An exact penalty function method for nonlinear mixed discrete programming problems

In this paper, we consider a general class of nonlinear mixed discrete programming problems. By introducing continuous variables to replace the discrete variables, the problem is first transformed into an equivalent nonlinear continuous optimization problem subject to original constraints and additional linear and quadratic constraints. Then, an exact penalty function is employed to construct a sequence of unconstrained optimization problems, each of which can be solved effectively by unconstrained optimization techniques, such as conjugate gradient or quasi-Newton methods. It is shown that any local optimal solution of the unconstrained optimization problem is a local optimal solution of the transformed nonlinear constrained continuous optimization problem when the penalty parameter is sufficiently large. Numerical experiments are carried out to test the efficiency of the proposed method.     

Optimal birth control of population dynamics. II. Problems with free final time,phase constraints,and mini-max costs

A previous analysis of optimal birth control of population systems of the McKendrick type (a distributed parameter system involving 1st order partial differential equations with nonlocal bilinear boundary control) raised 3 additional issues--free final time problem, system with phase constraints, and the mini-max control problem of a population. The free final time problem considers the minimum time problem to be a special case, but relaxes many convexity assumptions. Theorems (maximum principles) and corollaries are developed that flow from the terminology and mathematical notations set forth in the earlier article.     

Minimum-Time Control of a Crane with Simultaneous Traverse and Hoisting Motions

The problem of the minimum-time control of a crane having simultaneous traverse and hoisting motions is considered. We propose an approach that converts this problem into a finite-dimensional optimization problem via control parametrization with an appropriate basis function. Such an approach simplifies the treatment of the constraints and allows for the easy satisfaction of the endpoint constraints. This optimization problem is solved using a novel two-stage optimization process. Under additional conditions, the solution obtained from this process can be shown to be the optimum. When these conditions are not met, a near-optimal solution is obtained. Several numerical examples are provided, including the case where there is unequal cable length at the endpoints. The validity of the solution is verified experimentally on a test rig.     

An Exact Penalty Function Method for Continuous Inequality Constrained Optimal Control Problem

In this paper, we consider a class of optimal control problems subject to equality terminal state constraints and continuous state and control inequality constraints. By using the control parametrization technique and a time scaling transformation, the constrained optimal control problem is approximated by a sequence of optimal parameter selection problems with equality terminal state constraints and continuous state inequality constraints. Each of these constrained optimal parameter selection problems can be regarded as an optimization problem subject to equality constraints and continuous inequality constraints. On this basis, an exact penalty function method is used to devise a computational method to solve these optimization problems with equality constraints and continuous inequality constraints. The main idea is to augment the exact penalty function constructed from the equality constraints and continuous inequality constraints to the objective function, forming a new one. This gives rise to a sequence of unconstrained optimization problems. It is shown that, for sufficiently large penalty parameter value, any local minimizer of the unconstrained optimization problem is a local minimizer of the optimization problem with equality constraints and continuous inequality constraints. The convergent properties of the optimal parameter selection problems with equality constraints and continuous inequality constraints to the original optimal control problem are also discussed. For illustration, three examples are solved showing the effectiveness and applicability of the approach proposed.     

Discrete time model and algorithms for container yard crane scheduling

Container terminal (CT) operations are often bottlenecked by slow YC (yard crane) movements. PM (prime mover) queues in front of the YCs are common. Hence, efficient YC scheduling to reduce the PM waiting time is critical in increasing a CT’s throughput. We develop an efficient model for YC scheduling by taking into account realistic operational constraints such as inter-crane interference, fixed YC separation distances and simultaneous container storage/retrievals. Among them, only inter-crane interference has ever been considered in the literature. The model requires far fewer integer variables than the literature by using bi-index decision variables. We show how the model can be solved quickly using heuristics and rolling-horizon algorithm, yielding close to optimal solutions in seconds. The solution quality and solution time are both better than the literature even with additional constraints considered. The proposed formulations and algorithms can be extended to other problems with time windows and space constraints.     

Semi-Infinite Programming Approach to Continuously-Constrained Linear-Quadratic Optimal Control Problems

Consider the class of linear-quadratic (LQ) optimal control problems with continuous linear state constraints, that is, constraints imposed on every instant of the time horizon. This class of problems is known to be difficult to solve numerically. In this paper, a computational method based on a semi-infinite programming approach is given. The LQ optimal control problem is formulated as a positive-quadratic infinite programming problem. This can be done by considering the control as the decision variable, while taking the state as a function of the control. After parametrizing the decision variable, an approximate quadratic semi-infinite programming problem is obtained. It is shown that, as we refine the parametrization, the solution sequence of the approximate problems converges to the solution of the infinite programming problem (hence, to the solution of the original optimal control problem). Numerically, the semi-infinite programming problems obtained above can be solved efficiently using an algorithm based on a dual parametrization method.     

Mixed integer programming for a special logic constrained optimal control problem

Integrating logical constraints into optimal control problems is not an easy task. In fact, optimal control problems are usually continuous while logical constraints are naturally expressed by integer (binary) variables. In this article we are interested is a particular form of an LQR optimal control problem: the energy (control L² norm) is to be minimized, system dynamic is linear and logical constraints on the control use are to be fulfilled. Even if the starting continuous problem is not a complicated one, difficulties arise when integrating the additional logical constraints. First, we will present two different ways of modeling the problem, both of them leading us to Mixed Integer Problems. Furthermore, algorithms (Generalized Outer Approximation, Benders Decomposition and Branch and Cut) are applied on each model and results analyzed. We also present a Benders Decomposition algorithm variant that is adapted to our problem (taking into account its particular form) and we will conclude by looking at the optimal solutions obtained in an interesting physical example: the harmonic spring.     

A decomposition approach for optimal control problems with integer innerpoint state constraints

A large class of optimal control problems for hybrid dynamic systems can be formulated as mixed‐integer optimal control problems (MIOCPs). A decomposition approach is suggested to solve a special subclass of MIOCPs with mixed integer inner point state constraints. It is the intrinsic combinatorial complexity of the discrete variables in addition to the high nonlinearity of the continuous optimal control problem that forms the challenges in the theoretical and numerical solution of MIOCPs. During the solution procedure the problem is decomposed at the inner time points into a multiphase problem with mixed integer boundary constraints and phase transitions at unknown switching points. Due to a discretization of the state space at the switching points the problem can be decoupled into a family of continuous optimal control problems (OCPs) and a problem similar to the asymmetric group traveling salesman problem (AGTSP). The OCPs are transcribed by direct collocation to large‐scale nonlinear programming problems, which are solved efficiently by an advanced SQP method. The results are used as weights for the edges of the graph of the corresponding TSP‐like problem, which is solved by a Branch‐and‐Cut‐and‐Price (BCP) algorithm. The proposed approach is applied to a hybrid optimal control benchmark problem for a motorized traveling salesman. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Parameter Tuning of Multi-Proportional-Integral-Derivative Controllers Based on Optimal Switching Algorithms

Under the framework of switched systems, this paper considers a multi-proportional-integral-derivative controller parameter tuning problem with terminal equality constraints and continuous-time inequality constraints. The switching time and controller parameters are decision variables to be chosen optimally. Firstly, we transform the optimal control problem into an equivalent problem with fixed switching instants by introducing an auxiliary function and a time-scaling transformation. Because of the complexity of constraints, it is difficult to solve the problem by conventional optimization techniques. To overcome this difficulty, a novel exact penalty function is introduced for these constraints. Furthermore, the penalty function is appended to the cost functional to form an augmented cost functional, giving rise to an approximate nonlinear parameter optimization problem that can be solved using any gradient-based method. Convergence results indicate that any local optimal solution of the approximate problem is also a local optimal solution of the original problem as long as the penalty parameter is sufficiently large. Finally, an example is provided to illustrate the effectiveness of the developed algorithm.     

Second order sufficient conditions and sensitivity analysis for the optimal control of a container crane under state constraints

Stability and sensitivity analysis of parametric control problems has recently been elaborated for optimal control problems subject to pure state constraints. This paper illustrates the numerical aspects of sensitivity analysis for a complex practical example: the optimal control of a container crane with a state constraint on the vertical velocity. The multiple shooting method is used to determine a nominal solution satisfying first order necessary conditions. Second order sufficient conditions are checked by showing that an associated Riccati equation has a bounded solution. Sensitivity differentials of optimal solutions an computed with respect to variations in the swing angle     

Bounded knapsack sharing

A bounded knapsack sharing problem is a maximin or minimax mathematical programming problem with one or more linear inequality constraints, an objective function composed of single variable continuous functions called tradeoff functions, and lower and upper bounds on the variables. A single constraint problem which can have negative or positive constraint coefficients and any type of continuous tradeoff functions (including multi-modal, multiple-valued and staircase functions) is considered first. Limiting conditions where the optimal value of a variable may be plus or minus infinity are explicitly considered. A preprocessor procedure to transform any single constraint problem to a finite form problem (an optimal feasible solution exists with finite variable values) is developed. Optimality conditions and three algorithms are then developed for the finite form problem. For piecewise linear tradeoff functions, the preprocessor and algorithms are polynomially bounded. The preprocessor is then modified to handle bounded knapsack sharing problems with multiple constraints. An optimality condition and algorithm is developed for the multiple constraint finite form problem. For multiple constraints, the time needed for the multiple constraint finite form algorithm is the time needed to solve a single constraint finite form problem multiplied by the number of constraints. Some multiple constraint problems cannot be transformed to multiple constraint finite form problems.     

Optimal berth allocation and time-invariant quay crane assignment in container terminals

Due to the dramatic increase in the world’s container traffic, the efficient management of operations in seaport container terminals has become a crucial issue. In this work, we focus on the integrated planning of the following problems faced at container terminals: berth allocation, quay crane assignment (number), and quay crane assignment (specific). First, we formulate a new binary integer linear program for the integrated solution of the berth allocation and quay crane assignment (number) problems called BACAP. Then we extend it by incorporating the quay crane assignment (specific) problem as well, which is named BACASP. Computational experiments performed on problem instances of various sizes indicate that the model for BACAP is very efficient and even large instances up to 60 vessels can be solved to optimality. Unfortunately, this is not the case for BACASP. Therefore, to be able to solve large instances, we present a necessary and sufficient condition for generating an optimal solution of BACASP from an optimal solution of BACAP using a post-processing algorithm. In case this condition is not satisfied, we make use of a cutting plane algorithm which solves BACAP repeatedly by adding cuts generated from the optimal solutions until the aforementioned condition holds. This method proves to be viable and enables us to solve large BACASP instances as well. To the best of our knowledge, these are the largest instances that can be solved to optimality for this difficult problem, which makes our work applicable to realistic problems.     

Inexact Restoration for Euler Discretization of Box-Constrained Optimal Control Problems

The Inexact Restoration method for Euler discretization of state and control constrained optimal control problems is studied. Convergence of the discretized (finite-dimensional optimization) problem to an approximate solution using the Inexact Restoration method and convergence of the approximate solution to a continuous-time solution of the original problem are established. It is proved that a sufficient condition for convergence of the Inexact Restoration method is guaranteed to hold for the constrained optimal control problem. Numerical experiments employing the modelling language AMPL and optimization software Ipopt are carried out to illustrate the robustness of the Inexact Restoration method by means of two computationally challenging optimal control problems, one involving a container crane and the other a free-flying robot. The experiments interestingly demonstrate that one might be better-off using Ipopt as part of the Inexact Restoration method (in its subproblems) rather than using Ipopt directly on its own.     

An exact method for scheduling a yard crane

This paper studies an operational problem arising at a container terminal, consisting of scheduling a yard crane to carry out a set of container storage and retrieval requests in a single container block. The objective is to minimize the total travel time of the crane to carry out all requests. The block has multiple input and output (I/O) points located at both the seaside and the landside. The crane must move retrieval containers from the block to the I/O points, and must move storage containers from the I/O points to the block. The problem is modeled as a continuous time integer programming model and the complexity is proven. We use intrinsic properties of the problem to propose a two-phase solution method to optimally solve the problem. In the first phase, we develop a merging algorithm which tries to patch subtours of an optimal solution of an assignment problem relaxation of the problem and obtain a complete crane tour without adding extra travel time to the optimal objective value of the relaxed problem. The algorithm requires common I/O points to patch subtours. This is efficient and often results in obtaining an optimal solution of the problem. If an optimal solution has not been obtained, the solution of the first phase is embedded in the second phase where a branch-and-bound algorithm is used to find an optimal solution. The numerical results show that the proposed method can quickly obtain an optimal solution of the problem. Compared to the random and Nearest Neighbor heuristics, the total travel time is on average reduced by more than 30% and 14%, respectively. We also validate the solution method at a terminal.