检索结果-内蒙古大学图书馆

Specialised constraints for stable matching problems

11th international conference on principles and practice of constraint programming (CP 2005)

作者： Unsworth, C Prosser, P Univ Glasgow Dept Comp Sci Glasgow G12 8QQ Lanark Scotland

ISBN: (纸本)3540292381

the stable marriage problem (SM) and the Hospital / Residents problem (HR) are both stable matching problems. they consist of two sets of objects that need to be matched to each other;in SM men to women, and in HR residents to hospitals. Each set of objects expresses a ranked preference for the objects in the other set, in the form of a preference list. the problem is then to find a matching of one set to the other such that the matching is stable. A matching is stable iff it contains no blocking pairs. A blocking pair in a matching M consists of two objects x and y one from each set(x = man and y = woman for SM or x = hospital and y = resident in HR), such that x and y are not matched in M and both x and y would rather be matched to each other than to there assignment in M. Algorithms have been published for both of these problems and optimal constraint models have been published for the stable marriage problem. So the main question would be why the need for specialised constraint for these problems? the SM algorithm and the optimal constraint encodings all have a time complexity of O(n²), but in practice it can take over a minute for the constraint models to find a solution to a problem of size 45 while the SM algorithm can find a solution in less than two hundredths of a second. there have not been any optimal HR constraint models published, but I assume the same performance gap would exist. the advantage of the constraint solutions are their versatility. Many harder valiants of the stable matching problems can be solved by adding simple side constraints to the existing;models, this is not possible with the matching algorithms. So the motivation behind a specialised constraint is to try and combine the efficiency of the algorithm with the versatility of the constraint models. In the full version of this paper I discuss issues concerning the creation of specialised constraints to solve these problems. I then go on to present some empirical results that

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

Generalized conflict learning for hybrid discrete/linear optimization

引用

11th international conference on principles and practice of constraint programming (CP 2005)

作者： Li, H Williams, B MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA

ISBN: (纸本)3540292381

Conflict-directed search algorithms have formed the core of practical, model-based reasoning systems for the last three decades. At the core of many of these applications is a series of discrete constraint optimization problems and a conflict-directed search algorithm, which uses conflicts in the forward search step to focus search away from known infeasibilities and towards the optimal feasible solution. In the arena of model-based autonomy, deep space probes have given way to more agile vehicles, such as coordinated vehicle control, which must robustly control their continuous dynamics. Controlling these systems requires optimizing over continuous, as well as discrete variables, using linear as well as logical constraints. this paper explores the development of algorithms for solving hybrid discrete/linear optimization problems that use conflicts in the forward search direction, carried from the conflict-directed search algorithm in model-based reasoning. We introduce a novel algorithm called Generalized Conflict-Directed Branch and Bound (GCD-BB). GCD-BB extends traditional Branch and Bound (B&B), by first constructing conflicts from nodes of the search tree that are found to be infeasible or suboptimal, and then by using these conflicts to guide the forward search away from known infeasible and sub-optimal states. Evaluated empirically on a range of test problems of coordinated air vehicle control, GCD-BB demonstrates a substantial improvement in performance compared to a traditional B&B algorithm applied to either disjunctive linear programs or an equivalent binary integer programming encoding.

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

Spread: A balancing constraint based on statistics

引用

11th international conference on principles and practice of constraint programming - CP 2005

作者： Pesant, Gilles Régin, Jean-Charles ILOG 1681 route des Dolines 06560 Valbonne France Computing and Information Science Cornell University Ithaca NY 14850 United States

ISBN: (纸本)3540292381

Many combinatorial problems require of their solutions that they achieve a certain balance of given features. In the constraint programming literature, little has been written to specifically address this issue, particularly at the modeling level. We propose a new constraint dedicated to balancing, based on well-known and well-understood concepts in statistics. We show how it can be used to model different situations in which balance is important. We also design efficient filtering algorithms to guide the search towards balanced solutions. © Springer-Verlag Berlin Heidelberg 2005.

关键词： Computer systems programming

来源：评论

学校读者我要写书评

暂无评论

CoJava: A unified language for simulation and optimization

引用

11th international conference on principles and practice of constraint programming (CP 2005)

作者： Brodsky, A Nash, H George Mason Univ Fairfax VA 22030 USA

ISBN: (纸本)3540292381

We have proposed and implemented the language CoJava, which offers both the advantages of simulation-like process modeling in Java, and the capabilities of true decision optimization. We will demonstrate the modeling methodology and implementation techniques, following an optimization application example. By design, the syntax of CoJava is identical to the programming language Java, extended with special constructs to (1) make a non-deterministic choice of a numeric value, (2) assert a constraint, and (3) designate a program variable as the objective to be optimized. A CoJava program thus defines a set of nondeterministic execution paths, each being a program run with specific selection of values in the choice statements. the semantics of CoJava interprets a program as an optimal nondeterministic execution path, namely, a path that (1) satisfies the range conditions in the choice statements, (2) satisfies the assert-constraint statements, and (3) produces the optimal value in a designated program variable, among all execution paths that satisfy (1) and (2). thus, to run a CoJava program amounts to first finding an optimal execution path, and then procedurally executing it. To optimize a process, each real-world device or facility is modeled, tested and debugged in pure Java as a class of objects with private state and public methods which change the state. A process is described as a method of a separate class, which invokes methods of the model objects passing non-deterministic choices for arguments, and which designates an optimization objective. For model developers, it appears as if the program has simply followed a single execution path which coincidentally produces the optimal objective value. thus the learning curve for software developers is minimal. To find an optimal non-deterministic execution path, we have developed a reduction to a standard constraint optimization formulation. constraint variables represent values in program variables that can be create

关键词： Java programming language

来源：评论

学校读者我要写书评

暂无评论

Computing and exploiting tree-decompositions for solving constraint networks

引用

11th international conference on principles and practice of constraint programming - CP 2005

作者： Jégou, Philippe Ndiaye, Samba Ndojh Terrioux, Cyril Avenue Escadrille Normandie-Niemen 13397 Marseille Cedex 20 France

ISBN: (纸本)3540292381

Methods exploiting tree-decompositions seem to provide the best approach for solving constraint networks w.r.t. the theoretical time complexity. However, they have not shown a real practical interest yet. In this paper, we study several methods for computing a rough optimal tree-decomposition and assess their relevance for solving CSPs. © Springer-Verlag Berlin Heidelberg 2005.

关键词： Computer networks

来源：评论

学校读者我要写书评

暂无评论

Extension of O(n log n) filtering algorithms for the unary resource constraint to optional activities

引用

constraintS 2005年第4期10卷 403-425页

作者： Vilím, P Barták, R Cepek, O Charles Univ Prague Fac Math & Phys Prague 1 Czech Republic

Scheduling is one of the most successful application areas of constraint programming mainly thanks to special global constraints designed to model resource restrictions. Among these global constraints, edge-finding and not-first/not-last are the most popular filtering algorithms for unary resources. In this paper we introduce new O(n log n) versions of these two filtering algorithms and one more O(n log n) filtering algorithm called detectable precedences. these algorithms use a special data structures theta-tree and theta-Alpha-tree. these data structures are especially designed for "what-if" reasoning about a set of activities so we also propose to use them for handling so called optional activities, i.e. activities which may or may not appear on the resource. In particular, we propose new O(n log n) variants of filtering algorithms which are able to handle optional activities: overload checking, detectable precedences and not-first/not-last.

关键词： global constraints scheduling unary resource alternatives

来源：评论

学校读者我要写书评

暂无评论

Full arc consistency in WCSP and in constraint hierarchies with finite domains

引用

11th international conference on principles and practice of constraint programming (CP 2005)

作者： Zlomek, J Barták, R Charles Univ Fac Math & Phys Prague Czech Republic

ISBN: (纸本)3540292381

Consistency techniques proved to be an efficient method for reducing the search space of CSP and hence they were modified for soft constraint frameworks too. Several algorithms for local consistency in Weighted CSP, where costs are assigned to tuples, were introduced in [2,3]. the strongest form among them is Full Star Directional Arc Consistency (FDAC*). the algorithm for enforcing FDAC* is based on sending costs from one constraint to another in one direction with respect to the fixed order of variables. We consider the fixed order of variables to be rather limiting so we propose Full Star Arc Consistency (FAC*) which extends the cost sending process by allowing to send the costs in any direction. Because it may not be always possible to send the cost along a directed edge, the proposed extension enables the costs to be sent along other paths. the hope is that by combining more costs we can prune more values from variables' domains. When enforcing FAC*, we choose a variable and move the costs towards the chosen variable. the costs of values of that variable can be used by a value-ordering heuristics during Branch & Bound search. constraint hierarchies [1] are another popular soft constraint framework, which provides a very simple way for a user to specify preferences over constraints. It is possible to use the above-mentioned WCSP consistency algorithms for constraint hierarchies too. We show how constraint hierarchies with finite domains using the unsatisfied-count-better comparator [1] can be transformed to WCSP. We believe that constraint hierarchies with other comparators can also be transformed to a generalization of WCSP that still allows to use the algorithms for enforcing FDAC* and FAC*. © Springer-Verlag Berlin Heidelberg 2005.

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

Solution equivalent subquadrangle reformulations of constraint satisfaction problems

引用

11th international conference on principles and practice of constraint programming (CP 2005)

作者： Houghton, C Cohen, D Univ London Royal Holloway & Bedford New Coll Dept Comp Sci London NW1 4NS England

ISBN: (纸本)3540292381

constraint Satisfaction Problem instances (CSPs) are a natural way to model real life problems such as image processing, scheduling and natural language understanding. In this paper we are concerned with the modeling of problems as CSPs and how this can affect the performance of different solution algorithms. In particular we are interested in modeling in the language of subquadrangles. A Quadrangle is essentially an 'anything-goes' constraint for some Cartesian product of domains. A Subquadrangle [1] is a constraint all of whose projections to proper subsets of the scope are quadrangles. Subquadrangles are a very 'natural' way in which to represent constraints. this is because they do not place any restrictions on proper subsets of their scope, thus reducing the number of required constraint checks. this leads us to believe that a subquadrangle aware solver could be particularly efficient. However, in this paper we shall consider another intriguing use of subquadrangle modeling. Subquadrangles delay the failure of constraint checks until you try and assign a value to the last variable in their scope. this makes them ideal for testing constraint solvers as they are 'backtrack nasty'. In this paper we present two methods by which we might decompose a given instance into a solution equivalent instance whose constraints are all subquadrangles. Our first method converts individual constraints into sets of three subquadrangle constraints. this can then be done for each constraint in a CSP in order to convert the entire problem instance. We are able to demonstrate that this new formulation has a high degree of local consistency related to the arity of the original constraints which induce 'backtrack nasty' behavior in search algorithms. Unfortunately, this with this method one of the subquadrangles is always binary. We also investigate a second method which converts intersecting pairs of constraints. In this method all of the subquadrangles generated are similar in arity

关键词： Problem solving

来源：评论

学校读者我要写书评

暂无评论

GOOSE -: A generic object-oriented search environment

引用

11th international conference on principles and practice of constraint programming (CP 2005)

作者： Müller, H Jähnichen, S Fraunhofer FIRST D-12489 Berlin Germany

ISBN: (纸本)3540292381

the constraint programming community keeps on creating numerous search algorithms, which differ to a greater or lesser extent. It is an as desirable as difficult task to implement a variety of search algorithms in a unifying framework. this design proposal states the object-oriented environment GOOSE, which supports development of generic search algorithms. It is inspired by Prosser 's categorisation of backtracking search algorithms [2]. GOOSE is abstract enough to house dissimilar search approaches and separates abstract generic logic from domain details. the research focuses implementation needs and explicitly goes for an efficient object-oriented design, which enforces code reuse arid flexibility by adequate use of class inheritance and object composition [1]. GOOSE can be implemented in any modern object-oriented language, and as a proof of concept it is realised within our object-oriented solver firstcs. Up to now the concept handles variants of backtracking search and deals with topics like constraint-based scheduling, static and dynamic variable ordering, justifications and backjumping, optimisation, randomisation and restarting techniques. Multidimensional search structures and control flow organisation are of particular interest. Creating new complete search algorithms is easy: A generic frame algorithm is completed by implementing some domain-specific methods. Plug-and-play like assembly of compatible components easily realises algorithmic variations. the variations are chiefly achieved by using generic decorator or strategy objects [1], which can be exchanged during runtime. First experimental results (job-shop scheduling, 3-SAT, n-queens) indicate a performance loss between 0 % (strong pruning) and 10 % (weak pruning) compared to monolithic equivalents. Future work will cover the introduction of non-systematic generic search algorithms and dynamic adaptive search configuration, e.g. switching dynamically from chronological tree movement to backjumping o

关键词： Object oriented programming

来源：评论

学校读者我要写书评

暂无评论

Consistency for partially defined constraints

引用

11th international conference on principles and practice of constraint programming (CP 2005)

作者： Legtchenko, A Lallouet, A Univ Orleans LIFO F-45067 Orleans France

ISBN: (纸本)3540292381

Partially defined or Open constraints [2] can be used to model the incomplete knowledge of a concept or a relation. In an Open constraint, some tuples are known to be true, some other are known to be false and some are just unknown. We propose to complete its definition by using Machine Learning techniques. the idea of the technique we use for learning comes directly from the classical model of solvers computing a chaotic iteration of reduction operators [1]. We begin by learning the constraint. But instead of learning it by a classifier which takes as input all its variables and answers "yes" if the tuple belongs to the constraint and "no" otherwise, we choose to learn the support function n_〈x=a〉 of the constraint for each value of its variables' domains. A tuple is part of the constraint if accepted by all support functions for each of its values and rejected as soon as it gets rejected by one. We propose to use as representation for learning an Artificial Neural Network (ANN) with an intermediate hidden layer trained by the classical backpropagation algorithm [4]. When put in a CSP, a constraint should contribute to the domain reduction. We propose to use the learned classifiers also for solving. In order to do this, we take the natural extension to intervals [3] of the learned classifiers. Let N _〈x=a〉 be the natural interval extension of n _〈x=a〉. then, by using as input the current domain of the variables, we can obtain a range for its output. Since we put a 0.5 threshold after the output neuron, we can reject the value a for X if the maximum of the output range is less than 0.5, which means that all tuples are rejected in the current domain intervals. Otherwise, the value remains in the domain. Our experiments show that the learned consistency is weaker than more classical consistencies but still reduces notably the search space. We show that our technique not only has good learning performances but also yields a very efficient

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：