Sentimental causal rule discovery from Twitter

Social media, especially Twitter is now one of the most popular platforms where people can freely express their opinion. However, it is difficult to extract important summary information from many millions of tweets sent every hour. In this work we propose a new concept, sentimental causal rules, and techniques for extracting sentimental causal rules from textual data sources such as Twitter which combine sentiment analysis and causal rule discovery. Sentiment analysis refers to the task of extracting public sentiment from textual data. The value in sentiment analysis lies in its ability to reflect popularly voiced perceptions that are stated in natural language. Causal rules on the other hand indicate associations between different concepts in a context where one (or several concepts) cause(s) the other(s). We believe that sentimental causal rules are an effective summarization mechanism that combine causal relations among different aspects extracted from textual data as well as the sentiment embedded in these causal relationships. In order to show the effectiveness of sentimental causal rules, we have conducted experiments on Twitter data collected on the Kurdish political issue in Turkey which has been an ongoing heated public debate for many years. Our experiments on Twitter data show that sentimental causal rule discovery is an effective method to summarize information about important aspects of an issue in Twitter which may further be used by politicians for better policy making.     

Self-regularized causal structure discovery for trajectory-based networks

Trajectory-based networks exhibit strong heterogeneous patterns amid human behaviors. We propose a notion of causal time-varying dynamic Bayesian network (cTVDBN) to efficiently discover such patterns. While asymmetric kernels are used to make the model better adherence to causal principles, the variations of network connectivities are addressed by an adaptive over-fitting control. Compact regularization paths are obtained by approximate homotopy to make the solution tractable. In our experiments, cTVDBN structure discovery has successfully revealed the evolution of time-varying relationships in a ring road system, and provided insights for plausible road structure improvements from a traffic flow dataset.     

A new cutting-stock heuristic for scheduling production

This study interprets a scheduling problem in the woven fiberglass industry as an example of the cutting-stock problem; where wasted production capacity rather than wasted material is to be controlled. The solution is complicated due to the need to consider setup costs, so a heuristic is developed and tested. Comparison to one company's a historical production decisions indicates that both wasted capacity and setup Costs can be substantially reduced through application of the heuristic.     

A new heuristic algorithm for rectangle packing

The rectangle packing problem often appears in encasement and cutting as well as very large-scale integration design. To solve this problem, many algorithms such as genetic algorithm, simulated annealing and other heuristic algorithms have been proposed. In this paper, a new heuristic algorithm is recommended based on two important concepts, namely, the corner-occupying action and caving degree. Twenty-one rectangle-packing instances are tested by the algorithm developed, 16 of which having achieved optimum solutions within reasonable runtime. Experimental results demonstrate that the algorithm developed is fairly efficient for solving the rectangle packing problem.     

A new heuristic for inferring regular grammars

Modifications to a grammatical inference scheme by Feldman et al. are presented. A comparison of the relative performance of the original and modified schemes is made using the complexity measures of Feldman and Wharton. The case where a complex model is used to generate the sample set is then analyzed. A set of 104 samples was found that trained the program to infer the grammar that corresponded to the original model. The results of a study of the performance of this algorithm when there is a large number of samples is then presented. The major conclusion of this study is that the modified scheme has a superior performance on small sample sets but is highly unsuitable for large ones.     

A new fast heuristic for labeling points

In the point site labeling problem, we are given a set P={p₁,p₂,…,pn} of point sites in the plane. The label of a point pi is an axis-parallel rectangle of specified size. The objective is to label the maximum number of points on the map so that the placed labels are mutually non-overlapping. Here, we investigate a special class of the point site labeling problem where (i) height of the labels of all the points are same but their lengths may differ, (ii) the label of a point pi touches the point at one of its four corners, and (iii) the label of one point does not obscure any other point in P. We describe an efficient heuristic algorithm for this problem which runs in time in the worst case. We run our algorithm as well as the algorithm Rules proposed by Wagner et al. on randomly generated point sets and on the available benchmarks. The results produced by our algorithm are almost the same as Rules in most of the cases. But our algorithm is faster than Rules in dense instance. We have also computed the optimum solutions for all the examples we have considered by designing an algorithm, which performs an exhaustive search in the worst case. We found that the exhaustive search algorithm runs reasonably fast for most of the examples we have considered.     

A new heuristic approach for non-convex optimization problems

In this work a new optimization method, called the heuristic Kalman algorithm (HKA), is presented. This new algorithm is proposed as an alternative approach for solving continuous, non-convex optimization problems. The principle of HKA is to explicitly consider the optimization problem as a measurement process designed to give an estimate of the optimum. A specific procedure, based on the Kalman estimator, was developed to improve the quality of the estimate obtained through the measurement process. The main advantage of HKA, compared to other metaheuristics, lies in the small number of parameters that need to be set by the user. Further, it is shown that HKA converges almost surely to a near-optimal solution. The efficiency of HKA was evaluated in detail using several non-convex test problems, both in the unconstrained and constrained cases. The results were then compared to those obtained via other metaheuristics. The numerical experiments show that HKA is a promising approach for solving non-convex optimization problems, particularly in terms of computation time and success ratio.     

A new heuristic approach to assembly line balancing

The main feature of the method suggested in this paper is the assignment of priority to elements and priority elements are preferred to non-priority elements when assigning elements to stations. It gives the minimum number of stations under a predetermined cycle time. The work element time is considered to be invariant. This method has been tested by solving nearly all the problems available in the pertinent literature. This method yields better or similar results as available in the literature. A computer program incorporating the new heuristic method is presented in the paper.     

面向社交媒体的直接因果网络发现算法

高维时序因果网络发现是社交媒体因果关系发现的重要问题。然而,现有的时序因果关系发现方法不能发现直接因果以致因果网络推断结果不准确。针对此问题提出了一种直接因果网络发现方法。该方法考虑了时序因果模型的因果延迟、滞后期数量和条件节点集等因素,更准确地发现直接因果关系;另外,采用结合置换检验的因果关系检验方法,解决传递熵阈值难以设定的问题。实验结果表明,该方法在因果网络推断中优于现有方法,有效提升时序上直接因果网络推断的准确率,适用于发现潜在社交媒体因果关系网络。     

A new mapping heuristic based on mean field annealing

A new mapping heuristic is developed, based on the recently proposed Mean Field Annealing (MFA) algorithm. An efficient implementation scheme, which decreases the complexity of the proposed algorithm by asymptotical factors, is also given. Performance of the proposed MFA algorithm is evaluated in comparison with two well-known heuristics: Simulated Annealing and Kernighan-Lin. Results of the experiments indicate that MFA can be used as an alternative heuristic for solving the mapping problem. The inherent parallelism of the MFA is exploited by designing an efficient parallel algorithm for the proposed MFA heuristic.     

A new heuristic for detecting non-Hamiltonicity in cubic graphs

We analyse a polyhedron which contains the convex hull of all Hamiltonian cycles of a given undirected connected cubic graph. Our constructed polyhedron is defined by polynomially-many linear constraints in polynomially-many continuous (relaxed) variables. Clearly, the emptiness of the constructed polyhedron implies that the graph is non-Hamiltonian. However, whenever a constructed polyhedron is non-empty, the result is inconclusive. Hence, the following natural question arises: if we assume that a non-empty polyhedron implies Hamiltonicity, how frequently is this diagnosis incorrect? We prove that, in the case of bridge graphs, the constructed polyhedron is always empty. We also demonstrate that some non-bridge non-Hamiltonian cubic graphs induce empty polyhedra as well. We compare our approach to the famous Dantzig–Fulkerson–Johnson relaxation of a TSP, and give empirical evidence which suggests that the latter is infeasible if and only if our constructed polyhedron is also empty. By considering special edge cut sets which are present in most cubic graphs, we describe a heuristic approach, built on our constructed polyhedron, for which incorrect diagnoses of non-Hamiltonian graphs as Hamiltonian appear to be very rare. In particular, for cubic graphs containing up to 18 vertices, only four out of 45,982 undirected connected cubic graphs were so misdiagnosed. By constrast, we demonstrate that an equivalent heuristic, when built on the Dantzig–Fulkerson–Johnson relaxation of a TSP, is mostly unsuccessful in identifying additional non-Hamiltonian graphs. These empirical results suggest that polynomial algorithms based on our constructed polyhedron may be able to correctly identify Hamiltonicity of a cubic graph in all but rare cases.     

A new directed branching heuristic for the pq-median problem

The pq-median problem, of Serra and ReVelle seeks to locate hierarchical facilities at two levels so as to obtain a coherent structure. Coherence requires that the entire area assigned to a facility at the inferior level be assigned to one and the same facility at the next higher level of the hierarchy. Although optimal solutions can be obtained by means of solving biobjective integer linear programs, large problems are likely to require heuristics. Here we present a new heuristic that combines the generation of points, by means of a “directed” branching procedure with the final selection of points, using the FDH-technique. We further compare our new heuristic with the two most relevant heuristics proposed by Serra and ReVelle.     

知识发现中的因果关联规则挖掘研究

因果关联规则是知识库中一类重要的知识类型,具有重要的应用价值。首先对因果关系的特殊性质进行了分析,然后基于语言场和广义归纳逻辑因果模型,从表示、挖掘、评价和应用几方面,对因果关联规则的研究进行了详细论述。并在此基础上提出了隐含因果关联规则的概念。通过语言场和推理机制的运用,使因果关联规则这一重要知识形式的挖掘和评价过程具有良好的逻辑性和扩张性。     

A new energy landscape paving heuristic for satellite module layouts

This article describes a study of the satellite module layout problem (SMLP), which is a three-dimensional (3D) layout optimization problem with performance constraints that has proved to be non-deterministic polynomial-time hard (NP-hard). To deal with this problem, we convert it into an unconstrained optimization problem using a quasi-physical strategy and the penalty function method. The energy landscape paving (ELP) method is a class of Monte-Carlo-based global optimization algorithm that has been successfully applied to solve many optimization problems. ELP can search for low-energy layouts via a random walk in complex energy landscapes. However, when ELP falls into the narrow and deep valleys of an energy landscape, it is difficult to escape. By putting forward a new update mechanism of the histogram function in ELP, we obtain an improved ELP method which can overcome this drawback. By incorporating the gradient method with local search into the improved ELP method, a new global search optimization method, nELP, is proposed for SMLP. Two representative instances from the literature are tested. Computational results show that the proposed nELP algorithm is an effective method for solving SMLP with performance constraints.     

A new heuristic algorithm for the operating room scheduling problem

Due to the great importance of operating rooms in hospitals, this paper studies an operating room scheduling problem with open scheduling strategy. According to this strategy, no time slot is reserved for a particular surgeon. The surgeons can use all available time slots. Based on Fei et al.’s model which is considered to be close to reality, we develop a heuristic algorithm to solve it. The idea of this heuristic algorithm is from dynamic programming by aggregating states to avoid the explosion of the number of states. The objective of this paper is to design an operating program to maximize the operating rooms’ use efficiency and minimize the overtime cost. Computational results show that our algorithm is efficient, especially for large size instances where our algorithm always finds feasible solutions while the algorithm of Fei et al. does not.     

A new pruning heuristic based on variance analysis of sensitivityinformation

Architecture selection is a very important aspect in the design of neural networks (NNs) to optimally tune performance and computational complexity. Sensitivity analysis has been used successfully to prune irrelevant parameters from feedforward NNs. This paper presents a new pruning algorithm that uses the sensitivity analysis to quantify the relevance of input and hidden units. A new statistical pruning heuristic is proposed, based on the variance analysis, to decide which units to prune. The basic idea is that a parameter with a variance in sensitivity not significantly different from zero, is irrelevant and can be removed. Experimental results show that the new pruning algorithm correctly prunes irrelevant input and hidden units. The new pruning algorithm is also compared with standard pruning algorithms.     

A new bidirectional heuristic for the assembly line balancing problem

Assembly line balancing problem (ALBP) is one of the well-known NP-hard layout planning problems for mass production systems. Many exact solution approaches have been developed, including 0–1 integer programming model, branch and bound algorithm, dynamic programming model, etc.; however, all optimal approaches are computationally inefficient in solving large-scale problems, which makes heuristic approaches a necessity in practice. In this paper we propose a new efficient heuristic, based on a recent bidirectional approach and the famous critical path method (CPM) widely used in project management, to resolve the issue of task assignment for ALBP. An example is given for illustration, and numerical results of sample problems selected from the literature are also given to show the effectiveness of the proposed heuristic.     

Conformant planning via heuristic forward search: A new approach

Conformant planning is the task of generating plans given uncertainty about the initial state and action effects, and without any sensing capabilities during plan execution. The plan should be successful regardless of which particular initial world we start from. It is well known that conformant planning can be transformed into a search problem in belief space, the space whose elements are sets of possible worlds. We introduce a new representation of that search space, replacing the need to store sets of possible worlds with a need to reason about the effects of action sequences. The reasoning is done by implication tests on propositional formulas in conjunctive normal form (CNF) that capture the action sequence semantics. Based on this approach, we extend the classical heuristic forward-search planning system FF to the conformant setting. The key to this extension is an appropriate extension of the relaxation that underlies FF's heuristic function, and of FF's machinery for solving relaxed planning problems: the extended machinery includes a stronger form of the CNF implication tests that we use to reason about the effects of action sequences. Our experimental evaluation shows the resulting planning system to be superior to the state-of-the-art conformant planners MBP, KACMBP, and GPT in a variety of benchmark domains.     

HC_AB: A new heuristic clustering algorithm based on Approximate Backbone

Clustering is an important research area with numerous applications in pattern recognition, machine learning, and data mining. Since the clustering problem on numeric data sets can be formulated as a typical combinatorial optimization problem, many researches have addressed the design of heuristic algorithms for finding sub-optimal solutions in a reasonable period of time. However, most of the heuristic clustering algorithms suffer from the problem of being sensitive to the initialization and do not guarantee the high quality results. Recently, Approximate Backbone (AB), i.e., the commonly shared intersection of several sub-optimal solutions, has been proposed to address the sensitivity problem of initialization. In this paper, we aim to introduce the AB into heuristic clustering to overcome the initialization sensitivity of conventional heuristic clustering algorithms. The main advantage of the proposed method is the capability of restricting the initial search space around the optimal result by defining the AB, and in turn, reducing the impact of initialization on clustering, eventually improving the performance of heuristic clustering. Experiments on synthetic and real world data sets are performed to validate the effectiveness of the proposed approach in comparison to three conventional heuristic clustering algorithms and three other algorithms with improvement on initialization.