It is known that the multiplication of an N ×M matrix with an M ×P matrix can be performed using fewer multiplications than what the naive NMP approach suggests. the most famous instance of this is Strassen&...
详细信息
In many situations, a set of hard constraints encodes the feasible configurations of some system or product over which users have preferences. We consider the problem of computing a best feasible solution when the use...
详细信息
ISBN:
(纸本)3540202021
In many situations, a set of hard constraints encodes the feasible configurations of some system or product over which users have preferences. We consider the problem of computing a best feasible solution when the user's utilities are partially known. Assuming bounds on utilities, efficient mixed integer linear programs are devised to compute the solution with minimax regret while exploiting generalized additive structure in a user's utility function.
constraint propagation is one of the techniques central to the success of constraintprogramming. Fast algorithms are used to prune the search space either before or during backtracking search. Propagating global cons...
详细信息
ISBN:
(纸本)3540232419
constraint propagation is one of the techniques central to the success of constraintprogramming. Fast algorithms are used to prune the search space either before or during backtracking search. Propagating global constraints is intractable in general. In this paper, we characterize a number of important questions related to constraint propagation. For example, we consider the two questions: "Is this problem generalized arc-consistent?" and "What are the maximal generalized arc-consistent domains?". We identify dependencies between the tractability and intractability of these questions for finite domain variables. Finally, we prove intractability for a range of global constraints.
System dynamics is often modeled by means of parametric differential equations. Despite their expressive power, they are difficult to reason about and make safe decisions, given their non-linearity and the important e...
详细信息
ISBN:
(纸本)3540202021
System dynamics is often modeled by means of parametric differential equations. Despite their expressive power, they are difficult to reason about and make safe decisions, given their non-linearity and the important effects that the uncertainty on data may cause. Either by traditional numerical simulation or relying on constraint based methods, it is difficult to express a number of constraints on the solution functions (for which there are usually no analytical solutions) and these constraints may only be handled passively, with generate and test techniques. In contrast, the framework we propose not only extends the declarativeness of the constraint based approach but also makes an active use of constraints on the solution functions, which makes it particularly suited for a number of decision making problems, such as those arising in the biomedical applications presented in the paper.
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.
the stretch constraint occurs in many rostering problems that arise in the industrial and public service sectors. In this paper we present an efficient algorithm for domain consistency propagation of the stretch const...
详细信息
ISBN:
(纸本)3540232419
the stretch constraint occurs in many rostering problems that arise in the industrial and public service sectors. In this paper we present an efficient algorithm for domain consistency propagation of the stretch constraint. Using benchmark and random instances, we show that this stronger consistency sometimes enables our propagator to solve more difficult problems than a previously proposed propagation algorithm for the stretch constraint. We also discuss variations of the stretch constraintthat seem simple and useful, but turn out to be intractable to fully propagate.
Despite boththe commercial and academic success of optimization technology and specifically constraintprogramming, using the technology still requires significant expertise. For non-trivial applications the quality ...
ISBN:
(纸本)3540232419
Despite boththe commercial and academic success of optimization technology and specifically constraintprogramming, using the technology still requires significant expertise. For non-trivial applications the quality of a system still has much to do withthe quality of the person that implemented it. We investigate algorithm control techniques aimed at achieving strong scheduling performance using off-the-shelf algorithms without requiring significant human expertise. Rather than building knowledge-intensive models relating algorithm performance to problem features, we base the control decisions on the evolution of solution quality over time. Such an approach is crucial to our goal of the reduction of expertise.
暂无评论