In this article, we present a constraint programming approach for solving hard design problems present when automatically designing specialized processor extensions. Specifically, we discuss our approach for automatic...
详细信息
In this article, we present a constraint programming approach for solving hard design problems present when automatically designing specialized processor extensions. Specifically, we discuss our approach for automatic selection and synthesis of processor extensions as well as efficient application compilation for these newly generated extensions. The discussed approach is implemented in our integrated design framework, IFPEC, built using constraint programming (CP). In our framework, custom instructions, implemented as processor extensions, are defined as computational patterns and represented as graphs. This, along with the graph representation of an application, provides a way to use our CP framework equipped with subgraph isomorphism and connected component constraints for identification of processor extensions as well as their selection, application scheduling, binding, and routing. All design steps assume architectures composed of runtime reconfigurable cells, implementing selected extensions, tightly connected to a processor. An advantage of our approach is the possibility of combining different heterogeneous constraints to represent and solve all our design problems. Moreover, the flexibility and expressiveness of the CP framework makes it possible to solve simultaneously extension selection, application scheduling, and binding and improve the quality of the generated results. The article is largely illustrated with experimental results.
The design and operation of synthetic aperture radars require compatible sets of hundreds of quantities. Compatibility is achieved when these quantities satisfy constraints arising from physics, geometry etc. In the a...
详细信息
ISBN:
(纸本)9781467315760;9781467315777
The design and operation of synthetic aperture radars require compatible sets of hundreds of quantities. Compatibility is achieved when these quantities satisfy constraints arising from physics, geometry etc. In the aggregate these quantities and constraints form a logical model of the radar. In practice the logical model is distributed over multiple people, documents and software modules thereby becoming fragmented. Fragmentation gives rise to inconsistencies and errors. The SAR Inference Engine addresses the fragmentation problem by implementing the logical model of a Sandia synthetic aperture radar in a form that is intended to be usable from system design to mission planning to actual operation of the radar. These diverse contexts require extreme flexibility that is achieved by employing the constraint programming paradigm.
The use of techniques and system of constraint programming enables the implementation of precise, flexible, efficient, and extensible scheduling systems. It has been identified as a strategic direction and dominant fo...
详细信息
The use of techniques and system of constraint programming enables the implementation of precise, flexible, efficient, and extensible scheduling systems. It has been identified as a strategic direction and dominant form for the application into planning and scheduling of industrial production. This paper systematically introduces the constraint modeling and solving technology for production scheduling problems, including various real-world industrial applications based on the Chip system of Cosytec Company. We trend of some concrete technology, such as modeling, search, constraint propagation, consistency, and optimization of constraint programming for scheduling problems. As a result of the application analysis, a generic application framework for real-life scheduling based on commercial constraint propagation (CP) systems is proposed.
This paper presents constraint programming-based solution approaches for the three-dimensional loading capacitated vehicle routing problem (3l-CVRP) that consists of vehicle routing and three-dimensional loading probl...
详细信息
This paper presents constraint programming-based solution approaches for the three-dimensional loading capacitated vehicle routing problem (3l-CVRP) that consists of vehicle routing and three-dimensional loading problems in distribution logistics. Despite the practical benefits in the logistics world, the 3l-CVRP has not been extensively studied in the literature for its high combinatorial complexity. Therefore, we developed integrated and decomposed constraint programming-based solution methods in this study. The decomposed models outperformed the mixed-integer programming model proposed earlier in the literature for small-size problems. Furthermore, we solved the well-known benchmark problems with a decomposed model using constraint programming for the vehicle routing part of the problem and an evolutionary algorithm for the loading part. The computational study results show that the best-known results are improved in 36 of 93 problems.
constraint programming is well suited for the computational modeling of music theories and composition: its declarative and modular approach shares similarities with the way music theory is traditionally expressed, na...
详细信息
constraint programming is well suited for the computational modeling of music theories and composition: its declarative and modular approach shares similarities with the way music theory is traditionally expressed, namely by a set of rules which describe the intended result. Various music theory disciplines have been modeled, including counterpoint, harmony, rhythm, form, and instrumentation. Because modeling music theories "from scratch" is a complex task, generic music constraint programming systems have been proposed that predefine the required building blocks for modeling a range of music theories. After introducing the field and its problems in general, this survey compares these generic systems according to a number of criteria such as the range of music theories these systems support.
In this paper we propose a general integration scheme for a Multi-Criteria Decision Making model of the Multi-Attribute Utility Theory in constraint programming. We introduce the Choquet integral as a general aggregat...
详细信息
In this paper we propose a general integration scheme for a Multi-Criteria Decision Making model of the Multi-Attribute Utility Theory in constraint programming. We introduce the Choquet integral as a general aggregation function for multi-criteria optimization problems and define the Choquet global constraint that propagates this function during the Branch-and-Bound search. Finally the benefits of the propagation of the Emphasis Choquet constraint are evaluated on the examination timetabling problem.
Today many companies face the challenge of matching highly-skilled professionals to high-end positions in large organizations and human deployment agencies. Unlike traditional Workforce Management problems such as shi...
详细信息
ISBN:
(纸本)9781424411177
Today many companies face the challenge of matching highly-skilled professionals to high-end positions in large organizations and human deployment agencies. Unlike traditional Workforce Management problems such as shift scheduling, highly-skilled employees are professionally distinguishable from each other and hence non-interchangeable. Our work specifically focuses on the services industry, where much of the revenue comes from the assignment of highly professional workers. Here, non-accurate matches may result in significant monetary losses and other negative effects. We deal with very large pools of both positions and employees, where optimal decisions should be made rapidly in a dynamic environment. Since traditional Operations Research (OR) methods fail to answer this problem, we employ constraint programming (CP), a subfield of Artificial Intelligence with strong algorithmic foundations. Our CP model builds on new constraint propagators designed for this problem (but applicable elsewhere), as well as on information retrieval methods used for analyzing the complex text describing high-end professionals and positions. Optimatch, which is based on this technology and is being used by IBM services organizations, provides strong experimental results.
Alternative splicing is a key process in post-transcriptional regulation, by which different mature RNA can be obtained from the same premessenger RNA. The resulting combinatorial complexity contributes to biological ...
详细信息
Alternative splicing is a key process in post-transcriptional regulation, by which different mature RNA can be obtained from the same premessenger RNA. The resulting combinatorial complexity contributes to biological diversity, especially in the case of the human immunodeficiency virus HIV-1. Using a constraint programming approach, we develop a model of the alternative splicing regulation in HIV-1. Our model integrates different scales (single site vs. multiple sites), and thus allows us to exploit several types of experimental data available to us. (C) 2004 Elsevier B.V. All rights reserved.
Logistic planning and programming of construction machinery involves complex sets of objectives and constraints;therefore traditional approaches typically result in a large monolithic model that is difficult to solve,...
详细信息
ISBN:
(纸本)1424403170
Logistic planning and programming of construction machinery involves complex sets of objectives and constraints;therefore traditional approaches typically result in a large monolithic model that is difficult to solve, understand, and maintain. In order, to tackle large, particularly combinatorial, problems in logistic support for construction machinery, we design a constraint programming system, namely DISPDESK, which comprises a specification generator and its underlying domain-specific architecture, an algorithm library and its selector, a pre-defined solution library and a problem solver. The system features separation of concerns in specifications, little requirements for programming skills, domain-specific optimization, and semi-automatic generation of high-performance and reliable problem solvers.
With increasing implementation of off-site prefabrication and modular construction technologies, the complexity of material supply chain management on construction projects has grown substantially. However, research o...
详细信息
With increasing implementation of off-site prefabrication and modular construction technologies, the complexity of material supply chain management on construction projects has grown substantially. However, research on construction scheduling has yet to take dynamic material logistics as an explicit constraint in analytically deriving construction schedules and addressing impacts of uncertainties in material supply on project budget. This study proposes a two-step analytical approach to tackle the identified problem. First, a constraint programming-based scheduling optimization model is developed to derive project schedules subject to variable material delivery times and finite crew resource availability. The second step is to take advantage of the valid optimization model for evaluating the impact of different input settings of material logistics on project budget. An example project adapted from the literature is used to illustrate the effectiveness of the proposed optimization model in coping with variable material delivery times. Based on the same case, the delivery date of a particular material is singled out as the risk factor of interest in order to derive the complex relationship between material delivery date and total project cost. In addition, a case study based on a bridge girder fabrication project is presented to demonstrate the applicability of the proposed optimization model on projects of practical size. In conclusion, this study adds to the body of knowledge by developing an analytical methodology that factors material supply constraints into the resource-constrained scheduling optimization model so as to analyze the impact of uncertainties in material deliveries on project budget.
暂无评论