Most Semantic Web Services discovery approaches are not well suited when using complex relational, arithmetic and logical expressions, because they are usually based on Description Logics. Moreover, these kind of expr...
详细信息
ISBN:
(纸本)9783540749738
Most Semantic Web Services discovery approaches are not well suited when using complex relational, arithmetic and logical expressions, because they are usually based on Description Logics. Moreover, these kind of expressions usually appear when discovery is performed including Quality-of- Service conditions. In this work, we present an hybrid discovery process for Semantic Web Services that takes care of QoS conditions. Our approach splits discovery into stages, using different engines in each one, depending on its search nature. This architecture is extensible and loosely coupled, allowing the addition of discovery engines at will. In order to perform QoS-aware discovery, we propose a stage that uses constraint programming, that allows to use complex QOS conditions within discovery queries. Furthermore, it is possible to obtain the optimal offer that fulfills a given demand using this approach.
The Traveling Salesperson Problem (TSP) is a well-known problem addressed in the literature through various techniques, including Integer Linear programming, constraint programming (CP) and Local Search. Many real lif...
详细信息
ISBN:
(数字)9783030770914
ISBN:
(纸本)9783030770914;9783030770907
The Traveling Salesperson Problem (TSP) is a well-known problem addressed in the literature through various techniques, including Integer Linear programming, constraint programming (CP) and Local Search. Many real life instances belong to the subclass of Euclidean TSPs, in which the nodes to be visited are points in the Euclidean plane, and the distance between them is the Euclidean distance. A well-known property of the Euclidean TSP is that no crossings can exist in an optimal solution. In a previous publication, we exploited this property to speed-up the solution of Euclidean instances in CP, by imposing a quadratic number of so-called no-overlapping constraints. In this work, we observe that not all the no-overlapping constraints are equally useful: by experimental analysis, some of them provide a speed-up, while others only introduce overhead. Thus, it is important to define a way to classify useful constraints. To do so, we use machine learning approaches with the objective to impose only those no-overlapping constraints that have been classified as effective. We compare two classifiers based on Random Forest and Neural Networks, which show to be effective, with a slight prevalence for Random Forest.
It is well-known that experience can lead to increased efficiency, yet this is largely unaccounted for in project scheduling. We consider project scheduling problems where the duration of activities can be reduced whe...
详细信息
ISBN:
(数字)9783030782306
ISBN:
(纸本)9783030782306;9783030782290
It is well-known that experience can lead to increased efficiency, yet this is largely unaccounted for in project scheduling. We consider project scheduling problems where the duration of activities can be reduced when scheduled after certain other activities that allow for learning relevant skills. Since per-period availabilities of renewable resources are limited and precedence requirements have to be respected, the resulting optimization problems generalize the resource-constrained project scheduling problem. We introduce four constraint programming formulations that incorporate the alternative learning-based job durations via logical constraints, dynamic interval lengths, multiple job modes, and a bi-objective reformulation, respectively. To provide tight optimality gaps for larger problem instances, we further develop five lower bounding techniques based on model relaxations. We also devise a destructive lower bounding method. We perform an extensive computational study across thousands of instances based on the PSPlib to quantify the impact of project size, potential learning occurrences, and learning effects on the optimal project duration. In addition, we compare formulation strength and quality of the obtained lower bounds using a state-of-the-art constraint programming solver.
Aiming at the integration of constraint programming (CP) and mathematical programming (MP), which are used to solve combinatorial optimization problems, the paper analyzes the characteristic and integration schemes of...
详细信息
ISBN:
(纸本)9781424420124
Aiming at the integration of constraint programming (CP) and mathematical programming (MP), which are used to solve combinatorial optimization problems, the paper analyzes the characteristic and integration schemes of both optimization techniques. Based on previous work, an integration framework is introduced and implemented on parallel machine scheduling problem in ILOG OPL. Simulation experiments show that the integration of CP and MP is efficient.
Time-Sensitive Networking (TSN) extends IEEE 802.1 Ethernet for safety-critical and real-time applications in several areas, e.g., automotive, aerospace or industrial automation. However, many of these systems also ha...
详细信息
ISBN:
(纸本)9781728183244
Time-Sensitive Networking (TSN) extends IEEE 802.1 Ethernet for safety-critical and real-time applications in several areas, e.g., automotive, aerospace or industrial automation. However, many of these systems also have stringent security requirements, and security attacks may impair safety. Given a TSN-based distributed architecture, a set of applications with tasks and messages, as well as a set of security and redundancy requirements, we are interested to synthesize a system configuration such that the real-time, safety and security requirements are satisfied. We use the Timed Efficient Stream Loss-Tolerant Authentication (TESLA) low-resource multicast authentication protocol to guarantee the security requirements, and redundant disjunct message routes to tolerate link failures. We consider that the tasks are scheduled using static cyclic scheduling and that the messages use the time-sensitive traffic class in TSN, which relies on schedule tables (called Gate Control Lists, GCLs) in the network switches. A configuration consists of the schedule tables for tasks as well as the disjoint routes and GCLs for messages. We propose a constraint programming-based formulation for this problem and we evaluate it on several test cases.
Non-deterministic specifications play a central role in the use of formal methods for software development. Such specifications can be more readable, but hard to execute efficiently due to the usually large search spa...
详细信息
ISBN:
(纸本)9783319929705;9783319929699
Non-deterministic specifications play a central role in the use of formal methods for software development. Such specifications can be more readable, but hard to execute efficiently due to the usually large search space. constraint programming offers advanced algorithms and heuristics for solving certain non-deterministic models. Unfortunately, this requires writing models in a form suitable for efficient solving where the readability typically required from a specification is lost. Tools like ProB attempt to bridge this gap by translating high-level first-order predicate logic specifications into formal models suitable for constraint solving. In this paper we study potential improvements to this methodology by (1) using refinement to transform specifications into models suitable for efficient solving, (2) translating first-order predicates directly into the OscaR framework and (3) using different kinds of solvers as a back end. Formal verification by proof ensures the correctness of the solution of the model with respect to the specification.
In this paper we solve the Dial-A-Ride Problem (DARP). The main objective of the DARP is to minimize operation costs for renting pieces of work from the transportation service providers. The resolution approach consid...
详细信息
ISBN:
(纸本)9783540755548
In this paper we solve the Dial-A-Ride Problem (DARP). The main objective of the DARP is to minimize operation costs for renting pieces of work from the transportation service providers. The resolution approach considered in this work, starting from a network formulation of the DARP, decomposes the problem in two phases: Clustering and Chaining. We model both phases like a Set Partitioning Problem (SPP) and solve them with an interesting sinergy between two different optimization methods: Ant Computing and constraint programming.
Job shop scheduling problem with sequence-dependent setup times is complicated because machines have to be reconfigured between two consecutive operations. More researchers have attracted attention to this problem. We...
详细信息
ISBN:
(纸本)9783642330124
Job shop scheduling problem with sequence-dependent setup times is complicated because machines have to be reconfigured between two consecutive operations. More researchers have attracted attention to this problem. We propose a constraint programming approach to minimize the makespan. Three branching strategies including binary constraint heuristic, variable-based heuristic, task-based heuristic are compared. The constraint model and search strategies are carried out by Xpress-MP. The results showed that binary constraint heuristic is more effective.
Block modeling has been used extensively in many domains including social science, spatial temporal data analysis and even medical imaging. Original formulations of the problem modeled the problem as a mixed integer p...
详细信息
ISBN:
(纸本)9783030300487
Block modeling has been used extensively in many domains including social science, spatial temporal data analysis and even medical imaging. Original formulations of the problem modeled the problem as a mixed integer programming problem, but were not scalable. Subsequent work relaxed the discrete optimization requirement, and showed that adding constraints is not straightforward in existing approaches. In this work, we present a new approach based on constraint programming, allowing discrete optimization of block modeling in a manner that is not only scalable, but also allows the easy incorporation of constraints. We introduce a new constraint filtering algorithm that outperforms earlier approaches, in both constrained and unconstrained settings. We show its use in the analysis of real datasets.
Contemporary motor vehicles have increasing numbers of automated functions to augment the safety and comfort of a car. The automotive industry has to incorporate increasing numbers of processing units in the structure...
详细信息
Contemporary motor vehicles have increasing numbers of automated functions to augment the safety and comfort of a car. The automotive industry has to incorporate increasing numbers of processing units in the structure of cars to run the software that provides these functionalities. The software components often need access to sensors or mechanical devices which they are designed to operate. The result is a network of hardware units which can accommodate a limited number of software programs, each of which has to be assigned to a hardware unit. A prime goal of this deployment problem is to find software-to-hardware assignments that maximise the reliability of the system. In doing so, the assignments have to observe a number of constraints to be viable. This includes limited memory of a hardware unit, collocation of software components on the same hardware units, and communication between software components. Since the problem consists of many constraints with a significantly large search space, we investigate an ACO and constraint programming (CP) hybrid for this problem. We find that despite the large number of constraints, ACO on its own is the most effective method providing good solutions by also exploring infeasible regions.
暂无评论