Problem simplification is of continuing interest in the field of constraint satisfaction. In this paper we examine properties associated with the basic idea of value substitutability and show how certain forms of substitutability can be organised into a strict hierarchy. One of these properties, here called replaceability, has been identified by other authors as being of special interest. We confirm these claims by showing that replaceability is the most general property in this hierarchy that allows local to global inferences. We introduce new algorithms for establishing local (neighbourhood) replaceability that are superior to other types of algorithms designed for this task and demonstrate their effectiveness (values removed) for a variety of constraint types. We show that it is sometimes possible to infer replaceability, leading to appreciable reductions in time required to reduce a problem to irreplaceable domain sets. We also describe a new kind of complexity peak that occurs with neighbourhood replaceability algorithms and analyse this effect.

Algorithms based on singleton arc consistency (SAC) show considerable promise for improving backtrack search algorithms for constraint satisfaction problems (CSPs). The drawback is that even the most efficient of them is still comparatively expensive. Even when limited to preprocessing, they give overall improvement only when problems are quite difficult to solve with more typical procedures such as maintained arc consistency (MAC). The present work examines a form of partial SAC and neighbourhood SAC (NSAC) in which a subset of the variables in a CSP are chosen to be made SAC-consistent or neighbourhood-SAC-consistent. Such consistencies, despite their partial character, are still well-characterized in that algorithms have unique fixpoints. Heuristic strategies for choosing an effective subset of variables are described and tested, the best being choice by highest degree and a more complex strategy of choosing by constraint weight after random probing. Experimental results justify the claim that these methods can be nearly as effective as the corresponding full version of the algorithm in terms of values discarded or problems proven unsatisfiable, while significantly reducing the effort required to achieve this.

We present a greedy version of an existing metaheuristic al-gorithm for a special version of the Cutting Stock Problem(CSP). For this version, it is only possible to have indirectcontrol over the patterns via a vector of continuous valueswhich we refer to as a weights vector. Our algorithm itera-tively generates new weights vectors by making local changesover the best weights vector computed so far. This allows usto achieve better solutions much faster than is possible withthe original metaheuristic.

Data uncertainty in real-life problems is a current challenge in many areas, including Operations Research (OR) and Constraint Programming (CP). This is especially true given the continual and accelerating increase in the amount of data associated with real-life problems, to which Large Scale Combinatorial Optimization (LSCO) techniques may be applied. Although data uncertainty has been studied extensively in the literature, many approaches do not take into account the partial or complete lack of information about uncertainty in real-life settings. To meet this challenge, in this paper we present a strategy for extrapolating data from limited uncertain information to ensure a certain level of robustness in the solutions obtained. Our approach is motivated by real-world applications of supply of timber from forests to saw-mills.

Many real life problems that can be solved by constraint programming, come from uncertain and dynamic environments. Because of the dynamism, the original problem may change over time, and thus the solution found for the original problem may become invalid. For this reason, dealing with such problems has become an important issue in the fields of constraint programming. In some cases, there exist extant knowledge about the uncertain and dynamic environment. In other cases, this information is fragmentary or unknown. In this paper, we extend the concept of robustness and stability for Constraint Satisfaction Problems (CSPs) with ordered domains, where only limited assumptions need to be made as to possible changes. We present a search algorithm that searches for both robust and stable solutions for CSPs of this nature. It is well-known that meeting both criteria simultaneously is a desirable objective for constraint solving in uncertain and dynamic environments. We also present compelling evidence that our search algorithm outperforms other general-purpose algorithms for dynamic CSPs using random instances and benchmarks derived from real life problems.

Many real life problems come from uncertain and dynamic environments, which means that the original problem may change over time. Thus, the solution found for the original problem may become invalid. Dealing with such problems has become an important issue in the field of constraint programming. In some cases, there exists knowledge about the uncertain and dynamic environment. In other cases, this information is unknown or hard to obtain. In this paper, we extend the concept of robustness for Constraint Satisfaction Problems (CSPs) with discrete and ordered domains where the only assumptions made about changes are those inherent in the structure of these problems. We present a search algorithm that searches for both robust and stable solutions for such CSPs. Meeting both criteria simultaneously is a well-known desirable objective for constraint solving in uncertain and dynamic environments.

This paper develops the idea that variable ordering heuristics can be classified on the basis of a small number of distinguishable actions, and that while specific heuristics may be classified differently depending on the problem type, the basic actions that determine their classification are the same. Previous work demonstrated two basic categories of heuristics, and that problems in an apparently homogeneous problem set differ in their amenability to heuristics of different types. The present paper shows that these heuristic actions, which may be described as building up contention and propagating effects, have distinct values for descriptive measures such as depth of failure and the depth at which a problem becomes tractable, that reflect differences in the rapidity of their effects with respect to search depth. Heuristics behave similarly with respect to their basic actions across a wide range of propagation, from simple backtracking to maintained arc consistency. The propagation- of-effects type of action is closely related to the "simplification hypothesis" of Hooker and Vinay. This work contributes to the goals of explaining heuristic performance and putting heuristic selection on a rational basis.

Many knowledge-based applications require knowledge maintenance to keep the application functional throughout its lifecycle. In this paper we present iCAM, a constraintbased 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.

Traditional global search heuristics to solve constraint satisfaction problems focus on properties of an individual variable that mandate early search attention. If however, one could predict crucial subproblems (the portions of a constraint satisfaction problem likely to cause each other particular difficulty) in advance, search could address them first. This paper postulates several types of crucial subproblems, and shows how local search can be harnessed to identify them before global search for a solution. A variety of heuristics and metrics are then used to guide traditional constraint heuristics with those crucial subproblems. On certain classes of structured problems, such search outperforms traditional heuristics by at least an order of magnitude in both time and space

This paper argues that characterizing heuristic performance in terms of adherence to optimal policies can elucidate many differences in search effort associated with different variable ordering heuristics. This framework involves two policies that search must adhere to to be successful: the promise policy is in force when search is on a solution path; the fail-first policy holds when search is in an insoluble subtree. After discussing how adherence to these policies can be measured, the paper shows that many complex patterns of performance can be elucidated by measuring the adherence to each policy. For example, some strategies designed to maximize adherence to one policy are shown to be either unsuccessful in this regard or to affect adherence to the other policy adversely, thus impairing search. In contrast, strategies used by superior heuristics often balance features such as branching and local connectivity so as to enhance adherence to both policies simultaneously. Differences related to problem structure can also be elucidated

This paper describes the Adaptive Constraint Engine (ACE), an ambitious ongoing research project to support constraint programmers, both human and machine. The program begins with substantial knowledge about constraint satisfaction. The program harnesses a cognitively-oriented architecture (FORR) to manage search heuristics and to learn new ones. ACE can transfer what it learns on simple problems to solve more difficult ones, and can readily export its knowledge to ordinary constraint solvers. It currently serves both as a learner and as a test bed for the constraint community.

In this paper, we consider multi-agent constraint systems with preferences, modeled as soft constraint systems in which variables and constraints are distributed among multiple autonomous agents. We assume that each agent can set some preferences over its local data, and we consider two different criteria for finding optimal global solutions: fuzzy and Pareto optimality. We propose a general graph-based framework to describe the problem to be solved in its generic form. As a case study, we consider a distributed meeting scheduling problem where each agent has a pre-existing schedule and the agents must decide on a common meeting that satisfies a given optimality condition. For this scenario we consider the topics of solution quality, search efficiency, and privacy loss, where the latter pertains to information about an agent's pre-existing meetings and available time-slots. We also develop and test strategies that trade efficiency for solution quality and strategies that minimize information exchange, including some that do not require inter-agent comparisons of utilities. Our experimental results demonstrate some of the relations among solution quality, efficiency, and privacy loss, and provide useful hints on how to reach a tradeoff among these three factors. In this work, we show how soft constraint formalisms can be used to incorporate preferences into multi-agent problem solving along with other facets of the problem, such as time and distance constraints. This work also shows that the notion of privacy loss can be made concrete so that it can be treated as a distinct, manipulable factor in the context of distributed decision making.

A basic problem is to optimize the tradeoff between effort required to establish a local consistency and that required for search. An approach is presented to this problem which is termed selective relaxation. The idea is to perform consistency checking at places where it is likely to be effective, basing this judgment on local criteria. To this end, the authors introduce two forms of bounded relaxation, one in which consistency testing propagates for a limited distance from a point of change, and one in which it stops when the amount of change, or response, falls below threshold. Experiments show that these procedures can outperform well-known preprocessing or hybrid algorithms on many problems.>