Time transformed mixed integer optimal control problems with impacts

The solutions of mixed integer optimal control problems (MIOCPs) yield optimized trajectories for dynamical systems with instantly changing dynamical behavior. The instant change is caused by a changing value of the integer valued control function. For example, a changing integer value can cause a car to change the gear, or a mechanical system to close a contact. The direct discretization of a MIOCP leads to a mixed integer nonlinear program (MINLP) and can not be solved with gradient based optimization methods at once. We extend the work by Gerdts [1] and reformulate a MIOCP with integer dependent constraints as an ordinary optimal control problem (OCP). The discretized OCP can be solved using gradient based optimization methods. We show how the integer dependent constraints can be used to model systems with impact and present optimized trajectories of computational examples, namely of a lockable double pendulum and an acyclic telescope walker. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

The multi-commodity one-to-one pickup-and-delivery traveling salesman problem

This paper concerns a generalization of the traveling salesman problem (TSP) called multi-commodity one-to-one pickup-and-delivery traveling salesman problem (m-PDTSP) in which cities correspond to customers providing or requiring known amounts of m different commodities, and the vehicle has a given upper-limit capacity. Each commodity has exactly one origin and one destination, and the vehicle must visit each customer exactly once. The problem can also be defined as the capacitated version of the classical TSP with precedence constraints. This paper presents two mixed integer linear programming models, and describes a decomposition technique for each model to find the optimal solution. Computational experiments on instances from the literature and randomly generated compare the techniques and show the effectiveness of our implementation.     

Discrete mechanics and mixed integer optimal control of dynamical systems

Mixed integer optimal control problems are a generalization of ordinary optimal control problems that include additional integer valued control functions. The integer control functions are used to switch instantaneously from one system to another. We use a time transformation (similar as in [1]) to get rid of the integer valued functions. This allows to apply gradient based optimization methods to approximate the mixed integer optimal control problem. The time transformation from [1] is adapted such that problems with distinct state domains for each system can be solved and it is combined with the direct discretization method DMOC [2,3] (Discrete Mechanics and Optimal Control) to approximate trajectories of the underlying optimal control problems. Our approach is illustrated with the help of a first example, the hybrid mass oscillator. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A Simultaneous Enumeration Approach to the Traveling Salesman Problem

The solution procedure proposed in this paper uses certain principles of analog computers. The idea of using analog rather than digital computers to solve mathematical programming problems is not new—various methods have been proposed to solve linear programming, network flows, as well as shortest path problems (Dennis, 1959; Stern, 1965). These problems can be more efficiently solved with digital computers. To find a solution to the traveling salesman problem as well as other integer programming problems is difficult with existing hardware, especially if the number of variables is large. The question thus arises whether different hardware configurations make it possible to solve integer problems more efficiently. One such configuration is proposed below for the traveling salesman problem.     

On the time transformation of mixed integer optimal control problems using a consistent fixed integer control function

Nonlinear control systems with instantly changing dynamical behavior can be modeled by introducing an additional control function that is integer valued in contrast to a control function that is allowed to have continuous values. The discretization of a mixed integer optimal control problem (MIOCP) leads to a non differentiable optimization problem and the non differentiability is caused by the integer values. The paper is about a time transformation method that is used to transform a MIOCP with integer dependent constraints into an ordinary optimal control problem. Differentiability is achieved by replacing a variable integer control function with a fixed integer control function and a variable time allows to change the sequence of active integer values. In contrast to other contributions, so called control consistent fixed integer control functions are taken into account here. It is shown that these control consistent fixed integer control functions allow a better accuracy in the resulting trajectories, in particular in the computed switching times. The method is verified on analytical and numerical examples.     

蚁群遗传混合算法

将蚁群遗传混合算法分别求解离散空间的和连续空间优化问题.求解旅行商问题的混合算法是以遗传算法为整个算法的框架,利用了蚁群算法中的信息素特性的进行交叉操作;根据旅行商问题的特点,给出了4种变异策略;针对遗传算法存在的过早收敛问题,加入2-0pt方法对问题求解进行了局部优化.与模拟退火算法、标准遗传算法和标准蚁群算法进行比较,4种混合算法效果都比较好,策略D的混合算法效果最好.求解连续空间优化问题是以蚁群算法为整个算法的框架,加入遗传算法的交叉操作和变异操作,用测试函数验证了混合蚁群算法的正确性.     

The timetable constrained distance minimization problem

We define the timetable constrained distance minimization problem (TCDMP) which is a sports scheduling problem applicable for tournaments where the total travel distance must be minimized. The problem consists of finding an optimal home-away assignment when the opponents of each team in each time slot are given. We present an integer programming, a constraint programming formulation and describe two alternative solution methods: a hybrid integer programming/constraint programming approach and a branch and price algorithm. We test all four solution methods on benchmark problems and compare the performance. Furthermore, we present a new heuristic solution method called the circular traveling salesman approach (CTSA) for solving the traveling tournament problem. The solution method is able to obtain high quality solutions almost instantaneously, and by applying the TCDMP, we show how the solutions can be further improved.     

MILP-based approaches for medium-term planning of single-stage continuous multiproduct plants with parallel units

In this paper, we address the problem of medium-term planning of single-stage continuous multiproduct plants with multiple processing units in parallel. Sequence-dependent changeover times and costs occur when switching from one type of product to another. A traveling salesman problem (TSP)-based mixed-integer linear programming (MILP) model is proposed based on a hybrid discrete/continuous time representation. We develop additional constraints and variables to ensure that subtours do not occur in the solution. The model is successfully applied to an example of a polymer processing plant to illustrate its applicability. In order to solve larger model instances and planning horizons, a rolling horizon approach is developed to reduce the computational expense. Finally, the proposed model is compared to a recently published approach through literature examples, and the results show that the computational performance of the proposed model is superior.     

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.     

Exploiting the Special Structure for Real‐Time Control of Optimal Control Problems with Linear Controls: Numerical Experience

Often optimal control problems possess control variables appearing linearly in the dynamics, the objective function and the constraints. The special bang‐bang and singular structure of the optimal control is exploited to formulate a nonlinear programming problem (NLP)w ith variables in the switching points and singular subarcs of the controls. This method has several advantages: The dimension of the resulting NLP problem is considerably reduced compared to usual direct optimization methods, several constraints can be neglected, and a parametric sensitivity analysis and real‐time control with respect to the switching points can be performed.     

Quality inspection scheduling for multi-unit service enterprises

The traveling salesman problem is a classic NP-hard problem used to model many production and scheduling problems. The problem becomes even more difficult when additional salesmen are added to create a multiple traveling salesman problem (MTSP). We consider a variation of this problem where one salesman visits a given set of cities in a series of short trips. This variation is faced by numerous franchise companies that use quality control inspectors to ensure properties are maintaining acceptable facility and service levels. We model an actual franchised hotel chain using traveling quality inspectors to demonstrate the technique. The model is solved using a commercially available genetic algorithm (GA) tool as well as a custom GA program. The custom GA is proven to be an effective method of solving the proposed model.     

Two improved formulations for the minimum latency problem

In network problems, latency is associated with the metric used to evaluate the length of the path from a root vertex to each vertex in the network. In this work we are dealing with two applications or variations of the minimum latency problem known as the repairman problem and the deliveryman problem. We have developed two integer formulations for the minimum latency problem and compared them with other two formulations from the literature for the time-dependent traveling salesman problem. The present work highlights the similarities and differences between the different formulations. In addition, we discuss the convenience of including a set of constraints in order to reduce the computation time needed to reach the optimal solution. We have carried out extensive computational experimentation on asymmetrical instances, since they provide the characteristics of the deliveryman and repairman problems in a better way.     

Integer linear programming formulations of multiple salesman problems and its variations

In this paper, we extend the classical multiple traveling salesman problem (mTSP) by imposing a minimal number of nodes that a traveler must visit as a side condition. We consider single and multidepot cases and propose integer linear programming formulations for both, with new bounding and subtour elimination constraints. We show that several variations of the multiple salesman problem can be modeled in a similar manner. Computational analysis shows that the solution of the multidepot mTSP with the proposed formulation is significantly superior to previous approaches.     

Integer programming models and linearizations for the traveling car renter problem

The traveling car renter problem (CaRS) is an extension of the classical traveling salesman problem (TSP) where different cars are available for use during the salesman’s tour. In this study we present three integer programming formulations for CaRS, of which two have quadratic objective functions and the other has quadratic constraints. The first model with a quadratic objective function is grounded on the TSP interpreted as a special case of the quadratic assignment problem in which the assignment variables refer to visitation orders. The second model with a quadratic objective function is based on the Gavish and Grave’s formulation for the TSP. The model with quadratic constraints is based on the Dantzig–Fulkerson–Johnson’s formulation for the TSP. The formulations are linearized and implemented in two solvers. An experiment with 50 instances is reported.     

Recognition of Gilmore-Gomory traveling salesman problem

The best known special case of the traveling salesman problem that is well solved is that due to Gilmore and Gomory. It is a problem of scheduling a heat treatment furnace. In this paper we give a polynomial algorithm for detecting whether or not a given traveling salesman problem is an instance of their problem; we also compute the parameters necessary to apply their algorithm. Thus all such problems can not only be solved in polynomial time but also recognized in polynomial time.     

A branch and bound method for the job-shop problem with sequence-dependent setup times

This paper deals with the job-shop scheduling problem with sequence-dependent setup times. We propose a new method to solve the makespan minimization problem to optimality. The method is based on iterative solving via branch and bound decisional versions of the problem. At each node of the branch and bound tree, constraint propagation algorithms adapted to setup times are performed for domain filtering and feasibility check. Relaxations based on the traveling salesman problem with time windows are also solved to perform additional pruning. The traveling salesman problem is formulated as an elementary shortest path problem with resource constraints and solved through dynamic programming. This method allows to close previously unsolved benchmark instances of the literature and also provides new lower and upper bounds.     

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.     

Optimal control of impulsive hybrid systems

In this paper, we deal with optimization techniques for a class of hybrid systems that comprise continuous controllable dynamics and impulses (jumps) in the state. Using the mathematical techniques of distributional derivatives and impulse differential equations, we rewrite the original hybrid control system as a system with autonomous location transitions. For the obtained auxiliary dynamical system and the corresponding optimal control problem (OCP), we apply the Lagrange approach and derive the reduced gradient formulas. Moreover, we formulate necessary optimality conditions for the above hybrid OCPs, and discuss the newly elaborated Pontryagin-type Maximum Principle for impulsive OCPs. As in the case of the conventional OCPs, the proposed first order optimization techniques provide a basis for constructive computational algorithms.     

A Continuous Implementation of a Second-Variation Optimal Control Method for Space Trajectory Problems

The paper describes a continuous second-variation method to solve optimal control problems with terminal constraints where the control is defined on a closed set. The integration of matrix differential equations based on a second-order expansion of a Lagrangian provides linear updates of the control and a locally optimal feedback controller. The process involves a backward and a forward integration stage, which require storing trajectories. A method has been devised to store continuous solutions of ordinary differential equations and compute accurately the continuous expansion of the Lagrangian around a nominal trajectory. Thanks to the continuous approach, the method adapts implicitly the numerical time mesh and provides precise gradient iterates to find an optimal control. The method represents an evolution to the continuous case of discrete second-order techniques of optimal control. The novel method is demonstrated on bang–bang optimal control problems, showing its suitability to identify automatically optimal switching points in the control without insight into the switching structure or a choice of the time mesh. A complex space trajectory problem is tackled to demonstrate the numerical robustness of the method to problems with different time scales.     

A mathematical programming model and solution for scheduling production orders in Shanghai Baoshan Iron and Steel Complex

In this paper, we investigate the production order scheduling problem derived from the production of steel sheets in Shanghai Baoshan Iron and Steel Complex (Baosteel). A deterministic mixed integer programming (MIP) model for scheduling production orders on some critical and bottleneck operations in Baosteel is presented in which practical technological constraints have been considered. The objective is to determine the starting and ending times of production orders on corresponding operations under capacity constraints for minimizing the sum of weighted completion times of all orders. Due to large numbers of variables and constraints in the model, a decomposition solution methodology based on a synergistic combination of Lagrangian relaxation, linear programming and heuristics is developed. Unlike the commonly used method of relaxing capacity constraints, this methodology alternatively relaxes constraints coupling integer variables with continuous variables which are introduced to the objective function by Lagrangian multipliers. The Lagrangian relaxed problem can be decomposed into two sub-problems by separating continuous variables from integer ones. The sub-problem that relates to continuous variables is a linear programming problem which can be solved using standard software package OSL, while the other sub-problem is an integer programming problem which can be solved optimally by further decomposition. The subgradient optimization method is used to update Lagrangian multipliers. A production order scheduling simulation system for Baosteel is developed by embedding the above Lagrangian heuristics. Computational results for problems with up to 100 orders show that the proposed Lagrangian relaxation method is stable and can find good solutions within a reasonable time.