We present a Satisfiability (SAT)-based approach for building Mixed Covering Arrays with constraints of minimum length, referred to as the Covering Array Number problem. This problem is central in Combinatorial Testin...
详细信息
We present a Satisfiability (SAT)-based approach for building Mixed Covering Arrays with constraints of minimum length, referred to as the Covering Array Number problem. This problem is central in Combinatorial Testing for the detection of system failures. In particular, we show how to apply Maximum Satisfiability (MaxSAT) technology by describing efficient encodings for different classes of complete and incomplete MaxSAT solvers to compute optimal and suboptimal solutions, respectively. Similarly, we show how to solve through MaxSAT technology a closely related problem, the Tuple Number problem, which we extend to incorporate constraints. For this problem, we additionally provide a new MaxSAT-based incomplete algorithm. The extensive experimental evaluation we carry out on the available Mixed Covering Arrays with constraints benchmarks and the comparison with state-of-the-art tools confirm the good performance of our approaches.
This paper introduces, for the first time, a complete symmetry breaking constraint of polynomial size for a significant class of graphs: the class of uniquely Hamiltonian graphs. We introduce a canonical form for uniq...
详细信息
This paper introduces, for the first time, a complete symmetry breaking constraint of polynomial size for a significant class of graphs: the class of uniquely Hamiltonian graphs. We introduce a canonical form for uniquely Hamiltonian graphs and prove that testing whether a given uniquely Hamiltonian graph is canonical can be performed efficiently. Based on this canonicity test, we construct a complete symmetry breaking constraint of polynomial size which is satisfied only by uniquely Hamiltonian graphs which are canonical. We apply the proposed symmetry breaking constraint to show new results regarding the class of uniquely Hamiltonian graphs. We also show that the proposed approach applies almost directly for the class of graphs which contain any cycle of known length where it shown to result in a partial symmetry breaking constraint. Given that it is unknown if there exist complete symmetry breaking constraints for graphs of polynomial size, this paper makes a first step in the direction of identifying specific classes of graphs for which such constraints do exist.
As regards distributed hybrid flow shop scheduling with sequence-dependent setup times (DHFSP-SDST), three novel mixed-integer linear programming (MILP) models and a constraint programming (CP) model are formulated fo...
详细信息
As regards distributed hybrid flow shop scheduling with sequence-dependent setup times (DHFSP-SDST), three novel mixed-integer linear programming (MILP) models and a constraint programming (CP) model are formulated for the same-factory and different-factory environments. The three novel MILP models are based on two different modeling ideas. The existing MILP model and the three proposed MILP models are compared in detail from several aspects, such as binary decision variables, continuous decision variables, constraints, solution performance and solution time. By solving the benchmarks in existing studies, the effectiveness and superiority of the proposed MILP and CP models are proved. Experimental results show that the MILP model of sequence-based modeling idea performs best, the MILP model of adjacent sequence-based modeling idea takes the second place and the existing MILP model of position-based modeling idea performs worst. The CP model is more efficient and effective than MILP models. In addition, compared with the existing meta-heuristic algorithms (e.g., DABC and IABC), the proposed MILP models prove the optimal solutions of 37 instances and improve 17 current best solutions. The CP model solves all the 45 instances to optimality and improves 19 current best solutions for benchmarks in the existing studies
Search-Based Software Testing (SBST) has drawn a lot of interests as a powerful approach for automated test data generation. One major limitation of search-based methods is that they may get stuck in local optima and ...
详细信息
ISBN:
(纸本)9798400701207
Search-Based Software Testing (SBST) has drawn a lot of interests as a powerful approach for automated test data generation. One major limitation of search-based methods is that they may get stuck in local optima and become inefficient if the fitness function does not provide any direction toward a test target, particularly when dealing with hard branch targets (e.g., nested predicates). Recent research has focused on enhancing the fitness function by taking branch hardness into account in order to direct the evolutionary process. However, either the characteristics of constraints (e.g., their involved variables' domain) are not taken into account or the difficulty level of a branch is separately studied. In this paper, we aim to address the test data generation with a focus on hard branches by proposing a novel fitness function based on nested constraints (i.e., including the target constraint and those that impact its coverage) and the domain sizes of their variables. The empirical study promises efficiency and effectiveness for the new fitness function. Our proposed approach outperforms its counterparts significantly, particularly for the branches that are difficult to be covered.
Effective computational methods are important for practitioners and researchers working in strategic underground mine planning. We consider a class of problems that can be modeled as a resource-constrained project sch...
详细信息
Effective computational methods are important for practitioners and researchers working in strategic underground mine planning. We consider a class of problems that can be modeled as a resource-constrained project scheduling problem with optional activities;the objective maximizes net present value. We provide a computational review of math programming and constraint programming techniques for this problem, describe and implement novel problem-size reductions, and introduce an aggregated linear program that guides a list scheduling algorithm running over unaggregated instances. Practical, large-scale planning problems cannot be processed using standard optimization approaches. However, our strategies allow us to solve them to within about 5% of optimality in several hours, even for the most difficult instances.
Due to the outbreak of the COVID-19 pandemic, the manufacturing sector has been experiencing unprecedented issues, including severe fluctuation in demand, restrictions on the availability and utilization of the workfo...
详细信息
Due to the outbreak of the COVID-19 pandemic, the manufacturing sector has been experiencing unprecedented issues, including severe fluctuation in demand, restrictions on the availability and utilization of the workforce, and governmental regulations. Adopting conventional manufacturing practices and planning approaches under such circumstances cannot be effective and may jeopardize workers' health and satisfaction, as well as the continuity of businesses. Reconfigurable Manufacturing System (RMS) as a new manufacturing paradigm has demonstrated a promising performance when facing abrupt market or system changes. This paper investigates a joint workforce planning and production scheduling problem during the COVID-19 pandemic by leveraging the adaptability and flexibility of an RMS. In this regard, workers' COVID-19 health risk arising from their allocation, and workers' preferences for flexible working hours are incorporated into the problem. Accordingly, first, novel Mixed-Integer Linear programming (MILP) and constraint programming (CP) models are developed to formulate the problem. Next, exploiting the problem's intrinsic characteristics, two properties of an optimal solution are identified. By incorporating these properties, the initial MILP and CP models are considerably improved. Afterward, to benefit from the strengths of both improved models, a novel hybrid MILP-CP solution approach is devised. Finally, comprehensive computational experiments are conducted to evaluate the performance of the proposed models and extract useful managerial insights on the system flexibility.
This work focuses on freight consolidation in multimodal rail and road transportation. The transportation network comprises of a centralized source warehouse, a set of destination warehouses, and intermediate transshi...
详细信息
This work focuses on freight consolidation in multimodal rail and road transportation. The transportation network comprises of a centralized source warehouse, a set of destination warehouses, and intermediate transshipment terminals. The paper formulates a single period integer programming model and a multi-period constraint programming model for optimizing multimodal freight transportation with volume discount on rail freight rate. The first model is aimed at consignee organizations with comparatively low shipment quantity and less frequent transportation, while the second model targets organizations which require continuous freight transportation on a massive scale. The single-period model is solved using a commercially available CPLEX solver. However, due to the computational complexity of the multi-period constraint programming model, a heuristic named Rail and Truck Allocation Algorithm (RATAA) is proposed. Computational experiments are carried out to prove the efficiency of the proposed solution approaches.
Amidst the ongoing climate crisis, there is a pressing need to reduce energy consumption - especially in industrial settings, as recognized by the United Nations Sustainability Goals (in particular, 9 and 12). To miti...
详细信息
The cooperative veriflcation of Bounded Model Checking and Fuzzing has proved to be one of the most effective techniques when testing C programs. FuSeBMC is a test-generation tool that employs BMC and Fuzzing to produ...
详细信息
ISBN:
(数字)9783031308260
ISBN:
(纸本)9783031308253;9783031308260
The cooperative veriflcation of Bounded Model Checking and Fuzzing has proved to be one of the most effective techniques when testing C programs. FuSeBMC is a test-generation tool that employs BMC and Fuzzing to produce test cases. In Test-Comp 2023, we present an interval approach to FuSeBMC IA, improving the test generator to use interval methods and abstract interpretation (via Frama-C) to strengthen our instrumentation and fuzzing. Here, an abstract interpretation engine instruments the program as follows. It analyzes different program branches, combines the conditions of each branch, and produces a constraint Satisfaction Problem (CSP), which is solved using constraint programming (CP) by interval manipulation techniques called Contractor programming. This process has a set of invariants for each branch, which are introduced back into the program as constraints. Experimental results show improvements in reducing CPU time (37%) and memory (13%), while retaining a high score.
A Maximal-Sum Submatrix (MSS) maximizes the sum of the entries corresponding to the Cartesian product of a subset of rows and columns from an original matrix (with positive and negative entries). Despite being NP-hard...
详细信息
A Maximal-Sum Submatrix (MSS) maximizes the sum of the entries corresponding to the Cartesian product of a subset of rows and columns from an original matrix (with positive and negative entries). Despite being NP-hard, this recently introduced problem was already proven to be useful for practical data mining applications. It was used for identifying bi-clusters in gene expression data or to extract a sub matrix that is then visualized in a circular plot. The state-of-the-art results for MSS are obtained using an advanced constraint Programing approach that combines a custom filtering algorithm with a Large Neighborhood Search. We improve the state-of-the-art approach by introducing new upper bounds based on linear and mixed-integer programming formulations, along with dedicated pruning algorithms. We experiment on both synthetic and real-life data, and show that our approach outperforms the previous methods. (c) 2021 Elsevier B.V. All rights reserved.
暂无评论