In [1] we presented the language TOY (FD) that integrates the best features of existing functional and logic languages, as well as finite domain (FD) constraint solving. We believe that TOY (FD) is more flexible and e...
详细信息
ISBN:
(纸本)3540292381
In [1] we presented the language TOY (FD) that integrates the best features of existing functional and logic languages, as well as finite domain (FD) constraint solving. We believe that TOY (FD) is more flexible and expressive than the existing approaches of constraint logic programming on finite domain (CLP(FD)) as it integrates FD constraint solving, lazy evaluation, higher order applications of functions and constraints, polymorphism, type checking, composition of functions (and, in particular, constraints), combination of relational and functional notation, and a number of other characteristics. these features allow to write more concise programs, therefore increasing the expressivity level. Prom an implementation point of view, TOY (FD) integrates the higher-order lazy functional logic language TOY and the efficient FD constraint solver of SICStus Prolog. From a programming point of view, TOY (FD) is the first constraint functional logic programming system that provides a wide set of FD constraints comparable to existing CLP(FD) systems and which is competitive withthem. TOY(FD) supports relational constraints including equality, disequality, arithmetical operators on constraints, a wide set of well-known global constraints (e.g., all_different/1), membership constraints (e.g., domain/3), propositional constraints, and enumeration constraints (e.g., labeling/2, with a number of strategies) with optimization. TOY (FD) also provides a glass box approach via a set of predefined functions called reflection constraints that allow, at runtime, to recover internal information about the constraint solving process. these functions increase the flexibility of the language as they allow the user to construct specific constraint mechanisms such as new search strategies. Generally speaking, TOY(FD) is, from its nature, different to all existing CLP(FD) languages as its operational mechanism is the result of combining the operational methods of logic languages (i.e., unific
the annual international Trading Agent Competition-Supply Chain Management (TAC-SCM) game is based around the manufacture and supply of PCs. there are multiple agents in the game, scheduling production, competing for ...
详细信息
ISBN:
(纸本)3540292381
the annual international Trading Agent Competition-Supply Chain Management (TAC-SCM) game is based around the manufacture and supply of PCs. there are multiple agents in the game, scheduling production, competing for orders from customers and components from suppliers. A key decision to be made each day in the game is what offers should be made to customers. Each day, the agents receive a set of request for quotes (RFQ) from customers, agents respond with offers, and then the customers select the lowest bid. We have developed an agent to compete in the competition that combines constraint-based optimisation, reasoning with probabilities, and learning of market conditions in an attempt to determine what customer requests to bid on and what prices to bid. Our agent maintains prices that correspond to different probabilities of success in winning contracts, using an online learning approach. By keeping track of the ratio of offers accepted to those made, the prices can be updated iteratively to move closer to their target probability. this range of price/probability pairs is then used as input to a constraint model. For each request, the model chooses whether or not to bid, and selects a price from the range. these decisions are restricted by capacity and supply constraints. A capacity constraint ensures that we will be able to schedule any new orders we receive with existing orders such that the factory capacity for each day in the current horizon is not exceeded. the agents production ability is also subject to component availability, By ordering components in advance, we know the current amount of components available, and we also know how much of each component will be arriving at each clay. this allows us to add a constraint for availability of supplies. An objective function is specified that maximises our expected profit, where the profit on a request is calculated by subtracting from the selling price the cost of components together with late delivery penalties
In this paper, we present AC-*, a new configurable, generic and adaptive algorithm for establishing arc consistency for binary constraints. AC-* is configurable, that is by combining some parameters AC-* corresponds t...
详细信息
Factor analysis is a statistical technique for reducing the number of factors responsible for a matrix of correlations to a smaller number of factors that may reflect underlying variables. In this study factor analysi...
详细信息
One of the critical problems in the call center industries is the staffing problem, since they must face variable demands and because staff costs represent a major part of the costs of these industries. Prom a modelin...
详细信息
Preferences and uncertainty occur in many real-life problems. We are concerned withthe coexistence of preference and uncertainty in the same problem. In particular, we consider uncertainty, defined by the theory of p...
详细信息
We present an incomplete filtering algorithm for the circuit constraint. the filter removes redundant values by eliminating non-Hamiltonian edges from the associated graph. We prove a necessary condition for an edge t...
详细信息
ISBN:
(纸本)3540292381
We present an incomplete filtering algorithm for the circuit constraint. the filter removes redundant values by eliminating non-Hamiltonian edges from the associated graph. We prove a necessary condition for an edge to be Hamiltonian, which provides the basis for eliminating edges of a smaller graph defined on a separator of the original graph. the circuit constraint, circuit(y1,,yn}, where yj ∈ {1,,n}, is true if and only if for each j ∈ {1,, n}, y j is the successor of j in some permutation of 1 n and yj ∈ Dj, where Dj is the domain of variable j. On a graph of vertices 1,,n, the circuit constraint can be thought as defining a directed Hamiltonian cycle. Nodes of the graph represent the variables. A directed edge (i, j) exists if and only if j is in the domain of variable i. Moreover, elimination of an edge (i, j) from the graph means elimination of the value j from the domain of variable i. Withthis representation, the problem of domain reduction for the circuit constraint reduces to identifying and eliminating non-Hamiltonian edges on a digraph. In this paper, we present a recursive algorithm that eliminates non-Hamiltonian edges from the graph. A much smaller but denser multi-graph is constructed from a vertex separator S of the original graph by adding certain labelled edges to the subgraph induced by the separator. A directed edge (v, w) with label C is added if C is a connected component separated by S and (v, ci) and (cj, w) are edges of G for some pair of vertices ci, cj in C. We prove that edges that appear in no Hamiltonian cycle containing at least one edge of each component label in the constructed graph are non-Hamiltonian in the original graph. the condition that the constructed graph contains such a Hamiltonian cycle is viewed as a constraint. Global cardinality constraint with vertex degree constraints is a relaxation of this constraint. then by applying a filtering algorithm for the global cardinality constraint together with in and out-vertex de
In a constraint optimization problem for multiple agents, the agents have conflicting preferences in the final solution and the goal is to find an optimal assignment that maximizes total utilities of all agents. Two m...
详细信息
ISBN:
(纸本)3540292381
In a constraint optimization problem for multiple agents, the agents have conflicting preferences in the final solution and the goal is to find an optimal assignment that maximizes total utilities of all agents. Two major challenges when solving constraint optimization problems for multiple agents are the complexity of finding optimal solution and the incentive compatibility for participating agents. First, computing the optimal solution for large optimization problems are computationally infeasible and it can only be solved approximately by local search algorithms. Second, ensuring honest elicitation among self-interested agents is computationally expensive. It has been shown that the only known mechanism that guarantees truthfulness among agents requires computing optimal solutions, and sub-optimal solutions for such a mechanism will break the incentive compatibility ([2]). the long-term goal of our research is to solve these two challenges by using randomization in local search algorithms to find near-optimal solutions while ensuring incentive compatibility for bounded-rational agents. Our work is based on the observation that in real-world settings, the potential for manipulation is limited by uncertainty and risk. this uncertainty makes it difficult for a manipulator to predict the consequences of his manipulation and thus makes attempts at manipulating it uninteresting. In this paper we discuss a general randomization technique, called random subset optimization, for escaping from local minima in local search algorithms. In each local choice step, the local search procedure will randomly choose a part of the optimization function, and optimize for this part only. It turns out that this results in a more focussed optimization strategy and is shown to be especially effective in some hard optimization problems. We show that the uncertainty of our randomization algorithms can make the agents' manipulation hard, thus prevent bounded rational agents from manipulatin
the two most popular algorithms for solving constraint Satisfaction Problems are Forward Checking (FC) [1] and Maintaining Arc Consistency (MAC) [2]. MAC maintains full arc consistency while FC maintains a limited for...
详细信息
ISBN:
(纸本)3540292381
the two most popular algorithms for solving constraint Satisfaction Problems are Forward Checking (FC) [1] and Maintaining Arc Consistency (MAC) [2]. MAC maintains full arc consistency while FC maintains a limited form of arc consistency during search. there is no single champion algorithm: MAC is more efficient on sparse problems which are tightly constrained but FC has an increasing advantage as problems become dense and constraints loose. Ideally a good search algorithm should find the right balance - for any problem - between visiting fewer nodes in the search tree and reducing the work that is required to establish local consistency. In order to do so, we maintain probabilistic arc consistency during search. the idea is to assume that a support exists and skip the process of seeking a support if the probability of having some support for a value is at least equal to some, carefully chosen, stipulated threshold. Arc consistency involves revisions of domains, which require support checks to remove unsupported values. In many revisions, some or all values find some support. If we can predict the existence of a support then a considerable amount of work can be saved. In order to do so, we propose the notions of a Probabilistic Support Condition (PSC) and Probabilistic Revision Condition (PRC). If PSC holds then the probability of having some support for a value is at least equal to the threshold and the process of seeking a support is skipped. If PRC holds then for each value the probability of having some support is at least equal to the threshold and the corresponding revision is skipped. For hard dense problems constraint are generally loose, and on average each value has several supports, in which case the probability of having some support remains high for a while with respect to the number of values removed. this enables PSC and PRC to save checks. For hard sparse problems constraints are generally tight, and on average each value has only a few supports, in
the proceedings contain 97 papers. the special focus in this conference is on principles and practice of constraintprogramming. the topics include: constraints in program analysis and verification;algorithmic adventu...
ISBN:
(纸本)3540232419
the proceedings contain 97 papers. the special focus in this conference is on principles and practice of constraintprogramming. the topics include: constraints in program analysis and verification;algorithmic adventures at the interface of computer science, statistical physics, and combinatorics;challenges for constraintprogramming in networking;consistency and random constraint satisfaction models with a high constraint tightness;statistical regimes across constrainedness regions;unary resource constraint with optional activities;backtrack-free search for real-time constraint satisfaction;deriving filtering algorithms from constraint checkers;leveraging the learning power of examples in automated constraint acquisition;disjoint, partition and intersection constraints for set and multiset variables;decomposition and learning for a hard real time task allocation problem;quantified constraint satisfaction and 2-semilattice polymorphisms;heuristic selection for stochastic search optimization;a complete characterization of complexity for Boolean constraint optimization problems;bounding the resource availability of partially ordered events with constant resource impact;a domain consistency algorithm for the stretch constraint;counting-based look-ahead schemes for constraint satisfaction;completable partial solutions in constraintprogramming and constraint-based scheduling;global constraints for integer and set value precedence;constraint satisfaction in semi-structured data graphs;strategies for global optimization of temporal preferences;propagation guided large neighborhood search;generating robust partial order schedules;improved bound computation in presence of several clique constraints;controllability of soft temporal constraint problems and solving non-clausal formulas with DPLL search.
暂无评论