Most CSP algorithms are based on refinements arid extensions of backtracking, and employ one of two simple "branching schemes": 2-way branching or d-way branching, for domain size d. the schemes are not equi...
详细信息
constraint-Based Inference (CBI) [1] is an umbrella term for various superficially different problems including probabilistic inference, decision-making under uncertainty, constraint satisfaction, propositional satisf...
详细信息
ISBN:
(纸本)3540292381
constraint-Based Inference (CBI) [1] is an umbrella term for various superficially different problems including probabilistic inference, decision-making under uncertainty, constraint satisfaction, propositional satisfiability, decoding problems, and possibility inference. In this project we explicitly use the semiring concept to generalize various CBI problems into a single formal representation frame-work with a broader coverage of the problem space, based on the synthesis of existing generalized frameworks from bothconstraint processing and probability inference communities. Based on our generalized CBI framework, extensive comparative studies of exact and approximate inference approaches are commenced. First, we extend generalized arc consistency to probability inference based on a weaker condition [2]. All the existing arc consistency enforcing algorithms can be generalized and migrated to handle other concrete CBI problems that satisfy this condition. Second, based on our CBI framework we apply junction tree algorithms in probability inferences to solve soft CSPs [1]. We show that the message-passing schemes of junction tree algorithms can be modified to achieve better computational efficiency if the semiring of a CBI problem has additional properties. third, we study loopy message propagation in probability inference for general CBI problems. We claim in [1] that for CBI problems with a idempotent combination operator, the loopy message propagation is an exact inference approach. Our experimental results also show that the loopy message propagation yields high quality inference approximation for general CBI problems like Max CSPs. Finally, we discuss the possibilities of integrating stochastic approaches into our semiring-based CBI framework. We also discuss context-specific inference with backtracking as a promising inference approach for general CBI problems. In general, we are aiming at studying the most important common characteristics of various CBI prob
Recently, many algorithms have been designed to propagate global constraints. Unfortunately, some global constraints, such the AT-MOST-1 constraint and the EXTENDEDGCC are NP-Hard to propagate. Often, these constraint...
详细信息
In manufacturing scheduling, jobs may have uncertain earliest start times, caused by supplier lead-time uncertainty. How should we build initial schedules to be robust to these uncertain release dates? We are attempti...
详细信息
Representing and solving problems in terms of constraints can be difficult to do effectively. A single problem can be modeled in many different ways, either in terms of representation or in terms of the solving proces...
详细信息
ISBN:
(纸本)3540292381
Representing and solving problems in terms of constraints can be difficult to do effectively. A single problem can be modeled in many different ways, either in terms of representation or in terms of the solving process. Different approaches can outperform each other over different problem classes or even for different instances within the same class. It is possible that even the best combination of model and search on average is still too slow across a range of problems, taking orders of magnitude more time on some problems than combinations that are usually poorer. this fact complicates the use of constraints, and makes it very difficult for novice users to produce effective solutions. the modeling and solving process would be easier if we could develop robust algorithms, which perform acceptably across a range of problems. We present one method of developing a robust algorithm. We combine a single model and a single basic algorithm with a set of variable and value ordering heuristics, in a style similar to [1]. the aim is to exploit the variance among the orderings to get a more robust procedure, which may be slower on some problems, but avoids the significant deterioration on others. During the search, we allocate steadily increasing time slices to each ordering, restarting the search at each point. We demonstrate the performance of the multiple heuristic approach (MH) on a scheduling problem class [2] and on quasi groups with holes (QWH), showing that it is more robust and competitive than the standard recommended heuristic. We also compare to randomized restarts [3], the leading method for QWH and which uses a similar restart policy. We show that MH is poorer in run time and robustness on QWH, but better on the scheduling class. For the immediate future, we intend to investigate whether MH does perform better on insoluble problems (as indicated by the scheduling results). We will also tune the heuristics and time slices, and attempt to generate them automatical
For practical reasons, most scheduling problems are an abstraction of the real problem being solved. For example, when you plan your day, you schedule the activities which are critical;that is you schedule the activit...
详细信息
ISBN:
(纸本)3540292381
For practical reasons, most scheduling problems are an abstraction of the real problem being solved. For example, when you plan your day, you schedule the activities which are critical;that is you schedule the activities which are essential to the success of your day. So you may plan what time to leave the house to get to work, when to have meetings, how you share your vehicle with your spouse and so on. On the other hand, you probably do not consider the activities that are easy to arrange like brushing your teeth, going to the shops, making photocopies and other such tasks that can usually be accomplished whenever you have the time available. Scheduling all of these activities at once is often too complicated. Instead, a simpler schedule is produced by considering only the critical activities. However, if a schedule goes wrong, it is often because an activity turned out to be critical but was not scheduled. We typically learn which activities are critical by experience and create an abstract scheduling problem which includes all known critical activities. Instead of scheduling the non-critical activities we estimate their effects in the abstract scheduling problem. We are interested in automating this abstraction process for scheduling problems. In our approach, given a set of activities A to be scheduled1, we choose a subset of activities, critical(A), and create a simplified scheduling model which approximates the other activities non-critical(A) instead of scheduling them. We then search this abstract model for a good, if not optimal solution. A solution is a partial order schedule for activities in critical(A). this abstract solution is then extended to a solution the entire problem by inserting the remaining activities non-critical(A) into the schedule. While the approach reduces complexity by solving the problem in two stages it does so at a price. there is a risk that the good abstract solution will not produce a good solution to the entire problem. We know
We introduce a constraint for one-dimensional bin packing. this constraint uses propagation rules incorporating knapsack-based reasoning, as well as a lower bound on the number of bins needed. We show that this constr...
详细信息
ISBN:
(纸本)3540232419
We introduce a constraint for one-dimensional bin packing. this constraint uses propagation rules incorporating knapsack-based reasoning, as well as a lower bound on the number of bins needed. We show that this constraint can significantly reduce search on bin packing problems. We also demonstrate that when coupled with a standard bin packing search strategy, our constraint can be a competitive alternative to established operations research bin packing algorithms.
In this paper, we propose a general extension of constraint propagation for constraint optimization based on cooperative computation. It is similar both in principle and operations to constraint propagation. In princi...
详细信息
ISBN:
(纸本)3540232419
In this paper, we propose a general extension of constraint propagation for constraint optimization based on cooperative computation. It is similar both in principle and operations to constraint propagation. In principle, it eliminates variable values by checking the feasibility that they can be in any global optimum. In operations, it is based on parallel, local iterative computations. the proposed algorithm returns both a solution and a global lower bound at each iteration. As an approximation algorithm for optimization, it significantly outperform classical optimization methods, such as simulated annealing and local search with multi-restarts in practice.
In Online Problem Solving, partial solutions must be generated and executed before the complete problem is known. Many potential applications of constraintprogramming turn out to be online problems – for e...
ISBN:
(纸本)3540232419
In Online Problem Solving, partial solutions must be generated and executed before the complete problem is known. Many potential applications of constraintprogramming turn out to be online problems – for example, dynamic scheduling. How should we decide which values to assign to variables before all the variables and constraints are known? If we have some knowledge of the possible future developments of the problem, can we use that knowledge to make our initial assignments?
A key feature of constraintprogramming is the ability to design specific search strategies to solve problems. On the contrary, integer programming solvers have used efficient general-purpose strategies since their ea...
详细信息
ISBN:
(纸本)3540232419
A key feature of constraintprogramming is the ability to design specific search strategies to solve problems. On the contrary, integer programming solvers have used efficient general-purpose strategies since their earliest implementations. We present a new general purpose search strategy for constraintprogramming inspired from integer programming techniques and based on the concept of the impact of a variable. the impact measures the importance of a variable for the reduction of the search space. Impacts are learned from the observation of domain reduction during search and we show how restarting search can dramatically improve performance. Using impacts for solving multiknapsack, magic square, and Latin square completion problems shows that this new criteria for choosing variables and values can outperform classical general-purpose strategies.
暂无评论