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

28th international conference on principles and practice of constraint programming, cp 2022

作者： Cseh, Ágnes Escamocher, Guillaume Quesada, Luis Institute of Economics Centre for Economic and Regional Studies Budapest Hungary Insight Centre for Data Analytics School of Computer Science and Information Technology University College Cork Ireland

ISBN: (纸本)9783959772402

constraint programming has proven to be a successful framework for determining whether a given instance of the three-dimensional stable matching problem with cyclic preferences (3dsm-cyc) admits a solution. If such an instance is satisfiable, constraint models can even compute its optimal solution for several different objective functions. On the other hand, the only existing output for unsatisfiable 3dsm-cyc instances is a simple declaration of impossibility. In this paper, we explore four ways to adapt constraint models designed for 3dsm-cyc to the maximum relaxation version of the problem, that is, the computation of the smallest part of an instance whose modification leads to satisfiability. We also extend our models to support the presence of costs on elements in the instance, and to return the relaxation with lowest total cost for each of the four types of relaxation. Empirical results reveal that our relaxation models are efficient, as in most cases, they show little overhead compared to the satisfaction version. © Ágnes Cseh, Guillaume Escamocher, and Luis Quesada.

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

Positive and negative length-bound reachability constraints 27

Positive and negative length-bound reachability constraints

引用

27th international conference on principles and practice of constraint programming, cp 2021

作者： Quesada, Luis Brown, Kenneth N. Insight Centre for Data Analytics School of Computer Science University College Cork Ireland

ISBN: (纸本)9783959772112

In many application problems, including physical security and wildlife conservation, infrastructure must be configured to ensure or deny paths between specified locations. We model the problem as sub-graph design subject to constraints on paths and path lengths, and propose length-bound reachability constraints. Although reachability in graphs has been modelled before in constraint programming, the interaction of positive and negative reachability has not been studied in depth. We prove that deciding whether a set of positive and negative reachability constraints are satisfiable is NP complete. We show the effectiveness of our approach on decision problems, and also on optimisation problems. We compare our approach with existing constraint models, and we demonstrate significant improvements in runtime and solution costs, on a new problem set. © Luis Quesada and Kenneth N. Brown.

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

A collection of constraint programming models for the three-dimensional stable matching problem with cyclic preferences 27

A collection of constraint programming models for the three-...

引用

27th international conference on principles and practice of constraint programming, cp 2021

作者： Cseh, Ágnes Escamocher, Guillaume Genç, Begüm Quesada, Luis Hasso-Plattner-Institute Universität Potsdam Germany Institute of Economics Centre for Economic and Regional Studies Pécs Hungary Insight Centre for Data Analytics School of Computer Science and Information Technology University College Cork Ireland

ISBN: (纸本)9783959772112

We introduce five constraint models for the 3-dimensional stable matching problem with cyclic preferences and study their relative performances under diverse configurations. While several constraint models have been proposed for variants of the two-dimensional stable matching problem, we are the first to present constraint models for a higher number of dimensions. We show for all five models how to capture two different stability notions, namely weak and strong stability. Additionally, we translate some well-known fairness notions (i.e. sex-equal, minimum regret, egalitarian) into 3-dimensional matchings, and present how to capture them in each model. Our tests cover dozens of problem sizes and four different instance generation methods. We explore two levels of commitment in our models: one where we have an individual variable for each agent (individual commitment), and another one where the determination of a variable involves pairing the three agents at once (group commitment). Our experiments show that the suitability of the commitment depends on the type of stability we are dealing with. Our experiments not only led us to discover dependencies between the type of stability and the instance generation method, but also brought light to the role that learning and restarts can play in solving this kind of problems. © Ágnes Cseh, Guillaume Escamocher, Begüm Genç, and Luis Quesada.

关键词： Stability

来源：评论

学校读者我要写书评

暂无评论

On Relation Between constraint Propagation and Block-Coordinate Descent in Linear Programs 26th

On Relation Between Constraint Propagation and Block-Coordin...

引用

26th international conference on principles and practice of constraint programming, cp 2020

作者： Dlask, Tomáš Werner, Tomáš Faculty of Electrical Engineering Czech Technical University in Prague Prague Czech Republic

ISBN: (纸本)9783030584740

Block-coordinate descent (BCD) is a popular method in large-scale optimization. Unfortunately, its fixed points are not global optima even for convex problems. A succinct characterization of convex problems optimally solvable by BCD is unknown. Focusing on linear programs, we show that BCD fixed points are identical to fixed points of another method, which uses constraint propagation to detect infeasibility of a system of linear inequalities in a primal-dual loop (a special case of this method is the Virtual Arc Consistency algorithm by Cooper et al.). this implies that BCD fixed points are global optima iff a certain propagation rule decides feasibility of a certain class of systems of linear inequalities. © 2020, Springer Nature Switzerland AG.

关键词： Linear programming

来源：评论

学校读者我要写书评

暂无评论

A Two-Phase constraint programming Model for Examination Timetabling at University College Cork 26th

A Two-Phase Constraint Programming Model for Examination Tim...

引用

26th international conference on principles and practice of constraint programming, cp 2020

作者： Genc, Begum O’Sullivan, Barry Confirm Centre for Smart Manufacturing School of Computer Science and Information Technology University College Cork Cork Ireland Insight Centre for Data Analytics School of Computer Science and Information Technology University College Cork Cork Ireland

ISBN: (纸本)9783030584740

Examination timetabling is a widely studied NP-hard problem. An additional challenge to the complexity of the problem are many real-world requirements that can often prevent the relaxation of some constraints. We report on a project focused on automating the examination timetabling process of University College Cork (UCC) to enhance the examination schedules so that they are fairer to student, as well as being less resource intensive to generate from an administrative point of view. We work with a formulation developed in collaboration with the institution and real data that it provided to us. We propose a two-phase constraint programming approach to solving UCC ’s examination timetabling problem. the first phase considers the timing of examinations while the second phase considers their allocation to rooms. Both phases are modelled using bin-packing constraints and, in particular, an interesting variant in which items can be split across multiple bins. this variant is known as bin packing with fragmentable items. We investigate the tightly linked constraints and difficulties in decomposing the centralised model. We provide empirical results using different search strategies, and compare the quality of our solution with the existing UCC schedule. constraint programming allows us to easily modify the model to express additional constraints or remove the pre-existing ones. Our approach generates significantly better timetables for the university, as measured using a variety of real-world quality metrics, than those prepared by their timetabling experts, and in a reasonable timeframe. © 2020, Springer Nature Switzerland AG.

关键词： Students

来源：评论

学校读者我要写书评

暂无评论

A Join-Based Hybrid Parameter for constraint Satisfaction 25th

A Join-Based Hybrid Parameter for Constraint Satisfaction

引用

25th international conference on the principles and practice of constraint programming (cp)

作者： Ganian, Robert Ordyniak, Sebastian Szeider, Stefan TU Wien Algorithms & Complex Grp Vienna Austria Univ Sheffield Algorithms Grp Sheffield S Yorkshire England

ISBN: (纸本)9783030300487

We propose joinwidth, a new complexity parameter for the constraint Satisfaction Problem (CSP). the definition of joinwidth is based on the arrangement of basic operations on relations (joins, projections, and pruning), which inherently reflects the steps required to solve the instance. We use joinwidth to obtain polynomial-time algorithms (if a corresponding decomposition is provided in the input) as well as fixed-parameter algorithms (if no such decomposition is provided) for solving the CSP. Joinwidth is a hybrid parameter, as it takes both the graphical structure as well as the constraint relations that appear in the instance into account. It has, therefore, the potential to capture larger classes of tractable instances than purely structural parameters like hypertree width and the more general fractional hypertree width (fhtw). Indeed, we show that any class of instances of bounded fhtw also has bounded joinwidth, and that there exist classes of instances of bounded joinwidth and unbounded fhtw, so bounded joinwidth properly generalizes bounded fhtw. We further show that bounded joinwidth also properly generalizes several other known hybrid restrictions, such as fhtw with degree constraints and functional dependencies. In this sense, bounded joinwidth can be seen as a unifying principle that explains the tractability of several seemingly unrelated classes of CSP instances.

关键词： constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

Generalized support and formal development of constraint propagators

引用

AI COMMUNICATIONS 2017年第5期30卷 325-346页

作者： Caldwell, James Gent, Ian P. Nightingale, Peter Univ Wyoming Dept Comp Sci 1000 E Univ Ave Laramie WY 82071 USA Univ St Andrews Sch Comp Sci St Andrews KY16 9SX Fife Scotland

constraint programming is a family of techniques for solving combinatorial problems, where the problem is modelled as a set of decision variables (typically with finite domains) and a set of constraints that express relations among the decision variables. One key concept in constraint programming is propagation: reasoning on a constraint or set of constraints to derive new facts, typically to remove values from the domains of decision variables. Specialized propagation algorithms (propagators) exist for many classes of constraints. the concept of support is pervasive in the design of propagators. Traditionally, when a domain value ceases to have support, it may be removed because it takes part in no solutions. Arc-consistency algorithms such as AC2001 [in: Proceedings 17th international Joint conference on Artificial Intelligence (IJCAI 2001), 2001, pp. 309-315] make use of support in the form of a single domain value. GAC algorithms such as GAC-Schema [in: Proceedings 15th international Joint conference on Artificial Intelligence (IJCAI 97), 1997, pp. 398-404] use a tuple of values to support each literal. We generalize these notions of support in two ways. First, we allow a set of tuples to act as support. Second, the supported object is generalized from a set of literals (GAC-Schema) to an entire constraint or any part of it. We design a methodology for developing correct propagators using generalized support. A constraint is expressed as a family of support properties, which may be proven correct against the formal semantics of the constraint. We show how to derive correct propagators from the constructive proofs of the support properties. the framework is carefully designed to allow efficient algorithms to be produced. Derived algorithms may make use of dynamic literal triggers or watched literals [in: Proc. 12th international conference on the principles and practice of constraint programming (cp 2006), 2006, pp. 182-197] for efficiency. Finally, three case st

关键词： constraint satisfaction problem constraint programming formal methods

来源：评论

学校读者我要写书评

暂无评论

Rotation-Based Formulation for Stable Matching 23rd

Rotation-Based Formulation for Stable Matching

引用

33rd international conference on Logic programming / 23rd international conference on principles and practice of constraint programming (cp) / 20th international conference on theory and Applications of Satisfiability Testing (SAT)

作者： Siala, Mohamed O'Sullivan, Barry Univ Coll Cork Insight Ctr Data Analyt Dept Comp Sci Cork Ireland

ISBN: (纸本)9783319661582;9783319661575

We introduce new cp models for the many-to-many stable matching problem. We use the notion of rotation to give a novel encoding that is linear in the input size of the problem. We give extra filtering rules to maintain arc consistency in quadratic time. Our experimental study on hard instances of sex-equal and balanced stable matching shows the efficiency of one of our propositions as compared with the state-of-the-art constraint programming approach.

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

Defining and Evaluating Heuristics for the Compilation of constraint Networks 23rd

Defining and Evaluating Heuristics for the Compilation of Co...

引用

作者： Lagniez, Jean-Marie Marquis, Pierre Paparrizou, Anastasia Univ Artois CRIL Lens France CNRS Lens France

ISBN: (纸本)9783319661582;9783319661575

Several branching heuristics for compiling in a top-down fashion finite-domain constraint networks into multi-valued decision diagrams (MDD) or decomposable multi-valued decision graphs (MDDG) are empirically evaluated, using the cn2mddg compiler. this MDDG compiler has been enriched with various additional branching rules. these rules can be gathered into two families, the one consisting of heuristics for the satisfaction problem (which are suited to compiling networks into MDD representations) and the family of heuristics favoring decompositions (which are relevant when the MDDG language is targeted). Our empirical investigation on a large dataset shows the value of decomposability (targeting MDDG allows for compiling many more instances and leads to much smaller compiled representations). the well-known (Dom/Wdeg) heuristics appears as the best choice for compiling networks into MDD. When MDDG is the target, a new rule, based on a dynamic, yet parsimonious use of hypergraph partitioning for the decomposition purpose turns out to be the best option. As expected, the best heuristics for the satisfaction problem perform better than the best heuristics favoring decompositions when MDD is targeted, and the converse is the case when MDDG is targeted.

关键词： Knowledge compilation Top-down compiler Heuristics

来源：评论

学校读者我要写书评

暂无评论

Teaching constraint programming

Teaching Constraint Programming

引用

20th international conference on the principles and practice of constraint programming (cp)

作者： Prosser, Patrick Univ Glasgow Sch Comp Sci Glasgow G12 8QQ Lanark Scotland

ISBN: (纸本)9783319104287;9783319104270

How do we do research?We start with a question. then we read books, journal and conference papers, maybe even speak to people. then we do our own work, make our own contribution, maybe coming up with an improved technique or a greater *** then write up our findings, maybe submit this to a conference, present our work and get feedback, and this results in further research. this is a feedback loop, open to scrutiny by our peers.

关键词： constraint handling Feedback loop Pedagogy Teaching conference Papers Critique Peers journals

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：