Efficient Lifting of Symmetry Breaking Constraints for Complex Combinatorial Problems

ALICE TARZARIOL; KONSTANTIN SCHEKOTIHIN; MARTIN GEBSERMARK LAW

首页> 外文期刊>Theory and practice of logic programming >Efficient Lifting of Symmetry Breaking Constraints for Complex Combinatorial Problems

【24h】

Efficient Lifting of Symmetry Breaking Constraints for Complex Combinatorial Problems

机译：Efficient Lifting of Symmetry Breaking Constraints for Complex Combinatorial Problems

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相关主题

摘要

Many industrial applications require finding solutions to challenging combinatorial problems.Efficient elimination of symmetric solution candidates is one of the key enablers for highperformancesolving. However, existing model-based approaches for symmetry breaking are limitedto problems for which a set of representative and easily solvable instances is available,which is often not the case in practical applications. This work extends the learning frameworkand implementation of a model-based approach for Answer Set Programming to overcomethese limitations and address challenging problems, such as the Partner Units Problem. In particular,we incorporate a new conflict analysis algorithm in the Inductive Logic Programmingsystem ILASP, redefine the learning task, and suggest a new example generation method toscale up the approach. The experiments conducted for different kinds of Partner Units Probleminstances demonstrate the applicability of our approach and the computational benefits due tothe first-order constraints learned.

著录项

来源
《Theory and practice of logic programming》 |2022年第4期|606-622|共17页
作者
ALICE TARZARIOL; KONSTANTIN SCHEKOTIHIN; MARTIN GEBSERMARK LAW;
展开▼
作者单位

University of Klagenfurt, Klagenfurt, Austria;

University of Klagenfurt, Klagenfurt, Austria Graz University of Technology, Graz, Austria;

Imperial College London, London, UK;

展开▼
收录信息
原文格式 PDF
正文语种英语
中图分类
关键词
answer set programming; inductive logic programming; symmetry breaking constraints;

Efficient Lifting of Symmetry Breaking Constraints for Complex Combinatorial Problems

摘要

著录项

相关主题

期刊订阅