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

Mixed-integer programming models and heuristic algorithms for the maximum value dynamic network flow scheduling problem

引用

COMPUTERS & OPERATIONS RESEARCH 2025年 175卷

作者： Nixon, Tanner Curry, Robert M. Allaissem, B. Phanuel US Navy Arlington VA USA Univ Arkansas Coll Engn Dept Ind Engn 800 W Dickson St Fayetteville AR 72701 USA

Various applications in contested logistics and infrastructure restoration require dynamic flow solutions characterized by a schedule of network flows consecutively transmitted over a sequence of successive periods. For these schedules, we assume flows transmit via arcs during periods while flows reside at nodes from one period to the next. Within this context, we introduce the Maximum Value Dynamic network flow Problem (MVDFP) in which we seek to maximize the cumulative value of a non-simultaneous network flow schedule that accumulates node value whenever some minimum amount of flow resides at a node between periods. For solving the MVDFP, we first introduce a large mixed-integer program (MIP). As this MIP can become computationally-expensive for large networks, we present a trio of computationally-effective, easy to implement heuristic approaches that solve a series of smaller, more manageable MIPs. These heuristic approaches typically determine high-quality solutions significantly faster than the MIP obtains an optimal solution by dividing the full network flow schedule into a sequence of consecutive shorter network flow subschedules. In many cases, at least one of our heuristic approaches produces an optimal solution in a fraction of the MIP's computational time. We present extensive computational results to highlight our heuristics' efficacy, discuss for what instances each approach may be most applicable, and detail future research avenues.

关键词： network flow optimization Mixed-integer programming Heuristic methods

来源：评论

学校读者我要写书评

暂无评论

network optimization model approach to the volume-to-point heat conduction problem

引用

optimization AND ENGINEERING 2025年第1期26卷 229-251页

作者： Ferreira, Ricardo Poley Martins Pinto, Ricardo Luiz Utsch de Freitas Mahey, Philippe Fed Univ Minas Gerais UFMG Grad Program Mech Engn Ave Antonio Carlos 6627 Belo Horizonte MG Brazil Univ Clermont Auvergne UCA Lab Informat Modelling & Optimizat Syst Campus Univ Cezeaux1 Rue Chebarde F-63178 Aubiere France

This paper gives the classical volume-to-point heat conduction optimization problem a fresh model and formulation. The new volume-to-point problem model is a minimization problem, whereas the original model is a minimax problem. We establish that both problems have the same solution. The new formulation optimizes the volume and distribution of high-conductive materials while solving the heat flow equations and respecting a maximum temperature constraint. It was inspired by direct methods in optimal control problems. The problem is formulated as a mathematical programming problem, a network optimization problem, and it can be solved using off-the-shelf nonlinear optimization solvers. The new network design formulation is versatile and efficient as it can solve different problems fast and with good results. Numerical experiments show that the obtained solutions with the new formulation are competitive with state-of-the-art literature solutions, which were obtained using heuristics or computationally expensive methods.

关键词： network flow optimization Volume-to-point problem Heat transfer Minimization problem

来源：评论

学校读者我要写书评

暂无评论

Energy-efficient and delay-sensitive-based data gathering technique for multi-hop WSN using path-constraint mobile element

引用

WIRELESS networkS 2024年第1期30卷 77-95页

作者： Kumar, Naween Edla, D. Reddy Dash, Dinesh Swain, Gandharba Shankar, T. N. Bennett Univ Sch Comp Sci Engn & Technol Greater Noida 201310 UP India Natl Inst Technol Goa Dept CSE Ponda 403401 Goa India Natl Inst Technol Patna Dept CSE Patna Univ Campus Patna 800005 India Koneru Lakshmaiah Educ Fdn Dept CSE Guntur 522502 AP India

In path-constrained multi-hop sensor networks (M-WSNs), maximizing data collection with minimal energy consumption is critical, especially for delay-sensitive applications. Because a mobile element (ME) moving at a constant speed along a constrained-path must receive data from sensor nodes (SNs) within a given time bound. This issue can be addressed by efficiently scheduling the SNs' data transmission. The shortest path data transmission (SPT) or its variations are a simple and energy-efficient technique for scheduling data transmission from SNs. Although this method considerably minimizes total energy spent, it does not enhance data collection efficiency due to uneven data forwarding load. To solve this issue, this paper proposes a novel efficient heuristic method. The proposed method first computes a set of discrete sub-paths on a given path based on the start and end distance points of nearby SNs, the speed of ME, and the given time delay. Then, for each sub-path and SN-communication model, a network flow graph is used to schedule and optimize SN data transmission to ME. Finally, a sub-path is chosen among those which return maximum data with minimum energy consumption. The network flow graphs are created by considering two distinct SN-communication models: (1) energy-unrestricted SN-model and (2) energy-restricted SN-model. Finally, the simulation reports demonstrate the proposed method's efficacy over baseline schemes in terms of data collected, energy usage efficiency, and success-delivery ratio.

关键词： Constrained-path Mobile element network flow optimization Maximum data Time period Energy efficient sub-path Wireless sensor networks

来源：评论

学校读者我要写书评

暂无评论

Self-Supervised Association of Wi-Fi Probe Requests Under MAC Address Randomization

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2023年第12期22卷 7044-7056页

作者： He, Tianlang Tan, Jiajie Chan, S. -H. Gary Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Hong Kong Peoples R China

Wi-Fi-on devices such as smartphones search for network availability by periodically broadcasting probe requests which encapsulate MAC addresses as device identifiers. To protect identity privacy, modern devices embed random MAC addresses in probe frames, the so-called MAC address randomization. Such randomization disrupts the frame association, inadvertently frustrating identity-oblivious statistical analytic efforts such as people counting and trajectory inference. To address that, we propose Cappuccino, a novel privacy-preserving approach that captures the association of probe requests under MAC address randomization. Cappuccino first estimates pairwise frame correlation and then associates frames over time. For frame correlation, it employs a self-supervised estimator that jointly considers multiple modalities, i.e., information elements, sequence number, and received signal strength. For multiple frame association, Cappuccino formulates frames as a minimum-cost flow optimization. To the best of our knowledge, this is the first piece of work that leverages self-supervised learning to estimate frame correlation based on multiple modalities and formulates the probe request association problem as the network flow optimization. We have conducted extensive experiments in a leading and crowded shopping mall for more than three months. Cappuccino achieves remarkable performance in terms of V-measure scores (>0.85).

关键词： Wi-Fi MAC address randomization self-supervised learning multiple modalities network flow optimization

来源：评论

学校读者我要写书评

暂无评论

Minimum-cost flow problems having arc-activation costs

引用

NAVAL RESEARCH LOGISTICS 2022年第2期69卷 320-335页

作者： Curry, Robert M. Smith, J. Cole US Naval Acad Math Dept Annapolis MD 21401 USA Syracuse Univ Dept Elect Engn & Comp Sci Syracuse NY USA

Time-dependent network applications, such as wireless sensor network and infrastructure optimization settings, may require dynamic flows to be transmitted according to a nonsimultaneous schedule of path-flows. We study a dynamic network flow optimization problem considering the presence of activation costs required to begin transmitting flow on an arc. This problem can be modeled as a dynamic version of the minimum-cost flow problem having arc-activation costs (MCFA). The MCFA is related but not equivalent to the fixed-charge network flow problem. We first discuss the relationship between these two problems, and show how MCFA is unique in the network flow literature. We present a mixed-integer programming (MIP) model along with a series of symmetry-breaking inequalities for solving the MCFA. As an alternative, we employ a relaxation-based algorithm that iteratively obtains upper and lower bounds via the solution of a series of smaller, more tractable MIPs. We show that this algorithm finitely terminates with an optimal MCFA solution. Finally, computational results demonstrate the efficacy of our approach compared to solving a MIP using a state-of-the-art commercial solver.

关键词： consecutive flows fixed-charge network flow problems integer programming minimum-cost flow problems network flow optimization

来源：评论

学校读者我要写书评

暂无评论

Cross quantum homomorphic encryption based on the butterfly network

引用

Physical Review A 2024年第6期109卷 062606-062606页

作者： Xing-bo Pan Yu-Ting Lei Xiang-jie Li Xiu-bo Chen Gui-lu Long State Key Laboratory of Low-Dimensional Quantum Physics and Department of Physics

Quantum homomorphic encryption hides quantum information from unauthorized participants while still allowing them to perform calculations on encrypted quantum information. In this paper, we propose a cross quantum homomorphic encryption scheme based on the butterfly network, in which every receiver can receive the evaluated quantum state with perfect fidelity. The entangled states between senders of the butterfly network are preshared, and the Bell basis measurements are used to encrypt the quantum plaintext. With both classical and quantum channels, the homomorphic evaluation of quantum plaintext can be completed on the butterfly network perfectly and crossly. Our scheme solves a bottleneck problem of cross evaluation at the bottleneck nodes, and improves the evaluation efficiency and total network throughput. In addition, we have designed quantum circuits according to different quantum evaluations with a butterfly network, which provide a basic blueprint for experimental implementation. The security of the scheme is also analyzed.

关键词： Communication schemes network flow optimization Quantum circuits Quantum communication Quantum state transfer

来源：评论

学校读者我要写书评

暂无评论

Information geometric bound on general chemical reaction networks

引用

Physical Review E 2024年第4期109卷 044308-044308页

作者： Tsuyoshi Mizohata Tetsuya J. Kobayashi Louis-S. Bouchard Hideyuki Miyahara Graduate School of Information Science and Technology Hokkaido University Sapporo Hokkaido 060-0814 Japan Institute of Industrial Science The University of Tokyo 4-6-1 Komaba Meguro-ku Tokyo 153-8505 Japan Center for Quantum Science and Engineering University of California Los Angeles California 90095 USA Department of Chemistry and Biochemistry University of California Los Angeles California 90095 USA California NanoSystems Institute University of California Los Angeles California 90095 USA

We investigate the convergence of chemical reaction networks (CRNs), aiming to establish an upper bound on their reaction rates. The nonlinear characteristics and discrete composition of CRNs pose significant challenges in this endeavor. To circumvent these complexities, we adopt an information geometric perspective, utilizing the natural gradient to formulate a nonlinear system. This system effectively determines an upper bound for the dynamics of CRNs. We corroborate our methodology through numerical simulations, which reveal that our constructed system converges more rapidly than CRNs within a particular class of reactions. This class is defined by the count of chemicals, the highest stoichiometric coefficients in the reactions, and the total number of reactions involved. Further, we juxtapose our approach with traditional methods, illustrating that the latter falls short in providing an upper bound for CRN reaction rates. Although our investigation centers on CRNs, the widespread presence of hypergraphs across various disciplines, ranging from natural sciences to engineering, indicates potential wider applications of our method, including in the realm of information science.

关键词： Chemical kinetics, dynamics & catalysis Chemical reactions Learning network flow network flow optimization network optimization Stochastic thermodynamics Thermodynamics

来源：评论

学校读者我要写书评

暂无评论

Vulnerability of transport through evolving spatial networks

引用

Physical Review E 2024年第4期110卷 044305页

作者： Ali Molavi Hossein Hamzehpour Reza Shaebani Department of Physics Department of Theoretical Physics and Center for Biophysics

Insight into the blockage vulnerability of evolving spatial networks is important for understanding transport resilience, robustness, and failure of a broad class of real-world structures such as porous media and utility, urban traffic, and infrastructure networks. By exhaustive search for central transport hubs on porous lattice structures, we recursively determine and block the emerging main hub until the evolving network reaches the impenetrability limit. We find that the blockage backbone is a self-similar path with a fractal dimension which is distinctly smaller than that of the universality class of optimal path crack models. The number of blocking steps versus the rescaled initial occupation fraction collapses onto a master curve for different network sizes, allowing for the prediction of the onset of impenetrability. The shortest-path length distribution broadens during the blocking process reflecting an increase of spatial correlations. We address the reliability of our predictions upon increasing the disorder or decreasing the fraction of processed structural information.

关键词： Attacks on networks Cascades Complex systems Exhaustive network search network evolution network flow optimization network resilience Robustness Scaling laws of complex systems Transport in networks

来源：评论

学校读者我要写书评

暂无评论

Assessing a Synergistic Use of Alternate Broadband Delivery Models in Rural Areas

Assessing a Synergistic Use of Alternate Broadband Delivery ...

引用

IEEE International Conference on Pervasive Computing and Communications (PerCom)

作者： Max-Onakpoya, Esther Baker, Corey E. Univ Kentucky Dept Comp Sci Lexington KY 40506 USA

ISBN: (纸本)9781665416474

Access to broadband services is an important component in fostering the overall development of communities. However, some rural communities lack access to such services. To bridge this gap, various rural areas have adopted different kinds of alternate connectivity models. Such models attempt to mitigate the effect of the access gap on Internet-challenged rural areas. This work explores the synergistic use of such models by creating a theoretical framework for analyzing its benefits in predictable scenarios. More specifically, this work investigates a method of routing time-dependent data in quasi-deterministic delay tolerant networks that co-exist with communal access points within challenged rural environments. We formulate the problem as a maximum unsplittable multicommodity flow problem and propose an approximation algorithm that performs close to optimal.

关键词： rural connectivity network flow optimization multi-commodity flow alternate internet architectures

来源：评论

学校读者我要写书评

暂无评论

Optimal Transport with Constraints: From Mirror Descent to Classical Mechanics

引用

Physical Review Letters 2024年第5期133卷 057401-057401页

作者： Abdullahi Adinoyi Ibrahim Michael Muehlebach Caterina De Bacco <a href="https://***/04fq9j139">Max Planck Institute for Intelligent Systems</a> Cyber Valley Tübingen 72076 Germany.

Finding optimal trajectories for multiple traffic demands in a congested network is a challenging task. Optimal transport theory is a principled approach that has been used successfully to study various transportation problems. Its usage is limited by the lack of principled and flexible ways to incorporate realistic constraints. We propose a principled physics-based approach to impose constraints flexibly in optimal transport problems. Constraints are included in mirror descent dynamics using the D’Alembert-Lagrange principle from classical mechanics. This results in a sparse, local and linear approximation of the feasible set leading in many cases to closed-form updates.

关键词： Dynamics of networks network flow optimization network navigation network optimization optimization problems Traffic Transport in networks

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：