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.     

A Framework for Certified Boolean Branch-and-Bound Optimization

We consider optimization problems of the form (S, cost), where S is a clause set over Boolean variables x ₁?...?x _n , with an arbitrary cost function \(\mathit{cost}\colon \mathbb{B}^n \rightarrow \mathbb{R}\), and the aim is to find a model A of S such that cost(A) is minimized. Here we study the generation of proofs of optimality in the context of branch-and-bound procedures for such problems. For this purpose we introduce \(\mathtt{DPLL_{BB}}\), an abstract DPLL-based branch-and-bound algorithm that can model optimization concepts such as cost-based propagation and cost-based backjumping. Most, if not all, SAT-related optimization problems are in the scope of \(\mathtt{DPLL_{BB}}\). Since many of the existing approaches for solving these problems can be seen as instances, \(\mathtt{DPLL_{BB}}\) allows one to formally reason about them in a simple way and exploit the enhancements of \(\mathtt{DPLL_{BB}}\) given here, in particular its uniform method for generating independently verifiable optimality proofs.     

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

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

欧氏平面上NP-hard优化问题多项式时间近似方案设计技术

一、引言 欧氏空间中的组合优化问题均带有深远应用背景.这类问题的求解算法研究在计算机科学中占有重要位置.TSP问题、STEINER树问题、k-median 问题是三个经典的NP-Hard类组合优化问题[1～3],它们在欧氏平面上的求解算法广泛应用于网络可靠控制、集成电路设计、网络布局等领域.特别对TSP问题,虽然科学家们投入了大量的工作,但近三十年来没有取得实质性进展,而Arora等在1996-1998年应用相同的技术相继给出了上述问题在欧氏空间中的近似方案,使人们对该类问题的认识前进了一大步.     

立体堆与分枝界限算法

分枝界限算法是解决组合优化问题的常用方法之一.对于给定的问题和分枝策略,算法的运行时间取决于实现算法的数据结构.该文讨论了立体堆及其上的插入、删除算法;通过将分枝界限算法的运作过程与排序过程建立对应关系,给出了一般分枝界限算法的复杂度下界Ω(m+hlogh),其中m为评估的结点数,h为扩展的结点数;得出了立体堆为实现一般分枝界限算法的几乎最优数据结构;并对具体的作业分派问题实现了一个使用立体堆的分枝界限算法;提出了改善立体堆平衡性的措施.     

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

分枝定界算法是传统算法设计方法中重要算法之一,很多重要问题可以用它来解决。本文在对分枝定界算法进行深入研究的基础上,将其抽象成分枝定界算法设计模式,并使用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.     

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

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