Branch and Bound Algorithms to Solve Semiring Constraint Satisfaction Problems

机译：求解半圆约束满足问题的分支定界算法

获取原文

获取原文并翻译 | 示例

页面导航

摘要
著录项
相似文献
相关主题

摘要

The Semiring Constraint Satisfaction Problem (SCSP) framework is a, popular approach for the representation of partial constraint satisfaction problems. Considerable research has been done in solving SCSPs, but limited work has been done in building general SCSP solvers. This paper is part of a series in which incremental changes are made to a branch and bound (BnB) algorithm for solving SCSPs. We present two variants of a BnB algorithm: a backjumping algorithm and a forward checking algorithm. These algorithms are based on the maximal constraints algorithms of Freuder and Wallace [1], and we show they perform better than the BnB algorithm on some problem instances.

机译：半环约束满足问题（SCSP）框架是表示部分约束满足问题的一种流行方法。在解决SCSP方面已经进行了大量研究，但是在构建通用SCSP求解器方面所做的工作有限。本文是该系列的一部分，其中对解决SCSP的分支定界（BnB）算法进行了增量更改。我们提出了BnB算法的两个变体：回跳算法和前向检查算法。这些算法基于Freuder和Wallace [1]的最大约束算法，我们证明它们在某些问题实例上的性能优于BnB算法。

著录项

来源
《PRICAI 2008: Trends in Artificial Intelligence》|2008年|991-997|共7页
会议地点 Hanoi(VN);Hanoi(VN)
作者
Louise Leenen; Aditya Ghosc;
展开▼
作者单位

Decision Systems Laboratory. SCSSE, University of Wollongong, Australia CSIR, South Africa;

Decision Systems Laboratory. SCSSE, University of Wollongong, Australia;

展开▼
会议组织
原文格式 PDF
正文语种 eng
中图分类信息处理（信息加工）;
关键词

相似文献

外文文献
中文文献
专利

1. Interval Branch-and-Bound algorithms for optimization and constraint satisfaction: a survey and prospects [J] . Araya Ignacio, Reyes Victor Journal of Global Optimization . 2016,第4期

机译：优化和约束满足的区间分支定界算法：研究与展望
2. Constraint Satisfaction Problem Using Modified Branch and Bound Algorithm [J] . AZLINAH MOHAMED, MARINA YUSOFF, ITAZA AFIANI MOHTAR, WSEAS Transactions on Computers . 2008,第1a3期

机译：改进的分支定界算法的约束满足问题
3. An Algorithm Based on Theory of Constraints and Branch and Bound for Solving Integrated Product-Mix-Outsourcing Problem [J] . Mehdizadeh Esmaeil, Jalili Saeed Journal of Optimization in Industrial Engineering . 2019,第1期

机译：基于约束与分支定界理论的集成产品-混合-外包问题求解算法
4. Branch and Bound Algorithms to Solve Semiring Constraint Satisfaction Problems [C] . Louise Leenen, Aditya Ghose Pacific Rim International Conference on Artificial Intelligence . 2008

机译：分支和绑定算法解决精彩约束满足问题
5. ASYNCHRONOUS ALGORITHMS FOR DISTRIBUTED PROCESSING (PARALLEL, PROBLEM SOLVING, BLACKBOARD, TEAM APPROACH, BRANCH, BOUND) [D] . PYO, SAM SOO. 1985

机译：分布式处理的异步算法（并行，问题解决，黑板，团队方法，分支，绑定）
6. Matrix algorithms for solving (in)homogeneous bound state equations [O] . M. Blank, A. Krassnigg -1

机译：求解（内部）齐次约束状态方程的矩阵算法
7. Modeling and Solving Semiring Constraint Satisfaction Problems by Transformation to Weighted Semiring Max-SAT [O] . Louise Leenen, Thomas Meyer, Aditya Ghose 2008

机译：通过变换加权半环max-saT建模并求解半环约束满足问题

Branch and Bound Algorithms to Solve Semiring Constraint Satisfaction Problems

摘要

著录项

相似文献

相关主题

期刊订阅