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

constraint programming next challenge: Simplicity of use

10th international conference on principles and practice of constraint programming, CP 2004

作者： Puget, Jean-Francois ILOG 9 avenue de Verdun Gentilly France

ISBN: (纸本)3540232419

constraint programming (CP) is a healthy research area in the academic community. the growing number of participants to the CP conference series, as well as the number of workshops around CP is a good evidence of it. Many major conferences have a CP track, both in artificial intelligence, and in operations research. the existence of several commercial companies that offer CP tools and services is a further evidence of the value of CP as an industrial technology. ILOG is one of such companies. One of our uniqueness, as far as CP is concerned, is that the research and development team that produces our CP products is also responsible for the development of our mathematical programming (MP) tool, namely ILOG CPLEX. this provides a unique opportunity to contrast the way these products are developed, marketed and used. In this paper we argue that current CP technology is much too complex to use for the average engineer. Worse, we believe that much of the research occurring in the CP academic community makes this even worse every year. the rest of the paper provides evidence for this claim, and suggests ways to address the issue of simplicity of use by looking at how a similar issue has been addressed in the mathematical programming community.

关键词：

来源：评论

学校读者我要写书评

暂无评论

A pseudo-boolean set covering machine

A pseudo-boolean set covering machine

引用

18th international conference on principles and practice of constraint programming, CP 2012

作者： Germain, Pascal Giguère, Sébastien Roy, Jean-Francis Zirakiza, Brice Laviolette, François Quimper, Claude-Guy Département d'Informatique et de Génie Logiciel Université Laval Québec QC Canada

ISBN: (纸本)9783642335570

the Set Covering Machine (SCM) is a machine learning algorithm that constructs a conjunction of Boolean functions. this algorithm is motivated by the minimization of a theoretical bound. However, finding the optimal conjunction according to this bound is a combinatorial problem. the SCM approximates the solution using a greedy approach. Even though SCM seems very efficient in practice, it is unknown how it compares to the optimal solution. To answer this question, we present a novel pseudo-Boolean optimization model that encodes the minimization problem. It is the first time a constraint programming approach addresses the combinatorial problem related to this machine learning algorithm. Using that model and recent pseudo-Boolean solvers, we empirically show that the greedy approach is surprisingly close to the optimal. © 2012 Springer-Verlag.

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

A hybrid method for planning and scheduling

引用

10th international conference on principles and practice of constraint programming, CP 2004

作者： Hooker, John N. Carnegie Mellon University United States

ISBN: (纸本)3540232419

We combine mixed integer linear programming (MILP) and constraint programming (CP) to solve planning and scheduling problems. Tasks are allocated to facilities using MILP and scheduled using CP, and the two are linked via logic-based Benders decomposition. Tasks assigned to a facility may run in parallel subject to resource constraints (cumulative scheduling). We solve minimum cost problems, as well as minimum makespan problems in which all tasks have the same release date and deadline. We obtain computational speedups of several orders of magnitude relative to the state of the art in both MILP and CP. © Springer-Verlag Berlin Heidelberg 2004.

关键词： constraint 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

It is well-known that variable ordering heuristics play a central role in solving efficiently constraint Satisfaction Problem (CSP) instances. From the early 809;s, and during more than two decades, the dynamic var... 详细信息

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

来源：评论

学校读者我要写书评

暂无评论

Solving large-scale nonlinear programming problems by constraint partitioning

引用

11th international conference on principles and practice of constraint programming - CP 2005

作者： Wah, Benjamin W. Chen, Yixin Department of Electrical and Computer Engineering Coordinated Science Laboratory University of Illinois Urbana-Champaign Urbana IL 6180I United States

ISBN: (纸本)3540292381

In this paper, we present a constraint-partitioning approach for finding local optimal solutions of large-scale mixed-integer nonlinear programming problems (MINLPs). Based on our observation that MINLPs in many engineering applications have highly structured constraints, we propose to partition these MINLPs by their constraints into subproblems, solve each subproblem by an existing solver, and resolve those violated global constraints across the subproblems using our theory of extended saddle points. constraint partitioning allows many MINLPs that cannot be solved by existing solvers to be solvable because it leads to easier subproblems that are significant relaxations of the original problem. the success of our approach relies on our ability to resolve violated global constraints efficiently, without requiring exhaustive enumerations of variable values in these constraints. We have developed an algorithm for automatically partitioning a large MINLP in order to minimize the number of global constraints, an iterative method for determining the optimal number of partitions in order to minimize the search time, and an efficient strategy for resolving violated global constraints. Our experimental results demonstrate significant improvements over the best existing solvers in terms of solution time and quality in solving a collection of mixed-integer and continuous nonlinear constrained optimization benchmarks. © Springer-Verlag Berlin Heidelberg 2005.

关键词： Nonlinear programming

来源：评论

学校读者我要写书评

暂无评论

Improved Bounds of Integer Solution Counts via Volume and Extending to Mixed-Integer Linear constraints 30

Improved Bounds of Integer Solution Counts via Volume and Ex...

引用

30th international conference on principles and practice of constraint programming, CP 2024

作者： Ge, Cunjing Biere, Armin National Key Laboratory for Novel Software Technology Nanjing University China School of Artificial Intelligence Nanjing University China University of Freiburg Germany

ISBN: (纸本)9783959773362

Solution counting and solution space integration over linear constraints are important problems with many applications. Previous works addressed either only counting integer points in polytopes (integer counting) with integer variables or alternatively only computing the volume of polytopes (solution space integration) on variables over the reals, including approximating the integer count via a polytope's volume. We are not aware of a non-trivial algorithm which addresses the mixed case, where linear constraints are over mixed integer and real variables. In this paper, we propose a new randomized algorithm to approximate guarantees (bounds) of integer solution counts. then we present upper and lower bounds for solution space integration over mixed-integer linear constraints. thus, proposed algorithms can be extended to mixed-integer cases as well. the experiments show that approximations are often very close to exact results in practice, and bounds approximated by our algorithm are often tight and useful. © Cunjing Ge and Armin Biere.

关键词： Mixed-integer linear programming

来源：评论

学校读者我要写书评

暂无评论

A constraint programming approach to the stable marriage problem 1

引用

7th international conference on principles and practice of constraint programming, CP 2001

作者： Gent, Ian P Irving, Robert W Manlove, David F Prosser, Patrick Smith, Barbara M School of Computer Science University of St. Andrews United Kingdom Department of Computing Science University of Glasgow United Kingdom School of Computing and Mathematics University of Huddersfield United Kingdom

ISBN: (数字)9783540455783

ISBN: (纸本)3540428631

the Stable Marriage problem (SM) is an extensively-studied combinatorial problem with many practical applications. In this paper we present two encodings of an instance I of SM as an instance J of a constraint Satisfaction Problem. We prove that, in a precise sense, establishing arc consistency in J is equivalent to the action of the established Extended Gale/Shapley algorithm for SM on I. As a consequence of this, the man-optimal and woman-optimal stable matchings can be derived immediately. Furthermore we show that, in both encodings, all solutions of I may be enumerated in a failure-free manner. Our results indicate the applicability of constraint programming to the domain of stable matching problems in general, many of which are NP-hard. © Springer-Verlag Berlin Heidelberg 2001.

关键词： constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

Symmetry breaking constraints for value symmetries in constraint satisfaction

引用

constraintS 2006年第2-3期11卷 221-267页

作者： Law, Y. C. Lee, J. H. M. Chinese Univ Hong Kong Dept Comp Sci & Engn Shatin Hong Kong Peoples R China

constraint satisfaction problems (CSPs) sometimes contain both variable symmetries and value symmetries, causing adverse effects on CSP solvers based on tree search. As a remedy, symmetry breaking constraints are commonly used. While variable symmetry breaking constraints can be expressed easily and propagated efficiently using lexicographic ordering, value symmetry breaking constraints are often difficult to formulate. In this paper, we propose two methods of using symmetry breaking constraints to tackle value symmetries. First, we show theoretically when value symmetries in one CSP correspond to variable symmetries in another CSP of the same problem. We also show when variable symmetry breaking constraints in the two CSPs, combined using channeling constraints, are consistent. Such results allow us to tackle value symmetries efficiently using additional CSP variables and channeling constraints. Second, we introduce value precedence, a notion which can be used to break a common class of value symmetries, namely symmetries of indistinguishable values. While value precedence can be expressed using inefficient if-then constraints in existing CSP solvers, we propose efficient propagation algorithms for implementing global value precedence constraints. We also characterize several theoretical properties of the value precedence constraints. Extensive experiments are conducted to verify the feasibility and efficiency of the two proposals.

关键词： symmetry breaking value symmetries constraint satisfaction

来源：评论

学校读者我要写书评

暂无评论

constraint programming: An efficient and practical approach to solving the job-shop problem 2nd

Constraint programming: An efficient and practical approach ...

引用

2nd international conference on principles and practice of constraint programming, CP 1996

作者： Colombani, Yves Laboratoire D’Informatique De Marseille-URA CNRS 1787 163 av. De Luminy Marseille Cedex 913288 France

ISBN: (纸本)3540615512

Recent improvements in constraint programming have made it possible to tackle hard problems in a practical way. Before this, these problems were solved only by specialized programs often complex to implement. Scheduling problems and more especially the job-shop problem belong to this class. In this paper we explain a relatively simple constraint system, which enables us to solve 10 x 10 problems efficiently. the method described here, based on evaluations which come as close as possible to release and due dates of jobs to be scheduled, requires no prior knowledge of the problem being processed, in particular, no bounds over optimum value (consequently no specific algorithm to find approximate solutions). We also comment on the results of experiments on known problems. As far as we know, the system outlined here is the only one that, using just constraint solving and an exhaustive enumeration strategy, can completely solve orb3[AC91] in less than half an hour computational time. © Springer-Verlag Berlin Heidelberg 1996.

关键词： Job shop scheduling

来源：评论

学校读者我要写书评

暂无评论

PW-AC: Extending compact-table to enforce pairwise consistency on table constraints 24th

PW-AC: Extending compact-table to enforce pairwise consisten...

引用

24th international conference on the principles and practice of constraint programming, CP 2018

作者： Schneider, Anthony Choueiry, Berthe Y. Constraint Systems Laboratory University of Nebraska-Lincoln Lincoln United States

ISBN: (纸本)9783319983332

the Compact-Table (CT) algorithm is the current state-of-the-art algorithm for enforcing Generalized Arc Consistency (GAC) on table constraints during search. Recently, algorithms for enforcing Pairwise Consistency (PWC), which is strictly stronger than GAC, were shown to be advantageous for solving difficult problems. However, PWC algorithms can be costly in terms of CPU time and memory consumption. As a result, their overhead may offset the savings of search-space reduction. In this paper, we introduce PW-CT, an algorithm that modifies CT to enforce full PWC. We show that PW-CT avoids the high memory requirements of prior PWC algorithms and significantly reduces the time required to enforce PWC. © Springer Nature Switzerland AG 2018.

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：