How do we do research?We start with a question. then we read books, journal and conference papers, maybe even speak to people. then we do our own work, make our own contribution, maybe coming up with an improved techn...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
How do we do research?We start with a question. then we read books, journal and conference papers, maybe even speak to people. then we do our own work, make our own contribution, maybe coming up with an improved technique or a greater *** then write up our findings, maybe submit this to a conference, present our work and get feedback, and this results in further research. this is a feedback loop, open to scrutiny by our peers.
the tightness of a constraint refers to how restricted the constraint is. the existing work shows that there exists a relationship between tightness and global consistency of a constraint network. In this paper, we co...
详细信息
ISBN:
(纸本)3540232419
the tightness of a constraint refers to how restricted the constraint is. the existing work shows that there exists a relationship between tightness and global consistency of a constraint network. In this paper, we conduct a comprehensive study on this relationship. Under the concept of k-consistency (k is a number), we strengthen the existing results by establishing that only some of the tightest, not all, binary constraints are used to predict a number k such that strong k-consistency ensures global consistency of an arbitrary constraint network which may include non-binary constraints. More importantly, we have identified a lower bound of the number of the tightest constraints we have to consider in predicting the number k. To make better use of the tightness of constraints, we propose a new type of consistency: dually adaptive consistency. Under this concept, only the tightest directionally relevant constraint on each variable (and thus in total n - 1 such constraints where n is the number of variables) will be used to predict the level of "consistency" ensuring global consistency of a network.
Super solutions, introduced first for SAT problems in [1], are solutions in which, if a small number of variables lose their values, we are guaranteed to be able to repair the solution with only a few changes. In this...
ISBN:
(纸本)3540232419
Super solutions, introduced first for SAT problems in [1], are solutions in which, if a small number of variables lose their values, we are guaranteed to be able to repair the solution with only a few changes. In this paper, we stress the need to extend the super-solution framework along several dimensions to make it more useful practically. For instance, consider the jobshop scheduling problem (jsp). A jsp involves a set of jobs (sequences of activities) and a set of machines. the objective is to schedule the jobs such that no machine is required by two activities that overlap, and the makespan is minimized. A jsp can be formulated as a CSP, with one variable for each activity, and a domain size equal to the makespan minus its duration. To find the minimal makespan, one starts withthe makespan equal to a lower bound and increase it till a solution exists.
We analyze the complexity of optimization problems expressed using valued constraints. this very general framework includes a number of well-known optimization problems such as MAX-SAT, and WEIGHTED MAX-SAT, as well a...
详细信息
ISBN:
(纸本)3540232419
We analyze the complexity of optimization problems expressed using valued constraints. this very general framework includes a number of well-known optimization problems such as MAX-SAT, and WEIGHTED MAX-SAT, as well as properly generalizing the classical CSP framework by allowing the expression of preferences. We focus on valued constraints over Boolean variables, and we establish a dichotomy theorem which characterizes the complexity of any problem involving a fixed set of constraints of this kind.
Local branching is a general purpose heuristic search method successfully used in Mixed Integer programming (MIP). We propose its integration and extension in constraintprogramming (CP).
ISBN:
(纸本)9783540749691
Local branching is a general purpose heuristic search method successfully used in Mixed Integer programming (MIP). We propose its integration and extension in constraintprogramming (CP).
constraintprogramming is a powerful programming paradigm with a great impact on a number of important areas such as logic programming [45], concurrent programming [42], artificial intelligence [12], and combinatorial...
详细信息
ISBN:
(纸本)3540462678
constraintprogramming is a powerful programming paradigm with a great impact on a number of important areas such as logic programming [45], concurrent programming [42], artificial intelligence [12], and combinatorial optimization [46]. We believe that constraintprogramming is also a rich source of many challenging algorithmic problems, and co-operations between the constraintprogramming and the algorithms communities could be beneficial to both areas.
In this paper, we introduce a new framework for managing several kinds of renewable resources, including disjunctive resources, cumulative resources, and resources with setup times. In this framework, we use a list sc...
详细信息
ISBN:
(纸本)9783319661582;9783319661575
In this paper, we introduce a new framework for managing several kinds of renewable resources, including disjunctive resources, cumulative resources, and resources with setup times. In this framework, we use a list scheduling approach in which a priority order between activities must be determined to solve resource usage conflicts. In this context, we define a new differentiable constraint-based local search invariant which transforms a priority order into a full schedule and which incrementally maintains this schedule in case of change in the order. On top of that, we use multiple neighborhoods and search strategies, and we get new best upper bounds on several scheduling benchmarks.
Answer set programming (ASP) is a well-established declarative paradigm. One of the successes of ASP is the availability of efficient systems. State-of-the-art systems are based on the ground+solve approach. In some a...
详细信息
Answer set programming (ASP) is a well-established declarative paradigm. One of the successes of ASP is the availability of efficient systems. State-of-the-art systems are based on the ground+solve approach. In some applications, this approach is infeasible because the grounding of one or a few constraints is expensive. In this paper, we systematically compare alternative strategies to avoid the instantiation of problematic constraints, which are based on custom extensions of the solver. Results on real and synthetic benchmarks highlight some strengths and weaknesses of the different strategies.
Scheduling is one of the most successful application areas of constraintprogramming mainly thanks to special global constraints designed to model resource restrictions. Among these global constraints, edge-finding an...
详细信息
Scheduling is one of the most successful application areas of constraintprogramming mainly thanks to special global constraints designed to model resource restrictions. Among these global constraints, edge-finding and not-first/not-last are the most popular filtering algorithms for unary resources. In this paper we introduce new O(n log n) versions of these two filtering algorithms and one more O(n log n) filtering algorithm called detectable precedences. these algorithms use a special data structures theta-tree and theta-Alpha-tree. these data structures are especially designed for "what-if" reasoning about a set of activities so we also propose to use them for handling so called optional activities, i.e. activities which may or may not appear on the resource. In particular, we propose new O(n log n) variants of filtering algorithms which are able to handle optional activities: overload checking, detectable precedences and not-first/not-last.
We introduce a constraint system LC that handles arithmetic constraints over reals within the linear concurrent constraintprogramming (Icc) framework. this approach provides us with a general, extensible foundation f...
详细信息
ISBN:
(纸本)3540652248
We introduce a constraint system LC that handles arithmetic constraints over reals within the linear concurrent constraintprogramming (Icc) framework. this approach provides us with a general, extensible foundation for linear programming algorithm design that comes with a (linear) logical semantics. In particular, it allows us to build a 'glass-box' version of the (constraint solver) simplex algorithm by defining (monotone) cc ask and tell agents over a higher-level constraint system as Icc(LC) programs. We illustrate at the same time the use of the lccframework as a non-trivial concurrent algorithm specification tool.
暂无评论