constraintprogramming (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. ...
ISBN:
(纸本)3540232419
constraintprogramming (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.
We combine mixed integer linear programming (MILP) and constraintprogramming (CP) to solve planning and scheduling problems. Tasks are allocated to facilities using MILP and scheduled using CP, and the two are linked...
详细信息
Generating all constitutional isomers (chemical compounds that have the same molecular formula but different chemical structures) is a challenging problem. the structures are normally represented by molecular graphs, ...
ISBN:
(纸本)3540232419
Generating all constitutional isomers (chemical compounds that have the same molecular formula but different chemical structures) is a challenging problem. the structures are normally represented by molecular graphs, where vertices are atoms and edges are chemical bonds. the degree of a vertex in the graph represents the valency of the corresponding atom. the problem can be extended to generating all sets of molecules that can result from a reaction. I have formulated this chemistry problem as a constraint satisfaction problem (CSP). As an initial representation of the problem, I represent each bond as a pair of variables. the atoms are represented by integers and connected by the bonds. the domain of each variable is all of the atoms in the problem. Each atom must appear a fixed number of times (its valency). For example, consider a problem that consists of two oxygens, two carbons and four hydrogens, i.e. eight atoms in three types. the number of bonds is half the sum of the atoms valencies. For the sample problem we need 8 bonds. It is easy to specify the valency constraint with help of the Ilog Solver constraint IloDistribute, which restricts the appearance of variables that take a given value in an array. We believe this is the first constraint encoding of the problem.
Bound consistency can easily and efficiently be enforced on linear constraint. However, bound consistency techniques deal with every constraint separately. We show that in some cases much stronger bounds can be comput...
详细信息
the paper introduces value precedence on integer and set sequences. A useful application of the notion is in breaking symmetries of indistinguishable values, an important class of symmetries in practice. Although valu...
详细信息
this paper presents an algorithm that achieves hyper-arc consistency for the soft alldifferent constraint. To this end, we prove and exploit the equivalence with a minimum-cost flow problem. Consistency of the constra...
详细信息
Many combinatorial optimization problems do not have a clear structure, may present many side constraints, and may include subproblems. In addition, different instances within the same domain can have different struct...
ISBN:
(纸本)3540232419
Many combinatorial optimization problems do not have a clear structure, may present many side constraints, and may include subproblems. In addition, different instances within the same domain can have different structure and characteristics. As a consequence it is commonplace that a single algorithm is not the best performer on every problem instance. We consider an algorithm portfolio approach to try to help us select the best algorithm for a given problem instance. Our purpose is twofold: firstly, to show that structure at the instance level is tightly connected to algorithm performance, and secondly to demonstrate that different machine learning and modelling methodologies, specifically Decision Trees (DT), Case Based Reasoning (CBR) and Multinomial Logistic Regression (MLR), can be used to perform effective algorithm portfolio selection. We test our claims by applying the above mentioned techniques to a large set of instances of the Bid Evaluation Problem (BEP) in Combinatorial Auctions. A BEP consists of a Winner Determination Problem (a well-known NP-hard problem best solved by a IP-based approach), and additional temporal information and precedence constraints (which favour a CP-based approach). We solved the BEP instances using a set of different algorithms. We observed that two algorithms; one IP-based and the other a hybrid combining both CP and IP elements, outperformed all the others on all instances. Hence we divided the instances into 2 classes based on which of these 2 algorithms solves them best. In order to perform our analysis we extract a set of structure-based features, that are cheap to determine, from each instance . We apply the Machine Learning methodologies using the extracted features as input data and the best algorithms as prediction classes.
Although algorithms for Distributed constraint Optimization Problems (DCOPs) have emerged as a key technique for distributed reasoning, their application faces significant hurdles in many multiagent domains due to the...
详细信息
constraintprogramming is rapidly becoming the technology of choice for modeling and solving complex combinatorial problems. However, users of constraintprogramming technology need significant expertise in order to m...
详细信息
We study the global cardinality constraint (gcc) and propose an O(n1.5d) algorithm for domain consistency and an O(cn + dn) algorithm for range consistency where n is the number of variables, d the number of values in...
详细信息
暂无评论