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

OPTIMATHSAT: A Tool for optimization modulo theories

JOURNAL OF AUTOMATED REASONING 2020年第3期64卷 423-460页

作者： Sebastiani, Roberto Trentin, Patrick Univ Trento DISI Via Sommar 9 I-39123 Trento Italy

optimization modulo theories (OMT) is an extension of SMT which allows for finding models that optimize given objectives. OptiMathSAT is an OMT solver which allows for solving a list of optimization problems on SMT formulas with linear objective functions-on the Boolean, the rational and the integer domains, and on their combination thereof-including (partial weighted) MaxSMT . Multiple and heterogeneous objective functions can be combined together and handled either independently, or lexicographically, or in linear or min-max /max-min combinations. OptiMathSAT provides an incremental interface, it supports both an extended version of the SMT-LIBv2 language and a subset of the FlatZinc language, and can be interfaced via an API. In this paper we describe OptiMathSAT and its usage in full detail.

关键词： OPTIMATHSAT optimization modulo theories OMT MAXSMT Sorting networks Multi-objective optimization

来源：评论

学校读者我要写书评

暂无评论

Solving Multi-Objective Workflow Satisfiability Problems with optimization modulo theories Techniques 18

Solving Multi-Objective Workflow Satisfiability Problems wit...

引用

23rd ACM Symposium on Access Control Models and Technologies (SACMAT)

作者： Bertolissi, Clara dos Santos, Daniel R. Ranise, Silvio Aix Marseille Univ Marseille France CNRS Paris France Eindhoven Univ Technol Eindhoven Netherlands Fdn Bruno Kessler Trento Italy

ISBN: (纸本)9781450356664

Security-sensitive workflows impose constraints on the control-flow and authorization policies that may lead to unsatisfiable instances. In these cases, it is still possible to find "least bad" executions where costs associated to authorization violations are minimized, solving the so-called Multi-Objective Workflow Satisfiability Problem (MO-WSP). The MO-WSP is inspired by the Valued WSP and its generalization, the Bi-Objective WSP, but our work considers quantitative solutions to the WSP without abstracting control-flow constraints. In this paper, we define variations of the MO-WSP and solve them using bounded model checking and optimization modulo theories solving. We validate our solutions on real-world workflows and show their scalability on synthetic instances.

关键词： Business process Workflow Satisfiability optimization modulo theories

来源：评论

学校读者我要写书评

暂无评论

optimization modulo the theories of Signed Bit-Vectors and Floating-Point Numbers

引用

JOURNAL OF AUTOMATED REASONING 2021年第7期65卷 1071-1096页

作者： Trentin, Patrick Sebastiani, Roberto Univ Trento DISI Trento Italy

optimization modulo theories (OMT) is an important extension of SMT which allows for finding models that optimize given objective functions, typically consisting in linear-arithmetic or Pseudo-Boolean terms. However, many SMT and OMT applications, in particular from SW and HW verification, require handling bit-precise representations of numbers, which in SMT are handled by means of the theory of bit-vectors (BV) for the integers and that of floating-point numbers (FP) for the reals respectively. Whereas an approach for OMT with (unsigned) BV objectives has been proposed by Nadel & Ryvchin, unfortunately we are not aware of any existing approach for OMT with FP objectives. In this paper we fill this gap, and we address for the first time OMT with FP objectives. We present a novel OMT approach, based on the novel concept of attractor and dynamic attractor, which extends the work of Nadel and Ryvchin to work with signed-BV objectives and, most importantly, with FP objectives. We have implemented some novel OMT procedures on top of OPTIMATHSAT and tested them on modified problems from the SMT-LIB repository. The empirical results support the validity and feasibility of our novel approach.

关键词： optimization modulo theories OMT Satisfiability modulo theories SMT Floating-Point Arithmetic attractor dynamic attractor

来源：评论

学校读者我要写书评

暂无评论

Solving linear optimization over arithmetic constraint formula

引用

JOURNAL OF GLOBAL optimization 2017年第1期69卷 69-102页

作者： Chen, Li Lyu, Yinrun Wang, Chong Wu, Jingzheng Zhang, Changyou Min-Allah, Nasro Alhiyafi, Jamal Wang, Yongji Chinese Acad Sci Inst Software State Key Lab Comp Sci Beijing 100190 Peoples R China Chinese Acad Sci Inst Software Lab Parallel Software & Computat Sci Beijing 100190 Peoples R China Univ Chinese Acad Sci Beijing 100049 Peoples R China Univ Dammam CCSIT Dammam Saudi Arabia Chinese Acad Sci Inst Software Natl Engn Res Ctr Fundamental Software Beijing 100190 Peoples R China

Since Balas extended the classical linear programming problem to the disjunctive programming (DP) problem where the constraints are combinations of both logic AND and OR, many researchers explored this optimization problem under various theoretical or application scenarios such as generalized disjunctive programming (GDP), optimization modulo theories (OMT), robot path planning, real-time systems, etc. However, the possibility of combining these differently-described but form-equivalent problems into a single expression remains overlooked. The contribution of this paper is two folded. First, we convert the linear DP/GDP model, linear-arithmetic OMT problem and related application problems into an equivalent form, referred to as the linear optimization over arithmetic constraint formula (LOACF). Second, a tree-search-based algorithm named RS-LPT is proposed to solve LOACF. RS-LPT exploits the techniques of interval analysis and nonparametric estimation for reducing the search tree and lowering the number of visited nodes. Also, RS-LPT alleviates bad construction of search tree by backtracking and pruning dynamically. We evaluate RS-LPT against two most common DP/GDP methods, three state-of-the-art OMT solvers and the disjunctive transformation based method on optimization benchmarks with different types and scales. Our results favor RS-LPT as compared to existing competing methods, especially for large scale cases.

关键词： Linear programming Disjunctive programming optimization modulo theories Search algorithm

来源：评论

学校读者我要写书评

暂无评论

Solving SAT (and MaxSAT) with a quantum annealer: Foundations, encodings, and preliminary results

引用

INFORMATION AND COMPUTATION 2020年 275卷

作者： Bian, Zhengbing Chudak, Fabian Macready, William Roy, Aidan Sebastiani, Roberto Varotti, Stefano D Wave Syst Inc 3033 Beta Ave Burnaby BC V5G 4M9 Canada Univ Trento DISI Via Sommar 9 I-38123 Povo TN Italy Sanctuary AI Vancouver BC Canada

Quantum annealers (QAs) are specialized quantum computers that minimize objective functions over discrete variables by physically exploiting quantum effects. Current QA platforms allow for the optimization of quadratic objectives defined over binary variables (qubits), also known as Ising problems. In the last decade, QA systems as implemented by D-Wave have scaled with Moore-like growth. Current architectures provide 2048 sparselyconnected qubits, and continued exponential growth is anticipated, together with increased connectivity. We explore the feasibility of such architectures for solving SAT and MaxSAT problems as QA systems scale. We develop techniques for effectively encoding SAT -and, with some limitations, MaxSAT- into Ising problems compatible with sparse QA architectures. We provide the theoretical foundations for this mapping, and present encoding techniques that combine offline Satisfiability and optimization modulo theories with on-the-fly placement and routing. Preliminary empirical tests on a current generation 2048-qubit D-Wave system support the feasibility of the approach for certain SAT and MaxSAT problems. (C) 2020 Elsevier Inc. All rights reserved.

关键词： Quantum annealing (QA) Ising model Satisfiability modulo theories optimization modulo theories SAT MaxSAT Chimera graph Quadratic unconstrained binary optimization (QUBO)

来源：评论

学校读者我要写书评

暂无评论

An interleaved depth-first search method for the linear optimization problem with disjunctive constraints

引用

JOURNAL OF GLOBAL optimization 2018年第4期70卷 737-756页

作者： Lyu, Yinrun Chen, Li Zhang, Changyou Qu, Dacheng Min-Allah, Nasro Wang, Yongji Beijing Inst Technol Beijing 100081 Peoples R China Univ Dammam CCSIT Dammam Saudi Arabia Chinese Acad Sci Inst Software State Key Lab Comp Sci Beijing 100190 Peoples R China Univ Chinese Acad Sci Beijing 100049 Peoples R China

Being an extension of classical linear programming, disjunctive programming has the ability to express the problem constraints as combinations of linear equalities and inequalities linked with logic AND and OR operations. All the existing theories such as generalized disjunctive programming, optimization modulo theories, linear optimization over arithmetic constraint formula, and mixed logical linear programming pose one commonality of branching among different solving techniques. However, branching constructs a depth-first search which may traverse a whole bad subtree when the branching makes a mistake ordering a bad successor. In this paper, we propose the interleaved depth-first search with stochastic local optimal increasing (IDFS-SLOI) method for solving the linear optimization problem with disjunctive constraints. Our technique searches depth-first several subtrees in turn, accelerates the search by subtree splitting, and uses efficient backtracking and pruning among the subtrees. Additionally, the local optimal solution is improved iteratively by constructing and solving a stochastic linear programming problem. We evaluate our approach against existing counterparts on the rate-monotonic optimization problem (RM-OPT) and the linear optimization with fuzzy relation inequalities problem (LOFRI). Experimental results show that for the tested instances, the IDFS-SLOI method performs better from performance perspective, especially promising results have been obtained for the larger three groups where the execution time is reduced by 85.6 and 51.6% for RM-OPT and LOFRI, respectively.

关键词： Global optimization Disjunctive programming optimization modulo theories Search algorithm

来源：评论

学校读者我要写书评

暂无评论

Reliability-Aware Comprehensive Routing and Scheduling in Time-Sensitive Networking 17th

Reliability-Aware Comprehensive Routing and Scheduling in Ti...

引用

17th International Conference on Wireless Algorithms, Systems, and Applications (WASA)

作者： Feng, Jiaqi Zhang, Tong Yi, Changyan Nanjing Univ Aeronaut & Astronaut Coll Comp Sci & Technol Nanjing Peoples R China

ISBN: (纸本)9783031192135;9783031192142

Nowadays, Time-Sensitive Networking (TSN) has widespread application in many industrial fields, aiming to provide deterministic lowl-atency network transmission. Traffic in TSN is roughly divided into three categories: Time-Triggered (TT) traffic, Audio-Video-Bridging (AVB) traffic, and Best-Effort (BE) traffic. These different traffic needs to travel the network satisfying their respective reliability and performance requirements. Existing traffic routing and scheduling mechanisms mainly focus on TT traffic but pay little attention to other traffic types. In this paper, we present a novel optimization modulo theories (OMT) formulation for a comprehensive traffic routing and scheduling problem in TSN. Based on this, we propose a novel reliability-aware routing and scheduling mechanisms for all traffic types, in order to improve their own transmission reliability and performance. We conduct extensive evaluations to validate the effectiveness of the proposed mechanisms, and the results confirm that the proposed mechanism can really guarantee the reliability and latency requirements of TT flows and improve the transmission utility of all flows to a large extent.

关键词： Time-Sensitive Networking optimization modulo theories Routing Scheduling Reliability-aware

来源：评论

学校读者我要写书评

暂无评论

The Next Release Problem Revisited: A New Avenue for Goal Models 26

The Next Release Problem Revisited: A New Avenue for Goal Mo...

引用

26th IEEE International Requirements Engineering Conference (RE)

作者： Aydemir, Fatma Basak Dalpiaz, Fabiano Brinkkemper, Sjaak Giorgini, Paolo Mylopoulos, John Univ Utrecht Utrecht Netherlands Univ Trento Trento Italy Univ Ottawa Ottawa ON Canada

ISBN: (纸本)9781538674185

Context. Goal models have long been critiqued for the time it takes to construct them as well as for their limited cognitive and visual scalability. Is such criticism general or does it depend on the supported task? Objectives. We advocate for the latter and the aim of this paper is to demonstrate that the next release problem is a suitable application domain for goal models. This hypothesis stems from the fact that product release management is a long-term investment, and software products are commonly managed in "themes" which are smaller focus areas of the product. Methods. We employ a version of goal models that is tailored for the next release problem by capturing requirements, synergies among them, constraints, and release objectives. Such goal model allows discovering optimal solutions considering multiple criteria for the next release. Results. A retrospective case study confirms that goal models are easier to read and comprehend when organized in themes, and that the reasoning results help product managers decide for the next release. Our scalability experiments show that, through reasoning based on optimization modulo theories, the discovery of the optimal solution is fast and scales sufficiently well with respect to the model size, connectivity, and number of alternative solutions.

关键词： next release problem release planning goal-oriented requirements engineering constrained goal models multi-objective optimization optimization modulo theories

来源：评论

学校读者我要写书评

暂无评论

Design and Evolution of Sociotechnical Systems: A Requirements Engineering Perspective

Design and Evolution of Sociotechnical Systems: A Requiremen...

引用

作者： Fatma Basak Aydemir University of Trento

学位级别：博士

Sociotechnical systems are systems of systems where social, technical, and organiza- tional systems interact with each other to satisfy their requirements. The interplay of social and technical systems blurs the borders in between them, and the constant change within and outside the sociotechncial systems create difficulties to manage the overall evo- lution. This thesis explores the methods to model, analyse, and evolve the requirements of sociotechnical systems. We propose a systematic design process and a formal language to aid social systems refine their requirements into not other requirements but also so- cial interactions to generate system as well as interaction specifications. Although such specifications are useful to generate interaction protocols among systems, they haven't been investigated in detail by the requirements engineering community. We then explore the design space created during the design process with artificial intelligence planing to discover sequence of actions to satisfy requirements with minimal cost. We adopt an iterative approach for handling requirements evolution and focus on the problem of selecting the optimal set of requirements for the next release. We capture syn- ergies among requirements in goal-oriented requirements models and transform the next release problem into a multi-objective satisfiability modulo theories/optimization modulo theories problem and solve it using an external reasoner. We apply a similar approach for risk analysis using goal models. We model goals, risks, and treatments in three layers and solve multi-objective risk analysis problem with SMT/OMT reasoning. We evaluate our proposal with self-evaluation studies, a case study and scalability experiments and report results. The novelty of these two approaches is the combination of satisfiability analysis with multi-objective optimization for goal models.

关键词： requirements engineering sociotechnical systems design social commitments planing next release problem multi-objective optimization satisfiability modulo theories optimization modulo theories risk analysis goal-models

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：