Exact Solution of Cutting Stock Problems Using Column Generation and Branch-and-Bound

This paper describes an attempt to solve the one-dimensional cutting stock problem exactly, using column generation and branch-and-bound. A new formulation is introduced for the one-dimensional cutting stock problem that uses general integer variables, not restricted to be binary. It is an arc flow formulation with side constraints, whose linear programming relaxation provides a strong lower bound. In this model, a cutting pattern, which corresponds to a path, is decomposed into single arc variables. The decomposition serves the purpose of showing that it is possible to combine the branch-and-bound method with variable generation. Computational times are reported for one-dimensional cutting stock instances with a number of orders up to 30.     

基于边缘的图象配准改进算法

现有的图象配准方法对旋转处理比较困难,且处理效率不高。本文提出一种基于边缘的图象配准改进算法,该算法首先用小波的快速方法提取边缘特征点,通过线拟合模型消除噪声;然后得出特征点的边缘方向,定义“角度直方图”来估计两幅待配准图象间的旋转角,应用线性加权方法消除奇异点,最后得到图象间的精确变换关系。     

Euclidean Distance Based Permutation Methods in Atmospheric Science

The majority of existing statistical methods inherently involve complex nonmetric analysis spaces due to their least squares regression origin; consequently, the analysis space of such statistical methods is not consistent with the simple metric Euclidean geometry of the data space in question. The statistical methods presented in this paper are consistent with the data spaces in question. These alternative methods depend on exact and approximate permutation procedures for univariate and multivariate data involving cyclic phenomena, autoregressive patterns, covariate residual analyses including most linear model based experimental designs, and linear and nonlinear prediction model evaluations. Specific atmospheric science applications include climate change, Atlantic basin seasonal tropical cyclone predictions, analyses of weather modification experiments, and numerical model evaluations for phenomena such as cumulus clouds, clear-sky surface energy budgets, and mesoscale atmospheric predictions.     

一种存储最佳的分支界限轮廓查询算法

给定一组多维的点,轮廓(skyline)查询能返回在所有维度上均不被其他点所支配(dominate)的点集.目前,对于集中式环境下的静态数据,BBS(分支界限轮廓)是一种最为有效的轮廓查询算法.然而,它却存在内存空间耗费大的不足.鉴于此,提出了一种基于最佳优先最近邻居查找的轮廓查询算法,称为IBBS(改进的分支界限轮廓).它既有最佳的I/O代价和较低的CPU开销,又有最少的内存空间消耗.其核心是利用一系列有效的剪枝策略丢弃所有不必要的记录.大量的实验证实IBBS优于BBS,尤其是在低维空间.     

分枝定界算法设计模式研究与应用

分枝定界算法是传统算法设计方法中重要算法之一,很多重要问题可以用它来解决。本文在对分枝定界算法进行深入研究的基础上,将其抽象成分枝定界算法设计模式,并使用C＋＋的模板机制加以实现。最后通过具体实例说明本文开发的分枝定界算法模板具有较高的可重用性、可编程性和可靠性。     

SAR影像配准中控制点粗差剔除方法研究

复数影像配准是雷达干涉测量中的关键步骤之一,而配准中选取的控制点往往存在粗差,影响配准精度。分析了SAR影像配准时控制点粗差产生的原因,提出了方差因子检验和Baarda数据探测法剔除控制点粗差的方法,建立了基于可靠控制点计算影像纠正的几何变换模型。利用ENVISAT卫星ASAR图像对所提方法进行了验证,结果表明,影像配准的精度达到了0.1像素,粗差剔除后SAR影像配准精度有明显提高。     

约束满足问题的预处理方法研究

搜索控制问题是大多数人工智能问题求解面临的一个根本间题,而约束满足是解决这一问题的常用方法之一它源于机器视觉领域中的情景标识任务,如今在人工智能的众多领域(如规划、调度、时序推理)中获得了广泛的应用,受到了人工智能界的高度重视.在近几期的UCAI和AAAI等国际人工智能会议上这方面的内容均占有一定的比重,《A币ficial In-telligence》杂志曾于1992年出了一期约束满足问题的专辑     

Parallel Branch-and-Bound Formulations for AND/OR Tree Search

This paper discusses two general schemes for performing branch-and-bound (B&B) search in parallel. These schemes are applicable in principle to most of the problems which can be solved by B&B. The schemes are implemented for SSS*, a versatile algorithm having applications in game tree search, structural pattern analysis, and AND/OR graph search. The performance of parallel SSS* is studied in the context of AND/OR tree and game tree search. The paper concludes with comments on potential applications of these parallel implementations of SSS* in structural pattern analysis and game playing.     

Superconvergent Two-Grid Methods for Elliptic Eigenvalue Problems

Some numerical algorithms for elliptic eigenvalue problems are proposed, analyzed, and numerically tested. The methods combine advantages of the two-grid algorithm (Xu and Zhou in Math Comput 70(233):17–25, 2001), the two-space method (Racheva and Andreev in Comput Methods Appl Math 2:171–185, 2002), the shifted inverse power method (Hu and Cheng in Math Comput 80:1287–1301, 2011; Yang and Bi in SIAM J Numer Anal 49:1602–1624, 2011), and the polynomial preserving recovery enhancing technique (Naga et al. in SIAM J Sci Comput 28:1289–1300, 2006). Our new algorithms compare favorably with some existing methods and enjoy superconvergence property.     

Gradient Methods for Nonstationary Unconstrained Optimization Problems

Problems of unconstrained optimization with an objective function depending on a scalar parameter (time) are considered. The solution of these problems also depends on time and any numerical method must keep track of this dependence. For the solution of such nonstationary problems, a discrete gradient method is treated, in which only one gradient step is taken for the varying function at each instant of time. Estimates of intervals (variations) between exact and approximate solutions are found and an asymptotic behavior of these estimates is defined.__________Translated from Avtomatika i Telemekhanika, No. 6, 2005, pp. 38–46.Original Russian Text Copyright © 2005 by Popkov.     

Accelerated Alternating Descent Methods for Dykstra-Like Problems

This paper extends recent results by the first author and T. Pock (ICG, TU Graz, Austria) on the acceleration of alternating minimization techniques for quadratic plus nonsmooth objectives depending on two variables. We discuss here the strongly convex situation, and how ‘fast’ methods can be derived by adapting the overrelaxation strategy of Nesterov for projected gradient descent. We also investigate slightly more general alternating descent methods, where several descent steps in each variable are alternatively performed.     

一类电路布线问题的分支限界算法

分支限界策略对很多实际问题是重要和有效的。论文首先提出了一类电路布线问题,然后给出了解决该问题的分支限界算法并分析了所给出算法的复杂度。实验结果验证了所提出方法的有效性。     

AND/OR Branch-and-Bound search for combinatorial optimization in graphical models

This is the first of two papers presenting and evaluating the power of a new framework for combinatorial optimization in graphical models, based on AND/OR search spaces. We introduce a new generation of depth-first Branch-and-Bound algorithms that explore the AND/OR search tree using static and dynamic variable orderings. The virtue of the AND/OR representation of the search space is that its size may be far smaller than that of a traditional OR representation, which can translate into significant time savings for search algorithms. The focus of this paper is on linear space search which explores the AND/OR search tree. In the second paper we explore memory intensive AND/OR search algorithms. In conjunction with the AND/OR search space we investigate the power of the mini-bucket heuristics in both static and dynamic setups. We focus on two most common optimization problems in graphical models: finding the Most Probable Explanation in Bayesian networks and solving Weighted CSPs. In extensive empirical evaluations we demonstrate that the new AND/OR Branch-and-Bound approach improves considerably over the traditional OR search strategy and show how various variable ordering schemes impact the performance of the AND/OR search scheme.     

Second Order Methods for the Optimal Control Problems

The paper considers the iterative improvement algorithms, the efficiency of which substantially depends on the chosen parameters values. The problem of control of these parameters is formulated and discussed. We designed the modified algorithms where parameters are automatically adjusted at each iteration. The original and modified algorithms are applied to solve the problem of optimal control for the ecology-economic system.     

Superconvergence of Discontinuous Galerkin Methods for Convection-Diffusion Problems

Some discontinuous Galerkin methods for the linear convection-diffusion equation −ε u″+bu′=f are studied. Based on superconvergence properties of numerical fluxes at element nodes established in some earlier works, e.g., Celiker and Cockburn in Math. Comput. 76(257), 67–96, 2007, we identify superconvergence points for the approximations of u or q=u′. Our results are twofold: 1) For the minimal dissipation LDG method (we call it md-LDG in this paper) using polynomials of degree p, we prove that the leading terms of the discretization errors for u and q are proportional to the right Radau and left Radau polynomials of degree p+1, respectively. Consequently, the zeros of the right-Radau and left-Radau polynomials of degree p+1 are the superconvergence points of order p+2 for the discretization errors of the potential and of the gradient, respectively.     

High Order A-stable Numerical Methods for Stiff Problems

Stiff problems pose special computational difficulties because explicit methods cannot solve these problems without severe limitations on the stepsize. This idea is illustrated using a contrived linear test problem and a discretized diffusion problem. Even though the Euler method can solve these problems if the stepsize is small enough, there is no such limitation for the implicit Euler method. To obtain high order A-stable methods, it is traditional to turn to Runge–Kutta methods or to linear multistep methods. Each of these has limitations of one sort or another and we consider, as a middle ground, the use of general linear (or multivalue multistage) methods. Methods possessing the property of inherent Runge–Kutta stability are identified as promising methods within this large class, and an example of one of these methods is discussed. The method in question, even though it has four stages, out-performs the implicit Euler method if sufficient accuracy is required, because of its higher order