Balancing stability and efficiency in team formation as a generalized roommate problem

The assignment of personnel to teams is a fundamental managerial function typically involving several objectives and a variety of idiosyncratic practical constraints. Despite the prevalence of this task in practice, the process is seldom approached as an optimization problem over the reported preferences of all agents. This is due in part to the underlying computational complexity that occurs when intra-team interpersonal interactions are taken into consideration, and also due to game-theoretic considerations, when those taking part in the process are self-interested agents. Variants of this fundamental decision problem arise in a number of settings, including, for example, human resources and project management, military platooning, ride sharing, data clustering, and in assigning students to group projects. In this article, we study an analytical approach to “team formation” focused on the interplay between two of the most common objectives considered in the related literature: economic efficiency (i.e., the maximization of social welfare) and game-theoretic stability (e.g., finding a core solution when one exists). With a weighted objective across these two goals, the problem is modeled as a bi-level binary optimization problem, and transformed into a single-level, exponentially sized binary integer program. We then devise a branch-cut-and-price algorithm and demonstrate its efficacy through an extensive set of simulations, with favorable comparisons to other algorithms from the literature.     

搜索路径给定时的搜索对策问题及其应用

搜索路径给定时的最优搜索方案问题,也可以理解为是关于搜索者和目标的二人对策问题,主要讨论了当搜索路径给定时的单个搜索者和单个目标的搜索对策问题。首先根据问题的特点,利用动态规划和迭代的方法,确定关于目标逃逸路径混合策略的最优分区,证明该分区是多面体凸集;针对目标不同逃逸路径的分区,求出搜索者的最大期望收益,再将问题转化为二人有限零和对策,计算出搜索者的支付矩阵,确定最优搜索策略。最后结合海军护航行动,对我舰载直升机搜索小型海盗船进行分析和计算,说明搜索路径给定时的最优搜索对策对于双方的资源分配和提高搜索效率具有一定的应用价值。     

Single‐commodity stochastic network design under demand and topological uncertainties with insufficient data

Stochastic network design is fundamental to transportation and logistic problems in practice, yet faces new modeling and computational challenges resulted from heterogeneous sources of uncertainties and their unknown distributions given limited data. In this article, we design arcs in a network to optimize the cost of single‐commodity flows under random demand and arc disruptions. We minimize the network design cost plus cost associated with network performance under uncertainty evaluated by two schemes. The first scheme restricts demand and arc capacities in budgeted uncertainty sets and minimizes the worst‐case cost of supply generation and network flows for any possible realizations. The second scheme generates a finite set of samples from statistical information (e.g., moments) of data and minimizes the expected cost of supplies and flows, for which we bound the worst‐case cost using budgeted uncertainty sets. We develop cutting‐plane algorithms for solving the mixed‐integer nonlinear programming reformulations of the problem under the two schemes. We compare the computational efficacy of different approaches and analyze the results by testing diverse instances of random and real‐world networks. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 154–173, 2017     

Sensor placement in active multistatic sonar networks

The idea of deploying noncollocated sources and receivers in multistatic sonar networks (MSNs) has emerged as a promising area of opportunity in sonar systems. This article is one of the first to address point coverage problems in MSNs, where a number of points of interest have to be monitored in order to protect them from hostile underwater assets. We consider discrete “definite range” sensors as well as various diffuse sensor models. We make several new contributions. By showing that the convex hull spanned by the targets is guaranteed to contain optimal sensor positions, we are able to limit the solution space. Under a definite range sensor model, we are able to exclude even more suboptimal solutions. We then formulate a nonlinear program and an integer nonlinear program to express the sensor placement problem. To address the nonconvex single‐source placement problem, we develop the Divide Best Sector (DiBS) algorithm, which quickly provides an optimal source position assuming fixed receivers. Starting with a basic implementation of DiBS, we show how incorporating advanced sector splitting methods and termination conditions further improve the algorithm. We also discuss two ways to use DiBS to find multiple source positions by placing sensors iteratively or simultaneously. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 287–304, 2017     

滑模控制的新型双幂次组合函数趋近律

提出一种基于双幂次组合函数趋近律的新型滑模控制方案。与现有的快速幂次或双幂次趋近律相比,具有更快的收敛速度,同时还保持了全局固定时间收敛特性,收敛时间上界与滑模初值无关。当系统存在有界扰动时,能够使滑模变量在有限时间内收敛到稳态误差界内,同时其稳态误差要小于现有方法的。仿真实验验证了该方法的有效性及理论分析的正确性。     

融合空间偏好和语义的个体活动识别方法

个体活动识别对用户画像、个性化推荐、异常行为检测、群体行为分析和基于活动的资源配置优化具有重要价值。提出了一种基于稀疏的社交媒体签到数据的个体活动语义识别方法,从签到数据中提取活动行为的时间周期性和趋势性特征,并采用空间偏好量化算法,从个体与群体活动的空间关联中提取群体和个体的空间访问偏好,使用自然语言嵌入工具BERT模型提取访问兴趣点的语义。时间特征、空间偏好特征和访问兴趣点名称语义特征共同构成表征群体、个体偏好的时空联合特征,通过极限梯度提升分类器对其进行分类,得到活动语义识别结果。在Foursquare数据集上的对比实验和消融实验中验证了所提活动语义识别模型可以有效提升活动语义识别的准确性。     

基于粒子群优化的观测站部署算法

针对红外观测站部署问题,在研究观测站位置对定位精度影响的基础上,提出了基于粒子群优化的观测站部署算法。首先对ECEF坐标系下的CRLB矩阵进行推导;然后将观测站优化部署问题抽象为非线性规划模型,并将红外传感器联合定位的CRLB作为目标函数;最后采用粒子群优化算法求解该模型,避免了传统的非线性规划算法需要求解目标函数梯度的难题。结果表明,本文的部署算法具有一定的理论依据和工程意义;可以为实际红外观测站的静态部署和动态部署提供参考。     

The burglar problem with multiple options

We consider the burglar problem in which a burglar can either retire or choose among different types of burglaries, with each type having its own success probability and reward distribution. Some general structural results are established and, in the case of exponentially distributed reward distributions, a solution technique is presented. The burglar problem's relationship to a stochastic knapsack problem with a random exponentially distributed knapsack capacity is shown. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 359–364, 2014     

A branch‐and‐price approach for the stochastic generalized assignment problem

In this article, we address a stochastic generalized assignment machine scheduling problem in which the processing times of jobs are assumed to be random variables. We develop a branch‐and‐price (B&P) approach for solving this problem wherein the pricing problem is separable with respect to each machine, and has the structure of a multidimensional knapsack problem. In addition, we explore two other extensions of this method—one that utilizes a dual‐stabilization technique and another that incorporates an advanced‐start procedure to obtain an initial feasible solution. We compare the performance of these methods with that of the branch‐and‐cut (B&C) method within CPLEX. Our results show that all B&P‐based approaches perform better than the B&C method, with the best performance obtained for the B&P procedure that includes both the extensions aforementioned. We also utilize a Monte Carlo method within the B&P scheme, which affords the use of a small subset of scenarios at a time to estimate the “true” optimal objective function value. Our experimental investigation reveals that this approach readily yields solutions lying within 5% of optimality, while providing more than a 10‐fold savings in CPU times in comparison with the best of the other proposed B&P procedures. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 131–143, 2014     

微槽结构单点金刚石飞切加工的切削力建模

超精密单点金刚石飞刀切削技术是一种比较新颖的微槽类结构加工方式。在飞切过程中,切削力是切削过程中重要的物理量,对加工后的表面质量、刀具磨损等有着直接影响。提出了一种基于直角微切削理论的动态微槽类结构飞切的力学模型,基于微切削理论,得到了前、后刀面切削力的理论模型。根据飞切的几何运动特征,建立了飞切过程中剪切角的计算模型,并根据单圈飞切实验得到了飞切过程中剪切面的变化规律。为了验证模型的正确性,采用不同切削参数进行了多圈重叠飞切实验,对切削力进行了测量和分析。实验得到的切削力大小和变化规律与理论模型计算得到的基本一致,证明了该切削力模型的有效性。