Cyclic best first search: Using contours to guide branch‐and‐bound algorithms

The cyclic best‐first search (CBFS) strategy is a recent search strategy that has been successfully applied to branch‐and‐bound algorithms in a number of different settings. CBFS is a modification of best‐first search (BFS) that places search tree subproblems into contours which are collections of subproblems grouped in some way, and repeatedly cycles through all non‐empty contours, selecting one subproblem to explore from each. In this article, the theoretical properties of CBFS are analyzed for the first time. CBFS is proved to be a generalization of all other search strategies by using a contour definition that explores the same sequence of subproblems as any other search strategy. Further, a bound is proved between the number of subproblems explored by BFS and the number of children generated by CBFS, given a fixed branching strategy and set of pruning rules. Finally, a discussion of heuristic contour‐labeling functions is provided, and proof‐of‐concept computational results for mixed‐integer programming problems from the MIPLIB 2010 database are shown. © 2017 Wiley Periodicals, Inc. Naval Research Logistics, 64: 64–82, 2017     

各向异性矩形板平面应力问题一般解析解

采用复级数方法首次建立了线性偏微分方程组边值问题的一般解析解法,并用于求解各向异性矩形板平面应力问题,给出各向异性板平面应力问题一般解析解．引入（Ｕ,Ｖ）＝∑∞－∞（Ａ,Ｂ）ｅｉｍπζ,ｅｉｍπηｒ,代入控制方程组,推出实数型级数解,将其回代入平衡方程组中任一个,可确定待定系数（Ａ,Ｂ）之间关系．将一般解析解代入边界条件,用余弦级数的方法确定待求系数．数值计算验证了解析方法的收敛性．     

旋转单元电场矢量法的真解判定方法

旋转矢量法可被用来进行有源相控阵列的通道校准。每轮测试后在计算相应通道的幅相时会出现伪解。通过调整固定场矢量的幅度,进行两轮测试,判定两轮测试中绝对解不变的那组解为真解。其辨别方法,在有效判定真解的同时,也降低了计算量与测试量。另外,由于两轮测试时只需测量幅度信息,降低了测试设备复杂度。数值仿真结果证明了此方法的有效性。     

Hilbert 空间中半线性随机发展方程的 Mild 解的一个存在性定理

讨论如下的Ｈｉｌｂｅｒｔ空间中半线性随机发展方程的Ｃａｕｃｈｙ问题：ｄｙ（ｔ）＝［Ａｙ（ｔ）＋ｆ（ｔ,ｙ（ｔ））］ｄｔ＋Ｇ（ｔ,ｙ（ｔ））ｄＷ（ｔ）;ｙ（０）＝ｙ０．｛在并不要求系数ｆ、Ｇ满足Ｌｉｐｓｃｈｉｔｚ条件的情况下,对上述Ｃａｕｃｈｙ问题的Ｍｉｌｄ解建立了一个局部存在性定理．     

A branch‐and‐bound‐based solution approach for dynamic rerouting of airborne platforms

This article is a sequel to a recent article that appeared in this journal, “An extensible modeling framework for dynamic reassignment and rerouting in cooperative airborne operations” [ 17 ], in which an integer programming formulation to the problem of rescheduling in‐flight assets due to changes in battlespace conditions was presented. The purpose of this article is to present an improved branch‐and‐bound procedure to solve the dynamic resource management problem in a timely fashion, as in‐flight assets must be quickly re‐tasked to respond to the changing environment. To facilitate the rapid generation of attractive updated mission plans, this procedure uses a technique for reducing the solution space, supports branching on multiple decision variables simultaneously, incorporates additional valid cuts to strengthen the minimal network constraints of the original mathematical model, and includes improved objective function bounds. An extensive numerical analysis indicates that the proposed approach significantly outperforms traditional branch‐and‐bound methodologies and is capable of providing improved feasible solutions in a limited time. Although inspired by the dynamic resource management problem in particular, this approach promises to be an effective tool for solving other general types of vehicle routing problems. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

Bounded flexibility in days‐on and days‐off scheduling

This article presents a flexible days‐on and days‐off scheduling problem and develops an exact branch and price (B&P) algorithm to find solutions. The main objective is to minimize the size of the total workforce required to cover time‐varying demand over a planning horizon that may extend up to 12 weeks. A new aspect of the problem is the general restriction that the number of consecutive days on and the number of consecutive days off must each fall within a predefined range. Moreover, the total assignment of working days in the planning horizon cannot exceed some maximum value. In the B&P framework, the master problem is stated as a set covering‐type problem whose columns are generated iteratively by solving one of three different subproblems. The first is an implicit model, the second is a resource constrained shortest path problem, and the third is a dynamic program. Computational experiments using both real‐word and randomly generated data show that workforce reductions up to 66% are possible with highly flexible days‐on and days‐off patterns. When evaluating the performance of the three subproblems, it was found that each yielded equivalent solutions but the dynamic program proved to be significantly more efficient. © 2013 Wiley Periodicals, Inc. Naval Research Logistics 60: 678–701, 2013     

A mathematical formulation and efficient heuristics for the dynamic container relocation problem

The container relocation problem (CRP) is concerned with emptying a single yard‐bay which contains J containers each following a given pickup order so as to minimize the total number of relocations made during their retrieval process. The CRP can be modeled as a binary integer programming (IP) problem and is known to be NP‐hard. In this work, we focus on an extension of the CRP to the case where containers are both received and retrieved from a single yard‐bay, and call it the dynamic container relocation problem. The arrival (departure) sequences of containers to (from) the yard‐bay is assumed to be known a priori. A binary IP formulation is presented for the problem. Then, we propose three types of heuristic methods: index based heuristics, heuristics using the binary IP formulation, and a beam search heuristic. Computational experiments are performed on an extensive set of randomly generated test instances. Our results show that beam search heuristic is very efficient and performs better than the other heuristic methods.Copyright © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 101–118, 2014     

Decomposing inventory routing problems with approximate value functions

We present a time decomposition for inventory routing problems. The methodology is based on valuing inventory with a concave piecewise linear function and then combining solutions to single‐period subproblems using dynamic programming techniques. Computational experiments show that the resulting value function accurately captures the inventory's value, and solving the multiperiod problem as a sequence of single‐period subproblems drastically decreases computational time without sacrificing solution quality. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

兵力展开问题研究

如何将基地的兵力以最短时间展开到多个阵地中,是运输问题中的一种。为解决此问题对著名的兵力展开问题进行了研究。建立了兵力展开问题的数学模型,此模型是一个混合整数规划模型。提出了一种求解方法,该方法可解决类似的混合整数规划问题。最后给出了一个实例。     

使用三个数域的数域筛算法

大整数分解难题是RSA密码的数学安全基础.目前数域筛算法是分解365比特以上大整数的最有效方法,然而它的时间复杂度仍然是亚指数的.对于目前普遍使用的1024比特以上大整数,数域筛算法还不能分解,所以研究数域筛算法具有重要的意义.现有的一般数域筛算法普遍使用两个数域,对多个数域的研究极少.一般数域筛算法经过修改可以使用三个数域,即两个代数数域和一个有理数域.分析表明:修改后的数域筛算法与原来的一般数域筛算法在时间复杂度上处于同一量级.但修改后的数域筛算法有更多地方可以合并计算,所以计算速度更快了.通过两个实验也验证了这一结论.