Scheduling has been a successful domain of application for constraint programming since its beginnings. The cumulative constraint - which enforces the usage of a limited resource by several tasks - is one of the core ...
详细信息
ISBN:
(数字)9783319180083
ISBN:
(纸本)9783319180083;9783319180076
Scheduling has been a successful domain of application for constraint programming since its beginnings. The cumulative constraint - which enforces the usage of a limited resource by several tasks - is one of the core components that are surely responsible of this success. Unfortunately, ensuring bound-consistency for the cumulative constraint is already NP-Hard. Therefore, several relaxations were proposed to reduce domains in polynomial time such as Time-Tabling, Edge-Finding, Energetic Reasoning, and Not-First-Not-Last. Recently, Vilim introduced the Time-Table Edge-Finding reasoning which strengthens Edge-Finding by considering the time-table of the resource. We pursue the idea of exploiting the time-table to detect disjunctive pairs of tasks dynamically during the search. This new type of filtering - which we call time-table disjunctive reasoning - is not dominated by existing filtering rules. We propose a simple algorithm that implements this filtering rule with a O(n(2)) time complexity (where n is the number of tasks) without relying on complex data structures. Our results on well known benchmarks highlight that using this new algorithm can substantially improve the solving process for some instances and only adds a marginally low computation overhead for the other ones.
In this paper we demonstrate several examples of solving challenging algorithmic problems from the Google Code Jam programming contest with the Prolog-based (ECLPSe)-P-i system using declarative techniques: constraint...
详细信息
ISBN:
(纸本)9781450331968
In this paper we demonstrate several examples of solving challenging algorithmic problems from the Google Code Jam programming contest with the Prolog-based (ECLPSe)-P-i system using declarative techniques: constraint logic programming and linear (integer) programming. These problems were designed to be solved by inventing clever algorithms and efficiently implementing them in a conventional imperative programming language, but we present relatively simple declarative programs in (ECLPSe)-P-i that are fast enough to find answers within the time limit imposed by the contest rules. We claim that declarative programming with (ECLPSe)-P-i is better suited for solving certain common kinds of programming problems offered in Google Code Jam than imperative programming. We show this by comparing the mental steps required to come up with both kinds of solutions.
It is well recognized that a single, arbitrarily efficient solver can be significantly outperformed by a portfolio solver exploiting a combination of possibly slower on-average different solvers. Despite the success o...
详细信息
ISBN:
(纸本)9783319274362;9783319274355
It is well recognized that a single, arbitrarily efficient solver can be significantly outperformed by a portfolio solver exploiting a combination of possibly slower on-average different solvers. Despite the success of portfolio solvers within the context of solving competitions, they are rarely used in practice. In this paper we give an overview of the main limitations that hinder the practical adoption and development of portfolio solvers within the constraint programming (CP) paradigm, discussing also possible ways to overcome them and potential extensions outside the CP field.
constraint programming is traditionally presented as the combination of two components: a constraint model and a search procedure. In this paper we show that tree search procedures can be fully internalized in the con...
详细信息
ISBN:
(纸本)9781450335164
constraint programming is traditionally presented as the combination of two components: a constraint model and a search procedure. In this paper we show that tree search procedures can be fully internalized in the constraint model with a fixed enumeration strategy. This approach has several advantages: 1) it makes search strategies declarative, and modeled as constraint satisfaction problems;2) it makes it possible to express search strategies in existing front-end modeling languages supporting reified constraints without any extension;3) it opens up constraint propagation algorithms to search constraints and to the implementation of novel search procedures based on constraint propagation. We illustrate this approach with a Horn clause extension of the MiniZinc modeling language and the modeling in this language of a variety of search procedures, including dynamic symmetry breaking procedures and limited discrepancy search, as constraint satisfaction problems. We show that this generality does not come with a significant overhead, and can in fact exhibit exponential speedups over procedural implementations, thanks to the propagation of the search constraints.
Transition time constraints are ubiquitous in scheduling problems. They are said to be sequence-dependent if their durations depend on both activities between which they take place. In this context, we propose to exte...
详细信息
ISBN:
(纸本)9783319232195;9783319232188
Transition time constraints are ubiquitous in scheduling problems. They are said to be sequence-dependent if their durations depend on both activities between which they take place. In this context, we propose to extend the Theta-tree and Theta-Lambda-tree data structures introduced by Vilim in order to strengthen the bound computation of the earliest completion time of a set of activities, by taking into account the sequence dependent transition time constraints. These extended structures can be substituted seamlessly in the state-of-the-art Vilim's filtering algorithms for unary resource constraints (Overload Checking, Detectable Precedences, Not-First/Not-Last and Edge-Finding algorithms) without changing their O(n log(n)) time complexities. Furthermore, this new propagation procedure is totally independent from additional constraints or the objective function to optimize. The proposed approach is able to reduce the number of nodes by several order of magnitudes on some instances of the job-shop with transition times problem, without introducing too much overhead on other instances for which it is less effective.
Integer programming (IP) is one of the most successful approaches for combinatorial optimization problems. Many IP solvers make use of the linear relaxation, which removes the integrality requirement on the variables....
详细信息
ISBN:
(纸本)9783319232195;9783319232188
Integer programming (IP) is one of the most successful approaches for combinatorial optimization problems. Many IP solvers make use of the linear relaxation, which removes the integrality requirement on the variables. The relaxed problem can then be solved using linear programming (LP), a very efficient optimization paradigm. constraint programming (CP) can solve a much wider variety of problems, since it does not require the problem to be expressed in terms of linear equations. The cost of this versatility is that in CP there is no easy way to automatically derive a good bound on the objective. This paper presents an approach based on ideas from Lagrangian decomposition (LD) that establishes a general bounding scheme for any CP. We provide an implementation for optimization problems that can be formulated with knapsack and regular constraints, and we give comparisons with pure CP approaches. Our results clearly demonstrate the benefits of our approach on these problems.
In this paper we address a recent situation created by the explosive growth of web systems. For these reason we propose a framework to support adaptive elements in Web pages. Web pages can be accessed by different pla...
详细信息
ISBN:
(纸本)9783319213804;9783319213798
In this paper we address a recent situation created by the explosive growth of web systems. For these reason we propose a framework to support adaptive elements in Web pages. Web pages can be accessed by different platforms with different browsers and through different devices such as laptops, tablets or cellphones. In particular we focus on adaptive menus for this different kind of devices or browsers to optimize the selection patterns and their implementations. We propose a framework using an Adaptive constraint programming technique to optimize the decision of developers. constraint programming is a programming paradigm able to find efficient resolution in optimization problems. In constraint programming a problem is defined in term of variables and constraints. The variables hold a domain and represent the unknowns of the problem, while the relations among them are modeled as constraints.
This paper is concerned with developing a knowledge-based approach for selecting portfolio of product concepts for development. The critical success factors for new product development are identified on the basis of i...
详细信息
ISBN:
(纸本)9783319196381;9783319196374
This paper is concerned with developing a knowledge-based approach for selecting portfolio of product concepts for development. The critical success factors for new product development are identified on the basis of information acquired from an enterprise system, including the fields of sales and marketing, project management, and production. The model of new product screening consists of enterprise functional domains and business information systems. The model has been described in terms of a constraint satisfaction problem (CSP) that contains a set of decision variables, their domains, and the constraints. Knowledge base is specified according to CSP framework and it reflects the company's resources and relationships identified. The illustrative example presents the use of fuzzy neural network to estimating the success of new products and constraint programming to product concept screening in the context of the different search strategies.
Traditional vehicle routing problems implicitly assume only one crew operates a vehicle for the entirety of its journey. However, this assumption is violated in many applications arising in humanitarian and military l...
详细信息
ISBN:
(纸本)9783319232195;9783319232188
Traditional vehicle routing problems implicitly assume only one crew operates a vehicle for the entirety of its journey. However, this assumption is violated in many applications arising in humanitarian and military logistics. This paper considers a Joint Vehicle and Crew Routing and Scheduling Problem, in which crews are able to interchange vehicles, resulting in space and time interdependencies between vehicle routes and crew routes. It proposes a constraint programming model that overlays crew routing constraints over a standard vehicle routing problem. The constraint programming model uses a novel optimization constraint that detects infeasibility and bounds crew objectives. Experimental results demonstrate significant benefits of using constraint programming over mixed integer programming and a vehicle-then-crew sequential approach.
Cumulative is an essential constraint in the CP framework, and is present in scheduling and packing applications. The lightest filtering for the cumulative constraint is time-tabling. It has been improved several time...
详细信息
ISBN:
(纸本)9783319232195;9783319232188
Cumulative is an essential constraint in the CP framework, and is present in scheduling and packing applications. The lightest filtering for the cumulative constraint is time-tabling. It has been improved several times over the last decade. The best known theoretical time complexity for time-table is O(n log n) introduced by Ouellet and Quimper. We show a new algorithm able to run in O(n), by relying on range min query algorithms. This approach is more of theoretical rather than practical interest, because of the generally larger number of iterations needed to reach the fixed point. On the practical side, the recent synchronized sweep algorithm of Letort et al, with a time-complexity of O(n 2), requires fewer iterations to reach the fix-point and is considered as the most scalable approach. Unfortunately this algorithm is not trivial to implement. In this work we present a O(n 2) simple two step alternative approach: first building the mandatory profile, then updating all the bounds of the activities. Our experimental results show that our algorithm outperforms synchronized sweep and the time-tabling implementations of other open-source solvers on large scale scheduling instances, sometimes significantly.
暂无评论