A variety of algorithms and technologies exist to cope with design space exploration for software distribution in terms of real-time, embedded, multiprocessor, and mixed-critical systems. The automotive domain not onl...
详细信息
ISBN:
(纸本)9783030302757;9783030302740
A variety of algorithms and technologies exist to cope with design space exploration for software distribution in terms of real-time, embedded, multiprocessor, and mixed-critical systems. The automotive domain not only combines those domains but even introduces further constraints and requirements due to several design decisions, standards, or evolved methodologies. In addition, solutions are predominantly proprietary, often lack in perspicuity, and sophisticated approaches towards the comprehensive concern of constraints are rather rare. This paper presents typical constraints along with distributing automotive applications across the processing units of vehicles, outlines three software distribution methodologies based on the constraint programming paradigm, and evaluates those in comparison to related design space exploration approaches. Benchmarks upon hypothetical and industrial models show that the constraint-based approaches outperform other forms in many cases regarding quality and effectiveness. Additionally, the presented approach benefits from a holistic consideration of constraints such as processing unit affinities, safety level aggregations, communication costs as well as processing unit utilization optimization among others whilst being applicable to heterogeneous, networked, hierarchical, embedded, multi and many core architectures.
The job shop scheduling problem (JSSP) is an abstraction of industrial scheduling and has been studied since the dawn of the computer era. Its combinatorial nature makes it easily expressible as a constraint satisfact...
详细信息
ISBN:
(纸本)9783030300487
The job shop scheduling problem (JSSP) is an abstraction of industrial scheduling and has been studied since the dawn of the computer era. Its combinatorial nature makes it easily expressible as a constraint satisfaction problem. Nevertheless, in the last decade, there has been a hiatus in the research on this topic from the constraint community;even when this problem is addressed, the target instances are from benchmarks that are more than 20 years old. And yet, constraint solvers have continued to evolve and the standards of today's industry have drastically changed. Our aim is to close this research gap by testing the capabilities of the best available CP solvers on the JSSP. We target not only the classic benchmarks from the literature but also a new benchmark of large-scale instances reflecting nowadays industrial scenarios. Furthermore, we analyze different encodings of the JSSP to measure the impact of high-level structures (such as interval variables and no-overlap constraints) on the problem solution. The solvers considered are OR-Tools, Google's open-source solver and winner of the last MiniZinc Challenge, and IBM's CP Optimizer, a proprietary solver targeted towards industrial scheduling problems.
Many of the famous single-player games, commonly called puzzles, can be shown to be NP-Complete. Indeed, this class of complexity contains hundreds of puzzles, since people particularly appreciate completing an intrac...
详细信息
ISBN:
(纸本)9781728118840
Many of the famous single-player games, commonly called puzzles, can be shown to be NP-Complete. Indeed, this class of complexity contains hundreds of puzzles, since people particularly appreciate completing an intractable puzzle, such as Sudoku, but also enjoy the ability to check their solution easily once it's done. For this reason, using constraint programming is naturally suited to solve them. In this paper, we focus on logic puzzles described in the Ludii general game system and we propose using the XCSP formalism in order to solve them with any CSP solver.
constraint programming initially aims to be a declarative paradigm, but its quest for efficiency is mainly achieved through the development of ad-hoc algorithms, which are encapsulated in global constraints. In this p...
详细信息
ISBN:
(纸本)9781728137988
constraint programming initially aims to be a declarative paradigm, but its quest for efficiency is mainly achieved through the development of ad-hoc algorithms, which are encapsulated in global constraints. In this paper, we explore the idea of extending constraint programming with abstract domains, a structure from program analysis by abstract interpretation. Abstract domains allow us to efficiently process constraints of the same form, such as linear constraints or difference constraints. This classification by constraint sub-languages instead of sub-problems, makes abstract domains more general and more reusable in many problems. We contribute to the definition of an abstract domain encapsulating a constraint solver in a conservative way w.r.t. constraint programming. We also define a product of abstract domains based on reified constraints and under-approximations. We study a well-known scheduling problem to motivate our approach and experiment its feasibility.
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.
This paper addresses a new problem of redirecting freight trains to revised destinations as a last-minute risk mitigation strategy. The problem is approached from a consignee’s perspective as the demand for a change ...
详细信息
This paper addresses a new problem of redirecting freight trains to revised destinations as a last-minute risk mitigation strategy. The problem is approached from a consignee’s perspective as the demand for a change of destination is made by the consignee. A constraint programming (CP) model is formulated to minimize the cost of redirecting trains subject to various constraints. The case of a government organization in India which is involved in food grain distribution is considered. The model is solved using an open source CP solver and is found to be highly efficient in terms of computation time.
This paper considers the scheduling of job families on parallel machines with time constraints on machine qualifications. In this problem, each job belongs to a family and a family can only be executed on a subset of ...
详细信息
ISBN:
(纸本)9783030192129;9783030192112
This paper considers the scheduling of job families on parallel machines with time constraints on machine qualifications. In this problem, each job belongs to a family and a family can only be executed on a subset of qualified machines. In addition, machines can lose their qualifications during the schedule. Indeed, if no job of a family is scheduled on a machine during a given amount of time, the machine loses its qualification for this family. The goal is to minimize the sum of job completion times, i.e. the flow time, while maximizing the number of qualifications at the end of the schedule. The paper presents a new constraint programming (CP) model taking more advantages of the CP feature to model machine disqualifications. This model is compared with two existing models: an Integer Linear programming (ILP) model and a constraint programming model. The experiments show that the new CP model outperforms the other model when the priority is given to the number of disqualifications objective. Furthermore, it is competitive with the other model when the flow time objective is prioritized.
The Golomb ruler problem is defined as follows: Given a positive integer n, locate n marks on a ruler such that the distance between any two distinct pair of marks are different from each other and the total length of...
详细信息
ISBN:
(纸本)9783030192129;9783030192112
The Golomb ruler problem is defined as follows: Given a positive integer n, locate n marks on a ruler such that the distance between any two distinct pair of marks are different from each other and the total length of the ruler is minimized. The Golomb ruler problem has applications in information theory, astronomy and communications, and it can be seen as a challenge for combinatorial optimization algorithms. Although constructing high quality rulers is well-studied, proving optimality is a far more challenging task. In this paper, we provide a computational comparison of different optimization paradigms, each using a different model (linear integer, constraint programming and quadratic integer) to certify that a given Golomb ruler is optimal. We propose several enhancements to improve the computational performance of each method by exploring bound tightening, valid inequalities, cutting planes and branching strategies. We conclude that a certain quadratic integer programming model solved through a Benders decomposition and strengthened by two types of valid inequalities performs the best in terms of solution time for small-sized Golomb ruler problem instances. On the other hand, a constraint programming model improved by range reduction and a particular branching strategy could have more potential to solve larger size instances due to its promising parallelization features.
constraint programming (CP) is an efficient technique for searching counter-examples that violate a property of the program to verify. However, the search process can become very long and costly when the program to ch...
详细信息
ISBN:
(纸本)9781728104928
constraint programming (CP) is an efficient technique for searching counter-examples that violate a property of the program to verify. However, the search process can become very long and costly when the program to check contains Floating Point (FP) computations. In this paper we discuss the capabilities of a set of variable choice strategies and subdomain selection strategies that take advantages of the very specific properties of the floats. We also outline the capabilities of a CP techniques for computing ranges of error values as well as input values that exercise a given error;a critical issue to take advantage of cancellation phenomena when searching counterexamples.
暂无评论