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

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)

作者： Lam, Edward Van Hentenryck, Pascal CSIRO Data61 Eveleigh NSW 2015 Australia Univ Melbourne Parkville Vic 3010 Australia Univ Michigan Ann Arbor MI 48109 USA

ISBN: (纸本)9783319661582;9783319661575

this paper proposes the framework of branch-and-check with explanations (BCE), a branch-and-check method where combinatorial cuts are found by general-purpose conflict analysis, rather than by specialized separation algorithms. Specifically, the method features a master problem that ignores combinatorial constraints, and a feasibility sub-problem that uses propagation to check the feasibility of these constraints and performs conflict analysis to derive nogood cuts. the BCE method also leverages conflict-based branching rules and strengthens cuts in a post-processing step. Experimental results on the Vehicle Routing Problem with Time Windows show that BCE is a potential alternative to branch-and-cut. In particular, BCE dominates branch-and-cut, both in proving optimality and in finding high-quality solutions quickly.

关键词： Integer programming

来源：评论

学校读者我要写书评

暂无评论

Minimum-Width Confidence Bands via constraint Optimization 23rd

Minimum-Width Confidence Bands via Constraint Optimization

引用

作者： 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

来源：评论

学校读者我要写书评

暂无评论

Arc Consistency via Linear programming 23rd

Arc Consistency via Linear Programming

引用

作者： German, Grigori Briant, Olivier Cambazard, Hadrien Jost, Vincent Univ Grenoble Alpes CNRS Grenoble INP G SCOP F-38000 Grenoble France

ISBN: (纸本)9783319661582;9783319661575

A typical technique in integer programming for filtering variables is known as variable fixing. the optimal dual solution of the linear relaxation can be used to detect some of the 0/1 variables that must be fixed to either 0 or 1 in any solution improving the best known, but this filtering is incomplete. A complete technique is proposed in this paper for satisfaction problems with an ideal integer programming formulation. We show, in this case, that the 0/1 variables taking the same value in all solutions can be identified by solving a single linear program with twice the number of the original variables. In other words, a complete variable fixing of the 0/1 variables can be performed for a small overhead. As a result, this technique can be used to design generic arc consistency algorithms. We believe it is particularly useful to quickly prototype arc consistency algorithms for numerous polynomial constraints and demonstrate it for the family of Sequence global constraints.

关键词： constraint programming Linear programming filtering Arc consistency Reduced-cost fixing

来源：评论

学校读者我要写书评

暂无评论

Logic programming approaches for routing fault-free and maximally parallel wavelength-routed optical networks-on-chip (Application paper)

引用

thEORY AND practice OF LOGIC programming 2017年第5-6期17卷 800-818页

作者： Gavanelli, Marco Nonato, Maddalena Peano, Andrea Bertozzi, Davide Ferrara Univ Dept Engn Ferrara Italy QuanTek Bologna Italy

One promising trend in digital system integration consists of boosting on-chip communication performance by means of silicon photonics, thus materializing the so-called Optical Networkson- Chip. Among them, wavelength routing can be used to route a signal to destination by univocally associating a routing path to the wavelength of the optical carrier. Such wavelengths should be chosen so to minimize interferences among optical channels and to avoid routing faults. As a result, physical parameter selection of such networks requires the solution of complex constrained optimization problems. In previous work, published in the proceedings of the international conference on Computer-Aided Design, we proposed and solved the problem of computing the maximum parallelism obtainable in the communication between any two endpoints while avoiding misrouting of optical signals. the underlying technology, only quickly mentioned in that paper, is Answer Set programming. In this work, we detail the Answer Set programming approach we used to solve such problem. Another important design issue is to select the wavelengths of optical carriers such that they are spread across the available spectrum, in order to reduce the likelihood that, due to imperfections in the manufacturing process, unintended routing faults arise. We show how to address such problem in constraint Logic programming on Finite Domains.

关键词： Answer set programming Logic programming applications Optical networks-on-chip Constrained optimization constraint logic programming on finite domains

来源：评论

学校读者我要写书评

暂无评论

Search Strategies for Floating Point constraint Systems 23rd

Search Strategies for Floating Point Constraint Systems

引用

作者： Zitoun, Heytem Michel, Claude Rueher, Michel Michel, Laurent Univ Cote Azur CNRS I3S Nice France Univ Connecticut Storrs CT 06269 USA

ISBN: (纸本)9783319661582;9783319661575

the ability to verify critical software is a key issue in embedded and cyber physical systems typical of automotive, aeronautics or aerospace industries. Bounded model checking and constraint programming approaches search for counter-examples that exemplify a property violation. the search of such counter-examples is a long, tedious and costly task especially for programs performing floating point computations. Indeed, available search strategies are dedicated to finite domains and, to a lesser extent, to continuous domains. In this paper, we introduce new strategies dedicated to floating point constraints. they take advantage of the properties of floating point domains (e.g., domain density) and of floating point constraints (e.g., floating point arithmetic) to improve the search for floating point constraint problems. First experiments on a set of realistic benchmarks show that such dedicated strategies outperform standard search and splitting strategies.

关键词： Aerospace industry

来源：评论

学校读者我要写书评

暂无评论

Preference Elicitation for DCOPs 23rd

Preference Elicitation for DCOPs

引用

作者： Tabakhi, Atena M. Le, Tiep Fioretto, Ferdinando Yeoh, William Washington Univ Dept Comp Sci & Engn St Louis MO 63110 USA New Mexico State Univ Dept Comp Sci Las Cruces NM 88003 USA Univ Michigan Dept Ind & Operat Engn Ann Arbor MI 48109 USA

ISBN: (纸本)9783319661582;9783319661575

Distributed constraint Optimization Problems (DCOPs) offer a powerful approach for the description and resolution of cooperative multi-agent problems. In this model, a group of agents coordinate their actions to optimize a global objective function, taking into account their preferences or constraints. A core limitation of this model is the assumption that the preferences of all agents or the costs of all constraints are specified a priori. Unfortunately, this assumption does not hold in a number of application domains where preferences or constraints must be elicited from the users. One of such domains is the Smart Home Device Scheduling (SHDS) problem. Motivated by this limitation, we make the following contributions in this paper: (1) We propose a general model for preference elicitation in DCOPs;(2) We propose several heuristics to elicit preferences in DCOPs;and (3) We empirically evaluate the effect of these heuristics on random binary DCOPs as well as SHDS problems.

关键词： Distributed constraint Optimization Smart homes Preference elicitation

来源：评论

学校读者我要写书评

暂无评论

A Column-Generation Algorithm for Evacuation Planning with Elementary Paths 23rd

A Column-Generation Algorithm for Evacuation Planning with E...

引用

作者： Hasan, Mohd. Hafiz Van Hentenryck, Pascal Univ Michigan Ann Arbor MI 48109 USA

ISBN: (纸本)9783319661582;9783319661575

Evacuation planning algorithms are critical tools for assisting authorities in orchestrating large-scale evacuations while ensuring optimal utilization of resources. To be deployed in practice, these algorithms must include a number of constraints that dramatically increase their complexity. this paper considers the zone-based non-preemptive evacuation planning problem in which each evacuation zone is assigned a unique evacuation path to safety and the flow of evacuees over time for a given zone follows one of a set of specified response curves. the starting point of the paper is the recognition that the first and only optimization algorithm previously proposed for zone-based non-preemptive evacuation planning may produce non-elementary paths, i.e., paths that visit the same node multiple times over the course of the evacuation. Since non-elementary paths are undesirable in practice, this paper proposes a column-generation algorithm where the pricing subproblem is a least-cost path under constraints. the paper investigates a variety of algorithms for solving the subproblem as well as their hybridization. Experimental results on a real-life case study show that the new algorithm produces evacuation plans with elementary paths of the same quality as the earlier algorithm in terms of the number of evacuees reaching safety and the completion time of the evacuation, at the expense of a modest increase in CPU time.

关键词： Column generation Evacuation planning k-shortest paths Mixed-integer programming constraint programming

来源：评论

学校读者我要写书评

暂无评论

A constraint Composite Graph-Based ILP Encoding of the Boolean Weighted CSP 23rd

A Constraint Composite Graph-Based ILP Encoding of the Boole...

引用

作者： Xu, Hong Koenig, Sven Kumar, T. K. Satish Univ Southern Calif Los Angeles CA 90089 USA

ISBN: (纸本)9783319661582;9783319661575

the weighted constraint satisfaction problem (WCSP) occurs in the crux of many real-world applications of operations research, artificial intelligence, bioinformatics, etc. Despite its importance as a combinatorial substrate, many attempts for building an efficient WCSP solver have been largely unsatisfactory. In this paper, we introduce a new method for encoding a (Boolean) WCSP instance as an integer linear program (ILP). this encoding is based on the idea of the constraint composite graph (CCG) associated with a WCSP instance. We show that our CCG-based ILP encoding of the Boolean WCSP is significantly more efficient than previously known ILP encodings. theoretically, we show that the CCG-based ILP encoding has a number of interesting properties. Empirically, we show that it allows us to solve many hard Boolean WCSP instances that cannot be solved by ILP solvers with previously known ILP encodings.

关键词： constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

Program completion in the input language of GRINGO

引用

thEORY AND practice OF LOGIC programming 2017年第5-6期17卷 855-871页

作者： Harrison, Amelia Lifschitz, Vladimir Raju, Dhananjay Dept Comp Sci Austin TX 78712 USA

We argue that turning a logic program into a set of completed definitions can be sometimes thought of as the "reverse engineering" process of generating a set of conditions that could serve as a specification for it. Accordingly, it may be useful to define completion for a large class of Answer Set programming (ASP) programs and to automate the process of generating and simplifying completion formulas. Examining the output produced by this kind of software may help programmers to see more clearly what their program does, and to what degree its behavior conforms with their expectations. As a step toward this goal, we propose here a definition of program completion for a large class of programs in the input language of the ASP grounder gringo, and study its properties.

关键词： formal methods program completion Answer Set programming

来源：评论

学校读者我要写书评

暂无评论

Kernelization of constraint Satisfaction Problems: A Study through Universal Algebra 23rd

Kernelization of Constraint Satisfaction Problems: A Study T...

引用

作者： Lagerkvist, Victor Wahlstrom, Magnus Tech Univ Dresden Inst Algebra Dresden Germany Royal Holloway Univ London Dept Comp Sci Egham Surrey England

ISBN: (纸本)9783319661582;9783319661575

A kernelization algorithm for a computational problem is a procedure which compresses an instance into an equivalent instance whose size is bounded with respect to a complexity parameter. For the constraint satisfaction problem (CSP), there exist many results concerning upper and lower bounds for kernelizability of specific problems, but it is safe to say that we lack general methods to determine whether a given problem admits a kernel of a particular size. In this paper, we take an algebraic approach to the problem of characterizing the kernelization limits of NP-hard CSP problems, parameterized by the number of variables. Our main focus is on problems admitting linear kernels, as has, somewhat surprisingly, previously been shown to exist. We show that a finite-domain CSP problem has a kernel with O(n) constraints if it can be embedded (via a domain extension) into a CSP which is preserved by a Maltsev operation. this result utilise a variant of the simple algorithm for Maltsev constraints. In the complementary direction, we give indication that the Maltsev condition might be a complete characterization for Boolean CSPs with linear kernels, by showing that an algebraic condition that is shared by all problems with a Maltsev embedding is also necessary for the existence of a linear kernel unless NP subset of co-NP/poly.

关键词： constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：