Column enumeration based decomposition techniques for a class of non-convex MINLP problems

We propose a decomposition algorithm for a special class of nonconvex mixed integer nonlinear programming problems which have an assignment constraint. If the assignment decisions are decoupled from the remaining constraints of the optimization problem, we propose to use a column enumeration approach. The master problem is a partitioning problem whose objective function coefficients are computed via subproblems. These problems can be linear, mixed integer linear, (non-)convex nonlinear, or mixed integer nonlinear. However, the important property of the subproblems is that we can compute their exact global optimum quickly. The proposed technique will be illustrated solving a cutting problem with optimum nonlinear programming subproblems.     

A filled function method for finding a global minimizer on global integer optimization

The paper gives a definition of the filled function for nonlinear integer programming. This definition is modified from that of the global convexized filled function for continuous global optimization. A filled function with only one parameter which satisfies this definition is presented. We also discuss the properties of the proposed function and give a filled function method to solve the nonlinear integer programming problem. The implementation of the algorithm on several test problems is reported with satisfactory numerical results.     

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

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

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.     

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.     

Global optimization of mixed-integer bilevel programming problems

Two approaches that solve the mixed-integer nonlinear bilevel programming problem to global optimality are introduced. The first addresses problems mixed-integer nonlinear in outer variables and C²-nonlinear in inner variables. The second adresses problems with general mixed-integer nonlinear functions in outer level. Inner level functions may be mixed-integer nonlinear in outer variables, linear, polynomial, or multilinear in inner integer variables, and linear in inner continuous variables. This second approach is based on reformulating the mixed-integer inner problem as continuous via its vertex polyheral convex hull representation and solving the resulting nonlinear bilevel optimization problem by a novel deterministic global optimization framework. Computational studies illustrate proposed approaches.     

Nonlinear transformations for the simplification of unconstrained nonlinear optimization problems

Formalization decisions in mathematical programming could significantly influence the complexity of the problem, and so the efficiency of the applied solver methods. This widely accepted statement induced investigations for the reformulation of optimization problems in the hope of getting easier to solve problem forms, e.g. in integer programming. These transformations usually go hand in hand with relaxation of some constraints and with the increase in the number of the variables. However, the quick evolution and the widespread use of computer algebra systems in the last few years motivated us to use symbolic computation techniques also in the field of global optimization. We are interested in potential simplifications generated by symbolic transformations in global optimization, and especially in automatic mechanisms producing equivalent expressions that possibly decrease the dimension of the problem. As it was pointed out by Csendes and Rapcsák (J Glob Optim 3(2):213–221, 1993), it is possible in some cases to simplify the unconstrained nonlinear objective function by nonlinear coordinate transformations. That means mostly symbolic replacement of redundant subexpressions expecting less computation, while the simplified task remains equivalent to the original in the sense that a conversion between the solutions of the two forms is possible. We present a proper implementation of the referred theoretical algorithm in a modern symbolic programming environment, and testing on some examples both from the original publications and from the set of standard global optimization test problems to illustrate the capabilities of the method.     

A global optimization using linear relaxation for generalized geometric programming

Many local optimal solution methods have been developed for solving generalized geometric programming (GGP). But up to now, less work has been devoted to solving global optimization of (GGP) problem due to the inherent difficulty. This paper considers the global minimum of (GGP) problems. By utilizing an exponential variable transformation and the inherent property of the exponential function and some other techniques the initial nonlinear and nonconvex (GGP) problem is reduced to a sequence of linear programming problems. The proposed algorithm is proven that it is convergent to the global minimum through the solutions of a series of linear programming problems. Test results indicate that the proposed algorithm is extremely robust and can be used successfully to solve the global minimum of (GGP) on a microcomputer.     

一类特殊多项式整数规划问题的最优化算法

本文考虑了一类特殊的多项式整数规划问题。此类问题有很广泛的实际应用,并且是NP难问题。对于这类问题,最优性必要条件和最优性充分条件已经给出。我们在本文中将要利用这些最优性条件设计最优化算法。首 先,利用最优性必要条件,我们给出了一种新的局部优化算法。进而我们结合最优性充分条件、新的局部优化算法和辅助函数,设计了新的全局最优化算法。本文给出的算例展示出我们的算法是有效的和可靠的。     

An algorithm for a class of nonlinear fractional problems using ranking of the vertices

In this note we consider an algorithm for quasiconcave nonlinear fractional programming problems, based on ranking the vertices of a linear fractional programming problem and techniques from global optimization.     

基于粒子群算法的非线性二层规划问题的求解算法

粒子群算法（Particle Swarm Optimization，PSO）是一种新兴的优化技术，其思想来源于人工生命和演化计算理论。PSO通过粒子追随自己找到的最好解和整个群的最好解来完成优化。该算法简单易实现，可调参数少，已得到了广泛研究和应用。本文根据该算法能够有效的求出非凸数学规划全局最优解的特点，对非线性二层规划的上下层问题求解，并根据二层规划的特点，给出了求解非线性二层规划问题全局最优解的有效算法。数值计算结果表明该算法有效。     

整数规划的布谷鸟算法

布谷鸟搜索算法是一种新型的智能优化算法．本文采用截断取整的方法将基本布谷鸟搜索算法用于求解整数规划问题．通过对标准测试函数进行仿真实验并与粒子群算法进行比较,结果表明本文所提算法比粒子群算法拥有更好的性能和更强的全局寻优能力,可以作为一种实用方法用于求解整数规划问题．     

A General Hybrid Optimization Strategy for Curve Fitting in the Non-uniform Rational Basis Spline Framework

In this paper, a general methodology to approximate sets of data points through Non-uniform Rational Basis Spline (NURBS) curves is provided. The proposed approach aims at integrating and optimizing the full set of design variables (both integer and continuous) defining the shape of the NURBS curve. To this purpose, a new formulation of the curve fitting problem is required: it is stated in the form of a constrained nonlinear programming problem by introducing a suitable constraint on the curvature of the curve. In addition, the resulting optimization problem is defined over a domain having variable dimension, wherein both the number and the value of the design variables are optimized. To deal with this class of constrained nonlinear programming problems, a global optimization hybrid tool has been employed. The optimization procedure is split in two steps: firstly, an improved genetic algorithm optimizes both the value and the number of design variables by means of a two-level Darwinian strategy allowing the simultaneous evolution of individuals and species; secondly, the optimum solution provided by the genetic algorithm constitutes the initial guess for the subsequent gradient-based optimization, which aims at improving the accuracy of the fitting curve. The effectiveness of the proposed methodology is proven through some mathematical benchmarks as well as a real-world engineering problem.     

Solutions to quadratic minimization problems with box and integer constraints

This paper presents a canonical duality theory for solving quadratic minimization problems subjected to either box or integer constraints. Results show that under Gao and Strang’s general global optimality condition, these well-known nonconvex and discrete problems can be converted into smooth concave maximization dual problems over closed convex feasible spaces without duality gap, and can be solved by well-developed optimization methods. Both existence and uniqueness of these canonical dual solutions are presented. Based on a second-order canonical dual perturbation, the discrete integer programming problem is equivalent to a continuous unconstrained Lipschitzian optimization problem, which can be solved by certain deterministic technique. Particularly, an analytical solution is obtained under certain condition. A fourth-order canonical dual perturbation algorithm is presented and applications are illustrated. Finally, implication of the canonical duality theory for the popular semi-definite programming method is revealed.     

A reformulation framework for global optimization

In this paper, we present a global optimization method for solving nonconvex mixed integer nonlinear programming (MINLP) problems. A convex overestimation of the feasible region is obtained by replacing the nonconvex constraint functions with convex underestimators. For signomial functions single-variable power and exponential transformations are used to obtain the convex underestimators. For more general nonconvex functions two versions of the so-called αBB-underestimator, valid for twice-differentiable functions, are integrated in the actual reformulation framework. However, in contrast to what is done in branch-and-bound type algorithms, no direct branching is performed in the actual algorithm. Instead a piecewise convex reformulation is used to convexify the entire problem in an extended variable-space, and the reformulated problem is then solved by a convex MINLP solver. As the piecewise linear approximations are made finer, the solution to the convexified and overestimated problem will form a converging sequence towards a global optimal solution. The result is an easily-implementable algorithm for solving a very general class of optimization problems.     

A linear programming-based optimization algorithm for solving nonlinear programming problems

In this paper a linear programming-based optimization algorithm called the Sequential Cutting Plane algorithm is presented. The main features of the algorithm are described, convergence to a Karush–Kuhn–Tucker stationary point is proved and numerical experience on some well-known test sets is showed. The algorithm is based on an earlier version for convex inequality constrained problems, but here the algorithm is extended to general continuously differentiable nonlinear programming problems containing both nonlinear inequality and equality constraints. A comparison with some existing solvers shows that the algorithm is competitive with these solvers. Thus, this new method based on solving linear programming subproblems is a good alternative method for solving nonlinear programming problems efficiently. The algorithm has been used as a subsolver in a mixed integer nonlinear programming algorithm where the linear problems provide lower bounds on the optimal solutions of the nonlinear programming subproblems in the branch and bound tree for convex, inequality constrained problems.     

New and efficient algorithms for transfer prices and inventory holding policies in two-enterprise supply chains

We consider a multi-period problem of fair transfer prices and inventory holding policies in two enterprise supply chains. This problem was formulated as a mixed integer non-linear program by Gjerdrum et al. (Eur J Oper Res 143:582–599, 2002). Existing global optimization methods to solve this problem are computationally expensive. We propose a continuous approach based on difference of convex functions (DC) programming and DC Algorithms (DCA) for solving this combinatorial optimization problem. The problem is first reformulated as a DC program via an exact penalty technique. Afterward, DCA, an efficient local approach in non-convex programming framework, is investigated to solve the resulting problem. For globally solving this problem, we investigate a combined DCA-Branch and Bound algorithm. DCA is applied to get lower bounds while upper bounds are computed from a relaxation problem. The numerical results on several test problems show that the proposed algorithms are efficient: DCA provides a good integer solution in a short CPU time although it works on a continuous domain, and the combined DCA-Branch and Bound finds an \(\epsilon \) -optimal solution for large-scale problems in a reasonable time.     

一类非线性两级整数规划问题的全局优化方法

本文研究了整数规划连续化的途径,对一类非线性两级整数规划问题的上级规划连续化以后采用模拟退火算法;其对应的下级规划问题采用离散搜索法求解,从而给出了求解一类非线性两级整数规划问题的一种全局优化算法,并通过算例验证了该算法是有效的.     

A note on “A Continuous Approach to Nonlinear Integer Programming”

Ge and Huang (1989) proposed an approach to transform nonlinear integer programming problems into nonlinear global optimization problems, which are then solved by the filled function transformation method. The approach has recently attracted much attention. This note indicates that the formulae to determine a penalty parameter in two fundamental theorems are incorrect, and presents the corrected formulae and revised theorems.     

Global optimization for the sum of generalized polynomial fractional functions

In this paper, a branch and bound approach is proposed for global optimization problem (P) of the sum of generalized polynomial fractional functions under generalized polynomial constraints, which arises in various practical problems. Due to its intrinsic difficulty, less work has been devoted to globally solving this problem. By utilizing an equivalent problem and some linear underestimating approximations, a linear relaxation programming problem of the equivalent form is obtained. Consequently, the initial non-convex nonlinear problem (P) is reduced to a sequence of linear programming problems through successively refining the feasible region of linear relaxation problem. The proposed algorithm is convergent to the global minimum of the primal problem by means of the solutions to a series of linear programming problems. Numerical results show that the proposed algorithm is feasible and can successfully be used to solve the present problem (P).