We examine a decomposition approach to find good quality feasible solutions. In particular, we studya method to reduce the search-space by decomposing a problem into two partitions, where the second partition (i.e., the subproblem) contains the fixed solution of the first (i.e., the master). This type of approach is usually motivated by the presence of two sub-problems that are each more easily solved by different methods. Our work is motivated by methods for which it is nontrivial to return a strong `no-good', `Benders feasibility', or 'optimality' cut. Instead, we focus our attention on a uni-directional decomposition approach. Instead of providing a relaxation of the sub-problem for the master problem, as in Benders decomposition, we provide an approximation of the sub-problem. Thus, we aim at finding good quality feasible solutions in the first iteration. While the quality of the approximation itself affects the impact of this approach, we illustrate that even using a simple approximation can havestrong positive impact on two examples: the Travelling Purchaser Problem and a Mine Planning Problem.

Causal structure discovery methods are investigated recently but none of them has taken possible time-varying structure into consideration. This paper uses a notion of causal time-varying dynamic Bayesian network (CTV-DBN) and define a causal boundary to govern cross-time information sharing. CTV-DBN is constructed by using asymmetric kernels to address sample scarcity and to adhere to causal principles; while maintaining good variance and bias trade-off. Upon satisfying causal Markov assumption, causal inference can be made based on manipulation rule. We explore trajectory data collected from taxis in Beijing which exhibit heterogeneous patterns, data sparseness and distribution skewness. Experiments show that by using casual structures and trajectory clustering, we can analyse the spatio-temporal behavior of the trajectory data.

Since semantic trajectories can discover more semantic meanings of a user’s interests without geographic restrictions, research on semantic trajectories has attracted a lot of attentions in recent years. Most existing work discover the similar behavior of moving objects through analysis of their semantic trajectory pattern, that is, sequences of locations. However, this kind of trajectories without considering the duration of staying on a location limits wild applications. For example, Tom and Anne have a common pattern of Home Restaurant Company Restaurant , but they are not similar, since Tom works at Restaurant , sends snack to someone at Company and return to Restaurant while Anne has breakfast at Restaurant , works at Company and has lunch at Restaurant . If we consider duration of staying on each location we can easily to differentiate their behaviors. In this paper, we propose a novel approach for discovering common behaviors by considering the duration of staying on each location of trajectories (DoSTra). Our approach can be used to detect the group that has similar lifestyle, habit or behavior patterns and predict the future locations of moving objects. We evaluate the experiment based on synthetic dataset, which demonstrates the high effectiveness and efficiency of the proposed method.

We describe a multi-modal cargo routing (MMCR) domain for modelling military logistics planning problems. These are transport optimisation problems that feature timing constraints, concurrency, capacitated resources, and action costs. We have developed a PDDL domain model, and have released a collection of problem instances along with a software tool to aid in the design and generation of new problem instances. Small instances of this domain stretch the capabilities of existing automated planning procedures, and larger realistic instances are beyond the capabilities of existing automated planning systems. We anticipate that scalable solution procedures for this domain will follow in the footsteps of systems, such as OPTIC and TIMIPLAN, which combine heuristic search concepts with mathematical programming optimisation tools.

This paper presents a divide-and-conquer decomposition for solving continuous state reinforcement learning problems. The contribution lies in a method for stitching together continuous state subtasks in a near-seamless manner along wide continuous boundaries. We introduce the concept of Termination Approximation where the set of subtask termination states are covered by goal sets to generate a set of subtask option policies. The approach employs hierarchical reinforcement learning methods and exploits any underlying repetition in continuous problems to allow reuse of the option policies both within a problem and across related problems. The approach is illustrated using a series of challenging racecar problems.

Generalized Additive Models (GAM) are a widely popular class of regression models to forecast electricity demand, due to their high accuracy, flexibility and interpretability. However, the residuals of the fitted GAM are typically heteroscedastic and leptokurtic caused by the nature of energy data. In this paper we propose a novel approach to estimate the time-varying conditional variance of the GAM residuals, which we call the GAM2 algorithm. It allows utility companies and network operators to assess the uncertainty of future electricity demand and incorporate it into their planning processes. The basic idea of our algorithm is to apply another GAM to the squared residuals to explain the dependence of uncertainty on exogenous variables. Empirical evidence shows that the residuals rescaled by the estimated conditional variance are approximately normal. We combine our modeling approach with online learning algorithms that adjust for dynamic changes in the distributions of demand. We illustrate our method by a case study on data from RTE, the operator of the French transmission grid.

Discovering congestion patterns from table-formed traffic reports is critical for traffic bottleneck analysis. However, patterns mined by existing algorithms often do not satisfy user requirements and are not actionable for traffic management. Traffic officers may not pursue the most frequent patterns but expect mining outcomes showing the dependence between congestion and various kinds of road properties for traffic planning. Such multi-view analysis requires to integrate user preferences of data attributes into pattern mining process. To tackle this problem, we propose a multi-view attributes reduction model for discovering the patterns of user interests, in which user views are interpreted as preferred attributes and formulated by attribute orders. Based on the pattern discovery model, a workflow is built for traffic bottleneck analysis, which consists of data preprocessing, preference representation and congestion pattern mining. Our approach is validated on the reports of road conditions from Shanghai, which shows that the resultant multi-view findings are effective for analyzing congestion causes and traffic management.

We propose and evaluate a number of solutions to the problem of calculating the cost to serve each location in a single-vehicle transport setting. Such cost to serve analysis has application both strategically and operationally in transportation. The problem is formally given by the traveling salesperson game (TSG), a cooperative total utility game in which agents correspond to locations in a travelling salesperson problem (TSP). The cost to serve a location is an allocated portion of the cost of an optimal tour. The Shapley value is one of the most important normative division schemes in cooperative games, giving a principled and fair allocation both for the TSG and more generally. We consider a number of direct and sampling-based procedures for calculating the Shapley value, and present the first proof that approximating the Shapley value of the TSG within a constant factor is NP-hard. Treating the Shapley value as an ideal baseline allocation, we then develop six proxies for that value which are relatively easy to compute. We perform an experimental evaluation using Synthetic Euclidean games as well as games derived from real-world tours calculated for fast-moving consumer goods scenarios. Our experiments show that several computationally tractable allocation techniques correspond to good proxies for the Shapley value.

Mixture modelling involves explaining some observed evidence using a combination of probability distributions. The crux of the problem is the inference of an optimal number of mixture components and their corresponding parameters. This paper discusses unsupervised learning of mixture models using the Bayesian Minimum Message Length (MML) criterion. To demonstrate the effectiveness of search and inference of mixture parameters using the proposed approach, we select two key probability distributions, each handling fundamentally different types of data: the multivariate Gaussian distribution to address mixture modelling of data distributed in Euclidean space, and the multivariate von Mises-Fisher (vMF) distribution to address mixture modelling of directional data distributed on a unit hypersphere. The key contributions of this paper, in addition to the general search and inference methodology, include the derivation of MML expressions for encoding the data using multivariate Gaussian and von Mises-Fisher distributions, and the analytical derivation of the MML estimates of the parameters of the two distributions. Our approach is tested on simulated and real world data sets. For instance, we infer vMF mixtures that concisely explain experimentally determined three-dimensional protein conformations, providing an effective null model description of protein structures that is central to many inference problems in structural bioinformatics. The experimental results demonstrate that the performance of our proposed search and inference method along with the encoding schemes improve on the state of the art mixture modelling techniques.

Finding satisfying assignments for the variables involved in a set of constraints can be cast as a (bounded) model generation problem: search for (bounded) models of a theory in some logic. The state-of-the-art approach for bounded model generation for rich knowledge representation languages like ASP and FO(.) and a CSP modeling language such as Zinc, is ground-and-solve: reduce the theory to a ground or propositional one and apply a search algorithm to the resulting theory. An important bottleneck is the blow-up of the size of the theory caused by the grounding phase. Lazily grounding the theory during search is a way to overcome this bottleneck. We present a theoretical framework and an implementation in the context of the FO(.) knowledge representation language. Instead of grounding all parts of a theory, justifications are derived for some parts of it. Given a partial assignment for the grounded part of the theory and valid justifications for the formulas of the non-grounded part, the justifications provide a recipe to construct a complete assignment that satisfies the non-grounded part. When a justification for a particular formula becomes invalid during search, a new one is derived; if that fails, the formula is split in a part to be grounded and a part that can be justified. Experimental results illustrate the power and generality of this approach.