Loop scheduling and bank type assignment for heterogeneous multi-bank memory

Many high-performance DSP processors employ multi-bank on-chip memory to improve performance and energy consumption. This architectural feature supports higher memory bandwidth by allowing multiple data memory accesses to be executed in parallel. However, making effective use of multi-bank memory remains difficult, considering the combined effect of performance and energy requirement. This paper studies the scheduling and assignment problem about how to minimize the total energy consumption while satisfying the timing constraint with heterogeneous multi-bank memory for applications with loop. An algorithm, TASL (Type Assignment and Scheduling for Loops), is proposed. The algorithm uses bank type assignment with the consideration of variable partition to find the best configuration for both memory and ALU. The experimental results show that the average improvement on energy-saving is significant by using TASL.     

Explaining circuit propagation

The circuit constraint is used to constrain a graph represented by a successor for each node, such that the resulting edges form a circuit. Circuit and its variants are important for various kinds of tour-finding, path-finding and graph problems. In this paper we examine how to integrate the circuit constraint, and its variants, into a lazy clause generation solver. To do so we must extend the constraint to explain its propagation. We consider various propagation algorithms for circuit and examine how best to explain each of them. We compare the effectiveness of each propagation algorithm once we use explanation, since adding explanation changes the trade-off between propagation complexity and power. Simpler propagators, although less powerful, may produce more reusable explanations. Even though the most powerful propagator considered for circuit and variants creates huge explanations, we find that explanation is highly advantageous for solving problems involving this kind of constraint.     

Experimental Analysis of Numeric and Symbolic Constraint Satisfaction Techniques for Temporal Reasoning

Many temporal applications like planning and scheduling can be viewed as special cases of the numeric and symbolic temporal constraint satisfaction problem. Thus we have developed a temporal model, TemPro, based on the interval Algebra, to express such applications in term of qualitative and quantitative temporal constraints. TemPro extends the interval algebra relations of Allen to handle numeric information. To solve a constraint satisfaction problem, different approaches have been developed. These approaches generally use constraint propagation to simplify the original problem and backtracking to directly search for possible solutions. The constraint propagation can also be used during the backtracking to improve the performance of the search. The objective of this paper is to assess different policies for finding if a TemPro network is consistent. The main question we want to answer here is how much constraint propagation is useful for finding a single solution for a TemPro constraint graph. For this purpose, we have experimented by randomly generating large consistent networks for which either arc and/or path consistency algorithms (AC-3, AC-7 and PC-2) were applied. The main result of this study is an optimal policy combining these algorithms either at the symbolic (Allen relation propagation) or at the numerical level.     

Searching for optimal integer solutions to set partitioning problems using column generation

In this paper, we describe a new approach to increase the possibility of finding integer feasible columns to a set partitioning problem (SPP) directly in solving the linear programming (LP) relaxation using column generation. Traditionally, column generation is aimed to solve the LP‐relaxation as quickly as possible without any concern for the integer properties of the columns formed. In our approach, we aim to generate columns forming an optimal integer solution while simultaneously solving the LP‐relaxation. Using this approach, we can improve the possibility of finding integer solutions by heuristics at each node in the branch‐and‐bound search. In addition, we improve the possibility of finding high‐quality integer solutions in cases where only the columns in the root node are used to solve the problem. The basis of our approach is a subgradient technique applied to a Lagrangian dual formulation of the SPP extended with an additional surrogate constraint. This extra constraint is not relaxed and is used to better control the subgradient evaluations and how the multiplier values are computed. The column generation is then directed, via the multipliers, to construct columns that form feasible integer solutions. Computational experiments show that we can generate optimal integer columns in a large set of well‐known test problems as compared to both standard and stabilized column generation, and simultaneously keep the number of columns smaller than standard column generation. This is also supported by tests on a case study with work‐shift generation.     

基于等价类划分的配置求解与解释计算

基于约束的配置模型中会有一些变量之间不存在任何直接或间接的约束关系,这样的变量之间进行约束传播不会互相影响取值.基于配置问题的这一特点,提出了一种等价类划分的思想,用于构造产品模型时的预处理技术,可以有效地将原问题划分为若干子问题,证明了这些子问题可以分别处理.分别采用两种回溯策略对求解效率进行了测试,结果表明能够有效地提高求解效率.最后,等价类划分方法与计算解释的QUICKXPLAIN算法集成计算冲突解释,测试结果表明,经过等价类划分后,同样可以有效地提高计算解释的效率.     

Scene understanding by rule evaluation

We consider how machine learning can be used to help solve the problem of identifying objects or structures composed of parts in complex scenes. We first discuss a conditional rule generation technique that is designed to describe structures using part attributes and their relations. We then show how the resultant rules can be used for region labeling and examine constraint propagation techniques for improving rule-based object classification     

Improving constrained clustering with active query selection

In this article, we address the problem of automatic constraint selection to improve the performance of constraint-based clustering algorithms. To this aim we propose a novel active learning algorithm that relies on a k-nearest neighbors graph and a new constraint utility function to generate queries to the human expert. This mechanism is paired with propagation and refinement processes that limit the number of constraint candidates and introduce a minimal diversity in the proposed constraints. Existing constraint selection heuristics are based on a random selection or on a min–max criterion and thus are either inefficient or more adapted to spherical clusters. Contrary to these approaches, our method is designed to be beneficial for all constraint-based clustering algorithms. Comparative experiments conducted on real datasets and with two distinct representative constraint-based clustering algorithms show that our approach significantly improves clustering quality while minimizing the number of human expert solicitations.     

Towards Fast Vickrey Pricing using Constraint Programming

Ensuring truthfulness amongst self-interested agents bidding against one another in an auction can be computationally expensive when prices are determined using the Vickrey–Clarke–Groves (VCG) mechanism. This mechanism guarantees that each agent's dominant strategy is to tell the truth, but it requires solving n+ 1 optimization problems when the overall optimal solution involves n agents. This paper first examines a case-study example demonstrating how Operations Research techniques can be used to compute Vickrey prices efficiently. In particular, the case-study focuses on the Assignment Problem. We show how, in this case, Vickrey prices can be computed in the same asymptotic time complexity as that of the original optimization problem. This case-study can be seen as serving a pedagogical role in the paper illustrating how Operations Research techniques can be used for fast Vickrey pricing. We then propose a Constraint Programming approach that can be used in a more general context, where nothing is assumed about the nature of the constraints that must be satisfied or the structure of the underlying problem. In particular, we demonstrate how nogood learning can be used to improve the efficiency of constraint-based Vickrey pricing in combinatorial auctions.     

Interchangeability with thresholds and degradation factors for Soft CSPs

Substitutability and interchangeability in constraint satisfaction problems (CSPs) have been used as a basis for search heuristics, solution adaptation and abstraction techniques. In this paper, we consider how the same concepts can be extended to soft constraint satisfaction problems (SCSPs). We introduce two notions: threshold α and degradation factor δ for substitutability and interchangeability, ( _α substitutability/interchangeability and ^δ substitutability/interchangeabi-lity respectively). We show that they satisfy analogous theorems to the ones already known for hard constraints. In _α interchangeability, values are interchangeable in any solution that is better than a threshold α, thus allowing to disregard differences among solutions that are not sufficiently good anyway. In ^δ interchangeability, values are interchangeable if their exchange could not degrade the solution by more than a factor of δ. We give efficient algorithms to compute ( ^δ / _α )interchangeable sets of values for a large class of SCSPs, and show an example of their application. Through experimental evaluation based on random generated problem we measure first, how often neighborhood interchangeable values are occurring, second, how well they can approximate fully interchangeable ones, and third, how efficient they are when used as preprocessing techniques for branch and bound search.     

The effect of mid-term estimation on back propagation for time series prediction

This research proposes estimation of mid-terms in a time series for improving the prediction performance of back propagation. In this research, the process of estimating mid-terms is called VTG (virtual term generation) and schemes for doing that are called VTG schemes. This research proposes three VTG schemes: mean method, 2nd Lagrange method, and 1st Taylor method. We adopt only back propagation as prediction model, since the goal of this research is to improve its prediction performance and back propagation is used most popular for regression among supervised neural networks. By implementing the VTG schemes as preprocessing of time series prediction, it will be observed that the prediction performance of back propagation is improved through experiments of Sect. 5.     

Explaining the <Literal>cumulative</Literal> propagator

The global cumulative constraint was proposed for modelling cumulative resources in scheduling problems for finite domain (FD) propagation. Since that time a great deal of research has investigated new stronger and faster filtering techniques for cumulative, but still most of these techniques only pay off in limited cases or are not scalable. Recently, the “lazy clause generation” hybrid solving approach has been devised which allows a finite domain propagation engine possible to take advantage of advanced SAT technology, by “lazily” creating a SAT model of an FD problem as computation progresses. This allows the solver to make use of SAT explanation and autonomous search capabilities. In this article we show how, once we use lazy clause generation, modelling the cumulative constraint by decomposition creates a highly competitive version of cumulative. Using decomposition into component parts automatically makes the propagator incremental and able to explain itself. We then show how, using the insights from the behaviour of the decomposition, we can create global cumulative constraints that explain their propagation. We compare these approaches to explaining the cumulative constraint on resource constrained project scheduling problems. All our methods are able to close a substantial number of open problems from the well-established PSPlib benchmark library of resource-constrained project scheduling problems.     

Solving Various Weighted Matching Problems with Constraints

This paper studies the resolution of (augmented) weighted matching problems within a constraint programming (CP) framework. The first contribution of the paper is a set of techniques that improves substantially the performance of branch-and-bound algorithms based on constraint propagation and the second contribution is the introduction of weighted matching as a global constraint ( WeightedMatching), that can be propagated using specialized incremental algorithms from Operations Research. We first compare programming techniques that use constraint propagation with specialized algorithms from Operations Research, such as the Busaker and Gowen flow algorithm or the Hungarian method. Although CP is shown not to be competitive with specialized polynomial algorithms for pure matching problems, the situation is different as soon as the problems are modified with additional constraints. Using the previously mentioned set of techniques, a simpler branch-and-bound algorithm based on constraint propagation can outperform a complex specialized algorithm. These techniques have been applied with success to the Traveling Salesman Problems [5], which can be seen as an augmented matching problem. We also show that an incremental version of the Hungarian method can be used to propagate a WeightedMatching constraint. This is an extension to the weighted case of the work of Régin [19], which we show to bring significant improvements on a timetabling example.     

A Decomposition Scheme for System Optimal Dynamic Traffic Assignment Models

In this paper, a Dantzig-Wolfe decomposition based solution algorithm is developed for the linear programming formulation introduced by Ziliaskopoulos (2000) for System Optimal Dynamic Traffic Assignment problem. The algorithm takes advantage of the network structure in the constraint set of the formulation: the sub-problem is formulated as a minimum-cost-flow problem and the master as a simpler linear programming problem, which allows DTA to be solved more efficiently on meaningful networks. The algorithm is tested on an example network and its performance is analyzed.     

Exhaustive and Efficient Constraint Propagation: A Graph-Based Learning Approach and Its Applications

This paper presents a novel pairwise constraint propagation approach by decomposing the challenging constraint propagation problem into a set of independent semi-supervised classification subproblems which can be solved in quadratic time using label propagation based on $k$ -nearest neighbor graphs. Considering that this time cost is proportional to the number of all possible pairwise constraints, our approach actually provides an efficient solution for exhaustively propagating pairwise constraints throughout the entire dataset. The resulting exhaustive set of propagated pairwise constraints are further used to adjust the similarity matrix for constrained spectral clustering. Other than the traditional constraint propagation on single-source data, our approach is also extended to more challenging constraint propagation on multi-source data where each pairwise constraint is defined over a pair of data points from different sources. This multi-source constraint propagation has an important application to cross-modal multimedia retrieval. Extensive results have shown the superior performance of our approach.     

Increasing Constraint Propagation by Redundant Modeling: an Experience Report

This paper describes our experience with a simple modeling and programming approach for increasing the amount of constraint propagation in the constraint solving process. The idea, although similar to redundant constraints, is based on the concept of redundant modeling. We introduce the notions of CSP model and model redundancy, and show how mutually redundant models can be combined and connected using channeling constraints. The combined model contains the mutually redundant models as sub-models. Channeling constraints allow the sub-models to cooperate during constraint solving by propagating constraints freely amongst the sub-models. This extra level of pruning and propagation activities becomes the source of execution speedup. real-life nurse rostering system. We perform two case studies to evaluate the effectiveness and efficiency of our method. The first case study is based on the simple and well-known n-queens problem, while the second case study applies our method in the design and construction of a real-life nurse rostering system. Experimental results provide empirical evidence in line with our prediction.     

基于改进成对约束扩充的标签传播聚类算法

针对半监督聚类算法性能受到成对约束数量多寡的限制问题,现有的研究大都依赖于原始成对约束的数量。因此,首先提出了基于灰关联分析的成对约束初始化算法（initialization algorithm of pair constraints based on grey relational analysis,PCIG）。该算法通过均衡接近度计算数据对象间的相似度,并根据相似度的取值来确定可信区间,然后借鉴网络结构初始化方法来扩充数据对象间的成对关系。最后,将其应用于标签传播聚类算法。通过在五个基准数据集上进行实验,基于改进成对约束扩充的标签传播聚类算法与其他方法相比NMI值和ARI值有所提升。实验结果证明了改进成对约束扩充可以有效改善标签传播算法的聚类效果。     

Improving Linear Constraint Propagation by Changing Constraint Representation

Propagation based finite domain solvers provide a general mechanism for solving combinatorial problems. Different propagation methods can be used in conjunction by communicating through the domains of shared variables. The flexibility that this entails has been an important factor in the success of propagation based solving for solving hard combinatorial problems. In this paper we investigate how linear integer constraints should be represented in order that propagation can determine strong domain information. We identify two kinds of substitution which can improve propagation solvers, and can never weaken the domain information. This leads us to an alternate approach to propagation based solving where the form of constraints is modified by substitution as computation progresses. We compare and contrast a solver using substitution against an indexical based solver, the current method of choice for implementing propagation based constraint solvers, identifying the relative advantages and disadvantages of the two approaches. In doing so, we investigate a number of choices in propagation solvers and their effects on a suite of benchmarks.     

Guided design search in the interval-bounded sailor assignment problem

The problem of assigning Navy personnel to jobs is primarily a manual process performed by enlisted detailers, with decision support from the Enlisted Assignment Information System. In this paper, we offer an expanded interval bounded network flow model of the sailor assignment process creating teams of skilled sailors to be assigned to ships. A new integer preprocessing and solution technique, Guided Design Search (GDS), is integrated into the CPLEX solver with promising results for these difficult problems. Computational results show GDS/CPLEX speed improvements of 10-fold to optimality and for larger problems found feasible assignments when CPLEX alone could not. We show how GDS results can be used by detailers to gauge the effectiveness of alternative sailor assignments and also how it can be used to validate the objective function coefficients of the decision variables.     

最大受限路径相容约束传播算法的研究进展

约束传播技术对于约束满足问题的求解性能至关重要。约束传播技术在一个预处理过程中能彻底地移除一些局部不相容值,或者在搜索期间高效地剪枝搜索树。最大受限路径相容算法(max Restricted Path Consistency,maxRPC)是最近提出的一种强相容性约束传播算法,它能够删除更多不相容值,在解决复杂问题中取得了很好的效果。文中对弧相容算法AC和最大受限路径相容算法maxRPC的相关算法AC3,AC3rm,maxRPC1,maxRPC2,maxRPCrm,maxRPC3等及其相关变体分别进行介绍和比较。在Mistral求解器上的实验测试结果验证了各种算法的性能。     

An Efficient Bounds Consistency Algorithm for the Global Cardinality Constraint

Previous studies have demonstrated that designing special purpose constraint propagators can significantly improve the efficiency of a constraint programming approach. In this paper we present an efficient algorithm for bounds consistency propagation of the generalized cardinality constraint (gcc). Using a variety of benchmark and random problems, we show that on some problems our bounds consistency algorithm can dramatically outperform existing state-of-the-art commercial implementations of constraint propagators for the gcc. We also present a new algorithm for domain consistency propagation of the gcc which improves on the worst-case performance of the best previous algorithm for problems that occur often in applications.