The Experts below are selected from a list of 16308 Experts worldwide ranked by ideXlab platform
Patrick Prosser - One of the best experts on this subject based on the ideXlab platform.
-
a specialised Binary Constraint for the stable marriage problem
Symposium on Abstraction Reformulation and Approximation, 2005Co-Authors: Chris Unsworth, Patrick ProsserAbstract:We present a specialised Binary Constraint for the stable marriage problem. This Constraint acts between a pair of integer variables where the domains of those variables represent preferences. Our Constraint enforces stability and disallows bigamy. For a stable marriage instance with n men and women we require n2 of these Constraints, and the complexity of enforcing arc-consistency is O(n3). Although this is non-optimal, empirical evidence suggests that in practical terms our encoding significantly outperforms the optimal encoding given in [7] in both space and time.
-
SARA - A specialised Binary Constraint for the stable marriage problem
Lecture Notes in Computer Science, 2005Co-Authors: Chris Unsworth, Patrick ProsserAbstract:We present a specialised Binary Constraint for the stable marriage problem. This Constraint acts between a pair of integer variables where the domains of those variables represent preferences. Our Constraint enforces stability and disallows bigamy. For a stable marriage instance with n men and women we require n2 of these Constraints, and the complexity of enforcing arc-consistency is O(n3). Although this is non-optimal, empirical evidence suggests that in practical terms our encoding significantly outperforms the optimal encoding given in [7] in both space and time.
-
An empirical study of phase transitions in Binary Constraint satisfaction problems
Artificial Intelligence, 1996Co-Authors: Patrick ProsserAbstract:Abstract An empirical study of randomly generated Binary Constraint satisfaction problems reveals that for problems with a given number of variables, domain size, and connectivity there is a critical level of Constraint tightness at which a phase transition occurs. At the phase transition, problems change from being soluble to insoluble, and the difficulty of problems increases dramatically. A theory developed by Williams and Hogg [44], and independently developed by Smith [37], predicts where the hardest problems should occur. It is shown that the theory is in close agreement with the empirical results, except when Constraint graphs are sparse.
Jano Van Hemert - One of the best experts on this subject based on the ideXlab platform.
-
A Study into Ant Colony Optimization, Evolutionary Computation and Constraint Programming on Binary Constraint Satisfaction Problems
2004Co-Authors: Jano Van Hemert, C. SolnonAbstract:We compare two heuristic approaches, evolutionary computation and ant colony optimisation, and a complete tree-search approach, Constraint programming, for solving Binary Constraint satisfaction problems. We experimentally show that, if evolutionary computation is far from being able to compete with the two other approaches, ant colony optimisation nearly always succeeds in finding a solution, so that it can actually compete with Constraint programming. The resampling ratio is used to provide insight into heuristic algorithms performances. Regarding efficiency, we show that if Constraint programming is the fastest when instances have a low number of variables, ant colony optimisation becomes faster when increasing the number of variables.
-
EvoCOP - A Study into Ant Colony Optimisation, Evolutionary Computation and Constraint Programming on Binary Constraint Satisfaction Problems
Evolutionary Computation in Combinatorial Optimization, 2004Co-Authors: Jano Van Hemert, C. SolnonAbstract:We compare two heuristic approaches, evolutionary computation and ant colony optimisation, and a complete tree-search approach, Constraint programming, for solving Binary Constraint satisfaction problems. We experimentally show that, if evolutionary computation is far from being able to compete with the two other approaches, ant colony optimisation nearly always succeeds in finding a solution, so that it can actually compete with Constraint programming. The resampling ratio is used to provide insight into heuristic algorithms performances. Regarding efficiency, we show that if Constraint programming is the fastest when instances have a low number of variables, ant colony optimisation becomes faster when increasing the number of variables.
-
Robust Parameter Settings for Variation Operators by Measuring the Resampling Ratio: A Study on Binary Constraint Satisfaction Problems
Journal of Heuristics, 2004Co-Authors: Jano Van Hemert, Thomas BäckAbstract:In this article, we try to provide insight into the consequence of mutation and crossover rates when solving Binary Constraint satisfaction problems. This insight is based on a measurement of the space searched by an evolutionary algorithm. From data empirically acquired we describe the relation between the success ratio and the searched space. This is achieved using the resampling ratio, which is a measure for the amount of points revisited by a search algorithm. This relation is based on combinations of parameter settings for the variation operators. We then show that the resampling ratio is useful for identifying the quality of parameter settings, and provide a range that corresponds to robust parameter settings.
-
comparing classical methods for solving Binary Constraint satisfaction problems with state of the art evolutionary computation
Lecture Notes in Computer Science, 2002Co-Authors: Jano Van HemertAbstract:Constraint Satisfaction Problems form a class of problems that are generally computationally difficult and have been addressed with many complete and heuristic algorithms. We present two complete algorithms, as well as two evolutionary algorithms, and compare them on randomly generated instances of Binary Constraint satisfaction problems. We find that the evolutionary algorithms are less effective than the classical techniques.
-
EvoWorkshops - Comparing Classical Methods for Solving Binary Constraint Satisfaction Problems with State of the Art Evolutionary Computation
Lecture Notes in Computer Science, 2002Co-Authors: Jano Van HemertAbstract:Constraint Satisfaction Problems form a class of problems that are generally computationally difficult and have been addressed with many complete and heuristic algorithms. We present two complete algorithms, as well as two evolutionary algorithms, and compare them on randomly generated instances of Binary Constraint satisfaction problems. We find that the evolutionary algorithms are less effective than the classical techniques.
Chris Unsworth - One of the best experts on this subject based on the ideXlab platform.
-
a specialised Binary Constraint for the stable marriage problem
Symposium on Abstraction Reformulation and Approximation, 2005Co-Authors: Chris Unsworth, Patrick ProsserAbstract:We present a specialised Binary Constraint for the stable marriage problem. This Constraint acts between a pair of integer variables where the domains of those variables represent preferences. Our Constraint enforces stability and disallows bigamy. For a stable marriage instance with n men and women we require n2 of these Constraints, and the complexity of enforcing arc-consistency is O(n3). Although this is non-optimal, empirical evidence suggests that in practical terms our encoding significantly outperforms the optimal encoding given in [7] in both space and time.
-
SARA - A specialised Binary Constraint for the stable marriage problem
Lecture Notes in Computer Science, 2005Co-Authors: Chris Unsworth, Patrick ProsserAbstract:We present a specialised Binary Constraint for the stable marriage problem. This Constraint acts between a pair of integer variables where the domains of those variables represent preferences. Our Constraint enforces stability and disallows bigamy. For a stable marriage instance with n men and women we require n2 of these Constraints, and the complexity of enforcing arc-consistency is O(n3). Although this is non-optimal, empirical evidence suggests that in practical terms our encoding significantly outperforms the optimal encoding given in [7] in both space and time.
A G Steenbeek - One of the best experts on this subject based on the ideXlab platform.
-
a genetic local search algorithm for random Binary Constraint satisfaction problems
ACM Symposium on Applied Computing, 2000Co-Authors: Elena Marchiori, A G SteenbeekAbstract:This paper introduces a genetic local search algorithm for bi nary Constraint satisfaction problems. The core of the algo rithm consists of an ad-hoc optimization procedure followed by the application of blind genetic operators. A standard set of benchmark instances is used in order to assess the performance of the algorithm. The results indicate that this apparently naive hybridation of a genetic algorithm with lo cal search yields a rather powerful heuristic algorithm for random Binary Constraint satisfaction problems.
-
SAC (1) - A genetic local search algorithm for random Binary Constraint satisfaction problems
Proceedings of the 2000 ACM symposium on Applied computing - SAC '00, 2000Co-Authors: Elena Marchiori, A G SteenbeekAbstract:This paper introduces a genetic local search algorithm for bi nary Constraint satisfaction problems. The core of the algo rithm consists of an ad-hoc optimization procedure followed by the application of blind genetic operators. A standard set of benchmark instances is used in order to assess the performance of the algorithm. The results indicate that this apparently naive hybridation of a genetic algorithm with lo cal search yields a rather powerful heuristic algorithm for random Binary Constraint satisfaction problems.
-
solving Binary Constraint satisfaction problems using evolutionary algorithms with an adaptive fitness function
Parallel Problem Solving from Nature, 1998Co-Authors: Jano Van Hemert, Elena Marchiori, A. E. Eiben, A G SteenbeekAbstract:This paper presents a comparative study of Evolutionary Algorithms (EAs) for Constraint Satisfaction Problems (CSPs). We focus on EAs where fitness is based on penalization of Constraint violations and the penalties are adapted during the execution. Three different EAs based on this approach are implemented. For highly connected Constraint networks, the results provide further empirical support to the theoretical prediction of the phase transition in Binary CSPs.
Meinolf Sellmann - One of the best experts on this subject based on the ideXlab platform.
-
the linear programming polytope of Binary Constraint problems with bounded tree width
Integration of AI and OR Techniques in Constraint Programming, 2007Co-Authors: Meinolf Sellmann, Luc Mercier, Daniel H LeventhalAbstract:We show how to efficiently model Binary Constraint problems (BCP) as integer programs. After considering tree-structured BCPs first, we show that a Sherali-Adams-like procedure results in a polynomial-size linear programming description of the convex hull of all integer feasible solutions when the BCP that is given has bounded tree-width.
-
CPAIOR - The Linear Programming Polytope of Binary Constraint Problems with Bounded Tree-Width
Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 2007Co-Authors: Meinolf Sellmann, Luc Mercier, Daniel H LeventhalAbstract:We show how to efficiently model Binary Constraint problems (BCP) as integer programs. After considering tree-structured BCPs first, we show that a Sherali-Adams-like procedure results in a polynomial-size linear programming description of the convex hull of all integer feasible solutions when the BCP that is given has bounded tree-width.
-
a totally unimodular description of the consistent value polytope for Binary Constraint programming
Integration of AI and OR Techniques in Constraint Programming, 2006Co-Authors: Ionuţ D Aron, Daniel H Leventhal, Meinolf SellmannAbstract:We present a theoretical study on the idea of using mathematical programming relaxations for filtering Binary Constraint satisfaction problems. We introduce the consistent value polytope and give a linear programming description that is provably tighter than a recently studied formulation. We then provide an experimental study that shows that, despite the theoretical progress, in practice filtering based on mathematical programming relaxations continues to perform worse than standard arc-consistency algorithms for Binary Constraint satisfaction problems.
-
CPAIOR - A totally unimodular description of the consistent value polytope for Binary Constraint programming
Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 2006Co-Authors: Ionuţ D Aron, Daniel H Leventhal, Meinolf SellmannAbstract:We present a theoretical study on the idea of using mathematical programming relaxations for filtering Binary Constraint satisfaction problems. We introduce the consistent value polytope and give a linear programming description that is provably tighter than a recently studied formulation. We then provide an experimental study that shows that, despite the theoretical progress, in practice filtering based on mathematical programming relaxations continues to perform worse than standard arc-consistency algorithms for Binary Constraint satisfaction problems.
-
CPAIOR - The polytope of tree-structured Binary Constraint satisfaction problems
Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 1Co-Authors: Meinolf SellmannAbstract:We correct a result that we recently published in this conference series on the polytope of Binary Constraint Problems (BCPs). We had claimed that the so-called "support formulation" would characterize the convex hull of all feasible solutions to tree-structured BCPs. We show that this claim is not accurate by providing a small counter example. We then show that the respective polytope defines a facet of the stable-set polytope of a perfect graph which allows us to perform LP inference in polynomial time.