The emergence of specialized hardware, such as quantum computers and Digital/CMOS annealers, and the slowing of performance growth of general-purpose hardware raises an important question for our community: how can th...
详细信息
Intensional sets, i.e., sets given by a property rather than by enumerating elements, are widely recognized as a key feature to describe complex problems (see, e.g., specification languages such as B and Z). Notwithst...
详细信息
Intensional sets, i.e., sets given by a property rather than by enumerating elements, are widely recognized as a key feature to describe complex problems (see, e.g., specification languages such as B and Z). Notwithstanding, very few tools exist supporting high-level automated reasoning on general formulas involving intensional sets. In this paper we present a decision procedure for a first-order logic language offering both extensional and (a restricted form of) intensional sets (RIS). RIS are introduced as first-class citizens of the language, and set-theoretical operators on RIS are dealt with as constraints. Syntactic restrictions on RIS guarantee that the denoted sets are finite. The language of RIS, called LRIS, is parametric with respect to any first-order theory X providing at least equality and a decision procedure for X-formulas. In particular, we consider the instance of LRIS when X is the theory of hereditarily finite sets and binary relations. We also present a working implementation of this instance as part of the {log} tool, and we show through a number of examples and two case studies that, although RIS are a subclass of general intensional sets, they are still sufficiently expressive as to encode and solve many interesting problems. Finally, an extensive empirical evaluation provides evidence that the tool can be used in practice.
Learning constraint networks is known to require a number of membership queries exponential in the number of variables. In this paper, we learn constraint networks by asking the user partial queries. That is, we ask t...
详细信息
Learning constraint networks is known to require a number of membership queries exponential in the number of variables. In this paper, we learn constraint networks by asking the user partial queries. That is, we ask the user to classify assignments to subsets of the variables as positive or negative. We provide an algorithm, called QuAcQ2, that, given a negative example, elucidates a constraint of the target network in a number of queries logarithmic in the size of the example. The whole constraint network can then be learned with a polynomial number of partial queries. We give information theoretic lower bounds for learning some simple classes of constraint networks and show that our generic algorithm is optimal in some cases. We provide a version of QuAcQ2 with a cutoff mechanism that controls the time to generate a query. Our experiments illustrate the good behavior of QuAcQ2 in practice, especially in the case where QuAcQ2 is executed to learn the missing constraints in a partially filled constraint model. Our experiments also show that QuAcQ2 requires significantly fewer queries to learn a network than its predecessor QuAcQ1.(c) 2023 Elsevier B.V. All rights reserved.
constraint satisfaction modeling is both an efficient, and an elegant approach to model and solve many real world problems. In this paper, we present a constraint solver targeting module placement in static and partia...
详细信息
ISBN:
(纸本)9781467361804
constraint satisfaction modeling is both an efficient, and an elegant approach to model and solve many real world problems. In this paper, we present a constraint solver targeting module placement in static and partial run-time reconfigurable systems. We use the constraint solver to compute feasible placement positions. Our placement model incorporates communication, implementation variants and device configuration granularity. In addition, we model heterogeneous resources such as embedded memory, multipliers and logic. Furthermore, we take into account that logic resources consist of different types including logic only LUTs, arithmetic LUTs with carry chains, and LUTs with distributed memory. Our work targets state of the art field-programmable gate arrays (FPGAs) in both design-time and run-time applications. In order to evaluate our placement model and module placer implementation, we have implemented a repository containing 200 fully functional, placed and routed relocatable modules. The modules are used to implement complete systems. This validates the feasibility of both the model and the module placer. Furthermore, we present simulated results for run-time applications, and compare this to other state of the art research. In run-time applications, the results point to improved resource utilization. This is a result of using a finer tile grid and complex module shapes.
A common assumption in the shop scheduling literature is that the processing order of the operations of each job is sequential;however, in practice, there can be multiple connections and finish-to-start dependencies a...
详细信息
A common assumption in the shop scheduling literature is that the processing order of the operations of each job is sequential;however, in practice, there can be multiple connections and finish-to-start dependencies among the operations of each job. This paper studies flexible job shop scheduling problems with arbitrary precedence graphs. Rigorous mixed integer and constraint programming models are presented, as well as an evolutionary algorithm is proposed to solve large-scale problems. The proposed heuristic solution framework is equipped with efficient evolution and local search mechanisms as well as new feasibility detection and makespan estimation methods. To that end, new theorems are derived that extend previous theoretical contributions of the literature. Computational experiments on existing benchmark datasets show that the proposed solution methods outperform the current state-of-the-art. Overall, 59 new best solutions and 61 new lower bounds are produced for a total of 228 benchmark problem instances of the literature. To explore the impact of the arbitrary precedence graphs, lower bounds and heuristic solutions are generated for new large-scale problems. These experiments illustrate that the machine assignment flexibility and density of the precedence graphs, affect not only the makespan, but also the difficulty of producing good upper bounds.
Existing formal languages for the specification of self-adaptive cyber-physical systems focus on re-configuring the system-to-be depending on its current context, to satisfy the user's requirements, that is by dyn...
详细信息
Existing formal languages for the specification of self-adaptive cyber-physical systems focus on re-configuring the system-to-be depending on its current context, to satisfy the user's requirements, that is by dynamically composing the software's structure and behavior. While these approaches specify context-sensitive requirements, they rarely consider their run-time dynamic and scalable nature. The State-constraint Transition (SCT) modeling language, introduced in this paper, provides an answer to the problems linked to the specification of dynamic requirements by introducing the concept of configuration states, in which requirements are translated into constraints. The expressiveness of existing approaches is thus extended, combining the ease of use of well-established notations, notably those based on characteristics, and those based on Finite-state Machines (FSM), with the computational power and expressiveness of the constraint programming approach. The paper briefly presents the results of the preliminary evaluation, which assesses the expressiveness, scalability, and domain independence of the SCT language.
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.
In this paper, the problem of minimizing the smoothness index for an assembly line given a fixed cycle time and the number of workstations is studied. This problem which is known as the workload smoothing line balanci...
详细信息
In this paper, the problem of minimizing the smoothness index for an assembly line given a fixed cycle time and the number of workstations is studied. This problem which is known as the workload smoothing line balancing problem (WSLBP) is a mixed-integer quadratic programming problem. Until recently, this problem has only been tackled using heuristic approaches. Recently, there have been some attempts to solve this problem exactly using mixed-integer linear programming (MILP). The MILP formulations, however, are not usually capable of solving large size problem instances. In this paper, the aim is to solve the WSLBP using mathematical programming formulations by using off-the-shelf solvers. Differently from the literature some non-MILP formulations are also considered for the problem. For this purpose, three MILP formulations, one from the literature, and two non-MILP formulations are compared. The two non-MILP formulations include a mixed-integer second order cone programming formulation and a constraint programming model. The superiority of the non-MILP formulations over the considered MILP formulations is experimentally shown. (C) 2021 Karabuk University. Publishing services by Elsevier B.V.
The Semantic Web uses ontologies to cope with the data heterogeneity problem. However, ontologies become themselves heterogeneous;this heterogeneity may occur at the syntactic, terminological, conceptual, and semantic...
详细信息
The Semantic Web uses ontologies to cope with the data heterogeneity problem. However, ontologies become themselves heterogeneous;this heterogeneity may occur at the syntactic, terminological, conceptual, and semantic levels. To solve this problem, alignments between entities of ontologies must be identified. This process is called ontology matching. In this paper, the authors propose a new method to extract alignment with multiple cardinalities using integer linear programming techniques. The authors conducted a series of experiments and compared them with currently used methods. The obtained results show the efficiency of the proposed method.
constraint programming (CP) is a powerful technique for solving large-scale combinatorial problems. Solving a problem proceeds in two distinct phases: modelling and solving. Effec-tive modelling has a huge impact on t...
详细信息
constraint programming (CP) is a powerful technique for solving large-scale combinatorial problems. Solving a problem proceeds in two distinct phases: modelling and solving. Effec-tive modelling has a huge impact on the performance of the solving process. Even with the advance of modern automated modelling tools, search spaces involved can be so vast that problems can still be difficult to solve. To further constrain the model, a more aggressive step that can be taken is the addition of streamliner constraints, which are not guaranteed to be sound but are designed to focus effort on a highly restricted but promising portion of the search space. Previously, producing effective streamlined models was a manual, difficult and time-consuming task. This paper presents a completely automated process to the gen-eration, search and selection of streamliner portfolios to produce a substantial reduction in search effort across a diverse range of problems. The results demonstrate a marked im-provement in performance for both Chuffed, a CP solver with clause learning, and lingeling, a modern SAT solver.(c) 2023 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).
暂无评论