An Algorithm for Finding Global Minimum of Nonlinear Integer Programming

A filled function is proposed by R.Ge[2] for finding a global minimizer of a function of several continuous variables. In [4], an approach for finding a global integer minimizer of nonlinear function using the above filled function is given. Meanwhile a major obstacle is met: if $ρ > 0$ is small, and $||x_I-\overset{*}{x}_I||$ is large, where $x_I$ - an integer point, $\overset{*}{x}_I$ - a current local integer minimizer, then the value of the filled function almost equals zero. Thus it is difficult to recognize the size of the value of the filled function and can not find the global integer minimizer of nonlinear function. In this paper, two new filled functions are proposed for finding global integer minimizer of nonlinear function, and the new filled function improves some properties of the filled function proposed by R. Ge [2].Some numerical results are given, which indicate the new filled function (4.1) to find global integer minimizer of nonlinear function is efficient.     

An improved local branching approach for train formation planning

The train formation plan (TFP) determines routing and frequency of trains, and assigns the demands to trains. In this paper, an improved local branching algorithm is proposed for the TFP model in Iranian railway. This solution strategy is exact in nature, although it is designed to improve the heuristic behavior of the mixed integer programming (MIP) solver at hand. In the local branching algorithm, additional constraints are built in the model for the binary variables, but in the improved local branching algorithm, the additional constraints are built in the model for integer variables. A state-of-the-art method is applied for parameter tuning using design of experiments approach. To evaluate the proposed solution method, we have simulated and solved twenty test problems. The results show the efficiency and effectiveness of the proposed approach. The proposed algorithm is implemented for Iranian Railway network as a case study.     

A Trajectory-Based Method for Constrained Nonlinear Optimization Problems

A trajectory-based method for solving constrained nonlinear optimization problems is proposed. The method is an extension of a trajectory-based method for unconstrained optimization. The optimization problem is transformed into a system of second-order differential equations with the aid of the augmented Lagrangian. Several novel contributions are made, including a new penalty parameter updating strategy, an adaptive step size routine for numerical integration and a scaling mechanism. A new criterion is suggested for the adjustment of the penalty parameter. Global convergence properties of the method are established.     

Discrete global descent method for discrete global optimization and nonlinear integer programming

A novel method, entitled the discrete global descent method, is developed in this paper to solve discrete global optimization problems and nonlinear integer programming problems. This method moves from one discrete minimizer of the objective function f to another better one at each iteration with the help of an auxiliary function, entitled the discrete global descent function. The discrete global descent function guarantees that its discrete minimizers coincide with the better discrete minimizers of f under some standard assumptions. This property also ensures that a better discrete minimizer of f can be found by some classical local search methods. Numerical experiments on several test problems with up to 100 integer variables and up to 1.38 × 10¹⁰⁴ feasible points have demonstrated the applicability and efficiency of the proposed method.     

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.     

A new local and global optimization method for mixed integer quadratic programming problems

In this paper, a new local optimization method for mixed integer quadratic programming problems with box constraints is presented by using its necessary global optimality conditions. Then a new global optimization method by combining its sufficient global optimality conditions and an auxiliary function is proposed. Some numerical examples are also presented to show that the proposed optimization methods for mixed integer quadratic programming problems with box constraints are very efficient and stable.     

A cut-peak function method for global optimization

A new method is proposed for solving box constrained global optimization problems. The basic idea of the method is described as follows: Constructing a so-called cut-peak function and a choice function for each present minimizer, the original problem of finding a global solution is converted into an auxiliary minimization problem of finding local minimizers of the choice function, whose objective function values are smaller than the previous ones. For a local minimum solution of auxiliary problems this procedure is repeated until no new minimizer with a smaller objective function value could be found for the last minimizer. Construction of auxiliary problems and choice of parameters are relatively simple, so the algorithm is relatively easy to implement, and the results of the numerical tests are satisfactory compared to other methods.     

A filled function method for constrained global optimization

In this paper, a filled function method for solving constrained global optimization problems is proposed. A filled function is proposed for escaping the current local minimizer of a constrained global optimization problem by combining the idea of filled function in unconstrained global optimization and the idea of penalty function in constrained optimization. Then a filled function method for obtaining a global minimizer or an approximate global minimizer of the constrained global optimization problem is presented. Some numerical results demonstrate the efficiency of this global optimization method for solving constrained global optimization problems.     

An Exact Penalty Method for Free Terminal Time Optimal Control Problem with Continuous Inequality Constraints

In this paper, we consider a class of optimal control problems with free terminal time and continuous inequality constraints. First, the problem is approximated by representing the control function as a piecewise-constant function. Then the continuous inequality constraints are transformed into terminal equality constraints for an auxiliary differential system. After these two steps, we transform the constrained optimization problem into a penalized problem with only box constraints on the decision variables using a novel exact penalty function. This penalized problem is then solved by a gradient-based optimization technique. Theoretical analysis proves that this penalty function has continuous derivatives, and for a sufficiently large and finite penalty parameter, its local minimizer is feasible in the sense that the continuous inequality constraints are satisfied. Furthermore, this local minimizer is also the local minimizer of the constrained problem. Numerical simulations on the range maximization for a hypersonic vehicle reentering the atmosphere subject to a heating constraint demonstrate the effectiveness of our method.     

On the mixed integer signomial programming problems

This paper proposes an approximate method to solve the mixed integer signomial programming problem, for which the objective function and the constraints may contain product terms with exponents and decision variables, which could be continuous or integral. A linear programming relaxation is derived for the problem based on piecewise linearization techniques, which first convert a signomial term into the sum of absolute terms; these absolute terms are then linearized by linearization strategies. In addition, a novel approach is included for solving integer and undefined problems in the logarithmic piecewise technique, which leads to more usefulness of the proposed method. The proposed method could reach a solution as close as possible to the global optimum.     

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)     

整数规划的一类填充函数算法

填充函数算法是求解连续总体优化问题的一类有效算法。本文改造[1]的填充函数算法使之适于直接求解整数规划问题。首先,给出整数规划问题的离散局部极小解的定义,并设计找离散局部极小解的领域搜索算法。其次,构造整数规划问题的填充函数算法。该方法通过寻找填充函数的离散局部极小解以期找到整数规划问题的比当前离散局部极小解好的解。本文的算法是直接法,数值试验表明算法是有效的。     

Feature extraction algorithms for constrained global optimization II. Batch process scheduling application

The feature extraction algorithms developed in part I of this series are applied to solve nonconvex mixed integer nonlinear programming problems which arise in the optimal scheduling of multipurpose chemical plants. A general formulation of the multipurpose plant scheduling problem is developed which considers the allocation of plant equipment and secondary, limited resources to recipe operations so as to satisfy given production requirements while minimizing cost. Results obtained with a test example involving 135 binary and 922 continuous variables show that the successive refinement strategy is effective in identifying dominant regions of the solution space. Furthermore it is shown that multiple moment based characterization methods are superior to the interval analysis method reported in the literature. Trials using a second, larger nonlinear test problem involving 356 binary and 2402 continuous variables demonstrate that the focused successive refinement strategy is more efficient than a constant resolution strategy which employs genetic algorithm constructions. Although the conventional genetic algorithm can be significantly improved by introducing a heuristic mutation strategy which increases the likelihood of constant feasibility, the successive refinement strategy remains dominant. These studies demonstrate that the feature extraction strategy employing successive refinements and relatively low order moment based region characterization methods, offers an effective approach to solving an important class of large scale MINLP problems with multiple local optima.     

New Modified Function Method for Global Optimization

In this paper, a class of global optimization problems is considered. Corresponding to each local minimizer obtained, we introduced a new modified function and construct a corresponding optimization subproblem with one constraint. Then, by applying a local search method to the one-constraint optimization subproblem and using the local minimizer as the starting point, we obtain a better local optimal solution. This process is continued iteratively. A termination rule is obtained which can serve as stopping criterion for the iterating process. To demonstrate the efficiency of the proposed approach, numerical examples are solved.This research was partially supported by the National Science Foundation of China, Grant 10271073.     

Constrained Global Optimization of Expensive Black Box Functions Using Radial Basis Functions

We present a new strategy for the constrained global optimization of expensive black box functions using response surface models. A response surface model is simply a multivariate approximation of a continuous black box function which is used as a surrogate model for optimization in situations where function evaluations are computationally expensive. Prior global optimization methods that utilize response surface models were limited to box-constrained problems, but the new method can easily incorporate general nonlinear constraints. In the proposed method, which we refer to as the Constrained Optimization using Response Surfaces (CORS) Method, the next point for costly function evaluation is chosen to be the one that minimizes the current response surface model subject to the given constraints and to additional constraints that the point be of some distance from previously evaluated points. The distance requirement is allowed to cycle, starting from a high value (global search) and ending with a low value (local search). The purpose of the constraint is to drive the method towards unexplored regions of the domain and to prevent the premature convergence of the method to some point which may not even be a local minimizer of the black box function. The new method can be shown to converge to the global minimizer of any continuous function on a compact set regardless of the response surface model that is used. Finally, we considered two particular implementations of the CORS method which utilize a radial basis function model (CORS-RBF) and applied it on the box-constrained Dixon–Szegö test functions and on a simple nonlinearly constrained test function. The results indicate that the CORS-RBF algorithms are competitive with existing global optimization algorithms for costly functions on the box-constrained test problems. The results also show that the CORS-RBF algorithms are better than other algorithms for constrained global optimization on the nonlinearly constrained test problem.     

An algorithmic framework for convex mixed integer nonlinear programs

This paper is motivated by the fact that mixed integer nonlinear programming is an important and difficult area for which there is a need for developing new methods and software for solving large-scale problems. Moreover, both fundamental building blocks, namely mixed integer linear programming and nonlinear programming, have seen considerable and steady progress in recent years. Wishing to exploit expertise in these areas as well as on previous work in mixed integer nonlinear programming, this work represents the first step in an ongoing and ambitious project within an open-source environment. COIN-OR is our chosen environment for the development of the optimization software. A class of hybrid algorithms, of which branch-and-bound and polyhedral outer approximation are the two extreme cases, are proposed and implemented. Computational results that demonstrate the effectiveness of this framework are reported. Both the library of mixed integer nonlinear problems that exhibit convex continuous relaxations, on which the experiments are carried out, and a version of the software used are publicly available.     

A filled function method applied to nonsmooth constrained global optimization

The filled function method is an effective approach to find a global minimizer. In this paper, based on a new definition of the filled function for nonsmooth constrained programming problems, a one-parameter filled function is constructed to improve the efficiency of numerical computation. Then a corresponding algorithm is presented. It is a global optimization method which modify the objective function as a filled function, and which find a better local minimizer gradually by optimizing the filled function constructed on the minimizer previously found. Illustrative examples are provided to demonstrate the efficiency and reliability of the proposed filled function method.     

Global optimality conditions and optimization methods for quadratic integer programming problems

In this paper, we first establish some sufficient and some necessary global optimality conditions for quadratic integer programming problems. Then we present a new local optimization method for quadratic integer programming problems according to its necessary global optimality conditions. A new global optimization method is proposed by combining its sufficient global optimality conditions, local optimization method and an auxiliary function. The numerical examples are also presented to show that the proposed optimization methods for quadratic integer programming problems are very efficient and stable.     

A discrete dynamic convexized method for nonlinear integer programming

In this paper, we consider the box constrained nonlinear integer programming problem. We present an auxiliary function, which has the same discrete global minimizers as the problem. The minimization of the function using a discrete local search method can escape successfully from previously converged discrete local minimizers by taking increasing values of a parameter. We propose an algorithm to find a global minimizer of the box constrained nonlinear integer programming problem. The algorithm minimizes the auxiliary function from random initial points. We prove that the algorithm can converge asymptotically with probability one. Numerical experiments on a set of test problems show that the algorithm is efficient and robust.     

Derivative-free methods for bound constrained mixed-integer optimization

We consider the problem of minimizing a continuously differentiable function of several variables subject to simple bound constraints where some of the variables are restricted to take integer values. We assume that the first order derivatives of the objective function can be neither calculated nor approximated explicitly. This class of mixed integer nonlinear optimization problems arises frequently in many industrial and scientific applications and this motivates the increasing interest in the study of derivative-free methods for their solution. The continuous variables are handled by a linesearch strategy whereas to tackle the discrete ones we employ a local search-type approach. We propose different algorithms which are characterized by the way the current iterate is updated and by the stationarity conditions satisfied by the limit points of the sequences they produce.