1,721,068 research outputs found
k-Clustering Minimum Biclique Completion Via a Hybrid CP and SDP approach
No full textThis paper presents a hybrid Constraint Programming (CP) and Semidefinite Programming (SDP) approach to the k-clustering minimum biclique completion problem on bipartite graphs. The problem consists in partitioning a bipartite undirected graph into k clusters such that the sum of the edges that complete each cluster into a biclique, i.e., a complete bipartite subgraph, is minimum. The problem arises in telecommunications, in particular in bundling channels in multicast transmissions. In literature, the problem has been tackled with an Integer Bilinear Programming approach. We introduce two quasi-biclique constraints and we propose a SDP relaxation of the problem that provides much stronger lower bounds than the Bilinear Programming relaxation. The quasi-biclique constraints and the SDP relaxation are integrated into a hybrid CP and SDP approach. Computational results on a set of random instances provide further evidence about the potential of CP and SDP hybridizations. © 2009 Springer Berlin Heidelberg
Optimal shapelets tree for time series interpretable classification
No full textTime series shapelets are a state-of-the-art data mining technique that is applied to time series supervised classification tasks. Shapelets are defined as subsequences that retain the most discriminating power contained in time series. The main advantage of shapelets-based methods consists of their great interpretability. Indeed, shapelets can provide the end-user with very helpful insights about the most interesting subsequences. In this paper, we propose a novel Mixed-Integer Programming model to optimize shapelets discovery based on optimal binary decision trees. Our formulation provides a flexible and adaptable classification framework that is interpretable with respect to both the mathematical model and the final output. Computational results for a large class of datasets show that our approach achieves performance comparable with state-of-the-art shapelets-based classification methods. Our model is the first approach based on optimal decision tree induction for time series classification
Constraint Programming-based Column Generation
No full textThis paper surveys recent applications and advances of the Constraint Program- ming-based Column Generation framework, where the master subproblem is solved by tradi- tional OR techniques, while the pricing subproblem is solved by Constraint Programming. This framework has been introduced to solve crew assignment problems, where complex regulations make the pricing subproblem demanding for traditional techniques, and then it has been applied to other contexts. The main benefits of using Constraint Programming are the expressiveness of its modeling language and the flexibility of its solvers. Recently, the Constraint Programming-based Column Generation framework has been applied to many other problems, ranging from classical combinatorial problems such as graph coloring and two dimensional bin packing, to application oriented problems, such as airline planning and resource allocation in wireless ad-hoc networks
A lagrangian propagator for artificial neural networks in constraint programming
No full textThis paper discusses a new method to perform propagation over a (two-layer, feed-forward) Neural Network embedded in a Constraint Programming model. The method is meant to be employed in Empirical Model Learning, a technique designed to enable optimal decision making over systems that cannot be modeled via conventional declarative means. The key step in Empirical Model Learning is to embed a Machine Learning model into a combinatorial model. It has been showed that Neural Networks can be embedded in a Constraint Programming model by simply encoding each neuron as a global constraint, which is then propagated individually. Unfortunately, this decomposition approach may lead to weak bounds. To overcome such limitation, we propose a new network-level propagator based on a non-linear Lagrangian relaxation that is solved with a subgradient algorithm. The method proved capable of dramatically reducing the search tree size on a thermal-aware dispatching problem on multicore CPUs. The overhead for optimizing the Lagrangian multipliers is kept within a reasonable level via a few simple techniques. This paper is an extended version of [27], featuring an improved structure, a new filtering technique for the network inputs, a set of overhead reduction techniques, and a thorough experimentation
Optimizing over the closure of rank inequalities with a small right-hand side for the maximum stable set problem via bilevel programming
No full textIn the context of the maximum stable set problem, rank inequalities impose that the cardinality of any set of vertices contained in a stable set be, at most, as large as the stability number of the subgraph induced by such a set. Rank inequalities are very general, as they subsume many classical inequalities such as clique, hole, antihole, web, and antiweb inequalities. In spite of their generality, the exact separation of rank inequalities has never been addressed without the introduction of topological restrictions on the induced subgraph and the tightness of their closure has never been investigated systematically. In this work, we propose a methodology for optimizing over the closure of all rank inequalities with a right-hand side no larger than a small constant without imposing any restrictions on the topology of the induced subgraph. Our method relies on the exact separation of a relaxation of rank inequalities, which we call relaxed k-rank inequalities, whose closure is as tight. We investigate the corresponding separation problem, a bilevel programming problem asking for a subgraph of maximum weight with a bound on its stability number, whose study could be of independent interest. We first prove that the problem is SP2 -hard and provide some insights on its polyhedral structure. We then propose two exact methods for its solution: a branch-and-cut algorithm (which relies on a family of faced-defining inequalities which we introduce in this paper) and a purely combinatorial branch-and-bound algorithm. Our computational results show that the closure of rank inequalities with a right-hand side no larger than a small constant can yield a bound that is stronger, in some cases, than Lovasz’s Theta function, and substantially stronger than bounds obtained with standard inequalities that are valid for the stable set problem, including odd-cycle inequalities and wheel inequalities
The Kantorovich-Wasserstein distance for spatial statistics: The Spatial-KWD library
No full textIn this paper we present Spatial-KWD, a free open-source tool for efficient computation of the Kantorovich-Wasserstein Distance (KWD), also known as Earth Mover Distance, between pairs of binned spatial distributions (histograms) of a non-negative variable. KWD can be used in spatial statistics as a measure of (dis)similarity between spatial distributions of physical or social quantities. KWD represents the minimum total cost of moving the 'mass' from one distribution to the other when the 'cost' of moving a unit of mass is proportional to the euclidean distance between the source and destination bins. As such, KWD captures the degree of 'horizontal displacement' between the two input distributions. Despite its mathematical properties and intuitive physical interpretation, KWD has found little application in spatial statistics until now, mainly due to the high computational complexity of previous implementations that did not allow its application to large problem instances of practical interest. Building upon recent advances in Optimal Transport theory, the Spatial-KWD library allows to compute KWD values for very large instances with hundreds of thousands or even millions of bins. Furthermore, the tool offers a rich set of options and features to enable the flexible use of KWD in diverse practical applications
- …
