Collaborating Authors

Counting-Based Search for Constraint Optimization Problems

AAAI Conferences

Branching heuristics based on counting solutions in constraints have been quite good at guiding search  to solve constraint satisfaction problems. But do they perform as well for constraint optimization problems? We propose an adaptation of counting-based search for optimization, show how to modify solution density computation for some of the most frequently-occurring constraints, and empirically evaluate its performance on several benchmark problems.

Optimum Anytime Bounding for Constraint Optimization Problems Simon de Givry and G rard Verfaillie

AAAI Conferences

Edouard Belin, BP 4025, 31055 Toulouse Cedex 4, France {degivry,verfaillie} Abstract In this paper, we consider Constraint Optimization Problems in a Resource-Bounded context. We observe that both exact and approximate methods produce only an anytime upper bound of the optimum (in case of minimization). No lower bound, and thus no quality is available at run time. For a meta-reasoning system, it is difficult to reason on the basis of a so poor piece of information. Therefore, we discuss some ways of producing an anytime lower bound.


AAAI Conferences

There exist a number of algorithms that can solve dynamic constraint satisfaction/optimization problems (DynCSPs or DynCOPs). Because of the large variety in the characteristics of DynCSPs and DynCOPs, not all algorithms perform equally well on all problems. In this paper, we present the Dynamic Constraint Optimization Ant Algorithm (DynCOAA). It is based upon the ant colony optimization (ACO) meta-heuristic that has already proven its merit in other dynamic optimization problems. We perform a large number of experiments to identify the dynamic constraint problems which our algorithm is most suited for. It turns out that this is a large class of problems, namely heterogeneous problems that change often. We find this to be common characteristics in real-world applications. For these problems, DynCOAA outperforms both the complete and non-complete traditional algorithms that were used for comparison.


AAAI Conferences

Graph matching problem that incorporates pair-wise constraints can be formulated as Quadratic Assignment Problem(QAP). The optimal solution of QAP is discrete and combinational, which makes QAP problem NP-hard. Thus, many algorithms have been proposed to find approximate solutions. In this paper, we propose a new algorithm, called Nonnegative Orthogonal Graph Matching (NOGM), for QAP matching problem. NOGM is motivated by our new observation that the discrete mapping constraint of QAP can be equivalently encoded by a nonnegative orthogonal constraint which is much easier to implement computationally. Based on this observation, we develop an effective multiplicative update algorithm to solve NOGM and thus can find an effective approximate solution for QAP problem. Comparing with many traditional continuous methods which usually obtain continuous solutions and should be further discretized, NOGM can obtain a sparse solution and thus incorporates the desirable discrete constraint naturally in its optimization. Promising experimental results demonstrate benefits of NOGM algorithm.


AAAI Conferences

Many heuristics for cost-optimal planning are based on linear programming. We cover several interesting heuristics of this type by a common framework that fixes the objective function of the linear program. Within the framework, constraints from different heuristics can be combined in one heuristic estimate which dominates the maximum of the component heuristics. Different heuristics of the framework can be compared on the basis of their constraints. We present theoretical results on the relation between existing heuristics and experimental results that demonstrate the potential of the proposed framework.