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

Two-stage stochastic/robust scheduling based on permutable operation groups

ANNALS OF OPERATIONS RESEARCH 2024年第1-3期332卷 645-687页

作者： Riviere, Louis Artigues, Christian Fargier, Helene Univ Toulouse IRIT CNRS UPS Toulouse France Univ Toulouse LAAS CNRS CNRS UPS Toulouse France Univ Toulouse Artificial & Nat Intelligence Toulouse Inst Toulouse France

In this paper we study the performance of a two-stage approach to scheduling under uncertainty making use of sequences of groups of permutable operations. Given a sample set of uncertainty realization scenarios, the goal is to compute a sequence of groups of permutable operations representing a partial scheduling decision in the first-stage, that yields the best possible score in the second-stage, when, for a specific scenario, a full operation sequence is obtained via a second-stage decision policy. This approach is described for a single-machine problem and the jobshop problem with stochastic and robust optimization, as well as several commonly studied objectives. We propose new constraint programming models as well as a genetic algorithm meta-heuristic to compute such two-stage solutions. We also investigate a warm-start scheme to work around the difficult search space of sequences of permutable operations. Experiments are carried out to characterize when this two-stage approach yields better results. We also compare the introduced methods with existing ones. Theoretical extensions of the known methods are also described and evaluated.

关键词： Stochastic and robust 2-stage scheduling Permutable operation groups constraint programming

来源：评论

学校读者我要写书评

暂无评论

Learning cost action planning models with perfect precision via constraint propagation

引用

INFORMATION SCIENCES 2023年第1期628卷 148-176页

作者： Garrido, Antonio Univ Politecn Valencia Valencian Res Inst Artificial Intelligence VRAIN Valencia Spain

Data-driven AI is rapidly gaining importance. In the context of AI planning, a constraint programming formulation for learning action models in a data-driven fashion is proposed. Data comprises plan observations, which are automatically transformed into a set of planning constraints which need to be satisfied. The formulation captures the essence of the action model and unifies functionalities that are individually supported by other learning approaches, such as costs, noise/uncertainty on actions, information on intermediate state observations and mutex *** is a key concern in data-driven learning, but existing approaches usually learn action models that can be imprecise, where imprecision here is an error indicator of learning something incorrect. On the contrary, the proposed approach guarantees reliability in terms of perfect precision by using constraint propagation. This means that what is learned is 100% correct (i.e., error-free), not only for the initial observations, but also for future observations. To our knowledge, this is a novelty in action model learning literature. Although perfect precision might potentially limit the amount of learned information, the exhaustive experiments over 20 planning domains show that such amount is comparable, and even better, to ARMS and FAMA, two state-of-the-art benchmarks in action model learning.

关键词： Learning Cost action model Classical planning constraint programming Reliability Precision

来源：评论

学校读者我要写书评

暂无评论

Automatic Demirci-Selcuk Meet-In-The-Middle Attack On SIMON

引用

COMPUTER JOURNAL 2023年第12期66卷 3052-3068页

作者： Lv, Yin Shi, Danping Guo, Yi Chen, Qiu Hu, Lei Guo, Zihui Chinese Acad Sci Inst Informat Engn State Key Lab Informat Secur Beijing 100093 Peoples R China Univ Chinese Acad Sci Sch Cyber Secur Beijing 100093 Peoples R China Chinese Acad Sci Inst Informat Engn Beijing 100093 Peoples R China

Demirci-Selcuk meet-in-the-middle (DS-MITM) attack is an effective method for cryptanalysis. As far as we know, the published automatic results of DS-MITM attack are all for byte-oriented ciphers. In this article, we first propose the automatic analysis method of DS-MITM attack for bit-oriented ciphers based on constraint programming, which is integrated with key-bridging technique. Based on the automatic modeling method, we propose the first result of DS-MITM attack on SIMON, which is a family of lightweight block ciphers proposed by the National Security Agency (NSA) in 2013.

关键词： Demirci-Selcuk meet-in-the-middle attack SIMON constraint programming key-bridging technique

来源：评论

学校读者我要写书评

暂无评论

An efficient relax-and-solve method for the multi-mode resource constrained project scheduling problem

引用

ANNALS OF OPERATIONS RESEARCH 2024年第1期338卷 41-68页

作者： Etminaniesfahani, Alireza Gu, Hanyu Naeni, Leila Moslemi Salehipour, Amir Univ Technol Sydney Sch Math & Phys Sci Broadway Sydney NSW 2007 Australia Univ Technol Sydney Sch Built Environm Broadway Sydney NSW 2007 Australia Univ Sydney Business Sch Darlington NSW 2006 Australia

The multi-mode resource constrained project scheduling problem (MRCPSP) is an NP-hard optimisation problem involving scheduling tasks under resource and precedence constraints, while there are several modes for executing each task. In this paper, we propose a novel matheuristic based on relax-and-solve (R &S) algorithm to solve MRCPSP. In addition, a mathematical programming model, which is the generalisation of the multi-dimensional knapsack problem is developed. That model conducts the mode selection process for the purpose of generating an initial feasible solution. We evaluate the performance of the proposed algorithm by solving benchmark instances that are widely used in the literature. The results demonstrate that the proposed R &S algorithm outperforms the state-of-the-art methods for solving the MRCPSP.

关键词： Relax-and-solve Multi-mode resource constrained project scheduling problem Matheuristic Rolling time window constraint programming

来源：评论

学校读者我要写书评

暂无评论

Tumato 2.0-a constraint-based planning approach for safe and robust robot behavior

引用

ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE 2024年 1-27页

作者： Vermaelen, Jan Holvoet, Tom Katholieke Univ Leuven DistriNet B-3001 Leuven Belgium

Ensuring the safe and effective operation of autonomous systems is a complex undertaking that inherently relies on underlying decision-making processes. To rigorously analyze these processes, formal verification methods, such as model checking, offer a valuable means. However, the non-deterministic nature of realistic environments makes these approaches challenging and often impractical. This work explores the capabilities of a constraint-based planning approach, Tumato, in generating policies that guide the system to predefined goals while adhering to safety constraints. constraint-based planning approaches are inherently able to provide guarantees of soundness and completeness. Our primary contribution lies in extending Tumato's capabilities to accommodate non-deterministic outcomes of actions, enhancing the robustness of the behavior. Originally designed to accommodate only deterministic outcomes, actions can now be modeled to include alternative outcomes to address contingencies explicitly. The adapted solver generates policies that enable reaching the goals in a safe manner, even when such alternative outcomes of actions occur. Additionally, we introduce a purely declarative manner for specifying safety in Tumato to further enhance its expressiveness as well as to reduce the susceptibility to errors during specification. The incorporation of cost or duration values to actions enables the solver to restore safety in the most preferred manner when necessary. Finally, we highlight the overlap of Tumato's safety-related capabilities with a systems-theoretic approach, STPA (Systems-Theoretic Process Analysis). The aim is to emphasize the ability to avoid unsafe control actions without their explicit identification, contributing to a more comprehensive and holistic understanding of safety.

关键词： Autonomous systems Behavior specification Safe and robust planning constraint programming Tumato

来源：评论

学校读者我要写书评

暂无评论

Large neighborhood search for an aeronautical assembly line time-constrained scheduling problem with multiple modes and a resource leveling objective

引用

ANNALS OF OPERATIONS RESEARCH 2024年第1期338卷 13-40页

作者： Sanchidrian, Tamara Borreguero Portoleau, Tom Artigues, Christian Sanchez, Alvaro Garcia Mier, Miguel Ortega Lopez, Pierre Airbus Paseo John Lennon S-N Getafe 28906 Spain Univ Toulouse CNRS LAAS 7 Ave Colonel Roche F-31400 Toulouse France Univ Politecn Madrid Ind Engn & Logist Res Grp ETSII Jose Gutierrez Abascal 2 Madrid 28006 Spain

This paper deals with a scheduling problem arising at the tactical decision level in aeronautical assembly line. It has the structure of a challenging multi-mode resource-constrained project scheduling problem with incompatibility constraints, a resource leveling objective and also a large number of tasks. We first present a new event-based mixed-integer linear programming formulation and a standard constraint programming formulation of the problem. A large-neighborhood search approach based on the constraint programming model and tailored to the resource leveling objective is proposed. The approaches are tested and compared using industrial instances, yielding significant improvement compared to the heuristic currently used by the company. Moreover, the large-neighborhood search method significantly improves the method proposed in the literature on a related multi-mode resource investment problem when short CPU times are required.

关键词： Aeronautical assembly line scheduling Multiple modes Resource leveling Mixed-integer linear programming constraint programming Large neighborhood search

来源：评论

学校读者我要写书评

暂无评论

Extension of constraint-procedural logic-generated environments for deep Q-learning agent training and benchmarking

引用

JOURNAL OF LOGIC AND COMPUTATION 2023年第8期33卷 1712-1733页

作者： De Gasperis, Giovanni Costantini, Stefania Rafanelli, Andrea Migliarini, Patrizio Letteri, Ivan Dyoub, Abeer Univ LAquila Dept Informat Engn Comp Sci & Math Via Vetoio I-67100 Laquila Italy Univ Pisa Dept Comp Sci Largo B Pontecorvo I-57127 Pisa Italy

Autonomous robots can be employed in exploring unknown environments and performing many tasks, such as, e.g. detecting areas of interest, collecting target objects, etc. Deep reinforcement learning (RL) is often used to train this kind of robot. However, concerning the artificial environments aimed at testing the robot, there is a lack of available data sets and a long time is needed to create them from scratch. A good data set is in fact usually produced with high effort in terms of cost and human work to satisfy the constraints imposed by the expected results. In the first part of this paper, we focus on the specification of the properties of the solutions needed to build a data set, making the case of environment exploration. In the proposed approach, rather than using imperative programming, we explore the possibility of generating data sets using constraint programming in Prolog. In this phase, geometric predicates describe a virtual environment according to inter-space requirements. The second part of the paper is focused on testing the generated data set in an AI gym via space search techniques. We developed a Neuro-Symbolic agent built from the following: (i) A deep Q-learning component implemented in Python, able to address via RL a search problem in the virtual space;the agent has the goal to explore a generated virtual environment to seek for a target, improving its performance through a RL process. (ii) A symbolic component able to re-address the search when the Q-learning component gets stuck in a part of the virtual environment;these components stimulate the agent to move to and explore other parts of the environment. Wide experimentation has been performed, with promising results, and is reported, to demonstrate the effectiveness of the approach.

关键词： Procedural generation constraint programming deep Q-learning neuro-symbolic intelligent agents computer aided design architecture

来源：评论

学校读者我要写书评

暂无评论

Generic Exact Combinatorial Search at HPC Scale

引用

INTERNATIONAL JOURNAL OF PARALLEL programming 2023年第1期51卷 83-106页

作者： MacGregor, Ruairidh Archibald, Blair Trinder, Phil Univ Glasgow Sch Comp Sci Glasgow Scotland

Exact combinatorial search is essential to a wide range of important applications, and there are many large problems that need to be solved quickly. Searches are extremely challenging to parallelise due to a combination of factors, e.g. searches are non-deterministic, dynamic pruning changes the workload, and search tasks have very different runtimes. YewPar is a C++/HPX framework that generalises parallel search by providing a range of sophisticated search *** paper demonstrates generic high performance combinatorial search, i.e. that a variety of exact combinatorial searches can be easily parallelised for HPC using YewPar. We present a new mechanism for profiling key aspects of YewPar parallel combinatorial search, and demonstrate its value. We exhibit, for the first time, generic exact combinatorial searches at HPC scale. We baseline YewPar against state-of-the-art sequential C++ and C++/OpenMP implementations. We demonstrate that deploying YewPar on an HPC system can dramatically reduce the runtime of large problems, e.g. from days to just 100s. The maximum relative speedups we achieve for an enumeration search are near-linear up to 195(6825) compute-nodes(workers), super-linear for an optimisation search on up to 128(4480) (pruning reduces the workload), and sub-linear for decision searches on up to 64(2240) compute-nodes(workers).

关键词： Combinatorial search Parallel skeletons constraint programming High performance computing

来源：评论

学校读者我要写书评

暂无评论

A System for Automated Industrial Test Laboratory Scheduling

引用

ACM TRANSACTIONS ON INTELLIGENT SYSTEMS AND TECHNOLOGY 2023年第1期14卷 1-27页

作者： Danzinger, Philipp Geibinger, Tobias Janneau, David Mischek, Florian Musliu, Nysret Poschalko, Christian TU Wien DBAI Christian Doppler Lab Artificial Intelligence & O Karlspl 13 A-1040 Vienna Austria Robert Bosch AG Gollnergasse 15-17 A-1030 Vienna Austria

Automated scheduling solutions are tremendously important for the efficient operation of industrial laboratories. The Test Laboratory Scheduling Problem (TLSP) is an extension of the well-known Resource Constrained Project Scheduling Problem (RCPSP) and captures the specific requirements of such laboratories. In addition to several new scheduling constraints, it features a grouping phase, where the jobs to be scheduled are assembled from smaller units. In this work, we introduce an innovative scheduling system that allows the efficient and flexible generation of schedules for TLSP. It features a new constraint programming model that covers both the grouping and the scheduling aspect, as well as a hybrid Very Large Neighborhood Search that internally uses the CP model. Our experimental results on generated and real-world benchmark instances show that good results can be obtained even compared to settings which have a good grouping already provided, including several new best known solutions for these instances. Our algorithms for TLSP have been successfully implemented in a real-world industrial test laboratory. We provide a detailed description of the deployed system as well as additional useful soft constraints supported by the solvers and general lessons learned. This includes a discussion of the choice of soft constraint weights, with an analysis on the impact and relation of different objectives to each other. Our experiments show that some soft constraints complement each other well, while others require explicit trade-offs via their relative weights.

关键词： Test laboratory scheduling RCPSP constraint programming very large neighborhood search

来源：评论

学校读者我要写书评

暂无评论

Computing relaxations for the three-dimensional stable matching problem with cyclic preferences

引用

constraintS 2023年第2期28卷 138-165页

作者： Cseh, Agnes Escamocher, Guillaume Quesada, Luis Ctr Econ & Reg Stud Inst Econ Budapest Hungary Univ Bayreuth Dept Math Bayreuth Germany Insight Ctr Data Analyt Cork Ireland Univ Coll Cork Sch Comp Sci & Informat Technol Cork Ireland

constraint programming has proven to be a successful framework for determining whether a given instance of the three-dimensional stable matching problem with cyclic preferences (3dsm-cyc) admits a solution. If such an instance is satisfiable, constraint models can even compute its optimal solution for several different objective functions. On the other hand, the only existing output for unsatisfiable 3dsm-cyc instances is a simple declaration of impossibility. In this paper, we explore four ways to adapt constraint models designed for 3dsm-cyc to the maximum relaxation version of the problem, that is, the computation of the smallest part of an instance whose modification leads to satisfiability. We also extend our models to support the presence of costs on elements in the instance, and to return the relaxation with lowest total cost for each of the four types of relaxation. Empirical results reveal that our relaxation models are efficient, as in most cases, they show little overhead compared to the satisfaction version.

关键词： Three-dimensional stable matching with cyclic preferences 3dsm-cyc constraint programming Relaxation Almost stable matching

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：