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

Replicating the performance of a portfolio of stocks using minimum dominating set

EXPERT SYSTEMS WITH APPLICATIONS 2025年 263卷

作者： Biswas, Subhojit Texas A&M Univ Dept Ind & Syst Engn College Stn TX 77843 USA

Analyzing a portfolio with many assets (stocks) is mathematically challenging. This article considers a large portfolio within a graph theory framework to obtain a tracking portfolio of the actual network. Each asset forms a vertex (node), and the correlation between assets forms the weight of the edges in the graphical network. The large graphical network is efficiently managed using Minimum Dominating Sets (MDS). Finding the MDS of a given portfolio is a well-known NP-hard problem in graph theory. An integer linear programming formulation of MDS is used, and the optimal solution is found using a Gurobi solver. Additionally, greedy and local search algorithms are developed to find the MDS, reducing computation time for extensive portfolios without significantly compromising solution quality. The MDS obtained by the solver and the algorithms are directly compared with an alternative portfolio selection strategy of randomly sub-sampling a certain percentage of the actual portfolio based on size. The expected return of the tracking portfolio is compared to the actual portfolio's expected return graphically, and a statistical significance t-test is performed to confirm the validity of the MDS, . Further, a sensitivity analysis of the expected return of the tracking portfolio obtained from the algorithms is conducted for three different threshold values of the pairwise correlation between assets. Computational results are performed on eight independent instances, with the universe of stocks varying throughout the computation.

关键词： Minimum dominating set local search algorithm Stock selection Greedy algorithm Gurobi solver

来源：评论

学校读者我要写书评

暂无评论

Flexible job shop scheduling with preventive maintenance consideration

引用

JOURNAL OF INTELLIGENT MANUFACTURING 2024年第4期35卷 1517-1539页

作者： Wocker, Michael Mario Ostermeier, Frederik Ferid Wanninger, Tobias Zwinkau, Ronny Deuse, Jochen TU Dortmund Univ Inst Prod Syst Leonhard Euler Str 5 D-44227 Dortmund Germany Univ Technol Sydney Ctr Adv Mfg Sydney Australia Tech Univ Munich Lab Prod Dev & Lightweight Design Boltzmannstr 15 D-85748 Munich Germany BMW Grp Knorrstr 147 D-80937 Munich Germany BMW Grp Bremer Str 6 D-80807 Munich Germany

In highly automated manufacturing systems running 24/7, preventive maintenance activities need to be executed during production times. Flexible job shops with several identical machines generally bear the potential to compensate temporary machine unavailability times caused by preventive maintenance without a considerable increase of the makespan due to machine paralleling. However, this requires sophisticated scheduling of manufacturing jobs and the assignment of maintenance activities over the scheduling horizon. This work, therefore, introduces a mixed-integer program that models both job scheduling and maintenance activity assignment. A local search algorithm is developed to solve both problems in an integrated way. Numerical studies are carried out based on data from a real flexible job shop in the automotive industry with 78 machines and four products. The results show that joint job scheduling and maintenance activity assignment is required to obtain a makespan similar to the makespan without maintenance consideration. Non-sophisticated scheduling of maintenance windows can increase the makespan by more than 20 percentage points compared to sophisticated scheduling. Besides, we show that only a limited amount of maintenance activities can be compensated and that higher unavailability times will inevitably lead to detrimental effects on the makespan unless maintenance worker capacity is increased.

关键词： Manufacturing Flexible job shop Scheduling Preventive maintenance local search algorithm

来源：评论

学校读者我要写书评

暂无评论

Best Principal Submatrix Selection for the Maximum Entropy Sampling Problem: Scalable algorithms and Performance Guarantees

引用

OPERATIONS REsearch 2024年第2期72卷 493页

作者： Li, Yongchun Xie, Weijun Georgia Inst Technol H Milton Stewart Sch Ind & Syst Engn Atlanta 30332 Georgia

This paper studies a classic maximum entropy sampling problem (MESP), which aims to select the most informative principal submatrix of a prespecified size from a covariance matrix. By investigating its Lagrangian dual and primal characterization, we derive a novel convex integer program for MESP and show that its continuous relaxation yields a near-optimal solution. The results motivate us to develop a sampling algorithm and derive its approximation bound for MESP, which improves the best known bound in literature. We then provide an efficient deterministic implementation of the sampling algorithm with the same approximation bound. Besides, we investigate the widely used local search algorithm and prove its first known approximation bound for MESP. The proof techniques further inspire for us an efficient implementation of the local search algorithm. Our numerical experiments demonstrate that these approximation algorithms can efficiently solve medium-size and large-scale instances to near optimality. Finally, we extend the analyses to the A-optimal MESP, for which the objective is to minimize the trace of the inverse of the selected principal submatrix.

关键词： maximum entropy sampling problem convex integer program sampling algorithm local search algorithm A-optimality

来源：评论

学校读者我要写书评

暂无评论

Frequency veering of railway vehicle systems and its mapping to vibration characteristics

引用

MULTIBODY SYSTEM DYNAMICS 2024年第4期62卷 463-492页

作者： Liu, Guangyu Gong, Dao Zhou, Jinsong Ren, Lihui Wang, Zegen Deng, Xin Sun, Weiguang You, Taiwen Tongji Univ Inst Rail Transit 4800 Cao An Rd Shanghai 201804 Peoples R China Lanzhou Jiaotong Univ Sch Mech Engn 88 Anning West Rd Lanzhou 730070 Peoples R China

Frequency veering is a phenomenon that occurs during modal parameter changes and is closely related to the response characteristics of the system. First, by taking a system with simple DOFs as the research object, the variations in the modal damping ratio and mode shape in the process of frequency veering are analysed, and a criterion for identifying this phenomenon is preliminarily proposed. Then, to explore the modal changes in complex vehicle systems with multiple DOFs, an adaptive modal continuous tracking algorithm based on a local search algorithm is proposed that takes the Euclidean closeness between complex mode shapes as an index. Frequency veering is analysed with the established vehicle system dynamics model (Model I) and reproduced through the SIMPACK model (Model II) for multibody dynamics simulation. The perturbation method is used to analyse the mechanism by which the vehicle system eigenvectors are prone to mutations during frequency veering, and the abnormal changes in the mode shapes during this process are further verified. In addition, two quantitative indices for identifying frequency veering phenomena are proposed based on the modal assurance criterion and mode shape similarity. Finally, the mapping relationship between the frequency veering and vehicle system response is explored. The results indicate that before and after frequency veering, the mode shapes interchange, and in the frequency veering zone, the damping-hopping phenomenon occurs, resulting in a significant decrease in system stability. Corresponding to the phenomena of modal damping ratios and mode shapes, the motion morphology of the vehicle system is clearly observable. Moreover, the response at the DOFs of the car body and bogie are obviously enhanced;these responses are also manifested in the increasing vibrations of the car body and bogie and the deterioration of the vehicle ride quality.

关键词： Railway vehicles Complex mode Euclidean closeness local search algorithm Modal continuous tracking Frequency veering Mutations of eigenvectors Multimode coupling response

来源：评论

学校读者我要写书评

暂无评论

A MILP model and a heuristic algorithm for post-disaster connectivity problem with heterogeneous vehicles

引用

JOURNAL OF HEURISTICS 2024年第5-6期30卷 359-396页

作者： Tukenmez, Ilknur Sarac, Tugba Kaya, Onur Bursa Tech Univ Ind Engn Dept Bursa Turkiye Eskisehir Osmangazi Univ Ind Engn Dept Eskisehir Turkiye Eskisehir Tech Univ Ind Engn Dept Eskisehir Turkiye

Throughout the response phase of the disaster, the speedy restoration of transportation by reconnecting the nodes where the connection is broken is absolutely critical for evacuating civilians, providing clear access to hospitals, and distributing aid. Following a disaster, some roads in a disaster area might be closed to transportation. In reality, some roads can be blocked due to debris, and some of roads can be blocked by collapsing. In this model, different types of road unblocking methods are included, and each road can only be opened to access by a vehicle suitable for that method. So, different types of vehicles may be needed to repair the roads depending on the type of damage. In addition, fast-built bridges built both on land and over water are also used if necessary following a disaster. In problems of this nature, it is essential to restore the roads to enable the complete connectivity of the network such that all nodes can be reached by one another. In addition, it is also critical for the speedy reach of critical nodes, such as hospitals, and emergency disaster centers. This study aims to reduce the maximum time for connection and minimize the total time in which to reach critical nodes. For this purpose, we developed a bi-objective mathematical model that considers the multiple vehicle types that can repair different types of damages. Since the problem is NP-hard, two heuristic methods were developed, and the numerical results were presented. It has been observed that the local search algorithm gives better results than the hybrid algorithm. Additionally, different scenario data was produced. Numbers of unconnected components from 3 to 10 are solved with heuristic algorithms for test data containing 80 and 250 nodes, and real-life data containing 223 nodes and 391 edges are solved with heuristic algorithms for the number of unconnected components 6, 9, 12, and 15.

关键词： Connectivity problem Arc routing local search algorithm Hybrid algorithm Disaster management

来源：评论

学校读者我要写书评

暂无评论

Combating COVID-19 by placing facilities maintaining social distancing

引用

EXPERT SYSTEMS WITH APPLICATIONS 2024年第PartA期238卷

作者： Banerjee, Suman Pal, Bithika Mahapatra, Maheswar Singha Indian Inst Technol Jammu Dept Comp Sci & Engn Nagrota 181221 India Indian Inst Technol Kharagpur Dept Comp Sci & Engn Kharagpur 721302 W Bengal India Indian Inst Management Mumbai Mumbai 400087 Maharashtra India

In this paper, we introduce and study the problem of facility location along with the notion of 'social distancing'. The input to the problem is the road network of a city where the nodes are the residential zones, edges are the road segments connecting the zones along with their respective distance. We also have the information about the population at each zone, different types of facilities to be opened and in which number, and their respective demands in each zone. The goal of the problem is to locate the facilities such that the people can be served and at the same time the total social distancing is maximized. We formally call this problem as the SOCIAL DISTANCING-BASED FACILITy LOCATION PROBLEM. We mathematically quantify social distancing for a given allocation of facilities and proposed an optimization model. As the problem is NP-Hard, we propose three solution methodologies. The first one is a simulation-based approach, the second one is a greedy heuristic, and the third one is a local search heuristic. To validate the proposed solution methodologies, we collect the data from the Food Corporation of India for the city of Kolkata, which happens to be the largest city of eastern India. With this dataset, we perform an extensive set of experiments. From the results, we observe that the proposed local search heuristic allocates facilities that lead to minimum average queue length and greedy heuristic allocates facilities that lead to the maximum social distancing.

关键词： Facility location Social distancing Integer programming local search algorithm COVID-19

来源：评论

学校读者我要写书评

暂无评论

A local search method based on edge age strategy for minimum vertex cover problem in massive graphs

引用

EXPERT SYSTEMS WITH APPLICATIONS 2021年 182卷 115185-115185页

作者： Quan, Changsheng Guo, Ping Chongqing Univ Coll Comp Sci 174 Shazhengjie Chongqing 400044 Peoples R China Chongqing Key Lab Software Theory & Technol 174 Shazhengjie Chongqing 400044 Peoples R China

Minimum vertex cover problem (MVC) is a classic combinatorial optimization problem, which has many critical real-life applications in scheduling, VLSI design, artificial intelligence, and network security. For MVC, researchers have proposed many heuristic algorithms, especially local search algorithms. And recently, researchers have increased their interest in solving large real-world graphs which require algorithms with faster searching performance. In this work, we propose a new edge weighting method called EABMS. EABMS has a time complexity of O(1). Based on EABMS, we propose our MVC solver framework called EAVC in solving MVC for massive graphs. We conducted experiments and compared the results of EAVC solvers with state of the art solvers. The results show that EABMS is effective in weighing edges for large sparse graphs and EAVC solvers outperform state of the art solvers.

关键词： Minimum vertex cover local search algorithm Edge weighting Combinatorial optimization Heuristic algorithm

来源：评论

学校读者我要写书评

暂无评论

Higher-Order Multicuts for Geometric Model Fitting and Motion Segmentation

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2023年第1期45卷 608-622页

作者： Levinkov, Evgeny Kardoost, Amirhossein Andres, Bjoern Keuper, Margret Bosch Ctr Artificial Intelligence D-71272 Renningen Baden Wurttembe Germany Univ Mannheim Data & Web Sci Grp D-68131 Mannheim Baden Wurttembe Germany Tech Univ Dresden D-01069 Dresden Saxony Germany Ctr Syst Biol Dresden CSBD D-01307 Dresden Saxony Germany Univ Siegen D-57076 Siegen Germany Max Planck Inst Informat Saarland Informat Campus D-66123 Saarbrucken Saarland Germany

The minimum cost lifted multicut problem is a generalization of the multicut problem (also known as correlation clustering) and is a means to optimizing a decomposition of a graph w.r.t. both positive and negative edge costs. It has been shown to be useful in a large variety of applications in computer vision thanks to the fact that multicut-based formulations do not require the number of components given a priori;instead, it is deduced from the solution. However, the standard multicut cost function is limited to pairwise relationships between nodes, while several important applications either require or can benefit from a higher-order cost function, i.e., hyper-edges. In this paper, we propose a pseudo-boolean formulation for a multiple model fitting problem. It is based on a formulation of any-order minimum cost lifted multicuts, which allows to partition an undirected graph with pairwise connectivity such as to minimize costs defined over any set of hyper-edges. As the proposed formulation is np-hard and the branch-and-bound algorithm (as well as obtaining lower bounds) is too slow in practice, we propose an efficient local search algorithm for inference into resulting problems. We demonstrate versatility and effectiveness of our approach in several applications: 1) We define a geometric multiple model fitting, more specifically, a line fitting problem on all triplets of points and group points, that belong to the same line, together. 2) We formulate homography and motion estimation as a geometric model fitting problem where the task is to find groups of points that can be explained by the same geometrical transformation. 3) In motion segmentation our model allows to go from modeling translational motion to euclidean or affine transformations, which improves the segmentation quality in terms of F-measure.

关键词： Motion segmentation Computer vision Geometric modeling Costs Task analysis Data models Computational modeling Combinatorial optimization local search algorithm higher-order multicut motion segmentation geometric model fitting

来源：评论

学校读者我要写书评

暂无评论

Optimizing train stopping patterns for congestion management

引用

PUBLIC TRANSPORT 2023年第1期15卷 1-29页

作者： Yamauchi, Tatsuki Takamatsu, Mizuyo Imahori, Shinji Internet Initiat Japan Inc Tokyo 1020071 Japan Chuo Univ Dept Informat & Syst Engn Tokyo 1128551 Japan

In this paper, we optimize train stopping patterns during the morning rush hour in Japan. Since trains are extremely crowded, we need to determine stopping patterns based not only on travel time but also on congestion rates of trains. We exploit a Wardrop equilibrium model to compute passenger flows subject to congestion phenomena and present an efficient local search algorithm to optimize stopping patterns which iteratively computes a Wardrop equilibrium. The framework of the proposed algorithm is extended to solve the problem of optimizing the number of services for each train type. We apply our algorithms to railway lines in Tokyo including the Keio Line with six types of trains and demonstrate that we succeed in relaxing congestion.

关键词： Train stopping pattern Wardrop equilibrium local search algorithm Event-activity network

来源：评论

学校读者我要写书评

暂无评论

Two Hybrid Heuristic algorithms for Optimizing Data Processing Schedules in Distributed Edge Computing 11

Two Hybrid Heuristic Algorithms for Optimizing Data Processi...

引用

11th International Conference on Wireless Networks and Mobile Communications (WINCOM) - Inclusive and Intelligent Connectivity

作者： Sayah, Achraf Aqil, Said Aadil, Bouchra Lahby, Mohamed Hassan II Univ Lab Appl Math & Comp Sci Higher Normal Sch Casablanca Morocco Hassan II Univ Lab Artificial Intelligence & Complex Syst Engn Natl Higher Sch Arts & Crafts Casablanca Morocco

ISBN: (纸本)9798350377873;9798350377866

In recent years, edge computing has emerged as a promising solution in the field of network computing. This architecture ensures the availability of distributed computing resources located closer to end-users and IoT devices. However, resource scheduling remains a significant challenge in edge computing, requiring effective strategies to optimize resource utilization and ensure efficient task allocation. In this paper, we propose two hybrid approaches that combine the NawazEnscore-Ham (NEH) algorithm with local search and Greedy Random Adaptive search Procedure (GRASP) algorithm with local search for modeling and solving data traffic in distributed edge computing environments (DPSDEC). Through extensive evaluations, we consistently observe that the NEH algorithm outperforms GRASP, delivering minimized makespan and generating efficient schedules. Moreover, the NEH algorithm performs very well in less complex situations and maintains this advantage even in larger and more complex problems.

关键词： local search algorithm Edge Computing Distributed Networks Scheduling.

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：