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

Fast enumeration of all cost-bounded solutions for combinatorial problems using ZDDs

DISCRETE APPLIED MATHEMATICS 2025年 360卷 467-486页

作者： Minato, Shin-ichi Kawahara, Jun Banbara, Mutsunori Horiyama, Takashi Takigawa, Ichigaku Yamaguchi, Yutaro Kyoto Univ Kyoto Japan Nagoya Univ Nagoya Japan Hokkaido Univ Sapporo Japan Osaka Univ Osaka Japan

We propose a fast method for exactly enumerating a large number of all cost-bounded solutions for combinatorial problems using Zero-suppressed Binary Decision Diagrams (ZDDs). Enumerating cost-bounded solutions is an important task to know the exact ranking of any given solution, and it enables statistical p-value evaluation and qualitycontrolled random sampling. Our method is based on a backtracking search for a given ZDD representing the set of all feasible solutions. The key idea is to integrate "BDD operation cache"technique and "interval-memoizing"technique with a depth-first manner of backtracking procedure. The computation time of the algorithm is empirically bounded by the input and output sizes of ZDDs. It can be significantly faster than existing enumeration systems, especially when the input and output ZDDs are wellcompressed and the range of the cost constraint is large. As application examples, we applied our method to a set of difficult instances of the Hamiltonian cycle/path problems. Although it is NP-hard to find any one feasible solution without cost constraints, we tried more difficult problems to enumerate all cost-bounded solutions, and succeeded in implicitly enumerating all cost-bounded solutions for many nontrivial instances which contain billions of solutions. As cost constraints often appear in many real-life situations, our method will be useful in various fields, including data mining, statistical testing, hardware/software design, and many other operations research problems. (c) 2024 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).

关键词： Decision diagrams combinatorial problems Exact enumeration Cost-bounded solutions

来源：评论

学校读者我要写书评

暂无评论

An efficient enhanced exponential distribution optimizer: applications in global, engineering, and combinatorial optimization problems

引用

JOURNAL OF BIG DATA 2025年第1期12卷 1-55页

作者： Emam, Marwa M. Saad, Mohammed R. Younan, Mina Houssein, Essam H. Minia Univ Fac Comp & Informat Al Minya Egypt Luxor Univ Fac Comp & Informat Luxor Egypt Minia Natl Univ Al Minya Egypt

This paper introduces an enhanced exponential distribution optimizer (EDO), termed the exponential distribution optimizer with Levy flight orthogonal learning (EDO-LFOL). EDO-LFOL enhances EDO by integrating the Levy flight (LF) strategy during the intensification phase and utilizing the orthogonal learning (OL) approach after the end of the optimization cycle. This adjustment aims to mitigate the risk of local optima entrapment and improve the quality of the solutions obtained. This paper presents EDO-LFOL as a viable global and practical optimization problem solution. To evaluate the effectiveness of EDO-LFOL, we compare it against seven robust optimizers across 12 unconstrained test functions associated with the IEEE Congress on Evolutionary Computation 2022 (CEC 2022). The optimizers include the improved multi-operator differential evolution algorithm (IMODE), adaptive guided differential evolution algorithm (AGDE), whale optimization algorithm (WOA), grey wolf optimizer (GWO), sinh cosh optimizer (SCHO), RIME optimization algorithm (RIME), and the original EDO. Additionally, EDO-LFOL is tested on three combinatorial optimization challenges: the job shop scheduling problem (JSSP), quadratic assignment problem (QAP), and bin packing problem (BPP), to evaluate its applicability. Furthermore, EDO-LFOL addresses four distinct design engineering challenges: the pressure vessel design, three-bar truss, welded beam, and speed reducer. The results, supported by significance tests, demonstrate that EDO-LFOL significantly outperforms the standard EDO and its competitors.

关键词： Metaheuristic algorithms Exponential distribution optimizer Levy flight Orthogonal learning combinatorial problems Engineering design problems

来源：评论

学校读者我要写书评

暂无评论

combinatorial problems IN THE TREATMENT OF FUZZY C-13 NMR SPECTRAL INFORMATION IN THE PROCESS OF COMPUTER-AIDED STRUCTURE ELUCIDATION - ESTIMATION OF THE CARBON-ATOM HYBRIDIZATION AND ALPHA-ENVIRONMENT STATES

引用

ANALYTICA CHIMICA ACTA 1994年第1期298卷 33-52页

作者： BANGOV, IP LAUDE, I CABROLBASS, D UNIV NICE LARTIC F-06108 NICE 2 FRANCE

The information derived from various C-13 nuclear magnetic resonance spectra has in most cases more fuzzy than crisp character. An approach to treat this information by means of the membership function is discussed. The combinatorial problems emerging from such a treatment are critically considered and a structure generation scheme consisting of multiple depth-first procedures is suggested. It permits to constrain the structure generation process through a non-redundant and flexible employment of the spectral information available.

关键词： NUCLEAR MAGNETIC RESONANCE combinatorial problems COMPUTER-AIDED FUZZY THEORY STRUCTURE ELUCIDATION

来源：评论

学校读者我要写书评

暂无评论

Online over time processing of combinatorial problems

引用

CONSTRAINTS 2018年第3期23卷 310-334页

作者： Duque, Robinson Arbelaez, Alejandro Diaz, Juan F. Univ Valle Cali Colombia Cork Inst Technol Cork Ireland

In an online environment, jobs arrive over time and there is no information in advance about how many jobs are going to be processed and what their processing times are going to be. In this paper, we study the online scheduling of Boolean Satisfiability (SAT) and Mixed Integer Programming (MIP) instances that are well-known NP-complete problems. Typical online machine scheduling approaches assume that jobs are completed at some point in order to minimize functions related to completion time (e.g., makespan, minimum lateness, total weighted tardiness, etc). In this work, we formalize and present an online over time problem where arriving instances are subject to waiting time constraints. We propose computational approaches that combine the use of machine learning, MIP, and instance interruption heuristics. Unlike other approaches, we attempt to maximize the number of solved instances using single and multiple machine configurations. Our empirical evaluation with well-known SAT and MIP instances, suggest that our interruption heuristics can improve generic ordering policies to solve up to 21.6x and 12.2x more SAT and MIP instances. Additionally, our hybrid approach observed up to 90% of solved instances with respect to a semi clairvoyant policy (SCP).

关键词： Online scheduling combinatorial problems Machine learning Regression models Classification models Runtime estimation Mixed integer programming

来源：评论

学校读者我要写书评

暂无评论

combinatorial problems in OpenAD

Combinatorial Problems in OpenAD

引用

combinatorial Scientific Computing 2009

作者： Utke, Jean Naumann, Uwe Argonne National Laboratory MCS 9700 S. Cass Ave. ArgonneIL60439 United States RWTH Aachen University LuFG Informatik 12 Aachen52056 Germany

Computing derivatives using automatic differentiation methods entails a variety of combinatorial problems. The OpenAD tool implements automatic differentiation as source transformation of a program that represents a numerical model. We select three combinatorial problems and discuss the solutions implemented in OpenAD. Our intention is to explain the specific parts of the implementation so that readers can easily use OpenAD to investigate and develop their own solutions to these problems. © 2009 combinatorial Scientific Computing. All Rights Reserved.

关键词： automatic differentiation combinatorial problems OpenAD

来源：评论

学校读者我要写书评

暂无评论

An empirical study of constraint logic programming and answer set programming solutions of combinatorial problems

引用

JOURNAL OF EXPERIMENTAL & THEORETICAL ARTIFICIAL INTELLIGENCE 2009年第2期21卷 79-121页

作者： Dovier, Agostino Formisano, Andrea Pontelli, Enrico New Mexico State Univ Dept Comp Sci Las Cruces NM 88003 USA Univ Udine Dipartimento Matemat & Informat I-33100 Udine Italy Univ Perugia Dipartimento Matemat & Informat I-06123 Perugia Italy

This paper presents experimental comparisons between the declarative encodings of various computationally hard problems in Answer Set Programming (ASP) and Constraint Logic Programming over Finite Domains (CLP(FD)). The objective is to investigate how solvers in the two domains respond to different problems, highlighting the strengths and weaknesses of their implementations, and suggesting criteria for choosing one approach over the other. Ultimately, the work in this paper is expected to lay the foundations for a transfer of technology between the two domains, for example by suggesting ways to use CLP(FD) in the execution of ASP.

关键词： logic programming combinatorial problems constraint solving

来源：评论

学校读者我要写书评

暂无评论

Solving combinatorial problems using a parallel framework

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2018年第Part2期112卷 140-153页

作者： Menouer, Tarek Paris Nanterre Univ CNRS UMR7606 Lab LIP6 Paris France

This paper presents a new IBobpp framework which is an improvement of a high level parallel programming framework called Bobpp to optimize the performance of solving combinatorial problems. The Bobpp parallel computation model is as the majority of parallel models proposed in the context of tree search algorithms with node oriented parallelization, meaning that at every step of the algorithm, each thread gets one node from a unique global pool of non-explored nodes, generates the child nodes, and reinserts them into the pool to be explored later. This classical model has two drawbacks. First, the use of many threads creates a bottleneck problem. Second, grabbing a node causes memory contention problem when many nodes are generated and inserted into the same pool. To solve these problems, IBobpp framework proposes three solutions. The first consists of using multiple pools of nodes shared between all threads. The second solution consists of using a new computation model. The third solution consists of hybridization of the two previous solutions. Preliminary result shows that IBobpp gives a good result using the third solution. (C) 2017 Elsevier Inc. All rights reserved.

关键词： combinatorial problems Search algorithms Parallelism Cluster

来源：评论

学校读者我要写书评

暂无评论

LINEAR TIME-TRANSFORMATIONS BETWEEN combinatorial problems

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 1982年第2期11卷 91-110页

作者： DEWDNEY, AK MATH INST OXFORD OX1 3LBENGLAND

Besides showing the existence of NP-complete problems, Cook's theorem and subsequent developments have resulted in a large number of polynomial-time transformations between combinatorial problems. For both theoretical and practical reasons it is important to pursue these transformations, especially low-order ones. In this paper, two linear classes are displayed: it is shown that satisfiability, 3-colourability and set-splitting are linear-time equivalent. It is also shown that bipartite matching and path-connectivity are linear-time equivalent. The computational model on which these results are based is a 1-tape transducer.

关键词： Linear time transformations 1-tape transducers combinatorial problems complexity theory 5.23 5.32

来源：评论

学校读者我要写书评

暂无评论

ESSENCE:: A constraint language for specifying combinatorial problems

引用

CONSTRAINTS 2008年第3期13卷 268-306页

作者： Frisch, Alan M. Harvey, Warwick Jefferson, Chris Martinez-Hernandez, Bernadette Miguel, Ian Univ York Dept Comp Sci Artificial Intelligence Grp York YO10 5DD N Yorkshire England Univ St Andrews Sch Comp Sci St Andrews Fife Scotland Univ Oxford Oxford Univ Comp Lab Oxford England

Essence is a formal language for specifying combinatorial problems in a manner similar to natural rigorous specifications that use a mixture of natural language and discrete mathematics. Essence provides a high level of abstraction, much of which is the consequence of the provision of decision variables whose values can be combinatorial objects, such as tuples, sets, multisets, relations, partitions and functions. Essence also allows these combinatorial objects to be nested to arbitrary depth, providing for example sets of partitions, sets of sets of partitions, and so forth. Therefore, a problem that requires finding a complex combinatorial object can be specified directly by using a decision variable whose type is precisely that combinatorial object.

关键词： constraint languages specification languages constraint modelling constraint programming combinatorial problems

来源：评论

学校读者我要写书评

暂无评论

Seven combinatorial problems around isolated quasihomogeneous singularities

引用

JOURNAL OF ALGEBRAIC COMBINATORICS 2019年第4期50卷 447-482页

作者： Hertling, Claus Zilke, Philip Univ Mannheim Lehrstuhl Math 6 Seminargebaude A 56 D-68131 Mannheim Germany

This paper proposes seven combinatorial problems around formulas for the characteristic polynomial and the spectral numbers of an isolated quasihomogeneous hypersurface singularity. One of them is a new conjecture on the characteristic polynomial. It is an amendment to an old conjecture of Orlik on the integral monodromy of an isolated quasihomogeneous singularity. The search for a combinatorial proof of the new conjecture led us to the seven purely combinatorial problems.

关键词： Isolated quasihomogeneous singularity Weight system Monodromy Characteristic polynomial combinatorial problems Orlik blocks 32S40 12Y05 05C22 05C25

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：