Modern computer architectures have complex features that Can only be fully taken advantage of if tire compiler schedules the compiled code. A standard region of code for scheduling in an optimizing compiler is called ...
详细信息
ISBN:
(纸本)9783540859574
Modern computer architectures have complex features that Can only be fully taken advantage of if tire compiler schedules the compiled code. A standard region of code for scheduling in an optimizing compiler is called a superblock. Scheduling superblocks optimally is known to be NP-complete, and production compilers rise non-optimal heuristic algorithms. In this paper;we present ill application of constraintprogramming to the superblock instruction scheduling problem. the resulting system is both optimal and fast enough to be incorporated into production compilers, awl is the first optimal superblock scheduler for realistic architectures. In developing our optimal scheduler, tire keys to scaling up to large;real problems were ill applying and adapting several techniques from the literature including: implied gild dominance constraints, impact-based variable ordering heuristics, singleton bounds consistency, portfolios;and structure-based decomposition techniques. We experimentally evaluated our optimal scheduler oil the SPEC 2000 benchmarks, a standard benchmark suite. Depending oil the architectural model, between 98.29% to 99.98% of all superblocks were solved to optimality. the scheduler was able to routinely solve tire largest superblocks, including superblocks with up to 2,600 instructions, and gave noteworthy improvements over previous heuristic approaches.
constraints have played a central role in cp because they capture key substructures of a problem and efficiently exploit them to boost inference. this paper intends to do the same thing for search, proposing constrain...
详细信息
ISBN:
(纸本)3540749691
constraints have played a central role in cp because they capture key substructures of a problem and efficiently exploit them to boost inference. this paper intends to do the same thing for search, proposing constraint-centered heuristics which guide the exploration of the search space toward areas that are likely to contain a high number of solutions. We first propose new search heuristics based on solution counting information at the level of individual constraints. We then describe efficient algorithms to evaluate the number of solutions of two important families of constraints: occurrence counting constraints, such as all different, and sequencing constraints, such as regular. In both cases we take advantage of existing filtering algorithms to speed up the evaluation. Experimental results on benchmark problems show the effectiveness of our approach.
We propose joinwidth, a new complexity parameter for the constraint Satisfaction Problem (CSP). the definition of joinwidth is based on the arrangement of basic operations on relations (joins, projections, and pruning...
详细信息
ISBN:
(纸本)9783030300487
We propose joinwidth, a new complexity parameter for the constraint Satisfaction Problem (CSP). the definition of joinwidth is based on the arrangement of basic operations on relations (joins, projections, and pruning), which inherently reflects the steps required to solve the instance. We use joinwidth to obtain polynomial-time algorithms (if a corresponding decomposition is provided in the input) as well as fixed-parameter algorithms (if no such decomposition is provided) for solving the CSP. Joinwidth is a hybrid parameter, as it takes boththe graphical structure as well as the constraint relations that appear in the instance into account. It has, therefore, the potential to capture larger classes of tractable instances than purely structural parameters like hypertree width and the more general fractional hypertree width (fhtw). Indeed, we show that any class of instances of bounded fhtw also has bounded joinwidth, and that there exist classes of instances of bounded joinwidth and unbounded fhtw, so bounded joinwidth properly generalizes bounded fhtw. We further show that bounded joinwidth also properly generalizes several other known hybrid restrictions, such as fhtw with degree constraints and functional dependencies. In this sense, bounded joinwidth can be seen as a unifying principle that explains the tractability of several seemingly unrelated classes of CSP instances.
this paper studies how to generalize Lagrangian relaxation to high-level optimization models, including constraint-programming and local search models. It exploits the concepts of constraint violation (typically used ...
详细信息
constraint propagation [10,7,5] (cp) is a cornerstone algorithm of constraintprogramming, mainly devoted to the computation of local consistency properties of constraint satisfaction problems. the abstract formulatio...
ISBN:
(纸本)3540410538
constraint propagation [10,7,5] (cp) is a cornerstone algorithm of constraintprogramming, mainly devoted to the computation of local consistency properties of constraint satisfaction problems. the abstract formulation of cp is the combination of a set of reduction functions (black-box solvers) on a domain [8,9,2,1]. Intuitively, there is a dependence relation between functions and domains, such that a function must be applied if a domain it depends on is reduced. the essential property of cp is confluence or strategy-independence. In other words, the order solvers are applied does not influence the output characterized in terms of a common fixed-point of the solvers. Owing to this remark, several strategies based on heuristics, data structures, or knowledge of the solvers have been implemented.
constraint problems with incomplete or erroneous data are often simplified to tractable deterministic models, or modified using error correction methods, withthe aim of seeking a solution. However, this can lead us t...
详细信息
ISBN:
(纸本)3540202021
constraint problems with incomplete or erroneous data are often simplified to tractable deterministic models, or modified using error correction methods, withthe aim of seeking a solution. However, this can lead us to solve the wrong problem because of the approximations made. Such an outcome is of little help to a user who expects the right problem to be tackled and reliable information returned. the certainty closure framework we present aims to provide the user with reliable insight by: (1) enclosing the uncertainty using what is known for sure about the data, to guarantee that the true problem is contained in the model so described, (2) deriving a closure, a set of possible solutions to the uncertain constraint problem. In this paper we first demonstrate the benefits of reliable constraint reasoning on two different case studies, and then generalise our approaches into a formal framework.
the VALUED constraint SATISFACTION PROBLEM (VCSP) is a general framework encompassing many optimisation problems. We discuss precisely what;it means for a, problem to be modelled in the VCSP framework. Using our analy...
详细信息
ISBN:
(纸本)9783642042430
the VALUED constraint SATISFACTION PROBLEM (VCSP) is a general framework encompassing many optimisation problems. We discuss precisely what;it means for a, problem to be modelled in the VCSP framework. Using our analysis, we show that some optimisation problems, such as (s,t)-MIN-CUT and SUBMODULAR FUNCTION MINIMISATION, can be modelled using a restricted Set Of valued constraints which axe tractable to solve regard less of how they are combined. Hence, these problems can be viewed as special cases of more general problems which include all possible instances rising the same forms., of valued constraint. However, other, apparently similar, problems such as MINCUT and SYMMETRIC SUBMODULAR FUNCTION MINIMISATION, which also have polynomial-time algorithms, can only be naturally modelled in the VCSP framework by using valued constraints which can represent NP-complete problems. this suggests that the reason for tractability ill these problems is more subtle: it relies not;Only Oil the form of the valued constraints, but;also on the precise structure of the problem. Furthermore, our results suggest that allowing constant constraints can significantly alter the complexity of problems in the VScp framework, in contrast, to the CSP framework.
this book constitutes the thoroughly refereed post-conference proceedings of the 18thinternationalconference on principles and practice of constraintprogramming (cp 2012), held in Québec, Canada, in October 20...
详细信息
ISBN:
(数字)9783642335587
ISBN:
(纸本)9783642335570
this book constitutes the thoroughly refereed post-conference proceedings of the 18thinternationalconference on principles and practice of constraintprogramming (cp 2012), held in Québec, Canada, in October 2012.
the 68 revised full papers were carefully selected from 186 submissions. Beside the technical program, the conference featured two special tracks. the former was the traditional application track, which focused on industrial and academic uses of constraint technology and its comparison and integration with other optimization techniques (MIP, local search, SAT, etc.) the second track, featured for the first time in 2012, concentrated on multidisciplinary papers: cross-cutting methodology and challenging applications collecting papers that link cp technology with other techniques like machine learning, data mining, game theory, simulation, knowledge compilation, visualization, control theory, and robotics. In addition, the track focused on challenging application fields with a high social impact such as cp for life sciences, sustainability, energy efficiency, web, social sciences, finance, and verification.
We study decompositions of the global NVALUE constraint. Our main contribution is theoretical: we show that there are propagators for global constraints like NVALUE which decomposition can simulate withthe same time ...
详细信息
ISBN:
(纸本)9783642153952
We study decompositions of the global NVALUE constraint. Our main contribution is theoretical: we show that there are propagators for global constraints like NVALUE which decomposition can simulate withthe same time complexity but with a much greater space complexity. this suggests that the benefit of a global propagator may often not be in saving time but in saving space. Our other theoretical contribution is to show for the first time that range consistency can be enforced on NVALUE withthe same worst-case time complexity as bound consistency. Finally, the decompositions we study are readily encoded as linear inequalities. We are therefore able to use them in integer linear programs.
EnergeTIC is a recent industrial research project carried out in Grenoble on optimizing energy consumption in data-centres. the efficient management of a data-centre involves minimizing energy costs while ensuring ser...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
EnergeTIC is a recent industrial research project carried out in Grenoble on optimizing energy consumption in data-centres. the efficient management of a data-centre involves minimizing energy costs while ensuring service quality. We study the problem formulation proposed by EnergeTIC. First, we focus on a key sub-problem: a bin packing problem with linear costs associated withthe use of bins. We study lower bounds based on Linear programming and extend the bin packing global constraint with cost information. Second, we present a column generation model for computing the lower bound on the original energy management problem where the pricing problem is essentially a cost-aware bin packing with side constraints. third, we show that the industrial benchmark provided so far can be solved to near optimality using a large neighborhood search.
暂无评论