Relaxing mixed integer optimal control problems using a time transformation

Mixed integer control systems are used to model dynamical behavior that can change instantly, for example a driving car with different gears. Changing a gear corresponds to an instant change of the differential equation what is achieved in the model by changing the value of the integer control function. The optimal control of a mixed integer control system by a discretize-then-optimize approach leads to a mixed integer optimization problem that is not differentiable with respect to the integer variables, such that gradient based optimization methods can not be applied. In this work, differentiability with respect to all optimization variables is achieved by reformulating the mixed integer optimal control problem (MIOCP). A fixed integer control function and a time transformation are introduced. The combination of both allows to change the sequence of active differential equations by partially deactivating the fixed integer control function. In contrast to other works, here different fixed integer control functions are taken into account. Advantages of so called control consistent (CC) fixed integer control functions are discussed and confirmed on a numerical example. (© 2015 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

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)     

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 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)     

Direct methods with maximal lower bound for mixed-integer optimal control problems

Many practical optimal control problems include discrete decisions. These may be either time-independent parameters or time-dependent control functions as gears or valves that can only take discrete values at any given time. While great progress has been achieved in the solution of optimization problems involving integer variables, in particular mixed-integer linear programs, as well as in continuous optimal control problems, the combination of the two is yet an open field of research. We consider the question of lower bounds that can be obtained by a relaxation of the integer requirements. For general nonlinear mixed-integer programs such lower bounds typically suffer from a huge integer gap. We convexify (with respect to binary controls) and relax the original problem and prove that the optimal solution of this continuous control problem yields the best lower bound for the nonlinear integer problem. Building on this theoretical result we present a novel algorithm to solve mixed-integer optimal control problems, with a focus on discrete-valued control functions. Our algorithm is based on the direct multiple shooting method, an adaptive refinement of the underlying control discretization grid and tailored heuristic integer methods. Its applicability is shown by a challenging application, the energy optimal control of a subway train with discrete gears and velocity limits.      

Computing the integer programming gap

We determine the maximal gap between the optimal values of an integer program and its linear programming relaxation, where the matrix and cost function are fixed but the right hand side is unspecified. Our formula involves irreducible decomposition of monomial ideals. The gap can be computed in polynomial time when the dimension is fixed. Partially supported by the National Science Foundation (DMS-0200729).     

The value function of an integer program

We consider integer programs in which the objective function and constraint matrix are fixed while the right-hand side varies. The value function gives, for each feasible right-hand side, the criterion value of the optimal solution. We provide a precise characterization of the closed-form expression for any value function. The class of Gomory functions consists of those functions constructed from linear functions by taking maximums, sums, non-negative multiples, and ceiling (i.e., next highest integer) operations. The class of Gomory functions is identified with the class of all possible value functions by the following results: (1) for any Gomory functiong, there is an integer program which is feasible for all integer vectorsv and hasg as value function; (2) for any integer program, there is a Gomory functiong which is the value function for that program (for all feasible right-hand sides); (3) for any integer program there is a Gomory functionf such thatf(v)≤0 if and only ifv is a feasible right-hand side. Applications of (1)–(3) are also given.     

N-fold integer programming and nonlinear multi-transshipment

The multi-transshipment problem is NP-hard already for two commodities over bipartite networks. Nonetheless, using our recent theory of n-fold integer programming and extensions developed herein, we are able to establish the polynomial time solvability of the problem in two broad situations. First, for any fixed number of commodities and number of suppliers, we solve the problem over bipartite networks with variable number of consumers in polynomial time. This is very natural in operations research applications where few facilities serve many customers. Second, for every fixed network, we solve the problem with variable number of commodities in polynomial time.     

基于非均匀参数化的自由终端时间最优控制问题求解

针对自由终端时间最优控制问题,提出了一种基于非均匀控制向量参数化的数值解法.将控制时域离散化为不同长度的时间段,各时间段长度作为新的控制变量.通过引入标准化的时间变量,原问题转化为均匀参数化的固定终端时间最优控制问题.建立目标和约束函数的Hamilton函数,通过求解伴随方程获得目标和约束函数的梯度,采用序列二次规划(SQP)获得数值解.针对两个经典的化工过程自由终端时间最优控制问题进行仿真研究,验证了所提出算法的可行性和有效性.     

Distributionally robust simple integer recourse

The simple integer recourse (SIR) function of a decision variable is the expectation of the integer round-up of the shortage/surplus between a random variable with a known distribution and the decision variable. It is the integer analogue of the simple (continuous) recourse function in two-stage stochastic linear programming. Structural properties and approximations of SIR functions have been extensively studied in the seminal works of van der Vlerk and coauthors. We study a distributionally robust SIR function (DR-SIR) that considers the worst-case expectation over a given family of distributions. Under the assumption that the distribution family is specified by its mean and support, we derive a closed form analytical expression for the DR-SIR function. We also show that this nonconvex DR-SIR function can be represented using a mixed-integer second-order conic program.     

Subadditive approaches in integer programming

Linear programming duality is well understood and the reduced cost of a column is frequently used in various algorithms. On the other hand, for integer programs it is not clear how to define a dual function even though the subadditive dual theory has been developed a long time ago. In this work we propose a family of computationally tractable subadditive dual functions for integer programs. We develop a solution methodology that computes an optimal primal solution and an optimal subadditive dual function. We present computational experiments, which show that the new algorithm is tractable.     

A new variable reduction technique for convex integer quadratic programs

Convex integer quadratic programming involves minimization of a convex quadratic objective function with affine constraints and is a well-known NP-hard problem with a wide range of applications. We proposed a new variable reduction technique for convex integer quadratic programs (IQP). Based on the optimal values to the continuous relaxation of IQP and a feasible solution to IQP, the proposed technique can be applied to fix some decision variables of an IQP simultaneously at zero without sacrificing optimality. Using this technique, computational effort needed to solve IQP can be greatly reduced. Since a general convex bounded IQP (BIQP) can be transformed to a convex IQP, the proposed technique is also applicable for the convex BIQP. We report a computational study to demonstrate the efficacy of the proposed technique in solving quadratic knapsack problems.     

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.     

Unboundedness in reverse convex and concave integer programming

In this paper we are concerned with the problem of unboundedness and existence of an optimal solution in reverse convex and concave integer optimization problems. In particular, we present necessary and sufficient conditions for existence of an upper bound for a convex objective function defined over the feasible region contained in ${\mathbb{Z}^n}$ . The conditions for boundedness are provided in a form of an implementable algorithm, showing that for the considered class of functions, the integer programming problem is unbounded if and only if the associated continuous problem is unbounded. We also address the problem of boundedness in the global optimization problem of maximizing a convex function over a set of integers contained in a convex and unbounded region. It is shown in the paper that in both types of integer programming problems, the objective function is either unbounded from above, or it attains its maximum at a feasible integer point.     

An improved partial enumeration algorithm for integer programming problems

In this paper, we present an improved Partial Enumeration Algorithm for Integer Programming Problems by developing a special algorithm, named PE_SPEEDUP (partial enumeration speedup), to use whatever explicit linear constraints are present to speedup the search for a solution. The method is easy to understand and implement, yet very effective in dealing with many integer programming problems, including knapsack problems, reliability optimization, and spare allocation problems. The algorithm is based on monotonicity properties of the problem functions, and uses function values only; it does not require continuity or differentiability of the problem functions. This allows its use on problems whose functions cannot be expressed in closed algebraic form. The reliability and efficiency of the proposed PE_SPEEDUP algorithm has been demonstrated on some integer optimization problems taken from the literature.     

An adaptive parameter approach for an approximate solution of optimal control problems

In this paper, we consider a class of nonlinear optimal control problems (Bolza-problems) with constraints of the control vector, initial and boundary conditions of the state vectors. The time interval is fixed. Our approach to parametrize both the state functions and the control functions is described by general piecewise polynomials with unknown coefficients (parameters), where a fixed partition of the time interval is used. Here each of these functions in a suitable way individually will be approximated by such polynomials. The optimal control problem thus is reduced to a mathematical programming problem for these parameters. The existence of an optimal solution is assumed. Convergence properties of this method are not considered in this paper.     

On boundedness of (quasi-)convex integer optimization problems

In this paper we are concerned with the problem of boundedness and the existence of optimal solutions to the constrained integer optimization problem. We present necessary and sufficient conditions for boundedness of either a faithfully convex or quasi-convex polynomial function over the feasible set contained in , and defined by a system of faithfully convex inequality constraints and/or quasi-convex polynomial inequalities. The conditions for boundedness are provided in the form of an implementable algorithm, terminating after a finite number of iterations, showing that for the considered class of functions, the integer programming problem with nonempty feasible region is unbounded if and only if the associated continuous optimization problem is unbounded. We also prove that for a broad class of objective functions (which in particular includes polynomials with integer coefficients), an optimal solution set of the constrained integer problem is nonempty over any subset of .     

Minimizing Lipschitz-continuous strongly convex functions over integer points in polytopes

This paper is about the minimization of Lipschitz-continuous and strongly convex functions over integer points in polytopes. Our results are related to the rate of convergence of a black-box algorithm that iteratively solves special quadratic integer problems with a constant approximation factor. Despite the generality of the underlying problem, we prove that we can find efficiently, with respect to our assumptions regarding the encoding of the problem, a feasible solution whose objective function value is close to the optimal value. We also show that this proximity result is the best possible up to a factor polynomial in the encoding length of the problem.     

Optimal scanning control of flexible structures in two-dimensional space

A class of optimal control problems for hyperbolic systems in two-dimensional space is considered. An approach is proposed to damp the undesirable vibrations in the structures by pointwise moving force actuators extending over the spatial region occupied by the structure. A class of performance indices is introduced that includes functions of the state variable, its first and second-order space derivatives and first-order time derivative evaluated at a preassigned terminal time, and a suitable penalty term involving the control forces. A maximum principle is given for such general scanning control problem that facilitates the determination of the unique optimal control. A solution method is developed for the active vibration control of plates of general shape. The implementation of the method is presented and the effectiveness of a single moving force actuator is investigated and compared to a single fixed force actuator by a specific numerical example.     

Location of a discrete resource and its allocation according to a fractional objective

The problem considered is that of the location of a discrete resource and its allocation to activities with concave return functions in such a way as to maximize the ratio of ‘return’ to ‘cost’, the total cost being the sum of a fixed cost and linearly variable costs. It is assumed that each resource has an effectiveness of 0 or 1 against each activity. It is demonstrated that an optimal solution can be determined by the rounding to integers of the solution of an associated problem in continuous variables. Solutions with objective values arbitrarily close to the optimal value can be generated by resource-wise optimizations. An upper bound of the number of non-zero integer allocations in an optimal solution is derived.