An unsatisfiable set of constraints is minimal if all its (strict) subsets aresatisfiable.A number of forms of error diagnosis, including circuit error diagnosis and type error diagnosis, require finding all minimal u...
详细信息
ISBN:
(纸本)9781581137057
An unsatisfiable set of constraints is minimal if all its (strict) subsets aresatisfiable.A number of forms of error diagnosis, including circuit error diagnosis and type error diagnosis, require finding all minimal unsatisfiable subsets of a given set of constraints (representing an error), in order to generate the best explanation of the error. In this paper we give algorithms for efficiently determining all minimal unsatisfiable subsets for any kind of constraints. We show how taking into account notions of independence of constraints and using incremental constraint solvers can significantly improve the calculation of these subsets.
Many problems in areas as diverse as chemical engineering, economics, logistics, kinematics, statistics or even nuclear engineering are naturally expressed in terms of non-linear equations. Non-linear equations solvin...
详细信息
ISBN:
(纸本)3540637532
Many problems in areas as diverse as chemical engineering, economics, logistics, kinematics, statistics or even nuclear engineering are naturally expressed in terms of non-linear equations. Non-linear equations solving, or more generally global optimization, is a difficult problem because of its computational complexity and its numerical pitfalls. Global optimization has been studied for many years. the state of the art offers a wide variety of algorithmic solutions that encompass a number of goals. the purpose of the tutorial is to introduce the latest techniques used for non-linear constraints. It covers continuation methods from numerical analysis, classical Newton methods and interval methods. It presents each of them and discusses the various strength and weaknesses. these methods are then combined with techniques inspired from artificial intelligence like box-consistency, an approximation of arc-consistency, and bound-consistency. this mix is stirred into a global method, the Interval Newton method. the combination has many advantages to offer. It brings a global component that ensures completeness while the intervals offer soundness. this entails an elegant semantics with strong guarantees on the computation results. On the other hand, the numerical analysis stronghold plays a major rote in the efficiency of the method. Many tools can be adapted and used to improve boththe efficiency and the accuracy. the Taylor expansion is a remarkable example. It can be turned into an interval extension just like normal functions are. Moreover, its global nature introduces yet another pruning operator that blends quite nicely withthe others. It prunes under different circumstances and helps in establishing the proofs of existence for solutions. Other ideas like the utilization of redundant information has often proved worthy. this track is followed again withthe partial Groebner basis that introduces redundant polynomials. Traditional local techniques can also find thei
principles of agile information systems development (ISD) have attracted the interest of practice as well as research. the goal of this literature review is to validate, update and extend previous reviews in terms of ...
详细信息
ISBN:
(纸本)9781479925056
principles of agile information systems development (ISD) have attracted the interest of practice as well as research. the goal of this literature review is to validate, update and extend previous reviews in terms of the general state of research on agile ISD. Besides including categories such as the employed research methods and data collection techniques, the importance of theory is highlighted by evaluating the theoretical foundations and contributions of former studies. Since agile ISD is rooted in the IS as well as software engineering discipline, important outlets of both disciplines are included in the search process, resulting in 482 investigated papers. the findings show that quantitative studies and the theoretical underpinnings of agile ISD are lacking. Extreme programming is still the most researched agile ISD method, and more efforts on Scrum are needed. In consequence, multiple research gaps that need further research attention are identified.
this document represents the proceedings of the 2024 XCSP3 Competition. the results of this competition of constraint solvers were presented at CP'24 (30thinternationalconference on principles and practice of Co...
详细信息
this paper presents an alternative method to parallelize programs, better suited to manycore processors than actual operating system-/API-based approaches like OpenMP and MPI. the method relies on a parallelizing hard...
详细信息
this paper presents an alternative method to parallelize programs, better suited to manycore processors than actual operating system-/API-based approaches like OpenMP and MPI. the method relies on a parallelizing hardware and an adapted programming style. It frees and captures the instruction-level parallelism (ILP). A many-core design is presented in which cores are multithreaded and able to fork new threads. the programming style is based on functions. the hardware creates a concurrent thread at each function call. the programming style and the hardware create the conditions to free the ILP, by eliminating the architectural dependences between a call and its continuation after return. We illustrate the method on a sum reduction, a matrix multiplication and a sort. We measure the ILP of the parallel runs and show that it is high enough to feed thousands of cores because it increases with data size. We compare our method to pthread parallelization, showing that (1) our parallel execution is deterministic, (2) our thread management is cheap, (3) our parallelism is implicit, and (4) our method parallelizes functions and loops. Implicit parallelism makes parallel code easy to write and read. Deterministic parallel execution makes parallel code easy to debug.
Multi-agent path finding (MAPF) is the problem of planning a set of non-colliding paths for a set of agents so that each agent reaches its individual goal location following its path. A mutex from classical planning i...
详细信息
In most engineering applications the optimization is employed after the conceptual design is already frozen withthe only purpose of perfecting it. Although optimization algorithms capable of optimizing the configurat...
详细信息
ISBN:
(纸本)9781509042418
In most engineering applications the optimization is employed after the conceptual design is already frozen withthe only purpose of perfecting it. Although optimization algorithms capable of optimizing the configuration exist, their application is limited to electronics or control design, while for complex systems the conceptual design is often performed with manual trade off analyses among few options. In hypersonic propulsion for instance, the choice of which flow cycle to use is made mainly by means of experience or in the best case by a trade off between radically different architectures. For Combined Cycle Propulsion (CCP) however many flow cycle possibilities are available and it is very possible that the final design is influenced by the preconceptions of the engineers rather than a pure objective judgement. therefore a configurational optimization process, not bound to any known configuration, can potentially deliver totally new engine concepts, aiding the creativity of the designer. In this paper the first steps toward a configurational optimization of CCP are shown. this optimization is intended to find the optimal engine design without knowing the engine conceptual design a-priori. the optimization algorithm is based on the Genetic programming (GP) and it was presented for the first time at the 20~(th)AIAA international Space Planes and Hypersonic Systems and Technologies conference. In the present paper the fitness function has been improved withthe addition of a constraint like penalty function designed to solve a convergence problem outlined in the previous version. the results presented in this paper demonstrate that the optimizer is able to converge to a reasonable configuration, coherent withthe engineering practice. Moreover the improvements proposed in this paper proved to be effective in the mitigation of the previously detected problem, thus demonstrating that the optimization algorithm is robust and that the previous problems were only due t
暂无评论