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

An Almost exact Linear algorithm for Transformation of Chain-Cycle Graphs with Optimization of the Sum of Operation Costs

引用

DOKLADY MATHEMATICS 2020年第2期102卷 376-379页

作者： Gorbunov, K. Yu Lyubetsky, V. A. Russian Acad Sci Kharkevich Inst Inst Informat Transmiss Problems Moscow 127051 Russia Lomonosov Moscow State Univ Fac Mech & Math Moscow 119991 Russia

For weighted directed chain-cycle graphs, an algorithm transforming one graph into another is constructed. The algorithm runs in linear time and yields a sequence of transformations with the smallest, up to an additive error, total cost. The costs of the operations of inserting and deleting an edge segment may differ from each other and from the costs of the other operations. The additive error is estimated in terms of the operation costs.

关键词： exact algorithm graph transformation 2-degree graph chain-cycle graph operation cost DCJ-operations discrete optimization

来源：评论

学校读者我要写书评

暂无评论

exact Heuristic algorithm for Traveling Salesman Problem

Exact Heuristic Algorithm for Traveling Salesman Problem

引用

9th International Conference for Young Computer Scientists

作者： Lin, Dongmei Wu, Xiangbin Wang, Dong Foshan Univ Ctr Informat & Educ Technol Foshan 528000 Guangdong Peoples R China Cent S Univ Coll Geosci & Environm Engn Changsha 410083 Peoples R China Foshan Univ Dept Comp Sci & Technol Guanhdong PT-258000 Peoples R China

ISBN: (纸本)9781424441983

Natural properties of stochastic searching strategies and operations in metaheuristic algorithms have important influence on convergence performance of various metaheuristic algorithms. Through similarity analysis to two kinds of metaheuristic algorithms, exact heuristic algorithm based on branch-and-cut is put forward according to change trend of similarity between two arbitrary high-quality solutions. In the meanwhile, two conditions were given in this paper because efficiency of branch-and-cut algorithm is closely allied to complexity of solved object. New heuristic algorithm can help metaheuristic algorithms finding superior solutions than other heuristic algorithms, and accelerate metaheuristic algorithms convergence. Simulation experiments show that new heuristic algorithm is efficacious.

关键词： traveling salesman problem heuristic algorithm branch-and-cut exact algorithm local search algorithm

来源：评论

学校读者我要写书评

暂无评论

An exact fast algorithm for minimum hitting set

An exact fast algorithm for minimum hitting set

引用

3rd International Joint Conference on Computational Sciences and Optimization, CSO 2010: Theoretical Development and Engineering Practice

作者： Shi, Lei Cai, Xuan Shanghai Jiao Tong University Shanghai China Third Research Institute of Ministry of Public Security Shanghai China

ISBN: (纸本)9780769540306

We propose a branch-and-reduce algorithm to solve the MINIMUM HITTING SET PROBLEM in this paper and use a recently developed technique called measure and conquer to perform analysis on the algorithm. By applying such technique and quasiconvex programming when optimizing the analysis results, we prove that our algorithm can solve the MINIMUM HITTING SET PROBLEM in O(1:23801n) and polynomial space. © 2010 IEEE.

关键词： exact algorithm Measure and conquer Minimum hitting set Quasiconvex programming

来源：评论

学校读者我要写书评

暂无评论

EIA-CNDP: An exact iterative algorithm for critical node detection problem

引用

COMPUTERS & OPERATIONS RESEARCH 2021年 127卷 105138-105138页

作者： Rezaei, Javad Zare-Mirakabad, Fatemeh MirHassani, Seyed Ali Marashi, Sayed-Amir Amirkabir Univ Technol Dept Math & Comp Sci Tehran Iran Univ Tehran Coll Sci Dept Biotechnol Tehran Iran

In designing reliable and impermeable networks, the robustness of the network is evaluated against the removal and failure of the node or edge where the network robustness (network connectivity) is measured using various metrics (objective functions) such as the number of connected components, size of the largest connected component, and pairwise connectivity. Critical node detection problem (CNDP) is one of the main issues in this literature, which aims to find a set of vertices whose removal maximizes or minimizes some objective function. In this paper, the focus is on solving CNDP, considering the size of the largest connected component as its objective function. In this regard, we introduce a new problem called K-Group-Division-Problem and present a mixed integer linear programming model to solve it. We prove that under certain circumstances, any optimal solution of the new problem is also an optimal solution of CNDP. Analyzing the performance of the proposed model on solving CNDP, indicates that this model is highly competitive against the base model in the literature. Furthermore, a novel exact algorithm is introduced which improves the proposed mixed integer linear programming model to address CNDP more efficiently. The results show that the proposed algorithm is much more efficient, and, compared with the base model, it can solve the problem on networks with a higher number of nodes. (C) 2020 Elsevier Ltd. All rights reserved.

关键词： exact algorithm Critical node Largest connected component Mixed integer linear programming Network vulnerability

来源：评论

学校读者我要写书评

暂无评论

An exact Fast algorithm for Minimum Hitting Set

An Exact Fast Algorithm for Minimum Hitting Set

引用

The Third International Joint Conference on Computational Science and Optimization(第三届计算科学与优化国际大会 CSO 2010)

作者： Lei Shi Xuan Cai Shanghai Jiao Tong University Shanghai China The Third Research Institute of Ministry of Public Security Shanghai China

We propose a branch-and-reduce algorithm to solve the Minimum Hitting Set Problem in this paper and use a recently developed technique called measure and conquer to perform analysis on the algorithm. By applying such technique and quasiconvex programming when optimizing the analysis results, we prove that our algorithm can solve the Minimum Hitting Set Problem in 0(1.23801n) and polynomial space.

关键词： minimum hitting set exact algorithm measure and conquer quasiconvex programming

来源：评论

学校读者我要写书评

暂无评论

exact Heuristic algorithm for Traveling Salesman Problem

Exact Heuristic Algorithm for Traveling Salesman Problem

引用

The 9th International Conference for Young Computer Scientists(第九届国际青年计算机大会)

作者： Dongmei Lin Xiangbin Wu Dong Wang Center of Information and Education Technology Foshan University Foshan Guangdong 528000 China College of Geosciences and Environmental Engineering Central South University Changsha Hunan 41008 Department of Computer Science and Technology Foshan University Foshan Guangdong 528000 China

Natural properties of stochastic searching strategies and operations in metaheuristic algorithms have important influence on convergence performance of various metaheuristic algorithms. Through similarity analysis to two kinds of metaheuristic algorithms, exact heuristic algorithm based on branchand- cut is put forward according to change trend of similarity between two arbitrary high-quality solutions. In the meanwhile, two conditions were given in this paper because efficiency of branch-and-cut algorithm is closely allied to complexity of solved object. New heuristic algorithm can help metaheuristic algorithms finding superior solutions than other heuristic algorithms, and accelerate metaheuristic algorithms convergence. Simulation experiments show that new heuristic algorithm is efficacious.

关键词： traveling salesman problem heuristic algorithm branch-and-cut exact algorithm local search algorithm

来源：评论

学校读者我要写书评

暂无评论

An ILP-based exact approach for solving the variable cost and size bin packing problem with time-dependent cost modeling the shared satellite-based last-mile delivery

引用

COMPUTERS & OPERATIONS RESEARCH 2025年 180卷

作者： Bargetto, Roberto Bruni, Maria Elena Perboli, Guido Politecn Torino Corso Duca Abruzzi 24 I-10129 Turin Italy Univ Calabria Via Pietro Bucci I-87036 Arcavacata Di Rende Italy CIRRELT Montreal PQ Canada

In the nowadays common two-tier logistic systems for delivering products in urban areas, the last leg of the distribution chain, the so-called last mile, is by far the most problematic. The modeling of the last-mile delivery problem as a variable cost and size bin packing problem with time-dependent costs emerged recently as the best solution for planning the delivery operations. No exact solution has been yet proposed for efficiently solving this variant of the bin packing problem. In this paper, we present a new problem formulation and devise an exact branch-and-bound method for effective and efficient problem resolution. Upon the resulting tailored solution approach, we devise a procedure to speed up the problem resolution further. Numerical results collected on large-sized instances reveal the dramatic reduction of the computation time obtained with our solution approach, which turns out to be up to ten times faster than the commercial solver. The improvement in solving large-sized instances with a relatively easy-to-implement approach is remarkably relevant for real-world applications.

关键词： Last-mile delivery Variable cost and size bin packing Bin packing Integer linear programming exact algorithm

来源：评论

学校读者我要写书评

暂无评论

An exact approach for the two-dimensional strip packing problem with defects

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2025年 200卷

作者： Yao, Shaowen Zhang, Hao Wei, Lijun Liu, Qiang Guangdong Univ Technol Guangdong Prov Key Lab Comp Integrated Mfg Syst State Key Lab Precis Elect Mfg Technol & Equipment Guangzhou 510006 Peoples R China

The paper studies the two-dimensional strip packing problem with defects (2DSPP_D), focusing on packing rectangular items orthogonally within a fixed-width, variable-height strip that includes defects. The objective is to minimize the height of the strips used. This problem is important because it appears in many real-world applications, such as cutting processes for materials like paper or steel coils, where the goal is to minimize waste, and in continuous berth allocation problems, where the objective is to minimize total unloading time. Although this problem has a wide range of practical applications, it is rarely discussed in the literature. In this paper, we present an integer programming formulation and an exact two-stage approach. In the first stage of the exact method, the 2DSPP_D is converted into a two-dimensional orthogonal placement problem (2DOPP) by fixing the strip height. In the second stage, we solve this placement problem using a Benders' decomposition method. If the 2DOPP proves infeasible, we increase the strip height and repeat the algorithm. We employ customized preprocessing techniques, lower bounding methods, and valid inequalities to enhance the two-stage approach. Additionally, we propose a skyline-based adaptive iterative search heuristic algorithm that provides tight upper bounds for the 2DSPP_D, incorporating a randomized local search strategy and an adaptive search strategy to enhance algorithm effectiveness. Extensive computational results show that our approach proves optimal solutions for small and medium-sized benchmark instances within a reasonable time and achieves close gap values between upper and lower bounds for large benchmark instances.

关键词： Packing Defect exact algorithm Benders' decomposition

来源：评论

学校读者我要写书评

暂无评论

Provably Efficient Service Function Chain Embedding and Protection in Edge Networks

引用

IEEE TRANSACTIONS ON NETWORKING 2025年第1期33卷 178-193页

作者： Zheng, Danyang Cao, Xiaojun Southwest Jiaotong Univ Sch Comp & Artificial Intelligence Chengdu 611756 Sichuan Peoples R China Georgia State Univ Dept Comp Sci Atlanta GA 30302 USA

Internet-connected devices generate service function chain (SFC) requests for reliability-sensitive applications such as smart factories and intelligent healthcare. To facilitate reliable SFC provisioning, one can employ dedicated SFC protection approaches to protect the primary service function path (SFP) by constructing a fault-disjointed backup SFP. Notably, the construction processes of the fault-disjointed primary and backup SFPs are interdependent, and the direct application of existing SFC embedding approaches to construct these SFPs by separate processes may not effectively optimize overall resource consumption. In this work, for the first time, we comprehensively study how to embed and protect an SFC through collaborative processes that have provable bounds. We formally define the problem of SFC embedding and protection (SFCEP), for which we develop the novel techniques of a backup SFP identifier (BSI) and resource-aware Bellman-Ford loop (RBL) to address the challenges posed by collaborative embedding and protection. On the basis of these techniques, we propose an efficient algorithm called optimal SFC embedding and protection (Opt-SEP). When the network resources are sufficient to accommodate an incoming SFC request, we prove that Opt-SEP can minimize the overall resource cost of creating a pair of fault-disjointed primary and backup SFPs. Moreover, for cases in which the network resources are limited, our extensive simulation results show that Opt-SEP significantly outperforms the benchmarks.

关键词： Reliability Protection Heuristic algorithms Object recognition Service function chaining Reliability theory Firewalls (computing) Bandwidth Smart manufacturing Monitoring Network function virtualization reliable service function chain dedicated protection exact algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimal Solving of a Scheduling Problem Using Quantum Annealing Metaheuristics on the D-Wave Quantum Solver

引用

IEEE TRANSACTIONS ON SYSTEMS MAN CYBERNETICS-SYSTEMS 2025年第1期55卷 196-208页

作者： Bozejko, Wojciech Klempous, Ryszard Pempera, Jaroslaw Rozenblit, Jerzy Smutnicki, Czeslaw Uchronski, Mariusz Wodecki, Mieczyslaw Wroclaw Univ Sci & Technol Dept Control Syst & Mechatron PL-50370 Wroclaw Poland Univ Arizona Dept Elect & Comp Engn Tucson AZ 85721 USA Wroclaw Univ Sci & Technol Dept Comp Engn PL-50370 Wroclaw Poland Wroclaw Univ Sci & Technol Dept Telecommun & Teleinformat PL-50370 Wroclaw Poland

Accurately solving discrete optimization problems is still a serious challenge for classical computing systems. Despite significant progress, it is still impossible to optimally solve examples of the size found in real-world applications. This article examines the problem of scheduling tasks on one machine. Each task has an associated execution time, desired completion date, and a late penalty feature weight. The order of executing tasks should be determined in a manner that minimizes the sum of delay costs. Despite the simplicity of the formulation, this problem is NP-hard and is representative of optimization challenges encountered in the practice of production control, management, and *** this work, we propose using a quantum computing environment to solve it. The main disadvantage of calculations on quantum computers is their nondeterminism. Therefore, there is no guarantee of optimality of solutions to discrete optimization problems determined on a quantum *** propose a novel approach to constructing hybrid algorithms that guarantee the optimality of the solution. The algorithm for solving the task scheduling problem considered here is based on the branch and bound method. Calculations are performed alternately on a classical computer and a quantum computer. The lower and upper bounds of the criterion function are determined on a quantum computer. Computational experiments were performed on the D-Wave quantum computer. In small examples, the algorithm runs faster and generates significantly fewer solution tree vertices than its counterpart running on a classic computer. For larger examples, the proposed runtime-constrained method, acting as a heuristic, is an interesting alternative to using quantum computing hardware in relation to classical approaches based on silicon computers.

关键词： exact algorithm quantum annealing scheduling single machine scheduling

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：