Tabu Machine: A New Neural Network Solution Approach for Combinatorial Optimization Problems

A new artificial neural network solution approach is proposed to solve combinatorial optimization problems. The artificial neural network is called the Tabu Machine because it has the same structure as the Boltzmann Machine does but uses tabu search to govern its state transition mechanism. Similar to the Boltzmann Machine, the Tabu Machine consists of a set of binary state nodes connected with bidirectional arcs. Ruled by the transition mechanism, the nodes adjust their states in order to search for a global minimum energy state. Two combinatorial optimization problems, the maximum cut problem and the independent set problem, are used as examples to conduct a computational experiment. Without using overly sophisticated tabu search techniques, the Tabu Machine outperforms the Boltzmann Machine in terms of both solution quality and computation time.     

Probabilistic Analysis of Failures in Power Transmission Networks and Phase Transitions: Study Case of a High-Voltage Power Transmission Network

We present the failure analysis of a study case of a high-voltage power transmission network using the mathematical model of cascading blackouts introduced in Carreras et al. (Chaos 12:985–994, 2002). When the load of the network is randomly perturbed, we study the probability density function of the measure of the size of the resulting blackout as a function of the mean load level. The mathematical model used approximates the network with an undirected graph made of generator, load and junction nodes connected by branches representing the lines of the network. The electric flow in the network is found solving the optimal DC power-flow problem and the sequence of events causing a cascading blackout is simulated using a numerical scheme. The analysis points out the existence of values of the mean total power demand such that for higher values when the blackout size measure increases the decay of the blackout size measure probability density function changes from being best fitted by a negative exponential to being best fitted by an inverse power law. The analogies between this phenomenon and the phase transition phenomenon studied in statistical mechanics are discussed. The website: contains some auxiliary material including animations that helps the understanding of this paper. The numerical experience reported in this paper has been obtained using the computing grid of ENEA (Roma, Italy).     

Neural Approach for Solving Several Types of Optimization Problems

Neural networks consist of highly interconnected and parallel nonlinear processing elements that are shown to be extremely effective in computation. This paper presents an architecture of recurrent neural net-works that can be used to solve several classes of optimization problems. More specifically, a modified Hopfield network is developed and its inter-nal parameters are computed explicitly using the valid-subspace technique. These parameters guarantee the convergence of the network to the equilibrium points, which represent a solution of the problem considered. The problems that can be treated by the proposed approach include combinatorial optimiza-tion problems, dynamic programming problems, and nonlinear optimization problems.Communicated by L. C. W. Dixon     

A Heuristic for Boolean Optimization Problems

A heuristic method is proposed for the solution of a large class of binary optimization problems, which includes weighted versions of the set covering, graph stability, partitioning, maximum satisfiability, and numerous other problems. The reported substantial computational experiments amply demonstrate the efficiency of the proposed method.     

A Mixed-Integer Programming Model for Gas Purchase and Transportation

The natural gas supply chain involves three main agents: producers, transportation companies, and local distribution companies (LDCs). We present a MIP model that is the basis for a decision support system developed for a Chilean LDC. This model takes into account many of the complexities of the purchasing and transportation contracts to help optimize daily purchase and transportation decisions in the absence of local storage facilities. The model was solved to optimality within a reasonable time. We show how the model handles several contractual issues and give some insights for the case when demand scenarios are used to deal with uncertainty.     

燃气输配的数学模型

研究了某天然气公司向市民供应优质燃气的输配问题 ,建立了寻求合理的配产方案的非线性数学模型 ,运用拉格朗日乘子法、最速下降法、修正牛顿法、动态规划方法、化二次规划为线性规划的单纯形法和罚函数法等不同方法给出了各气井的合理的配产方案 .对于实际应用与大学生数学建模训练有一定的指导意义 .     

A Finite Algorithm for Solving Infinite Dimensional Optimization Problems

We consider the general optimization problem (P) of selecting a continuous function x over a -compact Hausdorff space T to a metric space A, from a feasible region X of such functions, so as to minimize a functional c on X. We require that X consist of a closed equicontinuous family of functions lying in the product (over T) of compact subsets Y _t of A. (An important special case is the optimal control problem of finding a continuous time control function x that minimizes its associated discounted cost c(x) over the infinite horizon.) Relative to the uniform-on-compacta topology on the function space C(T,A) of continuous functions from T to A, the feasible region X is compact. Thus optimal solutions x ^* to (P) exist under the assumption that c is continuous. We wish to approximate such an x ^* by optimal solutions to a net {P _i }, iI, of approximating problems of the form min_{xX i} c i(x) for each iI, where (1) the net of sets {X _i } _I converges to X in the sense of Kuratowski and (2) the net {c _i } _I of functions converges to c uniformly on X. We show that for large i, any optimal solution x ^* _i to the approximating problem (P _i ) arbitrarily well approximates some optimal solution x ^* to (P). It follows that if (P) is well-posed, i.e., limsupX _i ^* is a singleton {x ^*}, then any net {x _i ^*} _I of (P _i )-optimal solutions converges in C(T,A) to x ^*. For this case, we construct a finite algorithm with the following property: given any prespecified error and any compact subset Q of T, our algorithm computes an i in I and an associated x _i ^* in X _i ^* which is within of x ^* on Q. We illustrate the theory and algorithm with a problem in continuous time production control over an infinite horizon.     

A Branch-and-Bound Based Method for Solving Monotone Optimization Problems

Monotone optimization problems are an important class of global optimization problems with various applications. In this paper, we propose a new exact method for monotone optimization problems. The method is of branch-and-bound framework that combines three basic strategies: partition, convexification and local search. The partition scheme is used to construct a union of subboxes that covers the boundary of the feasible region. The convexification outer approximation is then applied to each subbox to obtain an upper bound of the objective function on the subbox. The performance of the method can be further improved by incorporating the method with local search procedure. Illustrative examples describe how the method works. Computational results for small randomly generated problems are reported. Dedicated to Professor Alex Rubinov on the occasion of his 65th birthday. The authors appreciate very much the discussions with Professor Alex Rubinov and his suggestion of using local search. Research supported by the National Natural Science Foundation of China under Grants 10571116 and 10261001, and Guangxi University Scientific Research Foundation (No. X051022).     

求解无约束优化问题的一个秩一适定方法

在本文中,我们给出一个求解无约束优化问题的秩一适定方法,该方法具有下述较好性质:校正矩阵是对称正定的;在适当条件下,对非凸函数拥有全局收敛性.我们还给出数值检验结果.     

A Gradient-based Continuous Method for Large-scale Optimization Problems

In this paper, we study a gradient-based continuous method for large-scale optimization problems. By converting the optimization problem into an ODE, we are able to show that the solution trajectory of this ODE tends to the set of stationary points of the original optimization problem. We test our continuous method on large-scale problems available in the literature. The simulation results are very attractive.This research was supported in part by Grants FRG/99-00/II-23 and FRG/00-0l/II-63 of Hong Kong Baptist University and the Research Grant Council of Hong Kong.     

基于GMDH-SVR致密气开发过程参数优化

本文基于非常规油气的致密气开发流程图,利用K-means将4291口气井根据单位压降产气量聚为三类。通过改进GMDH算法对训练集和测试集样本规模比例的完备性和样本次序的随机性进行研究以增强算法鲁棒性。以单位压降产气量作为评价参数对三类气井开发效能主要相关的11个参数进行特征提取并统计各参数作为主成分的概率,选择累计概率80%及以上最少参数作为SVR模型的输入变量,单位压降产气量作为输出变量,选择RBF 作为核函数。分别使三类井各一个样本井的压裂参数上下浮动20%,应用SVR模型统计相应单位压降产气量变化范围是[-18.08%,13.42%]、[-2.34%,5.39%]、[-16.10%,15.21%],分析不同压裂参数组合对单位压降产气量的影响趋势,确定工程实践最优压裂参数,提高气井效能。     

Mixed Integer Models for the Stationary Case of Gas Network Optimization

A gas network basically consists of a set of compressors and valves that are connected by pipes. The problem of gas network optimization deals with the question of how to optimize the flow of the gas and to use the compressors cost-efficiently such that all demands of the gas network are satisfied. This problem leads to a complex mixed integer nonlinear optimization problem. We describe techniques for a piece-wise linear approximation of the nonlinearities in this model resulting in a large mixed integer linear program. We study sub-polyhedra linking these piece-wise linear approximations and show that the number of vertices is computationally tractable yielding exact separation algorithms. Suitable branching strategies complementing the separation algorithms are also presented. Our computational results demonstrate the success of this approach. Received: April, 2004     

A Learning Framework for Neural Networks Using Constrained Optimization Methods

Conventional supervised learning in neural networks is carried out by performing unconstrained minimization of a suitably defined cost function. This approach has certain drawbacks, which can be overcome by incorporating additional knowledge in the training formalism. In this paper, two types of such additional knowledge are examined: Network specific knowledge (associated with the neural network irrespectively of the problem whose solution is sought) or problem specific knowledge (which helps to solve a specific learning task). A constrained optimization framework is introduced for incorporating these types of knowledge into the learning formalism. We present three examples of improvement in the learning behaviour of neural networks using additional knowledge in the context of our constrained optimization framework. The two network specific examples are designed to improve convergence and learning speed in the broad class of feedforward networks, while the third problem specific example is related to the efficient factorization of 2-D polynomials using suitably constructed sigma-pi networks.     

二维黏弹性力学问题的无网格自然单元法

基于无网格自然单元法,建立了求解二维黏弹性力学问题的一条新途径.基于弹性 黏弹性对应原理和Laplace(拉普拉斯)变换技术,首先将黏弹性问题转换成Laplace域内与弹性力学问题相同的形式,然后推导出基于自然单元法分析黏弹性问题的基本公式.作为一种新兴的无网格数值计算方法,自然单元法的实质是一种基于自然邻近插值的Galerkin(伽辽金)法.相对于其他无网格法,自然单元法的形函数具有插值性和支持域各向异性等特点.算例结果证明了所提分析方法的有效性.     

Information Transmission of a Policy Program: Models for the Optimal Detection of Key Players

The underlying motivation for this work stems from the observation that there was weak participation in a policy program to modernize the commerce of a city center. This was due in part to a poor performance from the trade association board in the transmission of information. Using the tools of social network analysis and combinatorial optimization, we search for new sets of key players that are better positioned to disseminate information in the collective. We detect 2 new sets of key players and compare them with the trade association board. The comparison shows that social network analysis and combinatorial optimization can be useful tools in making policy implementation processes more effective.     

A New Iteration and Preconditioning Method for Elliptic PDE-Constrained Optimization Problems

Optimal control problems constrained by a partial differential equation (PDE) arise in various important applications, such as in engineering and natural sciences. Normally the problems are of very large scale, so iterative solution methods must be used. Thereby the choice of an iteration method in conjunction with an efficient preconditioner is essential. In this paper, we consider a new iteration method and a new preconditioning technique for an elliptic PDE-constrained optimal control problem with a distributed control function. Some earlier used iteration methods and preconditioners in the literature are compared, both analytically and numerically with the new iteration method and the preconditioner.     

页岩气区块优选的模糊动态多属性决策模型研究

页岩气作为目前最现实的可替代能源倍受各国政府和企业的高度关注。针对信息不确定下页岩气区块优选的动态多属性决策难题,在初步估测不同阶段地质资源禀赋、基础设施建设投资以及环境保护要求等不确定信息下,以优选具有商业化价值开发的页岩气目标区块为重点研究对象,从解决不同区块的投资优先次序入手,运用多属性决策、模糊优化决策和动态决策优化的方法理论,通过剖析页岩气区块优选决策过程及其复杂性特征,将页岩气区块投资优选和排序问题进行形式化描述,提出一种探索解决这种模糊动态多属性决策问题的方法,并应用到具体的页岩气区块优选问题中。本项研究不仅有助于深化不确定条件下动态多属性决策理论的研究,还为解决页岩气区块优选这一投资决策难题提供新的思路和方法。     

最优化问题的并行算法

本文对求解非线性最优化问题的几种主要并行思想，即按变量分裂的并行算法，函数值、梯度值的并行计算，计算步骤并行的算法等，作了简要的综述，并介绍了近几年在这方面取得的进展．     

Nonconvex Stochastic Optimization for Model Reduction

In this paper a global stochastic optimization algorithm, which is almost surely (a.s.) convergent, is applied to the model reduction problem. The proposed method is compared with the balanced truncation and Hankel norm approximation methods by examples in step responses and in approximation errors as well. Simulation shows that the proposed algorithm provides better results.     

A Branch-and-Bound Algorithm for Concave Network Flow Problems

In this paper a Branch-and-Bound (BB) algorithm is developed to obtain an optimal solution to the single source uncapacitated minimum cost Network Flow Problem (NFP) with general concave costs. Concave NFPs are NP-Hard, even for the simplest version therefore, there is a scarcity of exact methods to address them in their full generality. The BB algorithm presented here can be used to solve optimally single source uncapacitated minimum cost NFPs with any kind of concave arc costs. The bounding is based on the computation of lower bounds derived from state space relaxations of a dynamic programming formulation. The relaxations, which are the subject of the paper (Fontes et al., 2005b) and also briefly discussed here, involve the use of non-injective mapping functions, which guarantee a reduction on the cardinality of the state space. Branching is performed by either fixing an arc as part of the final solution or by removing it from the final solution. Computational results are reported and compared to available alternative methods for addressing the same type of problems. It could be concluded that our BB algorithm has better performance and the results have also shown evidence that it has a sub-exponential time growth.