Solving the maximum edge weight clique problem via unconstrained quadratic programming

The unconstrained quadratic binary program (UQP) is proving to be a successful modeling and solution framework for a variety of combinatorial optimization problems. Experience reported in the literature with several problem classes has demonstrated that this approach works surprisingly well in terms of solution quality and computational times, often rivaling and sometimes surpassing more traditional methods. In this paper we report on the application of UQP to the maximum edge-weighted clique problem. Computational experience is reported illustrating the attractiveness of the approach.     

补孔措施目标井层优选方法

油井补孔措施就是增加射开新的油层,是保证油井高产、油田持续开发的重要增产措施.而补孔措施效果好坏,主要取决于目标井层的选择是否合适.分析了影响油井补孔措施效果的因素,认为主要包括两方面共7个因素,一方面是井因素,包括全井含水率和全井日产油量共2个因素,另一方面是小层因素,包括小层渗透率、小层孔隙度、小层有效厚度、小层含油饱和度和小层地层压力共5个因素.在此基础上,建立了油井补孔措施目标井层优选方法,该方法以模糊数学为基础,通过综合评判对侯选井层打分,从而优选补孔措施目标井层.实际应用结果表明,利用该方法优选补孔措施目标井层,可靠性高,补孔措施实施后效果好.这种方法具有较高的学术与实用价值.     

六西格玛管理中的网络计划技术及其应用

利用网络计划技术,对节点(事项)和箭条(作业活动)分别规定了六个时间值,讨论了他们之间的关系;结合实例应用,分析了资源的合理配置,得到了有一定参考意义的结果.     

微粒群算法及其在热轧生产调度中的应用

针对整数规划问题的特点,提出了一种在整数空间中进行进化计算的PSO算法,使微粒群的进化限于整数空间。给出了热轧生产调度问题的最优轧制单元数学规划模型。并将该方法成功应用于最优轧制单元求解。     

A fast Pareto genetic algorithm approach for solving expensive multiobjective optimization problems

We present a new multiobjective evolutionary algorithm (MOEA), called fast Pareto genetic algorithm (FastPGA), for the simultaneous optimization of multiple objectives where each solution evaluation is computationally- and/or financially-expensive. This is often the case when there are time or resource constraints involved in finding a solution. FastPGA utilizes a new ranking strategy that utilizes more information about Pareto dominance among solutions and niching relations. New genetic operators are employed to enhance the proposed algorithm’s performance in terms of convergence behavior and computational effort as rapid convergence is of utmost concern and highly desired when solving expensive multiobjective optimization problems (MOPs). Computational results for a number of test problems indicate that FastPGA is a promising approach. FastPGA yields similar performance to that of the improved nondominated sorting genetic algorithm (NSGA-II), a widely-accepted benchmark in the MOEA research community. However, FastPGA outperforms NSGA-II when only a small number of solution evaluations are permitted, as would be the case when solving expensive MOPs.     

Discrete Gradient Method: Derivative-Free Method for Nonsmooth Optimization

A new derivative-free method is developed for solving unconstrained nonsmooth optimization problems. This method is based on the notion of a discrete gradient. It is demonstrated that the discrete gradients can be used to approximate subgradients of a broad class of nonsmooth functions. It is also shown that the discrete gradients can be applied to find descent directions of nonsmooth functions. The preliminary results of numerical experiments with unconstrained nonsmooth optimization problems as well as the comparison of the proposed method with the nonsmooth optimization solver DNLP from CONOPT-GAMS and the derivative-free optimization solver CONDOR are presented.     

Comparison of bundle and classical column generation

When a column generation approach is applied to decomposable mixed integer programming problems, it is standard to formulate and solve the master problem as a linear program. Seen in the dual space, this results in the algorithm known in the nonlinear programming community as the cutting-plane algorithm of Kelley and Cheney-Goldstein. However, more stable methods with better theoretical convergence rates are known and have been used as alternatives to this standard. One of them is the bundle method; our aim is to illustrate its differences with Kelley’s method. In the process we review alternative stabilization techniques used in column generation, comparing them from both primal and dual points of view. Numerical comparisons are presented for five applications: cutting stock (which includes bin packing), vertex coloring, capacitated vehicle routing, multi-item lot sizing, and traveling salesman. We also give a sketchy comparison with the volume algorithm. This research has been supported by Inria New Investigation Grant “Convex Optimization and Dantzig-Wolfe Decomposition”.     

Global optimization of truss topology with discrete bar areas—Part I: theory of relaxed problems

This two part paper considers the classical problem of finding a truss design with minimal compliance subject to a given external force and a volume bound. The design variables describe the cross-section areas of the bars. While this problem is well-studied for continuous bar areas, we treat here the case of discrete areas. This problem is of major practical relevance if the truss must be built from pre-produced bars with given areas. As a special case, we consider the design problem for a single bar area, i.e., a 0/1-problem. In contrast to heuristic methods considered in other approaches, Part I of the paper together with Part II present an algorithmic framework for the calculation of a global optimizer of the underlying large-scaled mixed integer design problem. This framework is given by a convergent branch-and-bound algorithm which is based on solving a sequence of nonconvex continuous relaxations. The main issue of the paper and of the approach lies in the fact that the relaxed nonlinear optimization problem can be formulated as a quadratic program (QP). Here the paper generalizes and extends the available theory from the literature. Although the Hessian of this QP is indefinite, it is possible to circumvent the non-convexity and to calculate global optimizers. Moreover, the QPs to be treated in the branch-and-bound search tree differ from each other just in the objective function. In Part I we give an introduction to the problem and collect all theory and related proofs for the treatment of the original problem formulation and the continuous relaxed problems. The implementation details and convergence proof of the branch-and-bound methodology and the large-scale numerical examples are presented in Part II.     

Rainfall forecasting by technological machine learning models

Accurate forecasting of rainfall has been one of the most important issues in hydrological research. Due to rainfall forecasting involves a rather complex nonlinear data pattern; there are lots of novel forecasting approaches to improve the forecasting accuracy. Recurrent artificial neural networks (RNNS) have played a crucial role in forecasting rainfall data. Meanwhile, support vector machines (SVMs) have been successfully employed to solve nonlinear regression and time series problems. This investigation elucidates the feasibility of hybrid model of RNNs and SVMs, namely RSVR, to forecast rainfall depth values. Moreover, chaotic particle swarm optimization algorithm (CPSO) is employed to choose the parameters of a SVR model. Subsequently, example of rainfall values during typhoon periods from Northern Taiwan is used to illustrate the proposed RSVRCPSO model. The empirical results reveal that the proposed model yields well forecasting performance, RSVRCPSO model provides a promising alternative for forecasting rainfall values.     

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.