This paper presents an external parallelization of constraint programming (CP) search tree mixing both static and dynamic partitioning. The principle of the parallelization is to partition the CP search tree into a se...
详细信息
This paper presents an external parallelization of constraint programming (CP) search tree mixing both static and dynamic partitioning. The principle of the parallelization is to partition the CP search tree into a set of sub-trees, then assign each sub-tree to one computing core in order to perform a local search using a sequential CP solver. In this context, static partitioning consists of decomposing the CP variables domains in order to split the CP search tree into a set of disjoint sub-trees to assign them to the cores. This strategy performs well without adding an extra cost to the parallel search, but the problem is the load imbalance between computing cores. On the other hand, dynamic partitioning is based on preservation of the search state to generate, dynamically or on demand, the sub-trees that are assigned to the cores. This strategy offers good load balancing between the different computing cores, but computing overcosts appear due to the initialisation of the search when a sub-tree is migrated from one core to another. In this paper, we propose a new partitioning strategy that mixes the static and dynamic partitioning and enjoys the benefits of each strategy. This mixed partitioning is designed to run on shared and distributed memory architectures. The performances obtained are illustrated by solving the CP problems modelled using the FlatZinc format and solved using the Google OR-Tools solver on top of the parallel Bobpp framework.
Nowadays, Compressive Sensing (CS), is one of the emerging fields of research in signal processing. It aims at reconstructing a signal from a significantly reduced number of measurements. This is done by exploiting th...
详细信息
ISBN:
(纸本)9781538621233
Nowadays, Compressive Sensing (CS), is one of the emerging fields of research in signal processing. It aims at reconstructing a signal from a significantly reduced number of measurements. This is done by exploiting the sparsity property of the original signal. Since its start in 2006, CS has been applied in several domains such as wireless channel estimation, cognitive radio, and other domains. In this paper, we address a detailed overview of compressive sensing including recent CS algorithms and applications, also we propose a solution to CS limitations using constraint programming (CP) approach. Simulation results show that CP can be a new promising direction for CS.
作者：
Jaulin, LucOSM
IHSEV LabSTICC 2 Rue Francois Verny F-29806 Brest France
This paper deals with the simultaneous localization and mapping problem (SLAM) for a robot. The robot has to build a map of its environment while localizing itself using a partially built map. It is assumed that (i) t...
详细信息
This paper deals with the simultaneous localization and mapping problem (SLAM) for a robot. The robot has to build a map of its environment while localizing itself using a partially built map. It is assumed that (i) the map is made of point landmarks, (ii) the landmarks are indistinguishable, (iii) the only exteroceptive measurements correspond to the distance between the robot and the landmarks. This paper shows that SLAM can be cast into a constraint network the variables of which being trajectories, digraphs and subsets of Then, we show how constraint propagation can be extended to deal with such generalized constraint networks. As a result, due to the redundancy of measurements of SLAM, we demonstrate that a constraint-based approach provides an efficient backtrack-free algorithm able to solve our SLAM problem in a guaranteed way.
Context: Testing highly-configurable software systems is challenging due to a large number of test configurations that have to be carefully selected in order to reduce the testing effort as much as possible, while mai...
详细信息
Context: Testing highly-configurable software systems is challenging due to a large number of test configurations that have to be carefully selected in order to reduce the testing effort as much as possible, while maintaining high software quality. Finding the smallest set of valid test configurations that ensure sufficient coverage of the system's feature interactions is thus the objective of validation engineers, especially when the execution of test configurations is costly or time-consuming. However, this problem is NP-hard in general and approximation algorithms have often been used to address it in practice. Objective: In this paper, we explore an alternative exact approach based on constraint programming that will allow engineers to increase the effectiveness of configuration testing while keeping the number of configurations as low as possible. Method: Our approach consists in using a (time-aware) minimization algorithm based on constraint programming. Given the amount of time, our solution generates a minimized set of valid test configurations that ensure coverage of all pairs of feature values (a.k.a. pairwise coverage). The approach has been implemented in a tool called PACOGEN. Results: PACOGEN was evaluated on 224 feature models in comparison with the two existing tools that are based on a greedy algorithm. For 79% of 224 feature models, PACOGEN generated up to 60% fewer test configurations than the competitor tools. We further evaluated PACOGEN in the case study of an industrial video conferencing product line with a feature model of 169 features, and found 60% fewer configurations compared with the manual approach followed by test engineers. The set of test configurations generated by PACOGEN decreased the time required by test engineers in manual test configuration by 85%, increasing the feature-pairs coverage at the same time. Conclusion: Our experimental evaluation concluded that optimal time-aware minimization of pairwise-covering test configurati
In this article, we present a wood procurement problem that arises in Eastern Canada. We solve a multi-period wood supply planning problem, while taking into account bucking decisions. Furthermore, we present a new fo...
详细信息
In this article, we present a wood procurement problem that arises in Eastern Canada. We solve a multi-period wood supply planning problem, while taking into account bucking decisions. Furthermore, we present a new form of flexibility which allows the harvesting capacity to change from one time period to another. We study the impact of such flexibility upon the harvesting cost. We assess the performance of the problem by comparing it with a variant where the harvesting capacity is fixed during sites' harvesting. To address this problem, we develop a hybrid approach based on both constraint and mathematical programming. In the first phase, we propose a constraint programming model dealing with forest sites harvesting and bucking problems. The result of this model is used as part of an initial solution for the whole problem formulated as a mixed integer model. We test the two versions of the problem on a set of different demand instances and we compare their results.
Bike sharing systems need to be properly rebalanced to meet the demand of users and to operate successfully. However, the problem of Balancing Bike Sharing Systems (BBSS) is a demanding task: it requires the design of...
详细信息
Bike sharing systems need to be properly rebalanced to meet the demand of users and to operate successfully. However, the problem of Balancing Bike Sharing Systems (BBSS) is a demanding task: it requires the design of optimal tours and operating instructions for relocating bikes among stations to maximally comply with the expected future bike demands. In this paper, we tackle the BBSS problem by means of constraint programming (CP). First, we introduce two different CP models for the BBSS problem including two custom branching strategies that focus on the most promising routes. Second, we incorporate both models in a Large Neighborhood Search (LNS) approach that is adapted to the respective CP model. Third, we perform an experimental evaluation of our approaches on three different benchmark sets of instances derived from real-world bike sharing systems. We show that our CP models can be easily adapted to the different benchmark problem setups, demonstrating the benefit of using constraint programming to address the BBSS problem. Furthermore, in our experimental evaluation, we see that the pure CP (branch & bound) approach outperforms the state-of-the-art MILP on large instances and that the LNS approach is competitive with other existing approaches.
We present an original approach to compute efficient mid-term fleet configurations, at the request of a Queensland-based long-haul trucking carrier. Our approach considers one year's worth of demand data, and empl...
详细信息
We present an original approach to compute efficient mid-term fleet configurations, at the request of a Queensland-based long-haul trucking carrier. Our approach considers one year's worth of demand data, and employs a constraint programming (CP) model and an adaptive large neighbourhood search (LNS) scheme to solve the underlying multi-day multi-commodity split delivery capacitated vehicle routing problem. Our solver is able to provide the decision maker with a set of Pareto-equivalent fleet setups trading off fleet efficiency against the likelihood of requiring on-hire vehicles and drivers. Moreover, the same solver can be used to solve the daily loading and routing problem. We carry out an extensive experimental analysis, comparing our approach with an equivalent mixed integer programming (MIP) formulation, and we show that our approach is a sound methodology to provide decision support for the mid- and short-term decisions of a long-haul carrier.
During the past decade, inland vessels have gained importance in container transport because of their reliability, low enviromnental impact, and major capacity for increased exploitation. Although inland vessels are c...
详细信息
During the past decade, inland vessels have gained importance in container transport because of their reliability, low enviromnental impact, and major capacity for increased exploitation. Although inland vessels are crucial in container transport between terminals in the port and the hinterland, in a large seaport like the one in Rotterdam, Netherlands, only 62% of the inland vessels leave the port on time. The other vessels have to stay in the port area for a longer time than planned. This situation leads to uncertainty in waiting times of vessels at terminals and low utilization of terminal quay resources. A two-phase approach is proposed that integrates mixed-integer programming (MIP) and constraint programming (CP) to solve the problem by generating optimal rotation plans for inland vessels. In the first phase, the single-vessel optimization problem is formulated on the basis of MIP and solved with state-of-the-art MIP solvers. In the second phase, the multiple-vessel coordination problem is formulated on the basis of CP, and a large neighborhood search based heuristic is proposed to solve the problem. Commercial CP solvers are also used for comparison. Simulation results show that the proposed large neighborhood search based heuristic outperforms the commercial CP solver with regard to both the solution quality and the computation time. Moreover, simulation results with respect to departure time of the last vessel, total sojourn time, and waiting time show significant improvement with earlier departure times and shorter sojourn times and waiting times.
This 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 te...
详细信息
This 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.
An edge-coloring of a graph G = (V, E) is a function c that assigns an integer c(e) (called color) in {0,1,2, ... } to every edge e e E so that adjacent edges are assigned different colors. An edge-coloring is compact...
详细信息
An edge-coloring of a graph G = (V, E) is a function c that assigns an integer c(e) (called color) in {0,1,2, ... } to every edge e e E so that adjacent edges are assigned different colors. An edge-coloring is compact if the colors of the edges incident to every vertex form a set of consecutive integers. The deficiency problem is to determine the minimum number of pendant edges that must be added to a graph such that the resulting graph admits a compact edge-coloring. We propose and analyze three integer programming models and one constraint programming model for the deficiency problem. (C) 2015 Elsevier Ltd. All rights reserved.
暂无评论