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

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)

作者： Berg, Jeremias Oikarinen, Emilia Jarvisalo, Matti Puolamaki, Kai Univ Helsinki Dept Comp Sci HIIT Helsinki Finland Finnish Inst Occupat Hlth Helsinki Finland

ISBN: (纸本)9783319661582;9783319661575

the use of constraint optimization has recently proven to be a successful approach to providing solutions to various NP-hard search and optimization problems in data analysis. In this work we extend the use of constraint optimization systems further within data analysis to a central problem arising from the analysis of multivariate data, namely, determining minimum-width multivariate confidence intervals, i.e., the minimum-width confidence band problem (MWCB). Pointing out drawbacks in recently proposed formalizations of variants of MWCB, we propose a new problem formalization which generalizes the earlier formulations and allows for circumvention of their drawbacks. We present two constraint models for the new problem in terms of mixed integer programming and maximum satisfiability, as well as a greedy approach. Furthermore, we empirically evaluate the scalability of the constraint optimization approaches and solution quality compared to the greedy approach on real-world datasets.

关键词： Constrained optimization

来源：评论

学校读者我要写书评

暂无评论

the StockingCost constraint

The StockingCost Constraint

引用

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

作者： Houndji, Vinasetan Ratheil Schaus, Pierre Wolsey, Laurence Deville, Yves Catholic Univ Louvain Louvain La Neuve Belgium

ISBN: (纸本)9783319104287;9783319104270

Many production planning problems call for the minimization of stocking/storage costs. this paper introduces a new global constraint StockingCost ([X-1,..., X-n], [d(1),..., d(n)], H, c) that holds when each item X-i is produced on or before its due date d(i), the capacity c of the machine is respected, and H is an upper bound on the stocking cost. We propose a linear time algorithm to achieve bound consistency on the StockingCost constraint. On a version of the Discrete Lot Sizing Problem, we demonstrate experimentally the pruning and time efficiency of our algorithm compared to other state-of-the-art approaches.

关键词： Production Planning Discrete Lot Sizing constraint programming Global constraint

来源：评论

学校读者我要写书评

暂无评论

Binary constraint Trees and Structured Decomposability 29

Binary Constraint Trees and Structured Decomposability

引用

29th international conference on principles and practice of constraint programming, cp 2023

作者： Kučera, Petr Department of Theoretical Computer Science and Mathematical Logic Faculty of Mathematics and Physics Charles University Prague Czech Republic

ISBN: (纸本)9783959773003

A binary constraint tree (BCT, Wang and Yap 2022) is a normalized binary CSP whose constraint graph is a tree. A BCT constraint is a constraint represented with a BCT where some of the variables may be hidden (i.e. existentially quantified and used only for internal representation). Structured decomposable negation normal forms (SDNNF) were introduced by Pipatsrisawat and Darwiche (2008) as a restriction of decomposable negation normal forms (DNNF). Both DNNFs and SDNNFs were studied in the area of knowledge compilation. In this paper we show that the BCT constraints are polynomially equivalent to SDNNFs. In particular, a BCT constraint can be represented with an SDNNF of polynomial size and, on the other hand, a constraint that can be represented with an SDNNF, can be represented as a BCT constraint of polynomial size. this generalizes the result of Wang and Yap (2022) that shows that a multivalued decision diagram (MDD) can be represented with a BCT. Moreover, our result provides a full characterization of binary constraint trees using a language that is well studied in the area of knowledge compilation. It was shown by Wang and Yap (2023) that a CSP on n variables of domain sizes bounded by d that has treewidth k can be encoded as a BCT on O(n) variables with domain sizes O(dk+1). We provide an alternative reduction for the case of binary CSPs. this allows us to compile any binary CSP to an SDNNF of size that is parameterized by d and k. © Petr Kučera.

关键词： Polynomials

来源：评论

学校读者我要写书评

暂无评论

A Simple and Effective Decomposition for the Multidimensional Binpacking constraint

A Simple and Effective Decomposition for the Multidimensiona...

引用

19th Annual international conference on principles and practice of constraint programming (cp)

作者： Gualandi, Stefano Lombardi, Michele Univ Pavia Dipartimento Matemat I-27100 Pavia Italy Univ Bologna Dipartimento Informat Sci & Ingn Bologna Italy

ISBN: (纸本)9783642406263;9783642406270

the multibin_packing constraint captures a fundamental substructure of many assignment problems, where a set of items, each with a fixed number of dimensions, must be assigned to a number of bins with limited capacities. In this work we propose a simple decomposition for multibin_packing that uses a bin packing constraint for each dimension, a set of all different constraints automatically derived from a conflict graph, plus two alternative symmetry breaking approaches. Despite its simplicity, the proposed decomposition is very effective on a number of instances recently proposed in the literature.

关键词： Computer programming

来源：评论

学校读者我要写书评

暂无评论

Guiding Backtrack Search by Tracking Variables During constraint Propagation 29

Guiding Backtrack Search by Tracking Variables During Constr...

引用

29th international conference on principles and practice of constraint programming, cp 2023

作者： Audemard, Gilles Lecoutre, Christophe Prud'homme, Charles CRIL Univ. Artois CNRS France TASC IMT-Atlantique LS2N-CNRS France

ISBN: (纸本)9783959773003

It is well-known that variable ordering heuristics play a central role in solving efficiently constraint Satisfaction Problem (CSP) instances. From the early 80's, and during more than two decades, the dynamic variable ordering heuristic selecting the variable with the smallest domain was clearly prevailing. then, from the mid 2000's, some adaptive heuristics have been introduced: their principle is to collect some useful information during the search process in order to take better informed decisions. Among those adaptive heuristics, wdeg/dom (and its variants) remains particularly robust. In this paper, we introduce an original heuristic based on the midway processing of failing executions of constraint propagation: this heuristic called pick/dom tracks the variables that are directly involved in the process of constraint propagation, when ending with a conflict. the robustness of this new heuristic is demonstrated from a large experimentation conducted with the constraint solver ACE. Interestingly enough, one can observe some complementary between the early, midway and late forms of processing of conflicts. © 2023 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

关键词： constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

Applying constraint programming to rigid body protein docking

引用

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

作者： Krippahl, L Barahona, P Nova Univ Dept Informat P-2825 Monte De Caparica Portugal

ISBN: (纸本)3540292381

In this paper we show how constraint programming (cp) techniques can improve the efficiency and applicability of grid-based algorithms for optimising surface contact between complex solids. We use BiGGER [1] (Bimolecular complex Generation with Global Evaluation and Ranking) to illustrate the method as applied to modelling protein interactions, an important effort in current bioinformatics. BiGGER prunes the search space by maintaining bounds consistency on interval constraints that model the requirement for the shapes to be in contact but not overlapping, and by using a branch and bound approach to search the models with the best fit. this cp approach gives BiGGER some efficiency advantages over popular protein docking methods that use Fourier transforms to match protein structures. We also present an efficient algorithm to actively impose a broad range of constraints or combinations of constraints on distances between points of the two structures to dock, which allows the use of experimental data to increase the effectiveness and speed of modelling protein interactions and which cannot be done as efficiently in Fourier transform methods. this shows that constraint programming provides a different approach to protein docking (and fitting of shapes in general) that increases the scope of application while improving efficiency.

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

ASP with non-herbrand partial functions: a language and system for practical use

引用

thEORY AND practice OF LOGIC programming 2013年第4-5期13卷 547-561页

作者： Balduccini, Marcello Eastman Kodak Co Rochester NY 14650 USA

Dealing with domains involving substantial quantitative information in Answer Set programming (ASP) often results in cumbersome and inefficient encodings. Hybrid "CASP" languages combining ASP and constraint programming aim to overcome this limitation, but also impose inconvenient constraints - first and foremost that quantitative information must be encoded by means of total functions. this goes against central knowledge representation principles that contribute to the power of ASP, and makes the formalization of certain domains difficult. ASP{f} is being developed with the ultimate goal of providing scientists and practitioners with an alternative to CASP languages that allows for the efficient representation of qualitative and quantitative information in ASP without restricting one's ability to deal with incompleteness or uncertainty. In this paper we present the latest outcome of such research: versions of the language and of the supporting system that allow for practical, industrial-size use and scalability. the applicability of ASP{f} is demonstrated by a case study on an actual industrial application.

关键词： Answer Set programming non-herbrand functions constraint answer set programming practical applications

来源：评论

学校读者我要写书评

暂无评论

Learning a Generic Value-Selection Heuristic Inside a constraint programming Solver 29

Learning a Generic Value-Selection Heuristic Inside a Constr...

引用

29th international conference on principles and practice of constraint programming, cp 2023

作者： Marty, Tom François, Tristan Tessier, Pierre Gautier, Louis Rousseau, Louis-Martin Cappart, Quentin Polytechnique Montréal Montreal Canada Ecole Polytechnique Palaiseau France

ISBN: (纸本)9783959773003

constraint programming is known for being an efficient approach to solving combinatorial problems. Important design choices in a solver are the branching heuristics, designed to lead the search to the best solutions in a minimum amount of time. However, developing these heuristics is a time-consuming process that requires problem-specific expertise. this observation has motivated many efforts to use machine learning to automatically learn efficient heuristics without expert intervention. Although several generic variable-selection heuristics are available in the literature, the options for value-selection heuristics are more scarce. We propose to tackle this issue by introducing a generic learning procedure that can be used to obtain a value-selection heuristic inside a constraint programming solver. this has been achieved thanks to the combination of a deep Q-learning algorithm, a tailored reward signal, and a heterogeneous graph neural network. Experiments on graph coloring, maximum independent set, and maximum cut problems show that this framework competes with the well-known impact-based and activity-based search heuristics and can find solutions close to optimality without requiring a large number of backtracks. © Tom Marty, Tristan François, Pierre Tessier, Louis Gautier, Louis-Martin Rousseau, and Quentin Cappart.

关键词： Reinforcement learning

来源：评论

学校读者我要写书评

暂无评论

ASP with non-herbrand partial functions: a language and system for practical use

ASP with non-herbrand partial functions: a language and syst...

引用

29th international conference on Logic programming ICLP

作者： Balduccini, Marcello Eastman Kodak Co Rochester NY 14650 USA

关键词： Answer Set programming non-herbrand functions constraint answer set programming practical applications

来源：评论

学校读者我要写书评

暂无评论

MDD Archive for Boosting the Pareto constraint 29

MDD Archive for Boosting the Pareto Constraint

引用

29th international conference on principles and practice of constraint programming, cp 2023

作者： Malalel, Steve Malapert, Arnaud Pelleau, Marie Régin, Jean-Charles Université Côte d'Azur CNRS I3S Nice France

ISBN: (纸本)9783959773003

Multi-objective problems are frequent in the real world. In general they involve several incomparable objectives and the goal is to find a set of Pareto optimal solutions, i.e. solutions that are incomparable two by two. In order to better deal with these problems in cp the global constraint Pareto was developed by Schaus and Hartert to handle the relations between the objective variables and the current set of Pareto optimal solutions, called the archive. this constraint handles three operations: adding a new solution to the archive, removing solutions from the archive that are dominated by a new solution, and reducing the bounds of the objective variables. the complexity of these operations depends on the size of the archive. In this paper, we propose to use a multi-valued Decision Diagram (MDD) to represent the archive of Pareto optimal solutions. MDDs are a compressed representation of solution sets, which allows us to obtain a compressed and therefore smaller archive. We introduce several algorithms to implement the above operations on compressed archives with a complexity depending on the size of the archive. We show experimentally on bin packing and multi-knapsack problems the validity of our approach. © Steve Malalel, Arnaud Malapert, Marie Pelleau, and Jean-Charles Régin.

关键词： Optimal systems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：