An efficient procedure for finding best compromise solutions to the multi-objective assignment problem

In this paper, we consider the problem of determining a best compromise solution for the multi-objective assignment problem. Such a solution minimizes a scalarizing function, such as the weighted Tchebychev norm or reference point achievement functions. To solve this problem, we resort to a ranking (or k-best) algorithm which enumerates feasible solutions according to an appropriate weighted sum until a condition, ensuring that an optimal solution has been found, is met. The ranking algorithm is based on a branch and bound scheme. We study how to implement efficiently this procedure by considering different algorithmic variants within the procedure: choice of the weighted sum, branching and bounding schemes. We present an experimental analysis that enables us to point out the best variants, and we provide experimental results showing the remarkable efficiency of the procedure, even for large size instances.     

隐目标回归算法设计研究

对常用的回归方法进行研究.此类方法虽然几何解释明确、易于求解,但均须事先确定(或假定)变量间的因果关系,再考虑建模,在实际应用中,对于很难确定变量的因果关系的问题,如物联网数据分析,上述方法就会失效.为此,提出一种无需假定因变量的隐目标回归方法.该方法易于核化,可以推广到非线性回归问题.通过人工数据和国际标准数据集上的实验验证了所提算法的有效性.     

一种新型可变径管道机器人的结构设计与控制实现

基于ATmega128单片机的管道探测机器人系统,包括硬件系统设计以及软件程序实现。为满足不同工业环境的需要,设计了无线与RS485总线两套通信方案进行人机交互控制系统与单片机的通信。独特的变径结构可以让机器人适应不同管径的管道,配合高效的电池切换算法,可以使其更好的适应工业环境。为了观察管道内部信息,安装了一个可360°旋转的摄像头,将管道内部画面实时传送给上位机。     

On the complexity of role updating feasibility problem in RBAC

In Role Based Access Control (RBAC) systems, it is necessary and important to update the role–permission assignments in order to reflect the evolutions of the system transactions. However, role updating is generally complex and challenging, especially for large-scale RBAC systems. This is because the resulting state is usually expected to meet various requirements and constraints. In this paper, we focus on a fundamental problem of role updating in RBAC, which determines whether there exists a valid role–permission assignment, i.e., whether it can satisfy all the requirements of the role updating and without violating any role–capacity or permission–capacity constraint. We formally define such a problem as the Role Updating Feasibility Problem (RUFP), and study the computational complexity of RUFP in different subcases. Our results show that although several subcases are solvable in linear time, this problem is NP-complete in the general case.     

Triangle strings: Structures for augmentation of vertex-disjoint triangle sets

Vertex-disjoint triangle sets (triangle sets for short) have been studied extensively. Many theoretical and computational results have been obtained. While the maximum triangle set problem can be viewed as the generalization of the maximum matching problem, there seems to be no parallel result to Berge's augmenting path characterization on maximum matching (C. Berge, 1957 [1]). In this paper, we describe a class of structures called triangle string, which turns out to be equivalent to the class of union of two triangle sets in a graph. Based on the concept of triangle string, a sufficient and necessary condition that a triangle set can be augmented is given. Furthermore, we provide an algorithm to determine whether a graph G with maximum degree 4 is a triangle string, and if G is a triangle string, we compute a maximum triangle set of it. Finally, we give a sufficient and necessary condition for a triangle string to have a triangle factor.     

Coordinating efficiency and equity in disaster relief logistics via information updates

This paper addresses a multi-supplier, multi-affected area, multi-relief, and multi-vehicle relief allocation problem in disaster relief logistics. A multi-objective optimisation model based on disaster scenario information updates is proposed in an attempt to coordinate efficiency and equity through timely and appropriate decisions regarding issues such as vehicle routing and relief allocation. An optimal stopping rule is also proposed to determine the optimum period of delay before responding to disaster, because decision making requires accurate disaster information. The main contribution of this paper is solving relief allocation problem in a novel way by correlating operational research with statistical decision making and Bayesian sequential analysis. Finally, a case is presented based on the post-disaster rescue in Eastern China after supertyphoon Saomai to test the applicability and show the potential advantages of the proposed model.     

What you get is what you see: revisiting the evaluator effect in usability tests

Usability evaluation is essential to user-centred design; yet, evaluators who analyse the same usability test sessions have been found to identify substantially different sets of usability problems. We revisit this evaluator effect by having 19 experienced usability professionals analyse video-recorded test sessions with five users. Nine participants analysed moderated sessions; 10 participants analysed unmoderated sessions. For the moderated sessions, participants reported an average of 33% of the problems reported by all nine of these participants and 50% of the subset of problems reported as critical or serious by at least one participant. For the unmoderated sessions, the percentages were 32% and 40%. Thus, the evaluator effect was similar for moderated and unmoderated sessions, and it was substantial for the full set of problems and still present for the most severe problems. In addition, participants disagreed in their severity ratings. As much as 24% (moderated) and 30% (unmoderated) of the problems reported by multiple participants were rated as critical by one participant and minor by another. The majority of the participants perceived an evaluator effect when merging their individual findings into group evaluations. We discuss reasons for the evaluator effect and recommend ways of managing it.     

Robust Treatment of Degenerate Elements in Interactive Corotational FEM Simulations

We address the problem of robust and efficient treatment of element collapse and inversion in corotational FEM simulations of deformable objects in two and three dimensions, and show that existing degeneration treatment methods have previously unreported flaws that seriously threaten robustness and physical plausibility in interactive applications. We propose a new method that avoids such flaws, yields faster and smoother degeneration recovery and extends the range of well‐behaved degenerate configurations without adding significant complexity or computational cost to standard explicit and quasi‐implicit solvers.     

一种广义分子计算模型及其在 NP问题中的应用

目前各种分子计算模型多基于生物技术,求解一个问题的分子计算机算法很难不作修改地应用于其他类似的问题,尚不似传统计算机般通用。为此,提出一种基于图灵机的广义分子计算模型,其由一台单带图灵机、一条单向只写带和一条工作带组成,通过只写带与工作带之间特殊的映射函数实现并行的同时读、写操作。实验说明了该模型能够在多项式时间求解NP完全的满足性问题（SAT）,比现有分子计算模型在计算准确性和通用性上存在明显优势。     

基于博弈论的百万富翁协议

在经典的百万富翁协议中,一方在得到最后的财富比较结果后,没有动机将结果告诉另一方,或者告诉另一方一个错误的结果。结合博弈论和密码算法,提出一种百万富翁协议。在此协议中,参与者背离协议的收益小于遵守协议的收益,遵守协议是参与者的最优策略,任何百万富翁的欺骗行为都能被鉴别和发现,因此理性的参与者有动机发送正确的数据。最后每个参与者都能公平地得到最后的财富比较结果。