An Improved Bernstein Global Optimization Algorithm for MINLP Problems with Application in Process Industry

We present an improved Bernstein global optimization algorithm to solve polynomial mixed-integer nonlinear programming (MINLP) problems. The algorithm is of branch-and-bound type, and uses the Bernstein form of the polynomials for the global optimization. The new ingredients in the algorithm include a modified subdivision procedure, a vectorized Bernstein cut-off test and a new branching rule for the decision variables. The performance of the improved algorithm is tested and compared with earlier reported Bernstein global optimization algorithm (to solve polynomial MINLPs) and with several state-of-the-art MINLP solvers on a set of 19 test problems. The results of the tests show the superiority of the improved algorithm over the earlier reported Bernstein algorithm and the state-of-the-art solvers in terms of the chosen performance metrics. Similarly, efficacy of the improved algorithm in handling a real-world MINLP problem is brought out via a trim-loss minimization problem from the process industry.     

A New Mixed Iterative Algorithm to Solve the Fuel-Optimal Linear Impulsive Rendezvous Problem

The optimal fuel impulsive time-fixed rendezvous problem is reviewed. In a linear setting, it may be reformulated as a non-convex polynomial optimization problem for a pre-specified fixed number of velocity increments. Relying on variational results previously published in the literature, an improved mixed iterative algorithm is defined to address the issue of optimization over the number of impulses. Revisiting the primer vector theory, it combines variational tests with sophisticated numerical tools from algebraic geometry to solve polynomial necessary and sufficient conditions of optimality. Numerical examples under circular and elliptic assumptions show that this algorithm is efficient and can be integrated into a rendezvous planning tool.     

A Combinatorial user optimal dynamic traffic assignment algorithm

This paper introduces a polynomial combinatorial optimization algorithm for the dynamic user optimal problem. The approach can efficiently solve single destination networks and can be potentially extended to heuristically solve multidestinational networks. In the model, traffic is propagated according to sound traffic flow theoretical models rather than link exit functions; thereby allowing link queue evolution to be modeled more precisely. The algorithm is designed, proven, implemented and computationally tested.     

A new approach to the weighted peak-constrained least-square error FIR digital filter optimal design problem

This paper deals with the design of linear-phase finite impulse response (FIR) digital filters using weighted peak-constrained least-squares (PCLS) optimization. The PCLS error design problem is formulated as a quadratically constrained quadratic semi-infinite programming problem. An exchange algorithm with a new exchange rule is proposed to solve the problem. The algorithm provides the approximate optimal solution after a finite number of iterations. In particular, the subproblem solved at each iteration is a quadratically constrained quadratic programming. We can rewrite it as a conic optimization problem solvable in polynomial time. For illustration, numerical examples are solved using the proposed algorithm.     

求解凸二次规划问题的一种加权路径跟踪内点算法

基于Darvay提出用加权路径跟踪内点算法解线性规划问题的相关工作,本文致力于将此算法推广于解凸二次规划问题,并证明此算法具有局部二次收敛速度和目前所知的最好的多项式时间算法复杂性.     

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

Minimizing rational functions by exact Jacobian SDP relaxation applicable to finite singularities

This paper considers the optimization problem of minimizing a rational function. We reformulate this problem as a polynomial optimization problem by the technique of homogenization. These two problems are shown to be equivalent under some generic conditions. The exact Jacobian SDP relaxation method proposed by Nie is used to solve the resulting polynomial optimization problem. We also prove that the assumption of nonsingularity in Nie’s method can be weakened to the finiteness of singularities. Some numerical examples are given in the end.     

Application of an optimization problem in Max-Plus algebra to scheduling problems

The problem tackled in this paper deals with products of a finite number of triangular matrices in Max-Plus algebra, and more precisely with an optimization problem related to the product order. We propose a polynomial time optimization algorithm for 2×2 matrices products. We show that the problem under consideration generalizes numerous scheduling problems, like single machine problems or two-machine flow shop problems. Then, we show that for 3×3 matrices, the problem is NP-hard and we propose a branch-and-bound algorithm, lower bounds and upper bounds to solve it. We show that an important number of results in the literature can be obtained by solving the presented problem, which is a generalization of single machine problems, two- and three-machine flow shop scheduling problems. The branch-and-bound algorithm is tested in the general case and for a particular case and some computational experiments are presented and discussed.     

Infeasible Predictor-Corrector Interior-Point Method Applied to Image Restoration in the Presence of Noise

Image recovery problems can be solved using optimization techniques. They lead often to the solution of either a large-scale convex quadratic program or equivalently a nondifferentiable minimization problem. To solve the quadratic program, we use an infeasible predictor-corrector interior-point method, presented in the more general framework of monotone LCP. The algorithm has polynomial complexity and it converges with asymptotic quadratic rate. When implementing the method to recover images, we take advantage of the underlying sparsity of the problem. We obtain good performances, that we assess by comparing the method with a variable-metric proximal bundle algorithm applied to the solution of equivalent nonsmooth problem.     

Global optimization algorithm for sum of generalized polynomial ratios problem

In this paper, a global optimization algorithm is proposed for solving sum of generalized polynomial ratios problem (P) which arises in various practical problems. Due to its intrinsic difficulty, less work has been devoted to globally solve the problem (P). For such problems, we present a branch and bound algorithm. In this method, by utilizing exponent transformation and new three-level linear relaxation method, a sequence of linear relaxation programming of the initial nonconvex programming problem (P) are derived which are embedded in a branch and bound algorithm. The proposed method need not introduce new variables and constraints and it is convergent to the global minimum of prime problem by means of the subsequent solutions of a series of linear programming problems. Several numerical examples in the literatures are tested to demonstrate that the proposed algorithm can systematically solve these examples to find the approximate ?-global optimum.     

A class of nonlinear nonseparable continuous knapsack and multiple-choice knapsack problems

This paper considers a general class of continuous, nonlinear, and nonseparable knapsack problems, special cases of which arise in numerous operations and financial contexts. We develop important properties of optimal solutions for this problem class, based on the properties of a closely related class of linear programs. Using these properties, we provide a solution method that runs in polynomial time in the number of decision variables, while also depending on the time required to solve a particular one-dimensional optimization problem. Thus, for the many applications in which this one-dimensional function is reasonably well behaved (e.g., unimodal), the resulting algorithm runs in polynomial time. We next develop a related solution approach to a class of continuous, nonlinear, and nonseparable multiple-choice knapsack problems. This algorithm runs in polynomial time in both the number of variables and the number of variants per item, while again dependent on the complexity of the same one-dimensional optimization problem as for the knapsack problem. Computational testing demonstrates the power of the proposed algorithms over a commercial global optimization software package.     

求解多项式规划的一个全局最优化算法

提出一个求解带箱子约束的一般多项式规划问题的全局最优化算法, 该算法包含两个阶段, 在第一个阶段, 利用局部最优化算法找到一个局部最优解. 在第二阶段, 利用一个在单位球上致密的向量序列, 将多元多项式转化为一元多项式, 通过求解一元多项式的根, 找到一个比当前局部最优解更好的点作为初始点, 回到第一个 阶段, 从而得到一个更好的局部最优解, 通过两个阶段的循环最终找到问题的全局最优解, 并给出了算法收敛性分析. 最后, 数值结果表明了算法是有效的.     

Approximation algorithms for combinatorial fractional programming problems

We are concerned with a combinatorial optimization problem which has the ratio of two linear functions as the objective function. This type of problems can be solved by an algorithm that uses an auxiliary problem with a parametrized linear objective function. Because of its combinatorial nature, however, it is often difficult to solve the auxiliary problem exactly. In this paper, we propose an algorithm which assumes that the auxiliary problems are solved only approximately, and prove that it gives an approximate solution to the original problem, of which the accuracy is at least as good as that of approximate solutions to the auxiliary problems. It is also shown that the time complexity is bounded by the square of the computation time of the approximate algorithm for the auxiliary problem. As an example of the proposed algorithm, we present a fully polynomial time approximation scheme for the fractional 0–1 knapsack problem.     

A linear programming approach to the electricity contract capacity problem

Determination of electricity contract capacity is a problem faced by all industrial customers in Taiwan. In the literature, the problem has been solved using metaheuristics, such as genetic algorithm and particle swarm optimization, which require substantial computation time to solve. In this paper we formulate the problem as a linear program, which requires only polynomial time. Our proposed linear program is better than any metaheuristic approach because a globally optimal solution can be guaranteed while using much less computation time. Two real-world cases, one from a university and the other from a paper mill, are used to demonstrate that the model can minimize the electricity bill for industrial customers.     

Reid-Zhi符号数值混合消元方法的一个应用

将Reid和Zhi提出的符号数值混合消元方法应用于求解多项式优化问题,将多项式优化问题转化为矩阵最小特征值求解问题,并在Maple软件中实现了算法.     

带有边集限制的最均匀支撑树问题

本在无向网络中，建立了带有边集限制的最均匀支撑树问题的网络模型．中首先解决最均匀支撑树问题，并给出求无向网络中最均匀支撑树的多项式时间算法；然后，给出了求无向网络中带有边集限制的最小树多项式时间算法；最后，在已解决的两个问题的基础上解决了带有边集限制的最均匀支撑树问题．     

Managing pharmaceuticals delivery service using a hybrid particle swarm intelligence approach

Medicines or drugs have unique characteristics of short life cycle, small size, light weight, restrictive distribution time and the need of temperature and humidity control (selected items only). Thus, logistics companies often use different types of vehicles with different carrying capacities, and considering fixed and variable costs in service delivery, which make the vehicle assignment and route optimization more complicated. In this study, we formulate the problem to a multi-type vehicle assignment and mixed integer programming route optimization model with fixed fleet size under the constraints of distribution time and carrying capacity. Given non-deterministic polynomial hard and optimal algorithm can only be used to solve small-size problem, a hybrid particle swarm intelligence (PSI) heuristic approach, which adopts the crossover and mutation operators from genetic algorithm and 2-opt local search strategy, is proposed to solve the problem. We also adapt a principle based on cost network and Dijkstra’s algorithm for vehicle scheduling to balance the distribution time limit and the high loading rate. We verify the relative performance of the proposed method against several known optimal or heuristic solutions using a standard data set for heterogeneous fleet vehicle routing problem. Additionally, we compare the relative performance of our proposed Hybrid PSI algorithm with two intelligent-based algorithms, Hybrid Population Heuristic algorithm and Improved Genetic Algorithm, using a real-world data set to illustrate the practical and validity of the model and algorithm.

     

Completely positive reformulations for polynomial optimization

Polynomial optimization encompasses a very rich class of problems in which both the objective and constraints can be written in terms of polynomials on the decision variables. There is a well established body of research on quadratic polynomial optimization problems based on reformulations of the original problem as a conic program over the cone of completely positive matrices, or its conic dual, the cone of copositive matrices. As a result of this reformulation approach, novel solution schemes for quadratic polynomial optimization problems have been designed by drawing on conic programming tools, and the extensively studied cones of completely positive and of copositive matrices. In particular, this approach has been applied to solve key combinatorial optimization problems. Along this line of research, we consider polynomial optimization problems that are not necessarily quadratic. For this purpose, we use a natural extension of the cone of completely positive matrices; namely, the cone of completely positive tensors. We provide a general characterization of the class of polynomial optimization problems that can be formulated as a conic program over the cone of completely positive tensors. As a consequence of this characterization, it follows that recent related results for quadratic problems can be further strengthened and generalized to higher order polynomial optimization problems. Also, we show that the conditions underlying the characterization are conceptually the same, regardless of the degree of the polynomials defining the problem. To illustrate our results, we discuss in further detail special and relevant instances of polynomial optimization problems.     

Note – Uncrossing a Family of Set-Pairs

Frank and Jordán [1] proved an important min-max result on covering a crossing family of set-pairs. As an application, among others they can solve the unweighted node-connectivity augmentation problem for directed graphs in polynomial time. In this paper, we show how to solve the dual packing problem in polynomial time. To decompose a fractional dual optimum as a convex combination of integer vertices, besides the ellipsoid method, we use a polynomial-time algorithm for uncrossing a family of set-pairs. Our main result is this uncrossing algorithm. Received November 9, 1998 / Revised October 18, 1999     

Generating Functions for Computing the Myerson Value

The complexity of a computational problem is the order of computational resources which are necessary and sufficient to solve the problem. The algorithm complexity is the cost of a particular algorithm. We say that a problem has polynomial complexity if its computational complexity is a polynomial in the measure of input size. We introduce polynomial time algorithms based in generating functions for computing the Myerson value in weighted voting games restricted by a tree. Moreover, we apply the new generating algorithm for computing the Myerson value in the Council of Ministers of the European Union restricted by a communication structure.