Combinatorial optimization is widely applied in a number of areas nowadays. Unfortunately, many combinatorial optimization problems are NP-hard which usually means that they are unsolvable in practice. However, it is often unnecessary to have an exact solution. In this case one may use heuristic approach to obtain a near-optimal solution in some reasonable time. We focus on two combinatorial optimization problems, namely the Generalized Traveling Salesman Problem and the Multidimensional Assignment Problem. The first problem is an important generalization of the Traveling Salesman Problem; the second one is a generalization of the Assignment Problem for an arbitrary number of dimensions. Both problems are NP-hard and have hosts of applications. In this work, we discuss different aspects of heuristics design and evaluation. A broad spectrum of related subjects, covered in this research, includes test bed generation and analysis, implementation and performance issues, local search neighborhoods and efficient exploration algorithms, metaheuristics design and population sizing in memetic algorithm. The most important results are obtained in the areas of local search and memetic algorithms for the considered problems. In both cases we have significantly advanced the existing knowledge on the local search neighborhoods and algorithms by systematizing and improving the previous results. We have proposed a number of efficient heuristics which dominate the existing algorithms in a wide range of time/quality requirements. Several new approaches, introduced in our memetic algorithms, make them the state-of-the-art metaheuristics for the corresponding problems. Population sizing is one of the most promising among these approaches; it is expected to be applicable to virtually any memetic algorithm.

We revisit the SeqBin constraint. This meta-constraint subsumes a number of important global constraints like Change, Smooth and IncreasingNValue. We show that the previously proposed filtering algorithm for SeqBin has two drawbacks even under strong restrictions: it does not detect bounds disentailment and it is not idempotent. We identify the cause for these problems, and propose a new propagator that overcomes both issues. Our algorithm is based on a connection to the problem of finding a path of a given cost in a restricted $n$-partite graph. Our propagator enforces domain consistency in O(nd^2) and, for special cases of SeqBin that include Change, Smooth and IncreasingNValue, in O(nd) time.

We propose a probabilistic formulation that enables sequential detection of multiple change points in a network setting. We present a class of sequential detection rules for certain functionals of change points (minimum among a subset), and prove their asymptotic optimality properties in terms of expected detection delay time. Drawing from graphical model formalism, the sequential detection rules can be implemented by a computationally efficient message-passing protocol which may scale up linearly in network size and in waiting time. The effectiveness of our inference algorithm is demonstrated by simulations.

The multiple attribute mixed type decision making is performed by four methods, that is, the relative approach degree of grey TOPSIS method, the relative approach degree of grey incidence, the relative membership degree of grey incidence and the grey relation relative approach degree method using the maximum entropy estimation, respectively. In these decision making methods, the grey incidence degree in four-dimensional Euclidean space is used. The final arrangement result is obtained by weighted Borda method. An example illustrates the applicability of the proposed approach.

Hidden Markov Models (HMMs) (Baum and Eagon, 1967; Rabiner, 1989) are the workhorse statistical model for discrete time series, with widely diverse applications including automatic speech recognition, natural language processing (NLP), and genomic sequence modeling. In this model, a discrete hidden state evolves according to some Markovian dynamics, and observations at a particular time depend only on the hidden state at that time. The learning problem is to estimate the model only with observation samples from the underlying distribution. Thus far, the predominant learning algorithms have been local search heuristics, such as the Baum-Welch / EM algorithm (Baum et al., 1970; Dempster et al., 1977). It is not surprising that practical algorithms have resorted to heuristics, as the general learning problem has been shown to be hard under cryptographic assumptions (Terwijn, 2002). Fortunately, the hardness results are for HMMs that seem divorced from those that we are likely to encounter in practical applications. The situation is in many ways analogous to learning mixture distributions with samples from the underlying distribution. There, the general problem is also believed to be hard. However, much recent progress has been made when certain separation assumptions are made with respect to the component mixture distributions (e.g.

The restricted Boltzmann machine (RBM) is a flexible tool for modeling complex data, however there have been significant computational difficulties in using RBMs to model high-dimensional multinomial observations. In natural language processing applications, words are naturally modeled by K-ary discrete distributions, where K is determined by the vocabulary size and can easily be in the hundreds of thousands. The conventional approach to training RBMs on word observations is limited because it requires sampling the states of K-way softmax visible units during block Gibbs updates, an operation that takes time linear in K. In this work, we address this issue by employing a more general class of Markov chain Monte Carlo operators on the visible units, yielding updates with computational complexity independent of K. We demonstrate the success of our approach by training RBMs on hundreds of millions of word n-grams using larger vocabularies than previously feasible and using the learned features to improve performance on chunking and sentiment classification tasks, achieving state-of-the-art results on the latter.

A multiple attribute decision making (MADM), in which attributes are real number, interval real number, linguistic and uncertain linguistic value, has been already applied in practice such as the evaluation of enterprise effect, the selection of investment project, the selection of person, the research of military equipment scheme, the evaluation of strategy effect, the reliability assessment and the maintainability assessment, etc (Yongqi Xia, 2004, Dang Luo, Sifeng Liu, 2005, Yongqing Wei, Peide Liu, 2009). Extended TOPSIS Method with Interval-Valued Intuitionistic Fuzzy Numbers for Virtual Enterprise Partner Selection has been researched by Fei Ye(2010). Chuanming Ding (2007,a) defined a new similarity degree for various types of attribute and normalized the calculation of similarity degree of the attribute value of each type in unified metric space. Also, by this similarity degree, the comparison of each plan with ideal plan was performed and decision making method was given. Chuanming (2007,b), based on the TOPSIS (Technique for Order Preference by Similarity to Ideal Solution), transformed the attribute value of plan into four-dimensional attribute value, unified various types of attribute value, defined a fourdimensional approach degree, and by this approach degree, solved the multiple attribute mixed-type decision-making problem associated with real number, interval real number, linguistic and uncertain linguistic value. Yongqi Xia (2004) studied a method considering insufficiency degree of information and preference to danger on the basis of the grey-fuzzy comprehensive evaluation method of interval value preference. In the method, they represent the weight and the attribute value by two interval number pair by considering membership and grey degree at the same time. Sifeng Liu, Yaoguo Dang, Jiangling Wang, Zhengpeng Wu (2009), based on the definitions of entropy, proposed a method of getting weight that considers the character of grey cluster decision-making and 2-tuple linguistic assessment, and proposed the method of 2-tuple linguistic assessment based on grey cluster. Zhen Zhang, Chonghui Guo (2012) transformed uncertain linguistic evaluation information of each decision maker to trapezoidal fuzzy numbers, and then denoted, by solving two optimization models, the collective evaluation of the alternatives by trapezoidal fuzzy numbers.

A new generalized multilinear regression model, termed the Higher-Order Partial Least Squares (HOPLS), is introduced with the aim to predict a tensor (multiway array) $\tensor{Y}$ from a tensor $\tensor{X}$ through projecting the data onto the latent space and performing regression on the corresponding latent variables. HOPLS differs substantially from other regression models in that it explains the data by a sum of orthogonal Tucker tensors, while the number of orthogonal loadings serves as a parameter to control model complexity and prevent overfitting. The low dimensional latent space is optimized sequentially via a deflation operation, yielding the best joint subspace approximation for both $\tensor{X}$ and $\tensor{Y}$. Instead of decomposing $\tensor{X}$ and $\tensor{Y}$ individually, higher order singular value decomposition on a newly defined generalized cross-covariance tensor is employed to optimize the orthogonal loadings. A systematic comparison on both synthetic data and real-world decoding of 3D movement trajectories from electrocorticogram (ECoG) signals demonstrate the advantages of HOPLS over the existing methods in terms of better predictive ability, suitability to handle small sample sizes, and robustness to noise.

Macros have long been studied in AI planning [9, 18]. Many domain-dependent applications of macros have been exhibited and studied [15, 17, 12]; also, a number of domain-independent methods for learning, inferring, filtering, and applying macros have been the topic of research continuing up to the present [2, 7, 20]. In this paper, we present a domain-independent algorithm that computes macros in a novel way. Our algorithm computes macros "on-the-fly" for a given set of states and does not require previously learned or inferred information, nor does it need any prior domain knowledge. We exhibit the power of our algorithm by using it to define new domain-independent tractable classes of classical planning that strictly extend previously defined such classes [6], and can be proved to include Blocksworld-arm 1 and Towers of Hanoi. We believe that this is notable as theoretically defined, domainindependent tractable classes have generally struggled to incorporate construction-type domains such as these two. We hence give theoretically grounded evidence of the computational value of macros in planning.

We propose a hierarchy for approximate inference based on the Dobrushin, Lanford, Ruelle (DLR) equations. This hierarchy includes existing algorithms, such as belief propagation, and also motivates novel algorithms such as factorized neighbors (FN) algorithms and variants of mean field (MF) algorithms. In particular, we show that extrema of the Bethe free energy correspond to approximate solutions of the DLR equations. In addition, we demonstrate a close connection between these approximate algorithms and Gibbs sampling. Finally, we compare and contrast various of the algorithms in the DLR hierarchy on spin-glass problems. The experiments show that algorithms higher up in the hierarchy give more accurate results when they converge but tend to be less stable.