两种改进的模拟退火算法求解大值域约束满足问题

随机约束满足问题的相变现象及求解算法是NP-完全问题的研究热点。RB模型（Revised B）是一个非平凡的随机约束满足问题,它具有精确的可满足性相变现象和极易产生难解实例这两个重要特征。针对RB模型这一类具有大值域的随机约束满足问题,提出了两种基于模拟退火的改进算法即RSA（Revised Simulated Annealing Algorithm）和GSA（Genetic-simulated Annealing Algorithm）。将这两种算法用于求解RB模型的随机实例,数值实验结果表明：在进入相变区域时,RSA和GSA算法依然可以有效地找到随机实例的解,并且在求解效率上明显优于随机游走算法。在接近相变阈值点时,由这两种算法得到的最优解仅使得极少数的约束无法满足。     

一种基于变量熵求解约束满足问题的置信传播算法

在置信传播(belief propagation,BP)算法中,提出一种基于变量熵来挑选变量从而固定变量赋值的策略,用于求解一类具有增长定义域的随机约束满足问题.RB模型是一个具有增长定义域的随机约束满足问题的典型代表,已经严格证明它不仅存在精确的可满足性相变现象,而且可以生成难解实例.在RB模型上选取两组不同的参数进行数值实验.结果表明:在接近可满足性相变点时,BP引导的消去算法仍然可以非常有效地找到随机实例的解;不断增加问题的规模,算法的运行时间呈指数级增长;并且当控制参数(约束紧度)增加时,变量的平均自由度逐渐降低.     

On the competitive facility location problem with a free choice of suppliers

We consider a mathematical model from the class of competitive sequential facility location problems. In these problems, the competitors sequentially open their facilities, and each side aims to “capture” the consumers and maximize its profits. In the proposed model, we consider a situation of a “free” choice by each side of an open facility to service a customer. The model is formulated as a bilevel integer programming problem. We show that the problem of finding an optimal noncooperative solution can be represented as a maximization problem for a pseudo-Boolean function. We propose an algorithm for constructing an admissible noncooperative solution for fixed values of the variables in this pseudo-Boolean function. We also propose a method for constructing an upper bound on the maximal value of the pseudo-Boolean function on subsets of solutions defined by partial (0, 1)-vectors.     

GRASP with exterior path-relinking and restricted local search for the multidimensional two-way number partitioning problem

In this work, we tackle multidimensional two-way number partitioning (MDTWNP) problem by combining GRASP with Exterior Path Relinking. In the last few years, the combination of GRASP with path relinking (PR) has emerged as a highly effective tool for finding high-quality solutions for several difficult problems in reasonable computational time. However, in most of the cases, this hybridisation is limited to the variant known as interior PR. Here, we couple GRASP with the “exterior form” of path relinking and perform extensive experimentation to evaluate this variant. In addition, we enhance our GRASP with PR method with a novel local search method specially designed for the MDTWNP problem. Our computational experiments show the superiority of this approach compared with the previous best method for MDTWNP and with alternative methods for this problem that use other forms of PR.     

A Novel Model for the Time Dependent Competitive Vehicle Routing Problem: Modified Random Topology Particle Swarm Optimization

This paper presents a novel model for a time dependent vehicle routing problem when there is a competition between distribution companies for obtaining more sales. In a real-world situation many factors cause the time dependency of travel times, for example traffic condition on peak hours plays an essential role in outcomes of the planned schedule in urban areas. This problem is named as “Time dependent competitive vehicle routing problem” (TDVRPC) which a model is presented to satisfy the “non-passing” property. The main objectives are to minimize the travel cost and maximize the sale in order to serve customers before other rival distributors. To solve the problem, a Modified Random Topology Particle Swarm Optimization algorithm (RT-PSO) is proposed and the results are compared with branch and bound algorithm in small size problems. In large scales, comparison is done with original PSO. The results show the capability of the proposed RT-PSO method for handling this problem.     

Many hard examples in exact phase transitions

This paper analyzes the resolution complexity of two random constraint satisfaction problem (CSP) models (i.e. Model RB/RD) for which we can establish the existence of phase transitions and identify the threshold points exactly. By encoding CSPs into CNF formulas, it is proved that almost all instances of Model RB/RD have no tree-like resolution proofs of less than exponential size. Thus, we not only introduce new families of CSPs and CNF formulas hard to solve, which can be useful in the experimental evaluation of CSP and SAT algorithms, but also propose models with both many hard instances and exact phase transitions. Finally, conclusions are presented, as well as a detailed comparison of Model RB/RD with the Hamiltonian cycle problem and random 3-SAT, which, respectively, exhibit three different kinds of phase transition behavior in NP-complete problems.     

The Parameterized Complexity of Local Search for TSP, More Refined

We extend previous work on the parameterized complexity of local search for the Traveling Salesperson Problem (TSP). So far, its parameterized complexity has been investigated with respect to the distance measures (defining the local search area) “Edge Exchange” and “Max-Shift”. We perform studies with respect to the distance measures “Swap” and “r-Swap”, “Reversal” and “r-Reversal”, and “Edit”, achieving both fixed-parameter tractability and W[1]-hardness results. In particular, from the parameterized reduction showing W[1]-hardness we infer running time lower bounds (based on the exponential time hypothesis) for all corresponding distance measures. Moreover, we provide non-existence results for polynomial-size problem kernels and we show that some in general W[1]-hard problems turn fixed-parameter tractable when restricted to planar graphs.     

Finite Reasons for Safety

In this paper we investigate to what extent a very simple and natural “reachability as deducibility” approach, originating in research on formal methods for security, is applicable to the automated verification of large classes of infinite state and parameterized systems. In this approach the verification of a safety property is reduced to the purely logical problem of finding a countermodel for a first-order formula. This task is delegated then to generic automated finite model building procedures. A finite countermodel, if found, provides with a concise representation for a system invariant sufficient to establish the safety. In this paper we first present a detailed case study on the verification of a parameterized mutual exclusion protocol. Further we establish the relative completeness of the finite countermodel finding method (FCM) for a class of parameterized linear arrays of finite automata with respect to known methods based on monotonic abstraction and symbolic backward reachability. The practical efficiency of the method is illustrated on a set of verification problems taken from the literature using Mace4 model finding procedure.     

A novel Ising model processing achieving all interactions only by adjacent spins for a high-speed solver for versatile Ising machines

To implement the Ising model on hardware and create “things” with optimization capability for a future IoT society, two methods for solving an optimization and recognition problem by using a new general-purpose Ising model suitable for LSI chip implementation are proposed. An ordinary model cannot solve many optimization problems, by searching for the ground-state, because the number of interactions is not enough for mapping the problems to the model. This ordinary Ising model considers only interactions of adjacent spins. Actually, to solve an optimization problem, interactions between all spins must be considered. However, all interactions are impossible to implement in an LSI chip. Therefore, to consider all interactions equivalently by adjacent spins only, two models are proposed. By using these model that implements all interactions, it is possible to obtain good candidates for optimal solutions for the “traveling salesman problem” and the “support vector machine”. Moreover, since the features of original Ising model with all interactions is known as a general-purpose model, this result means that the proposed model can be used to obtain the optimal solution candidates for most optimization problems. Further, LSI block diagrams of the two models are presented.     

Cultural determinants of technology transfer - a case study in human resources planning for steel production

Technology transfer (TT) is a highly complex problem in development cooperation. Case studies that ITB has conducted in various projects focusing on automobile and steel production as well as in the machine tool sector indicate that the multi-dimensionality of know-how transfer is often and greatly underestimated during the planning and implementation of TTs from one industrial “culture” to another. Greater insight and knowledge of the problems associated with know-how transfer in TT projects can only be obtained from case studies in which this generalised finding is subject to detailed investigation. To illustrate this, we report on the planning and implementation of two joint ventures in Iran, namely a Soviet and an Italian steel works.     

Smile detection in the wild with deep convolutional neural networks

Smile or happiness is one of the most universal facial expressions in our daily life. Smile detection in the wild is an important and challenging problem, which has attracted a growing attention from affective computing community. In this paper, we present an efficient approach for smile detection in the wild with deep learning. Different from some previous work which extracted hand-crafted features from face images and trained a classifier to perform smile recognition in a two-step approach, deep learning can effectively combine feature learning and classification into a single model. In this study, we apply the deep convolutional network, a popular deep learning model, to handle this problem. We construct a deep convolutional network called Smile-CNN to perform feature learning and smile detection simultaneously. Experimental results demonstrate that although a deep learning model is generally developed for tackling “big data,” the model can also effectively deal with “small data.” We further investigate into the discriminative power of the learned features, which are taken from the neuron activations of the last hidden layer of our Smile-CNN. By using the learned features to train an SVM or AdaBoost classifier, we show that the learned features have impressive discriminative ability. Experiments conducted on the GENKI4K database demonstrate that our approach can achieve a promising performance in smile detection.     

Inductive hierarchical nonnegative graph embedding for “verb–object” image classification

Most existing image classification algorithms mainly focus on dealing with images with only “object” concepts. However, in real-world cases, a great variety of images contain “verb–object” concepts, rather than only “object” ones. The hierarchical structure embedded in these “verb–object” concepts can help to enhance classification. However, traditional feature representation methods cannot utilize it. To tackle this problem, we present in this paper a novel approach, called inductive hierarchical nonnegative graph embedding. By assuming that those “verb–object” concept images which share the same “object” part but different “verb” part have a specific hierarchical structure, we integrate this hierarchical structure into the nonnegative graph embedding technique, together with the definition of inductive matrix, to (1) conduct effective feature extraction from hierarchical structure, (2) easily transfer each new testing sample into its low-dimensional nonnegative representation, and (3) perform image classification of “verb–object” concept images. Extensive experiments compared with the state-of-the-art algorithms on nonnegative data factorization demonstrate the classification power of proposed approach on “verb–object” concept images classification.     

Multi-variable distributed backtracking with sessions

The Constraint Satisfaction Problem (CSP) formalism is used to represent many combinatorial decision problems instances simply and efficiently. However, many such problems cannot be solved on a single, centralized computer for various reasons (e.g., their excessive size or privacy). The Distributed CSP (DisCSP) extends the CSP model to allow such combinatorial decision problems to be modelled and handled. In this paper, we propose a complete DisCSP-solving algorithm, called Distributed Backtracking with Sessions (DBS), which can solve DisCSP so that each agent encapsulates a whole “complex” problem with many variables and constraints. We prove that the algorithm is sound and complete, and generates promising experimental results.     

Graphical models for optimal power flow

Optimal power flow (OPF) is the central optimization problem in electric power grids. Although solved routinely in the course of power grid operations, it is known to be strongly NP-hard in general, and weakly NP-hard over tree networks. In this paper, we formulate the optimal power flow problem over tree networks as an inference problem over a tree-structured graphical model where the nodal variables are low-dimensional vectors. We adapt the standard dynamic programming algorithm for inference over a tree-structured graphical model to the OPF problem. Combining this with an interval discretization of the nodal variables, we develop an approximation algorithm for the OPF problem. Further, we use techniques from constraint programming (CP) to perform interval computations and adaptive bound propagation to obtain practically efficient algorithms. Compared to previous algorithms that solve OPF with optimality guarantees using convex relaxations, our approach is able to work for arbitrary tree-structured distribution networks and handle mixed-integer optimization problems. Further, it can be implemented in a distributed message-passing fashion that is scalable and is suitable for “smart grid” applications like control of distributed energy resources. Numerical evaluations on several benchmark networks show that practical OPF problems can be solved effectively using this approach.     

An optimized real-time hands gesture recognition based interface for individuals with upper-level spinal cord injuries

This paper presents a hand gesture-based interface to facilitate interaction with individuals with upper-level spinal cord injuries, and offers an alternative way to perform “hands-on” laboratory tasks. The presented system consists of four modules: hand detection, tracking, trajectory recognition, and actuated device control. A 3D particle filter framework based on color and depth information is proposed to provide a more efficient solution to the independent face and hands tracking problem. More specifically, an interaction model utilizing spatial and motion information was integrated into the particle filter framework to tackle the “false merge” and “false labeling” problem through hand interaction and occlusion. To obtain an optimal parameter set for the interaction model, a neighborhood search algorithm was employed. An accuracy of 98.81 % was achieved by applying the optimal parameter set to the tracking module of the system. Once the hands were tracked successfully, the acquired gesture trajectories were compared with motion models. The dynamic time warping method was used for signals’ time alignment, and they were classified by a CONDENSATION algorithm with a recognition accuracy of 97.5 %. In a validation experiment, the decoded gestures were passed as commands to a mobile service robot and a robotic arm to perform simulated laboratory tasks. Control policies using the gestural control were studied and optimal policies were selected to achieve optimal performance. The computational cost of each system module demonstrated a real-time performance.     

Recursive “concave–convex” Fisher Linear Discriminant with applications to face,handwritten digit and terrain recognition

In classification, previous studies have shown that an eigenvalue based technique can be cast as an related SVM-type problem and that by solving this SVM-type problem, the performance can be improved significantly. In this paper, we develop a recursive “concave–convex” Fisher Linear Discriminant (DR) (RPFLD) for dimension reduction technique of high-dimensional data to extract as many meaningful features as possible, which incorporates the fundamental idea behind Fisher Linear Discriminant and casts the Fisher Linear Discriminant as a “concave–convex” programming problem based on the hinge loss. The solution of our method follows from solving the related SVM-type optimization problems iteratively, which means the proposed method, can be viewed as the combination of multiple related SVM-type problems. The special formulation of our method provides convenience for constructing sparse multi-class Fisher Linear Discriminant directly. Due to use of a recursive procedure, the number of features available from RPFLD is independent of the number of classes, meaning that in contrast to the original Fisher Linear Discriminant the number of features available from our method has no upper bound. We evaluate our algorithm on the Yale, and ORL face image databases, handwritten digit database and Terrain image dataset. Experimental results show that RPFLD outperforms other Fisher Linear Discriminant algorithms.     

Analysis and design of rank-based classifiers

In this paper, we propose a method to predict the presence or absence of correct classification results in classification problems with many classes and the output of the classifier is provided in the form of a ranking list. This problem differs from the “traditional” classification tasks encountered in pattern recognition. While the original problem of forming a ranking of the most likely classes can be solved by running several classification methods, the analysis presented here is moved one step further. The main objective is to analyse (classify) the provided rankings (an ordered list of rankings of a fixed length) and decide whether the “true” class is present on this list. With this regard, a two-class classification problem is formulated where the underlying feature space is built through a characterization of the ranking lists. Experimental results obtained for synthetic data as well as real world face identification data are presented.     

Predicate control: synchronization in distributed computations with look-ahead

The predicate control problem involves synchronizing a distributed computation to maintain a given global predicate. In contrast with many popular distributed synchronization problems such as mutual exclusion, readers writers, and dining philosophers, predicate control assumes a look-ahead, so that the computation is an off-line rather than an on-line input. Predicate control is targeted towards applications such as rollback recovery, debugging, and optimistic computing, in which such computation look-ahead is natural.We define predicate control formally and show that, in its full generality, the problem is NP-complete. We find efficient solutions for some important classes of predicates including “disjunctive predicates”, “mutual exclusion predicates”, and “readers writers predicates”. For each class of predicates, we determine the necessary and sufficient conditions for solving predicate control and describe an efficient algorithm for determining a synchronization strategy. In the case of “independent mutual exclusion predicates”, we determine that predicate control is NP-complete and describe an efficient algorithm that finds a solution under certain constraints.     

Construction method of shop-floor digital twin based on MBSE

Digital twin (DT) technology is essential for achieving the fusion of virtual-real cyber-physical systems. Academics and companies have made great strides in the theoretical research and case studies of constructing the shop-floor digital twin (SDT), which is the premise of applying DT technology on the shop floor. A shop floor is a large complex system that involves many elements including people, machines, materials, methods, and the environment and processes, such as the technical flow, business process, logistics, and control flow. However, most of the developed cases lack a hierarchical, structured and modularized implementation framework for the development of an SDT system, which leads to problems such as a low reuse rate of the system blocks, lack of scalability, and high upgrade and maintenance costs. In response to these issues, we propose a construction method of the DT for the shop floor based on model-based systems engineering from the perspective of the system. In this method, a comprehensive DT model for the shop floor is gradually constructed by using system modeling language, the modeling method “MagicGrid,” and the “V model” of systems engineering. The model includes four dimensions of the shop-floor requirements, structure, behavior, and parameters, as well as three stages (the problem domain, solution domain, and implementation domain), and connects nine steps of the “V model,” including the system requirements, system architecture, subsystem implementation, subsystem integration, and system verification. Then, based on an example of a real NC machining shop floor, subsystems including a visualization system, synchronization system, and simulation system, are discussed. Finally, the functions of the integrated systems are verified based on the requirements, including the real-time synchronization of “man, machine, material, and method” and the transient simulation in real time. The numerical indicators of the integrated system are verified, including the model completeness and synchronization timeliness.     

On a superconvergent lattice Boltzmann boundary scheme

In a seminal paper [20], Ginzburg and Adler (1994) analyzed the bounce-back boundary conditions for the lattice Boltzmann scheme and showed that it could be made exact to second order for the Poiseuille flow if some expressions depending upon the parameters of the method were satisfied, thus defining so-called “magic parameters”. Using the Taylor expansion method that one of us developed, we analyze a series of simple situations (1D and 2D) for diffusion and for linear fluid problems using bounce-back and “anti bounce-back” numerical boundary conditions. The result is that “magic parameters” depend upon the detailed choice of the moments and of their equilibrium values. They may also depend upon the way the flow is driven.