constraint Optimization Problems (COPs) ask for an assignment of values to variables in order to optimize an objective subject to constraints that restrict the value combinations in the assignment. They are usually so...
详细信息
constraint Optimization Problems (COPs) ask for an assignment of values to variables in order to optimize an objective subject to constraints that restrict the value combinations in the assignment. They are usually solved by the classical Branch and Bound (B & B) search algorithm. Dominance breaking is an important technique in B & B to prune assignments that are subordinate to others concerning the objective value and/or the satisfiability of constraints. In practice, the addition of constraints for dominance breaking can drastically speed up the B & B search for solving many COPs. However, identification of suboptimal assignments in COPs and derivation of useful constraints for dominance breaking are usually problem-specific and require sophisticated human insights on the problem *** paper proposes the first theoretical and practical framework for automatic generation of dominance breaking constraints for a class of COPs consisting of efficiently checkable objectives and constraints. In particular, the framework focuses on generating nogood constraints representing incompatible value assignments and formulates nogood generation as solving auxiliary constraint satisfaction problems. The proposed method can generate nogoods of varying strengths for dominance breaking by controlling the number of involved variables. Experimentation on various benchmarks demonstrates the effectiveness of the proposal in both efficiency and ease of use. The superior performance is also supported by a theoretical analysis to compare the relative strength of automatically generated nogoods with manually derived dominance breaking constraints in the literature. & COPY;2023 Elsevier B.V. All rights reserved.
Purpose Real-time location sensing (RTLS) systems offer a significant potential to advance the management of construction processes by potentially providing real-time access to the locations of workers and equipment. ...
详细信息
Purpose Real-time location sensing (RTLS) systems offer a significant potential to advance the management of construction processes by potentially providing real-time access to the locations of workers and equipment. Many location-sensing technologies tend to perform poorly for indoor work environments and generate large data sets that are somewhat difficult to process in a meaningful way. Unfortunately, little is still known regarding the practical benefits of converting raw worker tracking data into meaningful information about construction project progress, effectively impeding widespread adoption in construction. Design/methodology/approach The presented framework is designed to automate as many steps as possible, aiming to avoid manual procedures that significantly increase the time between progress estimation updates. The authors apply simple location tracking sensor data that does not require personal handling, to ensure continuous data acquisition. They use a generic and non-site-specific knowledge base (KB) created through domain expert interviews. The sensor data and KB are analyzed in an abductive reasoning framework implemented in Answer Set programming (extended to support spatial and temporal reasoning), a logic programming paradigm developed within the artificial intelligence domain. Findings This work demonstrates how abductive reasoning can be applied to automatically generate rich and qualitative information about activities that have been carried out on a construction site. These activities are subsequently used for reasoning about the progress of the construction project. Our framework delivers an upper bound on project progress ("optimistic estimates") within a practical amount of time, in the order of seconds. The target user group is construction management by providing project planning decision support. Research limitations/implications The KB developed for this early-stage research does not encapsulate an exhaustive body of domain expert kno
String constraint solving refers to solving combinatorial problems involving constraints over string variables. String solving approaches have become popular over the past few years given the massive use of strings in...
详细信息
String constraint solving refers to solving combinatorial problems involving constraints over string variables. String solving approaches have become popular over the past few years given the massive use of strings in different application domains like formal analysis, automated testing, database query processing, and cybersecurity. This article reports a comprehensive survey on string constraint solving by exploring the large number of approaches that have been proposed over the past few decades to solve string constraints.
This article addresses the Flexible Job Shop Scheduling and Lot Streaming Problem (FJSSP-LS) under setup and transport resource constraints. While the related literature emphasises the lot streaming policy for time-ba...
详细信息
This article addresses the Flexible Job Shop Scheduling and Lot Streaming Problem (FJSSP-LS) under setup and transport resource constraints. While the related literature emphasises the lot streaming policy for time-based objectives, setup and transport resource constraints were not considered simultaneously with this policy, limiting the resulting schedule's applicability in practice. For this reason, we propose a novel constraint programming (CP) model enriched by an efficient variable and value ordering strategy specifically designed for the FJSSP-LS with resource constraints. We also present a CP-based iterative improvement method, CP-based Large Neighbourhood Search (CP-based LNS), that focuses on exploring large neighbourhoods through the CP model. Both models are initially tested for the FJSSP and have been shown to provide the best solutions to well-known benchmark instances. Next, they are used for the FJSSP-LS, and the proposed CP-based LNS improves the objective function value by 4.68 percent on average compared to the CP model for the generated test problems.
A hybrid flow shop group scheduling problem (HFGSP) involves two distinct sub-problems, the arrangement of groups and the configuration of jobs within each group. Constructing its mathematical model based on the class...
详细信息
A hybrid flow shop group scheduling problem (HFGSP) involves two distinct sub-problems, the arrangement of groups and the configuration of jobs within each group. Constructing its mathematical model based on the classification of these sub-problems can help better understand the problem's characteristics. However, the existing literature fails to establish MILP models of HFGSP based on the interrelation between each subproblem and the respective process constraints satisfied by each subproblem. To address this gap, our study first categorizes all the constraints in the HFGSP according to several factors: group arrangement, job arrangement within the group, process requirements between groups, process requirements between jobs from the same group, process requirements between adjacent stages, and the relationship between the decision variables of completion time and the objective constraint. Following this classification, we construct 48 available MILP models of HFGSP. Additionally, we also propose an efficient constraint programming (CP) model of HFGSP. Numerous experiments are conducted to verify the correctness and performance of all 48 MILP models across different test instances, analyze the complexities of all models, and excavate their intrinsic characteristics. Through our evaluation for the 48 models, we observe that models 24 and 48 exhibit superior performance. This highlights the effectiveness of the hybrid modeling approach, which synergistically combines sequence-based modeling for groups and position-based adjacent modeling for jobs within each group. The utilization of this hybrid modeling approach enables the construction of high-quality MILP models for addressing the HFGSP problem. Our intention is to bridge the gap between MILP modeling of HFGSP and problem-specific algorithms, thereby providing a comprehensive understanding of the problem and offering potential solutions.
Routing and Spectrum Allocation (RSA) is one of the central problems in modern optical networks. In this setting, also called Flexible Grid, we want to find paths and allocate non-overlapping frequency slots for as ma...
详细信息
The research objective is to support the maintenance unit with route planning prior to performing road inspection, the model is based on VRP problem settings, and with the addition of compulsory road sections and allo...
详细信息
ISBN:
(纸本)9783037857762
The research objective is to support the maintenance unit with route planning prior to performing road inspection, the model is based on VRP problem settings, and with the addition of compulsory road sections and allowing shortcuts through small pathways during the inspection to reduce time consumption. By employing constraint programming (CP) technology and optimization solution mechanism to construct inspection scheduling model, and the objective is to minimize time consumption of the road inspection. The province and county roads in Douliou city are chosen as examples for analysis, plans out best routes for inspection process, and also displays all the road sections passed by inspection vehicle. Thus this model can be used as reference to support the authorities to efficiently allocate resources for the inspection process, and achieve the objective as shorten the inspection time consumption.
Giving personalized feedback to students is very important to the learning process. However, doing so in a timely manner can be difficult to accomplish in very large courses. Recent work has explored different types o...
详细信息
This paper introduces a constraint programming algorithm designed for efficient task scheduling in Maintenance, Repair, and Overhaul (MRO) operations, specifically for aircraft engines. By leveraging historical data f...
详细信息
We present a domain for string decision variables of bounded length, combining features from fixed-length and unbounded-length string solvers to reason on an interval defined by languages of prefixes and suffixes. We ...
详细信息
ISBN:
(纸本)9781479929719
We present a domain for string decision variables of bounded length, combining features from fixed-length and unbounded-length string solvers to reason on an interval defined by languages of prefixes and suffixes. We provide a theoretical groundwork for constraint solving on this domain and describe propagation techniques for several common constraints.
暂无评论