检索结果-内蒙古大学图书馆

29th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS)

作者： Lester, Martin Mariusz Univ Reading Reading Berks England

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.

关键词： constraint programming bounded model checking C programming language

来源：评论

学校读者我要写书评

暂无评论

An Efficient constraint programming Approach for Solving the Multi-Workshop Facility Layout Problem 10

An Efficient Constraint Programming Approach for Solving the...

引用

10th International Conference on Systems and Informatics, ICSAI 2024

作者： Zhang, Yu Zhang, Zeqiang Chen, Feng He, Zongxing School of Mechanical Engineering Southwest Jiaotong University Chengdu610031 China Chengdu SIWI High-Tech Industrial Co. Ltd. Chengdu610031 China

ISBN: (纸本)9798331510138

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 manufacturing systems. This study introduces constraint programming (CP) techniques to the facility layout problem and proposes a multi-objective optimization framework to address the MWFLP. The model employs interval variables to accurately represent facility dimensions and integrates cumulative functions to rigorously enforce non-overlapping and spatial constraints. To improve computational efficiency, symmetry-breaking constraints are introduced to minimize redundant solution spaces and accelerate the search for better layout. The effectiveness of the CP model is demonstrated through comprehensive experimental evaluations, where it consistently delivers superior solution quality and computational efficiency compared to the mixed-integer programming model. In multi-objective optimization scenarios, the CP framework outperforms the multi-objective particle swarm optimization method, offering enhanced solution precision and stability across diverse problem scales. © 2024 IEEE.

关键词： constraint programming

来源：评论

学校读者我要写书评

暂无评论

A comprehensive tolerant algebraic side-channel attack over modern ciphers using constraint programming

引用

JOURNAL OF CRYPTOGRAPHIC ENGINEERING 2022年第2期12卷 197-228页

作者： Liu, Fanghui Cruz, Waldemar Michel, Laurent Univ Connecticut Sch Engn Comp Sci & Engn Dept Storrs CT 06269 USA Univ Connecticut Sch Engn Comp Sci & Engn Dept Synchrony Chair Cybersecur Storrs CT 06269 USA

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.

关键词： Algebraic side-channel attack AES Cryptography Block cipher constraint programming Optimization

来源：评论

学校读者我要写书评

暂无评论

Solving the time-discrete winter runway scheduling problem: A column generation and constraint programming approach

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2022年第2期299卷 674-689页

作者： Pohl, Maximilian Artigues, Christian Kolisch, Rainer Tech Univ Munich TUM Sch Management Arcisstr 21 D-80333 Munich Germany CNRS Lab Anal & Architecture Syst 7 Ave Colonel Roche F-31031 Toulouse France

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.

关键词： Scheduling Airport operations Column generation constraint programming

来源：评论

学校读者我要写书评

暂无评论

Generative magic and designing magic performances with constraint programming

引用

constraintS 2022年第3期27卷 168-191页

作者： de Azevedo Silveira, Guilherme Alura Rua Vergueiro 3185 BR-04101300 Sao Paulo SP Brazil

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.

关键词： constraint Generative design Computer aided design constraint programming Generative magic Magical performance

来源：评论

学校读者我要写书评

暂无评论

New mathematical and constraint programming models for U-type assembly line balancing problems with assignment restrictions

引用

ENGINEERING OPTIMIZATION 2022年第8期54卷 1289-1304页

作者： Pinarbasi, Mehmet OSTIM Tech Univ Dept Ind Engn Ankara Turkey

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.

关键词： Assembly line balancing U-type problem assignment restrictions mathematical programming constraint programming

来源：评论

学校读者我要写书评

暂无评论

Mixed-integer linear programming, constraint programming and column generation approaches for operating room planning under block strategy

引用

APPLIED MATHEMATICAL MODELLING 2022年 105卷 438-453页

作者： Ghandehari, Najmeh Kianfar, Kamran Univ Isfahan Fac Adm Sci & Econ Dept Management Esfahan *** Iran Univ Isfahan Fac Engn Esfahan *** Iran

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.

关键词： Operating room planning Block strategy Master surgery schedule Mixed-integer linear programming constraint programming Column generation

来源：评论

学校读者我要写书评

暂无评论

Black-Box Value Heuristics for Solving Optimization Problems with constraint programming 30

Black-Box Value Heuristics for Solving Optimization Problems...

引用

30th International Conference on Principles and Practice of constraint programming, CP 2024

作者： Delecluse, Augustin Schaus, Pierre TRAIL ICTEAM UCLouvain Belgium ICTEAM UCLouvain Belgium

ISBN: (纸本)9783959773362

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. The Bound-Impact Value Selection achieves this goal through a look-ahead strategy, trying every value of the selected variable and ranking them based on their impact on the objective. However, this method is generally too computationally intensive for the entire search tree. We introduce two simple yet powerful modifications to improve its scalability. First, a lighter fix point computation involving only the constraints on the shortest path in the constraint graph between the variable and the objective. Second, a reverse look-ahead strategy optimistically fixes the objective variable to its minimum in order to prioritize the remaining values. These two ideas have been empirically validated on a range of academic problems and in the XCSP3 competition, demonstrating significant improvements in scalability. © Augustin Delecluse and Pierre Schaus.

关键词： constraint programming

来源：评论

学校读者我要写书评

暂无评论

Iterated Greedy constraint programming for Scheduling Steelmaking Continuous Casting 20th

Iterated Greedy Constraint Programming for Scheduling Steelm...

引用

20th International Conference on the Integration of constraint programming, Artificial Intelligence, and Operations Research (CPAIOR)

作者： Kim, Dongyun Choi, Yeonjun Moon, Kyungduk Lee, Myungho Lee, Kangbok Pinedo, Michael L. Pohang Univ Sci & Technol Pohang South Korea NYU Stern Sch Business New York NY USA

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.

关键词： Scheduling steelmaking-continuous casting process hybrid flow shop constraint programming computational experiments

来源：评论

学校读者我要写书评

暂无评论

Combining constraint programming Reasoning with Large Language Model Predictions 30

Combining Constraint Programming Reasoning with Large Langua...

引用

30th International Conference on Principles and Practice of constraint programming, CP 2024

作者： Régin, Florian De Maria, Elisabetta Bonlarron, Alexandre Université Côte d'Azur I3S CNRS Sophia Antipolis France Université Côte d'Azur Inria Sophia Antipolis France

ISBN: (纸本)9783959773362

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 proposes a solution by combining both approaches and embedding a Large Language Model (LLM) in CP. The LLM handles word generation and meaning, while CP manages structural constraints. This approach builds on GenCP, an improved version of On-the-fly constraint programming Search (OTFS) using LLM-generated domains. Compared to Beam Search (BS), a standard NLP method, this combined approach (GenCP with LLM) is faster and produces better results, ensuring all constraints are satisfied. This fusion of CP and ML presents new possibilities for enhancing text generation under constraints. © Florian Régin, Elisabetta De Maria, and Alexandre Bonlarron.

关键词： constraint programming

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：