SMOOTHING NEWTON ALGORITHM FOR THE CIRCULAR CONE PROGRAMMING WITH A NONMONOTONE LINE SEARCH

In this paper, we present a nonmonotone smoothing Newton algorithm for solving the circular cone programming(CCP) problem in which a linear function is minimized or maximized over the intersection of an affine space with the circular cone. Based on the relationship between the circular cone and the second-order cone(SOC), we reformulate the CCP problem as the second-order cone problem(SOCP). By extending the nonmonotone line search for unconstrained optimization to the CCP, a nonmonotone smoothing Newton method is proposed for solving the CCP. Under suitable assumptions, the proposed algorithm is shown to be globally and locally quadratically convergent. Some preliminary numerical results indicate the effectiveness of the proposed algorithm for solving the CCP.

Hybrid particle swarm optimization with chaotic search for solving integer and mixed integer programming problems

A novel chaotic search method is proposed,and a hybrid algorithm combining particle swarm optimization(PSO) with this new method,called CLSPSO,is put forward to solve 14 integer and mixed integer programming problems.The performances of CLSPSO are compared with those of other five hybrid algorithms combining PSO with chaotic search methods.Experimental results indicate that in terms of robustness and final convergence speed,CLSPSO is better than other five algorithms in solving many of these problems.Furthermore,CLSPSO exhibits good performance in solving two high-dimensional problems,and it finds better solutions than the known ones.A performance index(PI) is introduced to fairly compare the above six algorithms,and the obtained values of(PI) in three cases demonstrate that CLSPSO is superior to all the other five algorithms under the same conditions.

A Tabu Search Algorithm for Quadratic 0-1 Programming Problem

In this paper,quadratic 0-1 programming problem (I) is considered, in terms of its features quadratic 0-1 programming problem is solved by linear approxity heurstic algrothm and a developed tabu search ahgrothm .

Parallel Minimax Searching Algorithm for Extremum of Unimodal Unbounded Function

In this paper we consider a parallel algorithm that detects the maximizer of unimodal function f(x) computable at every point on unbounded interval (0, ∞). The algorithm consists of two modes: scanning and detecting. Search diagrams are introduced as a way to describe parallel searching algorithms on unbounded intervals. Dynamic programming equations, combined with a series of liner programming problems, describe relations between results for every pair of successive evaluations of function f in parallel. Properties of optimal search strategies are derived from these equations. The worst-case complexity analysis shows that, if the maximizer is located on a priori unknown interval (n-1], then it can be detected after cp(n)=「2log「p/2」+1(n+1)」-1 parallel evaluations of f(x), where p is the number of processors.

A Modified Algorithm for Nonliear Integer Programming

Based on the analysis to the random sear ch algorithm of LUUS, a modified random directed integer search algorithm (MRDI SA) is given for first time. And a practical example is given to show that the adva ntage of this kind of algorithm is the reliability can’t be infuenced by the ini tial value X (0) and the start search domain R (0) . Besides, i t can be applied to solve the higher dimensional constrained nonlinear integer p rogramming problem.

基于混合蒙特卡洛树搜索的电缆盘装箱方法

电缆盘装箱问题广泛存在于线缆企业的生产实际中,本质上属于带载重约束和正交旋转的多箱型二维装箱问题。针对电缆盘装箱问题,建立以装箱成本最小化为目标的混合整数规划模型,提出一种混合蒙特卡洛树搜索(HMCTS)算法。在蒙特卡洛树搜索框架下,通过融入高效邻域搜索策略,寻找得到较优的箱子选择方案,并确定每个箱子中货物的装箱位置和方式。在此基础上,构建电缆盘装箱问题的松弛模型,有效降低算法的计算成本。基于线缆企业生产实际中6种不同规模的数据集,对HMCTS算法进行仿真实验和对比分析,结果表明所提算法在求解电缆盘装箱问题中具有较高的有效性和鲁棒性。

GLOBAL CONVERGENCE RESULTS OF A THREE TERM MEMORY GRADIENT METHOD WITH A NON-MONOTONE LINE SEARCH TECHNIQUE

In this paper, a new class of three term memory gradient method with non-monotone line search technique for unconstrained optimization is presented. Global convergence properties of the new methods are discussed. Combining the quasi-Newton method with the new method, the former is modified to have global convergence property. Numerical results show that the new algorithm is efficient.

A SUBSPACE PROJECTED CONJUGATE GRADIENT ALGORITHM FOR LARGE BOUND CONSTRAINED QUADRATIC PROGRAMMING

A subspace projected conjugate gradient method is proposed for solving large bound constrained quadratic programming. The conjugate gradient method is used to update the variables with indices outside of the active set, while the projected gradient method is used to update the active variables. At every iterative level, the search direction consists of two parts, one of which is a subspace trumcated Newton direction, another is a modified gradient direction. With the projected search the algorithm is suitable to large problems. The convergence of the method is proved and same numerical tests with dimensions ranging from 5000 to 20000 are given.

A Method for Crude Oil Selection and Blending Optimization Based on Improved Cuckoo Search Algorithm

Refineries often need to find similar crude oil to replace the scarce crude oil for stabilizing the feedstock property. We introduced the method for calculation of crude blended properties firstly, and then created a crude oil selection and blending optimization model based on the data of crude oil property. The model is a mixed-integer nonlinear programming(MINLP) with constraints, and the target is to maximize the similarity between the blended crude oil and the objective crude oil. Furthermore, the model takes into account the selection of crude oils and their blending ratios simultaneously, and transforms the problem of looking for similar crude oil into the crude oil selection and blending optimization problem. We applied the Improved Cuckoo Search(ICS) algorithm to solving the model. Through the simulations, ICS was compared with the genetic algorithm, the particle swarm optimization algorithm and the CPLEX solver. The results show that ICS has very good optimization efficiency. The blending solution can provide a reference for refineries to find the similar crude oil. And the method proposed can also give some references to selection and blending optimization of other materials.

On the direct searches for non-smooth stochastic optimization problems

Many difficult engineering problems cannot be solved by the conventional optimization techniques in practice. Direct searches that need no recourse to explicit derivatives are revived and become popular since the new century. In order to get a deep insight into this field, some notes on the direct searches for non-smooth optimization problems are made. The global convergence vs. local convergence and their influences on expected solutions for simulation-based stochastic optimization are pointed out. The sufficient and simple decrease criteria for step acceptance are analyzed, and why simple decrease is enough for globalization in direct searches is identified. The reason to introduce the positive spanning set and its usage in direct searches is explained. Other topics such as the generalization of direct searches to bound, linear and non-linear constraints are also briefly discussed.

A UNIVERSAL APPROACH FOR CONTINUOUS OR DISCRETE NONLINEAR PROGRAMMINGS WITH MULTIPLE VARIABLES AND CONSTRAINTS

A universal numerical approach for nonlinear mathematic programming problems is presented with an application of ratios of first-order differentials/differences of objective functions to constraint functions with respect to design variables. This approach can be efficiently used to solve continuous and, in particular, discrete programmings with arbitrary design variables and constraints. As a search method, this approach requires only computations of the functions and their partial derivatives or differences with respect to design variables, rather than any solution of mathematic equations. The present approach has been applied on many numerical examples as well as on some classical operational problems such as one-dimensional and two-dimensional knap-sack problems, one-dimensional and two-dimensional resource-distribution problems, problems of working reliability of composite systems and loading problems of machine, and more efficient and reliable solutions are obtained than traditional methods. The present approach can be used without limitation of modeling scales of the problem. Optimum solutions can be guaranteed as long as the objective function, constraint functions and their First-order derivatives/differences exist in the feasible domain or feasible set. There are no failures of convergence and instability when this approach is adopted.

An Efficient Framework to Utilize Grover Search

This paper proposes an efficient framework to utilize quantum search practically.To the best of our knowledge,this is the first paper to show a concrete usage of quantum search in general programming.In our framework,we can utilize a quantum computer as a coprocessor to speed-up some parts of a program that runs on a classical computer.To do so,we propose several new ideas and techniques,such as a practical method to design a large quantum circuits for search problems and an efficient quantum comparator.

SEQUENTIAL QUADRATIC PROGRAMMING METHODS FOR OPTIMAL CONTROL PROBLEMS WITH STATE CONSTRAINTS

A kind of direct methods is presented for the solution of optimal control problems with state constraints. These methods are sequential quadratic programming methods. At every iteration a quadratic programming which is obtained by quadratic approximation to Lagrangian function and linear approximations to constraints is solved to get a search direction for a merit function. The merit function is formulated by augmenting the Lagrangian function with a penalty term. A line search is carried out along the search direction to determine a step length such that the merit function is decreased. The methods presented in this paper include continuous sequential quadratic programming methods and discreate sequential quadratic programming methods.

On the Solution of the Eigenvalue Complementarity Problem by a Line Search Filter-SQP Algorithm

In this paper, the Eigenvalue Complementarity Problem (EiCP) with real symmetric matrices is addressed, which appears in the study of contact problem in mechanics. We discuss a quadratic programming formulation to the problem. The resulting problems are nonlinear programs that can be solved by a line search filter-SQP algorithm.

Intelligent Iterated Local Search Methods for Solving Vehicle Routing Problem with Different Fleets

To solve vehicle routing problem with different fleets, two methodologies are developed. The first methodology adopts twophase strategy. In the first phase, the improved savings method is used to assign customers to appropriate vehicles. In the second phase, the iterated dynasearch algorithm is adopted to route each selected vehicle with the assigned customers. The iterated dynasearch algorithm combines dynasearch algorithm with iterated local search algorithm based on random kicks. The second methodplogy adopts the idea of cyclic transfer which is performed by using dynamic programming algorithm, and the iterated dynasearch algorithm is also embedded in it. The test results show that both methodologies generate better solutions than the traditional method, and the second methodology is superior to the first one.

Kernel Search-Framework for Dynamic Controller Placement in Software-Defined Network

In software-defined networking(SDN)networks,unlike traditional networks,the control plane is located separately in a device or program.One of the most critical problems in these networks is a controller placement problem,which has a significant impact on the network’s overall performance.This paper attempts to provide a solution to this problem aiming to reduce the operational cost of the network and improve their survivability and load balancing.The researchers have proposed a suitable framework called kernel search introducing integer programming formulations to address the controller placement problem.It demonstrates through careful computational studies that the formulations can design networks with much less installation cost while accepting a general connected topology among controllers and user-defined survivability parameters.The researchers used the proposed framework on six different topologies then analyzed and compared with Iterated Local Search(ILS)and Expansion model for the controller placement problem(EMCPP)along with considering several evaluation criteria.The results show that the proposed framework outperforms the ILS and EMCPP.Thus,the proposed framework has a 38.53%and 38.02%improvement in reducing network implementation costs than EMCPP and ILS,respectively.

A RECURSIVE QUADRATIC PROGRAMMING ALGORITHM THAT USES A NEW NONDIFFERENTIABLE PENALTY FUNCTIONS

In this papert a recursive quadratic programming algorithm is proposed andstudied.The line search functions used are Han's nondifferentiable penalty functionswith a second order penalty term. In order to avoid maratos effect,Fukushima's mixeddirection is used as the direction of line search.Finallyt we prove the global convergenceand the local second order convergence of the algorithm.

Towards Enhanced Program Comprehension for Service Oriented Architecture (SOA) Systems

Service Oriented Architecture (SOA) is an emerging paradigm for orchestrating software components to build new composite applications that enable businesses, government agencies and other organizations to collaborate across institutional boundaries. SOA offers new languages and a variety of software development tools that enable software engineers to configure software as services and to interconnect services with other services independent of differences in operating platform and programming and communicating languages. However, SOA composite applications introduce additional complexity into the construction, deployment and maintenance of software, for the purpose of aggravating the issue of program comprehension, which is at the heart of software maintenance. This article describes the challenges in SOA program comprehension and reports on the results of a two-part case study aimed at identifying information that would help a SOA software maintainer. Analysis of the results indicates a need for higher-level abstractions and visualizations that can enhance conventional text-based search to support SOA program understanding. This paper then reports on several specific abstractions, visualization methods, and the development of an intelligent search tool to enhance comprehension of the relationships and data within a SOA composite application.

线路运行中断下铁路旅客列车单向接运方案研究

为降低线路中断对铁路客运带来的影响,本文利用综合交通网络各方式间的互补性,提出线路中断条件下铁路旅客列车的接运方案优化方法。首先,从旅客列车运行变化和综合交通接运方案分析接运方案的成本及旅客延误时间,综合考虑接运车站折返及到发能力、接运车辆能力、接运站及车辆停站关系等方面,建立以旅客出行时间延误最小及接运方案成本最低为优化目标的线路中断下旅客列车单向接运方案双目标规划模型;其次,为提高算法效率,按照列车到发时间密集程度划分为多个单独计算的时段,为缩小算法搜索空间,分析接运车站的剩余折返能力,明确可行备选接运车站集,设计分时段禁忌搜索算法;最后,利用算例分析模型及算法的可行性及有效性。研究结果表明:当线路中断发生后,接运方案应选择接运距离较近的车站,接运成本及总延误比在列车原停靠站进行接运平均可降低45.3%和21.2%,因而,利用已不办理客运业务的车站进行接驳运输,可减轻其对铁路客运带来的影响;问题的研究有助于降低线路运行中断造成的影响程度,为运输管理部门提供决策参考。

城市轨道交通乘务交路方案编制的禁忌搜索优化方法

针对城市轨道交通普遍采用轮乘制、日班和两头班混合等特点,对城市轨道交通乘务交路方案编制问题进行研究,旨在降低乘务成本并提高乘务效率.首先,通过分析城市轨道交通乘务交路方案的构成要素,考虑值乘时长、值乘片段接续时间和接续地点等要求,构建值乘片段、值乘任务构成和乘务规则约束,由此建立以乘务组数量和总接续时间等综合指标最小化为目标函数的多目标0-1整数规划模型.然后,针对该模型设计禁忌搜索(Tabu Search,TS)算法进行求解,以先到先走(First-In-First-Out,FIFO)的就近指派原则得到初始解,并设计4种邻域变换策略,以提高邻域解的多样性,并构建基于多邻域结构的禁忌搜索求解算法,实现对乘务交路方案的优化.最后,以广州地铁7号线的乘务交路方案为例进行实例验证.研究结果表明:优化方案较实际运营方案的乘务作业段数和总接续时间分别降低了20%和4.94%,每个乘务作业段值乘列车数量从8.2列增加到10.3列,有效驾驶时间从5.4 h增加到5.8 h,优化方案的各项指标均得到显著提升.研究成果可以为城市轨道交通乘务计划编制提供理论和方法支持.