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

The multi-terminal vertex separator problem: Branch-and-Cut-and-Price

DISCRETE APPLIED MATHEMATICS 2021年 290卷 86-111页

作者： Magnouche, Y. Mahjoub, A. R. Martin, S. PSL Res Univ Univ Paris Dauphine CNRS UMR 7243LAMSADE F-75016 Paris France Univ Lorraine Lab Concept Optimisat & Modelisat Syst Metz France

We are given a graph G = (V boolean OR T, E), with V boolean OR T the set of vertices where T is a set of terminals and E the set of edges. The multi-terminal vertex separator problem consists in finding a subset of vertices S subset of V of minimum size intersecting all paths between every pair of terminals. In this paper we present three extended linear integer programming formulations for the multi-terminal vertex separator problem and we develop Branch-and-Price and Branch-and-Cut-and-Price algorithms. For each formulation we present the pricing problem, the branching scheme and the computation of the dual bound used during the column generation phase. Computational results are reported comparing the performance of the formulations on a set of instances. (C) 2020 Published by Elsevier B.V.

关键词： Vertex separator problem integer linear programming Combinatorial optimization Column generation Branch-and-Price Branch-and-Cut-and-Price

来源：评论

学校读者我要写书评

暂无评论

Integrated production planning and warehouse storage assignment problem: An IoT assisted case

引用

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS 2021年 234卷 108058-108058页

作者： Zhang, Guoqing Shang, Xiaoting Alawneh, Fawzat Yang, Yiqin Nishi, Tatsushi Univ Windsor Dept Mech Automot & Mat Engn Supply Chain & Logist Optimizat Res Ctr Windsor ON Canada Beijing Jiaotong Univ Sch Traff & Transportat Beijing Peoples R China Okayama Univ Grad Sch Nat Sci & Technol Okayama Japan

This study is motivated by a real-world problem in a food company, where production planning is restricted by the available warehouse space for the finished goods. A novel integrated strategy that combines production planning with a randomized storage assignment policy is presented. The strategy takes advantage of greater visibility and traceability of items provided by IoT-enabled tracking systems in order to increase space utilization. An integer linear programming model is developed to formulate the strategy to minimize the total cost of production and warehouse operations. Our model is the first dynamic model for a randomized storage assignment policy. The model's feasibility, complexity, and its lower bound are presented. A heuristic algorithm is developed to obtain the near-optimal solution for the large-scale real-world problem. Based on numerical experiments, comparisons between our solutions and the solutions to model with a dedicated storage policy are also presented. The results show that the integrated strategy with a randomized storage policy can significantly reduce the total cost (up to 16.84% with an average of 9.95%) and increase space utilization (up to 26.1% with an average of 14.8%), compared to the strategy with a dedicated policy. Such results provide evidence that may justify the cost of applying the new technologies, such as IoT-enabled tracking systems, in warehouse management.

关键词： Production planning Warehouse storage assignment Randomized policy integer linear programming Heuristic algorithm

来源：评论

学校读者我要写书评

暂无评论

A proactive aircraft recovery approach based on airport spatiotemporal network supply and demand coordination

引用

COMPUTERS & OPERATIONS RESEARCH 2024年 165卷

作者： Zang, Haipei Zhu, Jinfu Zhu, Qi Gao, Qiang Nanjing Univ Aeronaut & Astronaut Sch Civil Aviat Nanjing 211100 Peoples R China Shanghai Zheng Yuan Comp Technol Co Ltd Shanghai 200000 Peoples R China

The Aircraft Recovery Problem (ARP) is to modify the flight and aircraft schedules with compensation for the irregular aircraft operations due to disruptions, falling under passive control. This reactive approach is challenging and often leads to additional secondary delays. The accumulation of historical data and advancements in big data technology have enabled a proactive approach to ARP. If the disruptions that will occur in a certain period of time in the future can be predicted in advance, a preventive plan can be made in advance to actively control the irregular operation of the flight. Predicting disruptions before they occur allows for preemptive planning to actively manage flight irregularities. This paper proposes a proactive approach to ARP, optimizing recovery decisions considering the unpredictability of airport capacity in space and time and the dynamics of flight delay resolutions. It examines ARP from the viewpoint of balancing supply and demand across the airport spatiotemporal network through aircraft rotations between airports. The paper builds a Proactive Aircraft Recovery Model and proposes a Decision -Decomposition -Based Algorithm framework based on collaborative allocation of airport capacity and flow. By applying this approach to operational data from four Chinese airlines, it demonstrates the ability to dynamically reschedule flights and reassign aircraft based on anticipated disruptions, proactively addressing real-time aircraft schedule disruptions within a suitable operational timeframe. Results indicate that mitigating airport demand -capacity imbalances at the spatiotemporal level effectively reduce airline delays and operating costs in actual operations.

关键词： Aircraft Recovery Proactive Control Time -Space Networks Demand -capacity Balance integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Modeling and analysis of crosstalk-avoided and crosstalk-aware approaches in spectrally-spatially elastic optical networks

引用

COMPUTER NETWORKS 2024年 242卷

作者： Ahmed, Imran Oki, Eiji Chatterjee, Bijoy Chand South Asian Univ Dept Comp Sci New Delhi 110068 India Kyoto Univ Grad Sch Informat Kyoto 6068501 Japan

Inter-core crosstalk (Ic-Xt) and inter -mode crosstalk (Im-Xt) occur during the transmission of optical signals through multi-core multi-mode fibers in spectrally-spatially elastic optical networks (SS-EONs), which degrade the signal quality. Xt-Avoided (Xt-Av) and Xt-Aware (Xt-Aw) approaches, respectively, are used in SS-EONs for dealing with Ic-Xt and Im-Xt. From the network deployment perspective, network operators need to understand which approach, Xt-Av or Xt-Aw, is better in order to deal with Ic-Xt and Im-Xt in SS-EONs. To address the above issue, this paper models and analyzes Xt-Av and Xt-Aw approaches by considering Ic-Xt and Im-Xt simultaneously in SS-EONs. We formulate the optimization problems as the integer linear programming (ILP) problem for both Xt-Av and Xt-Aw approaches. When the ILP problems are intractable, we introduce heuristics for Xt-Av and Xt-Aw approaches. We compare ILP and heuristic approaches using Xt-Av and Xt-Aw in terms of the maximum allocated spectrum slot index, blocking ratio, and computation time. Numerical results indicate that the Xt-Aw approach for all Xt threshold values performs better than the Xt-Av approach in terms of resource utilization. At the same time, the Xt-Av approach has the advantage of using less computation time than the Xt-Aw approach. The analysis reveals that, in the Xt-Aw approach, the behavior of the maximum allocated spectrum slot index and blocking ratio on Xt threshold is reciprocal, and hence a suitable Xt threshold that enhances the network performances is required for network management.

关键词： Inter-core crosstalk Inter-mode crosstalk Elastic optical networks Space division multiplexing integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Combining an LNS-based approach and organizational mining for the Resource Replacement Problem

引用

COMPUTERS & OPERATIONS RESEARCH 2024年 161卷

作者： Diamantini, Claudia Pisacane, Ornella Potena, Domenico Storti, Emanuele Univ Politecn Marche Dipartimento Ingn Informaz I-60121 Ancona Italy

For companies, it is crucial to promptly react to (even short-term) lack of resources, for guaranteeing the continuity of the operations in business processes. This leads to the solution of a Resource Replacement Problem (RRP) aimed at reassigning as many activities performed by resources that are no longer available to those that are available. To this purpose, several aspects are considered simultaneously, e.g., resources skills, workloads and other domain-specific constraints. In this paper, we propose an innovative hybrid approach for solving RRP, combining mathematical optimization with organizational mining. In particular, logs of past process executions are used to model a social network of resources by organizational mining techniques. Then, a similarity measure among resources is derived and exploited along with run-time resource workload and information on activities priority to formulate an integer linear programming (ILP) model for reassigning the activities of unavailable resources, minimizing the total reassignment cost. To efficiently solve RRP, a Large Neighborhood Search based matheuristic is developed. Computational experiments show that the proposed matheuristic outperforms the commercial solver used to solve the ILP model. A sensitivity analysis, on possible variations of the input parameters and on the moves of the matheuristic, concludes the work.

关键词： Process planning Business continuity Process mining integer linear programming Matheuristic

来源：评论

学校读者我要写书评

暂无评论

CaSMap: Agile Mapper for Reconfigurable Spatial Architectures by Automatically Clustering Intermediate Representations and Scattering Mapping Process 22

CaSMap: Agile Mapper for Reconfigurable Spatial Architecture...

引用

49th IEEE/ACM Annual International Symposium on Computer Architecture (ISCA)

作者： Man, Xingchen Zhu, Jianfeng Song, Guihuan Yin, Shouyi Wei, Shaojun Liu, Leibo Tsinghua Univ Beijing Natl Res Ctr Informat Sci & Technol BNRis Sch Integrated Circuits Beijing Peoples R China

ISBN: (纸本)9781450386104

Today, reconfigurable spatial architectures (RSAs) have sprung up as accelerators for compute- and data-intensive domains because they deliver energy and area efficiency close to ASICs and still retain sufficient programmability to keep the development cost low. The mapper, which is responsible for mapping algorithms onto RSAs, favors a systematic backtracking methodology because of high portability for evolving RSA designs. However, exponentially scaling compilation time has become the major obstacle. The key observation of this paper is that the key limiting factor to the systematic backtracking mappers is the waterfall mapping model which resolves all mapping variables and constraints at the same time using single-level intermediate representations (IRs). This work proposes CaSMap, an agile mapper framework independent of software and hardware of RSAs. By clustering the lowest-level software and hardware IRs into multi-level IRs, the original mapping process can be scattered as multi-stage decomposed ones and therefore the mapping problem with exponential complexity is mitigated. This paper introduces (a) strategies for clustering low-level hardware and software IRs with static connectivity and critical path analysis. (b) a multi-level scattered mapping model in which the higher-level model carries out the heuristics from IR clustering, endeavors to promote mapping success rate, and reduces the scale of the lower-level model. Our evaluation shows that CaSMap is able to reduce the problem scale (nonzeros) by 80.5% (23.1%-94.9%) and achieve a mapping time speedup of 83x over the state-of-the-art waterfall mapper across four different RSA topologies: MorphoSys, HReA, HyCUBE, and REVEL.

关键词： Reconfigurable Spatial Architecture Coarse-Grained Reconfigurable Architecture Compiler integer linear programming

来源：评论

学校读者我要写书评

暂无评论

The Labeled Two Edge Connected Subgraph Problem 8

The Labeled Two Edge Connected Subgraph Problem

引用

8th International Conference on Control, Decision and Information Technologies (CoDIT)

作者： Ben Salem, Mariem Taktak, Raouia Univ Sfax FSEGS MIRACL Sfax Tunisia Univ Sfax ISIMS Sfax Tunisia Univ Sfax SmaRts CRNS Sfax Tunisia

ISBN: (纸本)9781665496070

In this paper, we address a variant of the Two Edge Connected Problem (TECP), that is the TECP with color constraint on the edges, also known as the Labeled Two Edge Connected Problem (LTECP). Given a connected undirected graph G whose edges are labeled (or colored), the LTECP consists in finding a two-edge connected spanning subgraph of G with a minimum number of distinct labels (or colors). We distinguish two variants of the problem: the first one is when each edge is associated with exactly one label (i.e., the LTECP), and the second is when each edge may be associated with more than one label. This variant is called the Generalized Labeled Two Edge Connected Problem (i.e., the GLTECP). Both problems are relevant in some application fields such as telecommunication networks or transportation networks. We propose integer linear programming formulations for the two variants, we identify a new class of valid inequalities, and present preliminary computational results.

关键词： Transportation Color integer linear programming Communications technology Information technology

来源：评论

学校读者我要写书评

暂无评论

Recommendations with minimum exposure guarantees: A post-processing framework

引用

EXPERT SYSTEMS WITH APPLICATIONS 2024年 236卷

作者： Lopes, Ramon Alves, Rodrigo Ledent, Antoine Santos, Rodrygo L. T. Kloft, Marius Univ Fed Reconcavo Bahia Cruz Das Almas Brazil Czech Tech Univ Prague Czech Republic Singapore Management Univ Singapore Singapore Univ Fed Minas Gerais Dept Comp Sci Belo Horizonte MG Brazil TU Kaiserslautern Kaiserslautern Rlp Germany

Relevance-based ranking is a popular ingredient in recommenders, but it frequently struggles to meet fairness criteria because social and cultural norms may favor some item groups over others. For instance, some items might receive lower ratings due to some sort of bias (e.g. gender bias). A fair ranking should balance the exposure of items from advantaged and disadvantaged groups. To this end, we propose a novel post-processing framework to produce fair, exposure-aware recommendations. Our approach is based on an integer linear programming model maximizing the expected utility while satisfying a minimum exposure constraint. The model has fewer variables than previous work and thus can be deployed to larger datasets and allows the organization to define a minimum level of exposure for groups of items. We conduct an extensive empirical evaluation indicating that our new framework can increase the exposure of items from disadvantaged groups at a small cost of recommendation accuracy.

关键词： Recommender systems Fairness Exposure integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Efficient Computation Offloading in Edge Computing Enabled Smart Home

引用

IEEE ACCESS 2021年 9卷 48631-48639页

作者： Yu, Bocheng Zhang, Xingjun You, Ilsun Khan, Umer Sadiq Xi An Jiao Tong Univ Sch Comp Sci & Technol Xian 710049 Peoples R China Soonchunhyang Univ Dept Informat Secur Engn Asan 31538 South Korea

Mobile edge computing which provides computing capabilities at the edge of the radio access network can help smart home reduce response time. However, the limited computing capacity of edge servers is the bottlenecks for the development of edge computing. We integrate cloud computing and edge computing in the Internet of Things to expand the capabilities. Nevertheless, the cost of leasing computing resources has been seldom considered. In this paper, we study the joint transmission power and resource allocation to minimize the users' overhead which is measured by the sum of energy consumption and cost leasing servers. We formulate the problem as a Mixed integer linear programming which is NP-hard and present the Branch-and-Bound to solve it. Due to high complexity, a learning method is proposed to accelerate the algorithm. The branching policy can be learned to reduce the time-cost of the Branch-and-Bound algorithm. Simulation results show our approach can improve the Branch-and-Bound efficiency and performs closely to the traditional branching scheme.

关键词： Task analysis Servers Cloud computing Smart homes Edge computing Energy consumption Internet of Things Deep learning integer linear programming mobile edge computing smart home task offloading

来源：评论

学校读者我要写书评

暂无评论

Multi-period Planning in Metro-Aggregation Networks using Point-to-Multipoint Transceivers

Multi-period Planning in Metro-Aggregation Networks using Po...

引用

IEEE Global Communications Conference (GLOBECOM)

作者： Hosseini, Mohammad M. Pedro, Joao Costa, Nelson Napoli, Antonio Prilepsky, Jaroslaw E. Turitsyn, Sergei K. Aston Univ Aston Inst Photon Birmingham W Midlands England Infinera Unipessoal Lda Opt Architecture Grp Carnaxide Portugal Inst Telecomunicacoes IST Lisbon Portugal Infinera Strategy Architecture & Engn Munich Germany

ISBN: (纸本)9781665435406

This paper proposes an integer linear programming (ILP) framework to optimize the multi-period planning of metro-aggregation networks exploiting both point-to-multipoint coherent pluggable transceivers and a filterless line system architecture. We investigate several planning strategies to minimize cost while also considering traffic prediction and operational expenditures. The results of a reference network provide evidence of transceiver cost reductions between 20% and 32% compared to the point-to-point approach over a five-year planning period.

关键词： point-to-multipoint transceivers filterless architecture multi-period planning integer linear programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：