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

A Resilient Variant of the Ring Star Problem

NETWORKS 2025年

作者： Khamphousone, Julien Castano, Fabian Rossi, Andre Toubaline, Sonia Orange INNOVAT Orange Chatillon France Frubana Mercado Libre Bogota Colombia Univ Paris 09 PSL CNRS LAMSADE Paris France

The survivable variant of the Ring Star Problem aims at building a network such that when a hub fails, the Ring Star structure is preserved thanks to backup arcs and edges. In this article, we propose a resilient variant of the Ring Star Problem named 1-R-RSP in which the failure of a node in a given subset of so-called uncertain nodes triggers two corrective operations to repair a ring star structure. The first operation repairs the ring, and the second operation reconnects the star. For a given real positive input parameter F$$ F $$, which represents the total duration of breakdowns during the considered time horizon, the objective is to minimize the classical costs of the Ring Star Problem plus the costs incurred by the corrective operations when the hub associated with the largest fixing cost fails during F$$ F $$ units of time. We model this problem as an integer linear program (ILP), which is also addressed with a Branch-and-bins-cut algorithm. We then perform a sensitivity analysis to help the decision maker understand the impact of the parameter F$$ F $$.

关键词： Benders decomposition Branch-and-Benders-cut integer linear programming network design resilience Ring Star Problem

来源：评论

学校读者我要写书评

暂无评论

Visualizing Geophylogenies – Internal and External Labeling with Phylogenetic Tree Constraints

引用

Journal of Graph Algorithms and Applications 2025年第1期29卷 29-61页

作者： Klawitter, Jonathan Klesen, Felix Scholl, Joris Y. van Dijk, Thomas C. Zaft, Alexander University of Auckland Aotearoa New Zealand Universität Würzburg Germany Ruhr-Universität Bochum Germany Eindhoven University of Technology Netherlands

A geophylogeny is a phylogenetic tree (or dendrogram) where each leaf (e.g. biological taxon) has an associated geographic location (site). To clearly visualize a geophylogeny, the tree is typically represented as a crossing-free drawing next to a map. The correspondence between the taxa and the sites is either shown with matching labels on the map (internal labeling) or with leaders that connect each site to the corresponding leaf of the tree (external labeling). In both cases, a good order of the leaves is paramount for understanding the association between sites and taxa. We define several quality measures for internal labeling and give an efficient algorithm for optimizing them. In contrast, minimizing the number of leader crossings in an external labeling is NP-hard. On the positive side, we show that crossing-free instances can be solved in polynomial time and give a fixed-parameter tractable (FPT) algorithm. Furthermore, optimal solutions can be found in a matter of seconds on realistic instances using integer linear programming. Finally, we provide several efficient heuristic algorithms and experimentally show them to be near optimal on real-world and synthetic instances. © 2025, Brown University. All rights reserved.

关键词： integer linear programming

来源：评论

学校读者我要写书评

暂无评论

A distributed optimization approach via symmetric group actions under time-varying communication networks

引用

SYSTEMS & CONTROL LETTERS 2024年 183卷

作者： Basco, Vincenzo Thales Alenia Space Via Saccomuro 24 I-00131 Rome Italy

The widespread adoption of edge computing has revolutionized data processing by decentralizing compu-tational power, resulting in faster response times, decreased network latency, and enhanced privacy. This paradigm shift is crucial due to the increasing demand for real-time analytics and the growth of Internet of Things devices. Optimizing resource allocation and decision-making in on-board computing presents challenges, especially in dynamic and heterogeneous environments. Distributed optimization techniques address these challenges by allowing multiple agents to collaborate and make decisions based on local knowledge. This paper focuses on distributed optimization in multi-agent systems with time-varying communication networks and explores the advantages of considering symmetric group action to reach global optimization. In particular, we focus our study into a class of integer linear programming (ILP) for modeling real-world optimization problems in decentralized environments. The paper introduces a novel approach that leverages group actions and probabilistic selection of initial states to enhance convergence to desirable solutions. The method guarantees feasibility while minimizing computational effort for the agents. Additionally, numerical simulations have been conducted to validate the proposed algorithm, demonstrating its efficacy in optimizing resource allocation for a class of scheduling problems.

关键词： Distributed optimization Time-varying network integer linear programming Group action

来源：评论

学校读者我要写书评

暂无评论

Line balancing and task scheduling to minimise power peak of reconfigurable manufacturing systems

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2024年第14期62卷 5061-5086页

作者： Delorme, Xavier Gianessi, Paolo Univ Clermont Auvergne Mines St Etienne INP Clermont Auvergne CNRSUMR 6158LIMOS F-42023 St Etienne France

Energy efficiency has become a major concern for manufacturing systems, due to industry being the largest user of scarce, finite energy sources, and also to recent events which have pushed energy prices to alarming levels. In the present Industry 4.0 context, Reconfigurable Manufacturing Systems (RMS) are therefore one of the most promising manufacturing paradigm. In this paper, we investigate the suitability of one of the most common types of RMS, the Parallel-Serial manufacturing line with Crossover, to help minimise the peak of the electric power consumption. More specifically, the balancing of such a production line is studied, so as to integrate power peak minimisation from the design stage. Thus, we define the Parallel-Serial-with-Crossover Assembly Line Balancing Problem with Power Peak Minimization, a new combinatorial NP-hard problem. We also propose a suitable time-indexed integer linear Program that integrates balancing and scheduling decisions and a matheuristic algorithm designed to tackle large-size instances. Both approaches are tested on a wide set of instances. The computational results show that relevant power peak reductions can be achieved (33% on average), opening up promising perspectives from both algorithmic and managerial viewpoints.

关键词： Reconfigurable manufacturing systems line balancing task scheduling power peak integer linear programming metaheuristics

来源：评论

学校读者我要写书评

暂无评论

A spatiotemporal optimization method for connected and autonomous vehicle operations in long tunnel constructions

引用

PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS 2024年 651卷

作者： Jiang, Yangsheng Xia, Kui Jiang, Haoran Chen, Fei Yao, Zhihong Southwest Jiaotong Univ Sch Transportat & Logist Chengdu 610031 Peoples R China Southwest Jiaotong Univ Natl Engn Lab Integrated Transportat Big Data Appl Chengdu 611756 Peoples R China Southwest Jiaotong Univ Natl United Engn Lab Integrated & Intelligent Tran Chengdu 611756 Peoples R China

With the advancement of technology, connected and autonomous vehicles (CAVs) can be applied to complex tunnel networks in long tunnel construction to enhance vehicle operation safety and efficiency. This paper proposes an optimization method for CAVs' operation in long tunnel constructions. Firstly, a spatiotemporal coordinated optimization model with decentralized time and hierarchical networks is proposed to minimize the total working time for completing transportation services. The model integrates macro task allocation and micro node control and optimizes the vehicle-space-time relationships of CAVs to prevent conflicts and collisions. Secondly, a heuristic algorithm named Search-Adjustment Genetic Algorithm (SAGA) is developed to solve the problem considering the model's complexity and engineering characteristics. Thirdly, numerical experiments are designed to validate the feasibility and efficiency of the proposed model and algorithm. The results indicate that (1) the proposed model can effectively deconflict CAVs in the road network to ensure safety and obtain a low total working time to fulfill the transportation demand. (2) Compared to the commercial solver Gurobi, the proposed algorithm demonstrates significantly superior solution accuracy and efficiency within an acceptable time limit. (3) The solution ensures the safety and efficiency of CAVs and increases their utilization compared with engineering-oriented methods, resulting in a 50 % reduction in CAV acquisition costs, a 29 % and 85 % reduction in running time and delay respectively, and a reduction in fuel consumption. (4) As the number of transportation services and the complexity of the road network increases, the efficiency gains become more prominent and better adapted to the needs of the actual long tunnel construction project. To sum up, the proposed model and algorithm can ensure the safety and efficiency of providing transportation services in future long tunnel construction. Moreover, it can

关键词： Connected and autonomous vehicles Spatiotemporal coordinated optimization Long tunnel constructions integer linear programming Search-Adjustment Genetic Algorithm

来源：评论

学校读者我要写书评

暂无评论

A survivable variant of the ring star problem

引用

NETWORKS 2024年第2期83卷 324-347页

作者： Khamphousone, Julien Castano, Fabian Rossi, Andre Toubaline, Sonia Univ Paris Dauphine PSL CNRS LAMSADE UMR 7243 Paris France Frubana Res & Dev Team Bogota Colombia

The Ring Star Problem consists in selecting a subset of nodes called hubs including the depot and linking them with a cycle, the remaining nodes being connected to exactly one hub, at minimum cost. We study a survivable variant of the Ring Star Problem where at most one node in a given subset of so-called uncertain nodes can fail if selected as a hub. We model this problem as an integer linear Program (ILP), that is also addressed with a Branch-and-Benders-cut decomposition. The Benders subproblem is turned into a linear program with the addition of new inequalities that are shown to be facet-defining, and several enhancements to both the ILP and Branch-and-Benders-cut algorithm are also presented. Both approaches are compared on the basis of extensive numerical experiments that bring the following conclusions. First, the survivable variant is shown to be much harder than the original Ring Star Problem, and the extra cost induced by survivability is significant. Second, the ILP formulation tends to produce tighter lower bounds but memory issues are frequent for large instances. Finally, the Branch-and-Benders-cut algorithm returns feasible solutions that are often of better quality than those produced by ILP, and is less frequently subjected to memory issues on the considered set of instances.

关键词： benders decomposition branch-and-benders-cut integer linear programming network design ring star problem survivability

来源：评论

学校读者我要写书评

暂无评论

Combinatorial Benders' decomposition for the constrained two-dimensional non-guillotine cutting problem with defects

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2024年第23期62卷 8299-8325页

作者： Yao, Shaowen Zhang, Hao Liu, Qiang Leng, Jiewu Wei, Lijun Guangdong Univ Technol Sch Electromech Engn Key Lab Comp Integrated Mfg Syst Guangzhou 510006 Peoples R China

This paper studies the constrained two-dimensional non-guillotine cutting problem with defects, in which a set of items of a specific size is cut from a large rectangular sheet with defective areas, with the number of each type of cut item cannot exceed a specified quantity. The objective is to maximise the total value of the cut items. We propose a decomposition approach to address the problem. The process involves decomposing the original problem into a master problem and a subproblem. The master problem is formulated as a one-dimensional contiguous bin packing problem, while the subproblem is an x-Check problem to identify a two-dimensional packing that does not lead to any overlap. The x-Check problem is effectively addressed by using an integer linear programming model. When the x-Check problem proves infeasible, cuts are added to the master problem, and the iteration is repeated until the x-Check finds a feasible solution. Furthermore, we introduce several novel techniques, including valid inequalities, preprocessing techniques, and lifting the cut methods to improve the performance of the algorithm. Extensive computational results show that our method can quickly find the optimal solution for the 5450 instances in the literature.

关键词： Cutting packing defect decomposition algorithm integer linear programming SDG 9: Industry innovation andinfrastructure

来源：评论

学校读者我要写书评

暂无评论

Parallel optimization over the integer efficient set

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2024年第3期31卷 1949-1974页

作者： Younes, Djellouli Sarah, Hamadou Djamal, Chaabane USTHB DGRSDT AMCD RO Lab Fac MathDept Operat Res BP 32 Algiers 16111 Algeria

This paper introduces a modified sequential version method for optimizing a linear function over an integer efficient set, as well as a new exact parallel algorithm. The performance of parallel programming in this context is clear and shown through different instances with different sizes. Each procedure builds a finite monotonous sequence of values for the main criterion to be optimized, in a reasonable amount of CPU execution time. This latter remains much better. For the first time, the Algerian IBNBADIS cluster-CERIST-was used with this type of problem. Significant results are obtained by both proposed techniques, particularly with the parallel one.

关键词： optimization integer linear programming multiple objective parallel computing OpenMP parallelization

来源：评论

学校读者我要写书评

暂无评论

Comparative analysis of mathematical formulations for the two-dimensional guillotine cutting problem

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2024年第5期31卷 3010-3035页

作者： Becker, Henrique Martin, Mateus Araujo, Olinto Buriol, Luciana S. S. Morabito, Reinaldo Fed Univ Rio Grande do Sul UFRGS Grad Programming Comp BR-91501970 Porto Alegre Brazil Fed Fluminense Univ Dept Prod Engn BR-25650050 Petropolis Brazil Fed Univ St Maria Ind Tech Coll Santa Maria Brazil Fed Univ Sao Carlos UFSCar Dept Prod Engn BR-13565905 Sao Carlos Brazil

About 15 years ago, a paper proposed the first integer linear programming formulation for the constrained two-dimensional guillotine cutting problem (with unlimited cutting stages). Since then, eight other formulations followed, seven of them in the last four years. This spike of interest gave no opportunity for a comprehensive comparison between the formulations. We review each formulation and compare their empirical results over instance datasets of the literature. We adapt most formulations to allow for piece rotation. The possibility of adaptation was already predicted but not realized by the prior work. The results show the dominance of pseudo-polynomial formulations until the point instances become intractable by them, while more compact formulations keep achieving good primal solutions. Our study also reveals a mistake in the generation of the T instances, which should have the same optima with or without guillotine cuts. We also propose hybridising a recent formulation with a prior formulation for a restricted version of the problem. The hybridisations show a reduction of about 20% of the branch-and-bound time thanks to the symmetries broken by the hybridisation.

关键词： knapsack problems cutting and packing problems two-dimensional cutting guillotine cuts unlimited stages constrained demand formulation integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Minimizing Virtual Machine Live Migration Latency for Proactive Fault Tolerance Using an ILP Model With Hybrid Genetic and Simulated Annealing Algorithms

引用

IEEE ACCESS 2024年 12卷 107232-107246页

作者： Ramesh, Jayroop Solatidehkordi, Zahra El-Fakih, Khaled Aburukba, Raafat Amer Univ Sharjah Dept Comp Sci & Engn Sharjah U Arab Emirates

Cloud computing has grown significantly in recent years and is now widely used by both individuals and businesses. Cloud service providers need to be prepared for failures to ensure that they can respond to them appropriately by minimizing downtime and achieving business continuity. This can be accomplished through fault tolerance mechanisms which aim to predict, prevent, and recover from failures. One of the common causes of task failures in the cloud is the deterioration of physical machines. If deterioration is detected in the physical machine, the virtual machines (VMs) being hosted must be moved to healthy physical machines. This paper proposes an approach to VM allocation in the event of host deterioration or failure. Namely, an integer linear programming optimization model is proposed for the allocation of the failing VMs while minimizing VM migration time. In addition, hybrid genetic and simulated annealing (HGA and HSA) algorithms are proposed for providing efficient solutions for the optimization model. The HGA is hybridized by a procedure that penalizes infeasible solutions to reduce their chances of being selected in the offspring populations and a hill-climbing procedure that modifies feasible solutions to produce better (or more fit) ones. The HSA starts from a feasible solution and also uses elitism as the HGA in its search to ensure that good candidate solutions are preserved. To validate the quality of the obtained solutions, we compare our approach to the commercial optimization solver CPLEX. In comparison to the CPLEX solver, the results show that for small size data center problems, the proposed HGA and HSA achieve near-optimal solutions with 70.80% and 81.43% increase in speed with an average solution quality trade-off by 20.57% and 78.52%, respectively. Notably, for medium, large and very large size problems the HGA and HSA obtained solutions where the CPLEX solver could not provide solutions within acceptable time. For medium size problems HGA

关键词： Cloud computing Fault tolerant systems Fault tolerance Genetic algorithms Task analysis Simulated annealing Data centers virtual machines live migration cloud monitoring optimization integer linear programming CPLEX hybrid genetic and simulated annealing algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：