A new branch-and-bound algorithm for standard quadratic programming problems

In this paper we propose convex and LP bounds for standard quadratic programming (StQP) problems and employ them within a branch-and-bound approach. We first compare different bounding strategies for StQPs in terms both of the quality of the bound and of the computation times. It turns out that the polyhedral bounding strategy is the best one to be used within a branch-and-bound scheme. Indeed, it guarantees a good quality of the bound at the expense of a very limited computation time. The proposed branch-and-bound algorithm performs an implicit enumeration of all the KKT (stationary) points of the problem. We compare different branching strategies exploiting the structure of the problem. Numerical results on randomly generated problems (with varying density of the underlying convexity graph) are reported which show the effectiveness of the proposed approach, in particular in limiting the growth of the number of nodes in the branch-and-bound tree as the density of the underlying graph increases.     

基于SQP 局部搜索的混沌粒子群优化算法

提出一种基于序贯二次规划(SQP)法的混沌粒子群优化方法(CPSO-SQP).将混沌PSO作为全局搜索器,并用SQP加速局部搜索,使得粒子能够在快速局部寻优的基础上对整个空间进行搜索,既保证了算法的收敛性,又大大增加了获得全局最优的几率.仿真结果表明,算法精度高、成功率大、全局收敛速度快,明显优于现有算法.将所提出的算法用于高密度聚乙烯(HDPE)装置串级反应过程的乙烯单耗优化,根据工业反应机理以及现场操作经验分析可知,所提出的算法是可行的.     

求解一类特殊的双层规划问题的遗传算法

主要研究上层函数及其约束函数不要求具有凸性和可微性,下层是关于下层决策变量是凸二次规划的双层规划模型,通过Karush-Kuhn-Tucher 条件转化为一个单层规划,利用下层是正定二次规划,将下层的决策变量表示为关于 Lagrangian乘子的表达式,从而降低了搜索空间的维数,设计了遗传算法,并通过数值实验表明该遗传算非常有效。     

Constrained two-dimensional cutting stock problems a best-first branch-and-bound algorithm

In this paper, we develop a new version of the algorithm proposed in Hifi (Computers and Operations Research 24/8 (1997) 727–736) for solving exactly some variants of (un)weighted constrained two-dimensional cutting stock problems. Performance of branch-and-bound procedure depends highly on particular implementation of that algorithm. Programs of this kind are often accelerated drastically by employing sophisticated techniques. In the new version of the algorithm, we start by enhancing the initial lower bound to limit initially the space search. This initial lower bound has already been used in Fayard et al. 1998 (Journal of the Operational Research Society, 49, 1270–1277), as a heuristic for solving the constrained and unconstrained cutting stock problems. Also, we try to improve the upper bound at each internal node of the developed tree, by applying some simple and effcient combinations. Finally, we introduce some new symmetric-strategies used for neglecting some unnecessary duplicate patterns . The performance of our algorithm is evaluated on some problem instances of the literature and other hard-randomly generated problem instances.     

一种求解混合整数非线性规划问题的模拟退火算法

通过适当处理离散变量，将求解无约束非凸ＮＬＰ问题的高效模拟退火全局优化算法推广到求解一般非凸混合整数非线性规划问题。数值计算结果表明，文中模拟退火算法在适用性、解的质量和计算效率等方面优于其它方法，是求解一般非凸ＭＩＮＬＰ问题的一种有效的全局优化算法。     

改进的微粒群优化算法在过程综合中的应用

针对过程综合中的混合整数非线性规划(Mixed Integer Non-Linear Programming,MINLP)问题,利用改进的微粒群优化(Particle Swarm Optimization,PSO)算法对其进行求解。在基本的PSO算法的基础上,通过利用罚函数和引入sigmoid函数把PSO算法应用到MINLP问题的求解中,利用两个测试函数和一个过程综合的实例对其进行了测试并与其它算法所得的结果进行了比较,结果表明,PSO算法在使用的普遍性、求解的准确性方面都优于一般的算法,是一种有效的求解MINLP问题的方法。     

兼顾负荷变化的裂解炉炉群调度建模与优化

裂解炉是乙烯生产的核心装置,工业生产乙烯通常采用多台裂解炉并行运行,将烃类原料裂解成乙烯等小分子烃类化合物。在裂解炉的运行过程中会不可避免的在炉管内壁产生结焦,从而导致乙烯产率的下降,为此需要对裂解炉进行定期的停炉清焦。当多台裂解炉同时处理多种不同类型的原料,而且在操作成本和产品收率都在不断变化的情况下,对裂解炉炉群进行优化调度以取得生产利润的最大化具有重要意义。针对乙烯裂解炉炉群调度建模与优化问题,提出了一个同时考虑原料及其进料量负荷的新的调度模型,克服了之前炉群调度仅针对原料选择、裂解炉负荷依赖人工设定的不足,优化后使裂解炉炉群的生产效益得到提高,为工厂合理地安排生产提供了理论依据。     

A branch-and-bound algorithm for implementing set covering model expert systems

The conventional rule-based expert system can be formulated as a 0–1, integer program, specifically, as a set covering problem. However, the implementation of an expert system in this way requires that the set covering model be solved for k-best alternate optima or near-optima. We have devised a branch-and-bound algorithm which accomplishes this. The details of the algorithm are explained in the paper. Computational results are provided.     

A dynamic convexized method for nonconvex mixed integer nonlinear programming

We consider in this paper the nonconvex mixed-integer nonlinear programming problem. We present a mixed local search method to find a local minimizer of an unconstrained nonconvex mixed-integer nonlinear programming problem. Then an auxiliary function which has the same global minimizers and the same global minimal value as the original problem is constructed. Minimization of the auxiliary function using our local search method can escape successfully from previously converged local minimizers by taking increasing values of parameters. For the constrained nonconvex mixed-integer nonlinear programming problem, we develop a penalty based method to convert the problem into an unconstrained one, and then use the above method to solve the later problem. Numerical experiments and comparisons on a set of MINLP benchmark problems show the effectiveness of the proposed algorithm.     

Feasibility refinement in sequential quadratic programming using parametric sensitivity analysis

In this paper we present results that extend the sequential quadratic programming (SQP) algorithm with an additional feasibility refinement based on parametric sensitivity derivatives. The refinement is applicable without restriction on the problem dimensions in sparse SQP solvers. Parametric sensitivity analysis is a tool for post optimality analysis of the solution of a nonlinear optimization problem. For the refinement approach we apply this technique on the quadratic subproblems in order to improve the overall algorithm. The sensitivity derivatives required for this approach can be computed without noticeable computational effort as the system of linear equations to be solved coincides with the system already solved for the search direction computation. For similar algorithms in the context of post optimality analysis a linear rate of convergence has been proven and therefore an extrapolation method is applied to speed up the process. The presented algorithm has been integrated into the nonlinear program (NLP) solver WORHP and we perform a numerical study to evaluate different termination criteria for the proposed algorithm. Furthermore, numerical results on the CUTEst test set are shown.     

基于金字塔结构的群智能演化策略求解混合整数规划问题

混合整数非线性规划问题（mixed-integer nonlinear programming,MINLP） 广泛应用于科学及工程系统设计,传统的群智能算法在求解混合整数规划问题时,未能很好地解决种群内部个体或者种群之间开采与探索、竞争与协作的矛盾。为了解决这两个矛盾及更高效率地寻优,提出一种基于金字塔结构的群智能演化策略（swarm intelligent evolution strategy based on pyramid structure）的PES算法来求解混合整数规划问题。PES算法中明确的分工机制能够平衡全局与局部搜索的能力,晋升机制解决了种群间竞争与协作的矛盾。利用标准测试函数进行仿真,对比改进的粒子群算法（CLSPSO、CLSPSO2）及改进的差分进化算法（ridDE、ridDE2）的结果,发现PES算法在成功率与精度方面具有优势,也体现了PES算法的有效性。     

A sequential quadratic programming-based algorithm for optimization of gas networks

British Gas uses a complex, heavily looped network of pipes and controllable units (compressors and regulators) to transmit gas from coastal supply terminals to regional demand points. Computer algorithms are required for efficient management of the system. This paper describes an algorithm for optimal control over periods of up to a day. The problem is large scale and highly nonlinear in both objective function and constraints. The method is based on Sequential Quadratic Programming and takes account of the structure of the pipeflow equations by means of a reduced gradient technique which eliminates most of the variables from the quadratic subproblems. The latter involve only simple bound constraints, which are handled efficiently by a conjugate gradient-active set algorithm. Trust region techniques permit use of the exact Hessian, preserving sparsity. More general constraints are handled at an outer level by a truncated augmented Lagrangian method. Results are included for some realistic problems. The algorithm is generally applicable to problems with a control structure.     

约束求解与优化技术的结合

提出了将混合约束问题转化为混合整数规划问题的方法.用约束求解方法及混合整数规划方法共同求解混合约束问题可以令二者相互借鉴,从而促进二者求解技术的进一步发展.同时,由混合约束问题转化而来的混合整数规划问题也可作为求解混合整数规划问题的测试问题（benchmarks）.     

基于Matlab的非线性规划问题的求解

非线性规划问题是运筹学重要的分支,非线性规划理论及其算法为工程、管理、经济、科研、军事等方面的最优设计提供了有力的工具.论文首先介绍了非线性规划的基本概念和一般形式,并重点讨论了二次规划,一般非线性规划和0-1非线性规划的求解算法及求解过程.并在Matlab R2012a环境下进行仿真,通过结果可以发现,用Matlab求解非线性规划问题,大大简化计算、提高了计算效率和结果的准确性.     

A branch-and-bound algorithm for globally optimal camera pose and focal length

This paper considers the problem of finding the global optimum of the camera rotation, translation and the focal length given a set of 2D–3D point pairs. The global solution is obtained under the L-infinity optimality by a branch-and-bound algorithm. To obtain the goal, we firstly extend the previous branch-and-bound formulation and show that the image space error (pixel distance) may be used instead of the angular error. Then, we present that the problem of camera pose plus focal length given the rotation is a quasi-convex problem. This provides a derivation of a novel inequality for the branch-and-bound algorithm for our problem. Finally, experimental results with synthetic and real data are provided.     

非线性规划问题的极大熵多目标粒子群算法

结合非线性规划的约束条件构造了一个新的极大熵函数,利用该函数将问题转化成了两个目标的多目标优化问题.通过对违反约束动态的进行惩罚,提出了一种新的极大熵多目标粒子群算法.该方法能有效的保持群体中不可行解的一定比例,从而增加了群体的多样性,而且避免了传统的过度惩罚缺陷,使群体更好地向最优解逼近.计算机仿真表明,该算法对非线性规划问题求解是非常有效的.     

Sequential quadratic programming enhanced backtracking search algorithm

In this paper, we propose a new hybrid method called SQPBSA which combines backtracking search optimization algorithm (BSA) and sequential quadratic programming (SQP). BSA, as an exploration search engine, gives a good direction to the global optimal region, while SQP is used as a local search technique to exploit the optimal solution. The experiments are carried on two suits of 28 functions proposed in the CEC-2013 competitions to verify the performance of SQPBSA. The results indicate the proposed method is effective and competitive.     

求解二次规划逆问题的非单调信赖域算法

为了提高求解二次规划逆问题的速度,提出了针对求解该问题的非单调信赖域算法.为了降低问题的复杂度,将二次规划逆问题转换为决策变量相对较少的对偶问题,采用增广Lagrange法构造对偶问题的子问题,并通过引入光滑函数将子问题转换为无约束优化问题,利用非单调信赖域算法进行求解.数值实验结果表明,该算法的迭代次数比牛顿算法、Gauss回代交替方向法少,运行速度快.因此,对于大规模二次规划逆问题,该算法更加有效.