constraint programming systems allow a diverse range of problems to be modelled and solved. Most systems require the user to learn a new constraint programming language, which presents a barrier to novice and casual u...
详细信息
ISBN:
(纸本)9783031308192;9783031308208
constraint programming systems allow a diverse range of problems to be modelled and solved. Most systems require the user to learn a new constraint programming language, which presents a barrier to novice and casual users. To address this problem, we present the CoPTIC constraint programming system, which allows the user to write a model in the well-known programming language C, augmented with a simple API to support using a guess-and-check paradigm. The resulting model is at most as complex as an ordinary C program that uses naive brute force to solve the same problem. CoPTIC uses the bounded model checker CBMC to translate the model into a SAT instance, which is solved using the SAT solver CaDiCaL. We show that, while this is less efficient than a direct translation from a dedicated constraint language into SAT, performance remains adequate for casual users. CoPTIC supports constraint satisfaction and optimisation problems, as well as enumeration of multiple solutions. After a solution has been found, CoPTIC allows the model to be run with the solution;this makes it easy to debug a model, or to print the solution in any desired format.
The multi-workshop facility layout problem (MWFLP) focuses on the optimal distribution and placement of departments across multiple workshops to maximize material handling efficiency and space utilization in manufactu...
详细信息
Tolerant algebraic side-channel attack (TASCA) exploits side-channel information with an algebraic formulation of a cipher to exploit its weaknesses and recover a secret key. Its inputs consist of a side-channel trace...
详细信息
Tolerant algebraic side-channel attack (TASCA) exploits side-channel information with an algebraic formulation of a cipher to exploit its weaknesses and recover a secret key. Its inputs consist of a side-channel trace of an encryption and the clear and cipher texts. TASCA demonstrated that pseudo-Boolean optimization can successfully recover a key with reasonable computational efforts. Unlike Boolean Satisfiability (SAT), constraint programming (CP) is an optimization technology that favors high-level, rich and expressive models that is ideal to naturally model and solve cryptanalysis challenges. It offers direct encoding of bit-wise operations and avoids costly bit-blasting formulation required by SAT and pseudo-Boolean solvers. TASCA-CP is an embodiment of TASCA and is used to attack AES-128 as well as AES-256 to recover keys when noisy side-channel measurements are available. It achieves this task orders of magnitude faster than the original TASCA approach. TASCA-CP, with its performance, enables cryptanalysts to explore larger key-sizes and probe weaknesses of ciphers. The article demonstrates, with an attack on Keeloq, that a high-level modeling approach is essential to easily adapt to different ciphers. The empirical evaluation establishes the performance of the system when compared to the original TASCA implementation on modern IP solvers and identical hardware.
We address the runway scheduling problem under consideration of winter operations. During snowfall, runways have to be temporarily closed in order to clear them from snow, ice and slush. We propose an integrated optim...
详细信息
We address the runway scheduling problem under consideration of winter operations. During snowfall, runways have to be temporarily closed in order to clear them from snow, ice and slush. We propose an integrated optimization model to simultaneously plan snow removal for multiple runways and to assign runways and take-off and landing times to aircraft. For this winter runway scheduling problem, we present a time-discrete binary model formulation using clique inequalities and an equivalent constraint programming model. To solve the winter runway scheduling problem optimally, we propose an exact solution methodology. Our start heuristic based on constraint programming generates a feasible initial start solution. We use a column generation scheme, which we initialize with a heuristic solution, to identify all variables of the binary program which are required to solve it optimally. Finally, we apply a branch-andbound procedure to our resulting binary program. Additionally, we present an enhanced time discretization method to balance model size and solution quality. We apply our algorithm to realistic instances from a large international airport. An analysis of resulting model sizes proves the ability of our approach to significantly reduce the number of required variables and constraints of the time-discrete binary program. We also show that our method computes optimal schedules in a short amount of time and often outperforms a time-continuous formulation as well as a pure constraint programming approach. (c) 2021 Elsevier B.V. All rights reserved.
Professional magicians employ the use of interesting properties of a deck of cards to create magical effects. These properties were traditionally discovered through trial and error, the application of heuristics or an...
详细信息
Professional magicians employ the use of interesting properties of a deck of cards to create magical effects. These properties were traditionally discovered through trial and error, the application of heuristics or analytical proofs. Those proofs come from diverse mathematical areas such as the set, number and graph theory. We discuss the limitations of relying on humans for such methods and present how professional magicians can use constraint programming as a computer-aided design tool (CAD) to search for desired properties in a deck of cards. Furthermore, we implement a solution in Python by making use of generative magic to design a new effect, demonstrating how this process broadens the level of freedom a magician can decree to their volunteers while retaining control of the outcomes of the magic. Finally, we demonstrate that the model can be easily adapted to multiple languages by presenting multiple variations of the effect supporting American English and Brazilian Portuguese.
In this study, the U-type assembly line balancing problem (UALBP) with assignment restrictions (AR-UALBP) is considered. Linked and incompatible distance and station restrictions are taken into account. New mathematic...
详细信息
In this study, the U-type assembly line balancing problem (UALBP) with assignment restrictions (AR-UALBP) is considered. Linked and incompatible distance and station restrictions are taken into account. New mathematical programming (MP) and constraint programming (CP) models are proposed. The objective function of the models is minimizing the cycle time for a given number of workstations. In addition to this objective, line efficiency and CPU time are also considered as other performance measurements. Numerical experiments on some problems from the literature are performed to evaluate the effectiveness of the proposed models. The results are compared with the results of the CP model of the straight ALBP with assignment restrictions and also the results from MP and CP models are compared with each other. The numerical results indicate that the proposed CP and MP models are more effective in obtaining better and optimal results when solving the AR-UALBP.
The planning of operating rooms under block strategy is addressed in this study. The decisions are about opening the operating rooms and assigning specialties and surgeons to blocks at the tactical level, and sequenci...
详细信息
The planning of operating rooms under block strategy is addressed in this study. The decisions are about opening the operating rooms and assigning specialties and surgeons to blocks at the tactical level, and sequencing the surgeries at the operational level. This problem aims to minimize the costs of opening the operating rooms and their overtime, the waiting costs of patients, and the surgeons' idle costs. We propose two mixed integer linear programming models, a constraint programming (CP) model and a constraint programming-based column generation (CPCG) method for handling the problem. The performance of the models is evaluated by random test instances. The results indicate that CP and CPCG models are more efficient than the linear programming models in terms of computational time, and the number of variables and constraints. The proposed method CPCG generates optimal solutions for problem instances of up to 30 surgeries in less than 4 min. The CP model finds the optimal solutions in about one minute but proving the optimality of the found solutions is time-consuming in some instances. The maximum optimality gap for the proposed two-step linear programming model is 2%, while its run time is less than 20 s. A sensitivity analysis is done on the main parameters of the problem like objectives' weights, opening cost of ORs, unit waiting cost of patients, and the maximum available time in surgery blocks. Among the three objectives, the unit waiting cost of patients has the most sensitivity to variations of the objective function weights.(c) 2022 Elsevier Inc. All rights reserved.
Significant research efforts have focused on black-box variable selection, with less attention given to value heuristics. An ideal value heuristic enables depth-first-search to prioritize high-quality solutions first....
详细信息
We consider a steelmaking-continuous casting (SCC) scheduling problem in the steel industry, which is a variant of the hybrid flow shop scheduling problem subject to practical constraints. Recently, Hong et al. [Hong,...
详细信息
ISBN:
(纸本)9783031332708;9783031332715
We consider a steelmaking-continuous casting (SCC) scheduling problem in the steel industry, which is a variant of the hybrid flow shop scheduling problem subject to practical constraints. Recently, Hong et al. [Hong, J., Moon, K., Lee, K., Lee, K., Pinedo, M.L., International Journal of Production Research 60(2), 623-643 (2022)] developed an algorithm, called Iterated Greedy Matheuristic (IGM), in which a Mixed Integer programming (MIP) model was proposed and its sub-problems are iteratively solved to improve the solution. We propose a new constraint programming (CP) formulation for the SCC scheduling problem and develop an algorithm, called Iterated Greedy CP (IGC), which uses the framework of IGM but replaces the MIP model with our CP model. When we solve the CP subproblems iteratively, we also refine them by adding appropriate constraints, reducing the domains of the variables, and giving the variables hints derived from the current solution. From computational experiments in various settings, we show that IGC implemented with an open-source CP solver can be competitive with IGM running on a commercial MIP solver.
constraint programming (CP) and Machine Learning (ML) face challenges in text generation due to CP's struggle with implementing "meaning"and ML's difficulty with structural constraints. This paper pr...
详细信息
暂无评论