The task at hand is that of a soft constraint problem with adversarial conditions. By amalgamating the weighted and quantified constraint satisfaction frameworks, a Minimax Weighted Constraint Satisfaction Problem (fo...
详细信息
The task at hand is that of a soft constraint problem with adversarial conditions. By amalgamating the weighted and quantified constraint satisfaction frameworks, a Minimax Weighted Constraint Satisfaction Problem (formerly Quantified Weighted Constraint Satisfaction Problem) consists of a set of finite domain variables, a set of soft constraints, and a min or max quantifier associated with each of these variables. We formally define the framework, suggest three solution concepts, and propose a complete solver based on alphabeta pruning techniques. We discuss in depth our novel definitions and implementations of node, arc and full directional arc consistency notions to help reduce search space on top of the basic tree search with alpha-beta pruning for solving ultra-weak solutions. In particular, these consistencies approximate the lower and upper bounds of the cost of a problem by exploiting the semantics of the quantifiers and reusing techniques from both Weighted and Quantified Constraint Satisfaction Problems. Lower bound computation employs standard estimation of costs in the sub-problems used in alpha-beta search. In estimating upper bounds, we propose two approaches based on the Duality Principle: duality of quantifiers and duality of constraints. The first duality amounts to changing quantifiers from min to max, while the second duality re-uses the lower bound approximation functions on dual constraints to generate upper bounds. Experiments on three benchmarks comparing basic alpha-beta pruning and the six consistencies from the two dualities are performed to confirm the feasibility and efficiency of our proposal.
Constraint programming is a powerful software technology for solving numerous real-life problems. Many of these problems can be modeled as Constraint Satisfaction Problems (CSPs) and solved using constraint programmin...
详细信息
Constraint programming is a powerful software technology for solving numerous real-life problems. Many of these problems can be modeled as Constraint Satisfaction Problems (CSPs) and solved using constraint programming techniques. However, solving a CSP is NP-complete so filtering techniques to reduce the search space are still necessary. Arc-consistency algorithms are widely used to prune the search space. The concept of arc-consistency is bidirectional, i.e., it must be ensured in both directions of the constraint (direct and inverse constraints). Two of the most well-known and frequently used arc-consistency algorithms for filtering CSPs are AC3 and AC4. These algorithms repeatedly carry out revisions and require support checks for identifying and deleting all unsupported values from the domains. Nevertheless, many revisions are ineffective, i.e., they cannot delete any value and consume a lot of checks and time. In this paper, we present AC4-OP, an optimized version of AC4 that manages the binary and non-normalized constraints in only one direction, storing the inverse founded supports for their later evaluation. Thus, it reduces the propagation phase avoiding unnecessary or ineffective checking. The use of AC4-OP reduces the number of constraint checks by 50% while pruning the same search space as AC4. The evaluation section shows the improvement of AC4-OP over AC4, AC6 and AC7 in random and non-normalized instances.
Many knowledge-based applications require knowledge maintenance to keep the application functional throughout its lifecycle. In this paper we present iCAM, a constraint-based knowledge maintenance system that operates...
详细信息
ISBN:
(纸本)9781595936431
Many knowledge-based applications require knowledge maintenance to keep the application functional throughout its lifecycle. In this paper we present iCAM, a constraint-based knowledge maintenance system that operates in a hospital's material management domain. iCAM uses consistency algorithms to assist users in placing orders and making order corrections, and to ensure that maintenance activities are consistent with the department's ordering environment. This approach allows iCAM to interact with the user to revise orders and/or to update the knowledge base. For the user, there is not much distinction between these two tasks. This is one of iCAM's greatest strengths;order corrections and knowledge maintenance are carried out in a similar manner, since both are based on inconsistencies with respect to the existing knowledge base. iCAM has various constraint types that support physical and policy restrictions. It also allows maintenance to be done by a number of users while maintaining the integrity of the knowledge base by a system of role restrictions.
Modeling of complex turbulent reacting flows is of great importance in efforts to reduce the fuel consumption and pollutant emissions of many practical devices. The transported PDF method offers the salient advantage ...
详细信息
Modeling of complex turbulent reacting flows is of great importance in efforts to reduce the fuel consumption and pollutant emissions of many practical devices. The transported PDF method offers the salient advantage that the chemical reaction and other one-point processes (e.g., radiative emission) can be represented exactly without modeling assumptions. To date the PDF method has been mostly applied to statistically stationary axisymmetric jet flames and other canonical flow *** research has broadened the accessibility of PDF methods so that they can be brought to bear in complex engineering flows of practical interest, which usually require three-dimensional time-dependent simulations for complicated (unstructured and/or deforming) meshes. For these flows, it is desirable to integrate the particle-based solution schemes into existing grid-based research and engineering computational fluid dynamics (CFD) codes with a hybrid particle/finite-volume PDF method. Key issues for further application of hybrid PDF methods to engineering flows include particle algorithms, particle/FV consistency and efficient algorithms for complex chemistry. In this thesis, an efficient, robust and accurate hybrid particle/FV method has been developed to tackle these three issues. The developed consistent and computationally efficient hybrid particle/FV PDF methods have been used to simulate a homogeneous-charge compression-ignition engine. A sensitivity study on effects of variations in engine operating conditions has shown that the simulation results are reasonably close to the experimental measurements and correctly capture the trends. The effects of variations in global equivalence ratio, wall temperature, swirl level, degree of mixture inhomogeneity, and a top-ring-land crevice have been investigated to examine the influence of turbulence/chemistry interactions on autoignition timing and emissions. This work demonstrates that the combination of consistent hybrid parti
In many Internet scale replicated system, not all replicas can be dealt with in the same way, since some will be in greater demand than others. In the case of weak consistency algorithms, we have observed that updatin...
详细信息
ISBN:
(纸本)0769515886
In many Internet scale replicated system, not all replicas can be dealt with in the same way, since some will be in greater demand than others. In the case of weak consistency algorithms, we have observed that updating first replicas having most demand a greater number of clients would gain access to updated content in a shorter period of time. In this work we have investigated the benefits that can be obtained by prioritizing replicas with greater demand, and considerable improvements have been achieved. In zones of higher demand, the consistent state is reached zip to six times quicker than with a normal weak consistency algorithm, without incurring the additional costs of the strong consistency.
Existing fault-tolerant clock synchronization algorithms are compared and contrasted. These include the following: software synchronization algorithms, such as convergence-averaging, convergence-nonaveraging, and cons...
详细信息
Existing fault-tolerant clock synchronization algorithms are compared and contrasted. These include the following: software synchronization algorithms, such as convergence-averaging, convergence-nonaveraging, and consistency algorithms, as well as probabilistic synchronization; hardware synchronization algorithms; and hybrid synchronization. The worst-case clock skews guaranteed by representative algorithms are compared, along with other important aspects such as time, message, and cost overhead imposed by the algorithms. More recent developments such as hardware-assisted software synchronization and algorithms for synchronizing large, partially connected distributed systems are especially emphasized
暂无评论