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

Optimizing wind farm cable layout considering ditch sharing

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2024年第1期31卷 88-114页

作者： Cerveira, Adelaide de Sousa, Amaro Pires, E. J. Solteiro Baptista, Jose Univ Tras os Montes & Alto Douro Escola Ciencias & Tecnol P-5000801 Vila Real Portugal INESC TEC INESC Technol & Sci INESC Porto UTAD pole Porto Portugal Univ Aveiro Inst Telecomunicacoes Aveiro Portugal

Wind power is becoming an important source of electrical energy production. In an onshore wind farm (WF), the electrical energy is collected at a substation from different wind turbines through electrical cables deployed over ground ditches. This work considers the WF layout design assuming that the substation location and all wind turbine locations are given, and a set of electrical cable types is available. The WF layout problem, taking into account its lifetime and technical constraints, involves selecting the cables to interconnect all wind turbines to the substation and the supporting ditches to minimize the initial investment cost plus the cost of the electrical energy that is lost on the cables over the lifetime of the WF. It is assumed that each ditch can deploy multiple cables, turning this problem into a more complex variant of previously addressed WF layout problems. This variant turns the problem best fitting to the real case and leads to substantial gains in the total cost of the solutions. The problem is defined as an integer linear programming model, which is then strengthened with different sets of valid inequalities. The models are tested with four WFs with up to 115 wind turbines. The computational experiments show that the optimal solutions can be computed with the proposed models for almost all cases. The largest WF was not solved to optimality, but the final relative gaps are small.

关键词： wind farm layout power cables ditch sharing optimization integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Spanning-Tree Based Coverage for a Tethered Robot

引用

IEEE ROBOTICS AND AUTOMATION LETTERS 2025年第2期10卷 1888-1895页

作者： Peng, Xiao Schwarzentruber, Francois Simonin, Olivier Solnon, Christine INSA Lyon CITI Lab INRIA F-69621 Villeurbanne France Univ Lyon ENS Lyon CNRS LIPUCB Lyon 1 F-69007 Lyon France

Tethered robots find widespread application in underwater and disaster recovery missions. This study focuses on the coverage path planning (CPP) problem for a tethered robot, considering cable constraints and the presence of forbidden areas in the environment. We propose adapting the spanning tree- based coverage algorithm to address CPP. Theoretical complexity analysis reveals NP-completeness in cases involving forbidden areas. We show how to solve CPP by searching for a tree in a configuration graph, and how to reduce the size of this graph to compute approximate solutions faster. We introduce integer linear programming (ILP) models corresponding to these approximations and experimentally compare them on various instances.

关键词： Robots Path planning Complexity theory Cables Solids integer linear programming Shape Polynomials Object recognition Mobile robots Coverage path planning tethered robot computational complexity

来源：评论

学校读者我要写书评

暂无评论

Minimizing the influence spread over a network through node interception

引用

OPTIMIZATION LETTERS 2024年第6期18卷 1361-1382页

作者： Yao, Shunyu Fan, Neng Krokhmal, Pavlo Univ Arizona Dept Syst & Ind Engn Tucson AZ 85721 USA

We consider the problem of determining the optimal node interception strategy during influence propagation over a (directed) network G=(V,A)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G=(V,A)$$\end{document}. More specifically, this work aims to find an interception set D subset of V\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$D \subseteq V$$\end{document} such that the influence spread over the remaining network G\D\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G \backslash D$$\end{document} under the linear threshold diffusion model is minimized. We prove its NP-hardness, even in the case when G is an undirected graph with unit edge weights. An exact algorithm based on integer linear programming and delayed constraint generation is proposed to determine the most critical nodes in the influence propagation process. Additionally, we investigate the technique of lifting inequalities of minimal activation sets. Experiments on the connected Watts-Strogatz small-world networks and real-world networks are also conducted to validate the effectiveness of our methodology.

关键词： Influence spread Influence minimization integer linear programming Delayed constraint generation

来源：评论

学校读者我要写书评

暂无评论

A Practical Approach for Resource-Constrained Project Scheduling

引用

IEEE ACCESS 2024年 12卷 12976-12991页

作者： Manousakis, Konstantinos Savva, Giannis Papadouri, Nicos Mavrovouniotis, Michalis Christofides, Athanasios Kolokotroni, Nedi Ellinas, Georgios Univ Cyprus Dept Elect & Comp Engn CY-1678 Nicosia Cyprus Univ Cyprus KIOS Res & Innovat Ctr Excellence CY-1678 Nicosia Cyprus Eratosthenes Ctr Excellence CY-3012 Limassol Cyprus Cyta CY-1396 Nicosia Cyprus

This work considers project scheduling and planning for the decision support of organizations, that continuously require the implementation of many projects for their successful operation. The efficient scheduling and planning of these projects is essential for the timely completion of all projects, utilizing the appropriate resources. To this end, this work presents a novel integer linear program (ILP) formulation, that takes into account the project requirements, the involved teams, their interdependencies, as well as other constraints, so as to provide an optimal scheduling plan. Moreover, additional constraints are considered to address practical challenges such as complexity and uncertainties. Finally, techniques are introduced in this work to address scalability issues, as well as dynamic changes that may occur when the obtained schedule is currently being implemented. All aforementioned techniques present a number of advantages for an organization, as they reduce considerably the person-hours required by the management team to perform the scheduling, they produce scheduling plans that span large planning horizons, and they decrease the project completion times, thus reducing the cost that the organization incurs for implementing the projects. Realistic scenarios are considered, where real data on projects and teams are taken into account. From the results obtained, it is evident that the proposed ILP can obtain the optimal solution in terms of minimizing the duration for the completion of all projects, while the proposed practical (heuristic) approaches, can obtain solutions close to the optimal in terms of planning horizon and objective score with significant reduction in computation time, from hours to seconds/minutes. Moreover, it is shown that the scheduling plan can be adapted in the event of miscalculations related to the effort required for implementing the projects or new projects can be added within the existing scheduling plan.

关键词： Project scheduling and planning decision support systems integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Designing compact, connected and gap-free reserves with systematic reserve site selection models

引用

APPLIED MATHEMATICAL MODELLING 2024年 134卷 307-323页

作者： Brunel, Adrien Omer, Jeremy Gicquel, Antoine Lanco, Sophie Univ Montpellier UMR MARBEC IRD IfremerCNRS F-34200 Sete France Univ Rennes INSA Rennes CNRS IRMAR UMR 6625 F-35000 Rennes France

Protected areas play a crucial role in current global policies to mitigate the erosion of biodiversity and systematic reserve site selection models are increasingly involved in their design. These models address the optimisation problem that seeks to cover spaces hosting biodiversity features with nature reserves at a minimum cost for human activities. To increase the likelihood of a successful implementation, reserves need to be spatially consistent. Widely used decision support tools such as Marxan and PrioritizR commonly enforce compactness indirectly by penalising the reserve perimeter in the objective function. Few other optimisation models explicitly consider spatial properties such as limited fragmentation, connectivity of selected sites, and buffer zones around them, etc . So far, no reserve site selection model can guarantee the production of a connected, compact, and gap -free reserve all at once. The impossibility of designing reserve solutions with desirable spatial properties using existing models makes it difficult to implement such solutions in the real world. Therefore, we propose a mixed -integer linear program to build a reserve that is connected, compact, and gap -free. To enforce these spatial attributes within a reserve site selection model, we used a multicommodity flow approach. We tested the computational feasibility of our model on generated instances and the real instance of Fernando de Noronha. The results indicate that a single model can be used to enforce compactness, connectivity, and the absence of gaps. Using this optimisation model, conservation practitioners can design reserve solutions with desirable spatial properties, thereby increasing the likelihood of a successful implementation.

关键词： Reserve site selection integer linear programming Connectivity Compactness Gap-free Fragmentation

来源：评论

学校读者我要写书评

暂无评论

Scheduling jobs using queries to interactively learn human availability times

引用

COMPUTERS & OPERATIONS RESEARCH 2024年 167卷

作者： Varga, Johannes Raidl, Guenther R. Roennberg, Elina Rodemann, Tobias TU Wien Inst Log & Computat A-1040 Vienna Austria Linkoping Univ Dept Math S-58183 Linkoping Sweden Honda Res Inst Europe D-63073 Offenbach Germany

The solution to a job scheduling problem that involves humans as well some other shared resource has to consider the humans' availability times. For practical acceptance of a scheduling tool, it is crucial that the interaction with the humans is kept simple and to a minimum. It is rarely practical to ask users to fully specify their availability times or to let them enumerate all possible starting times for their jobs. In the scenario we are considering, users initially only propose a single starting time for each of their jobs and a feasible and optimized schedule shall then be found within a small number of interaction rounds. In each such interaction round, our scheduling approach may propose each user a small number of alternative time intervals for scheduling the user's jobs, and then the user may accept or reject these. To make the best out of these limited interaction possibilities, we propose an approach that utilizes integer linear programming and an exact and computationally efficient probability calculation for the users' availabilities assuming two different stochastic models. In this way, educated proposals of alternative time intervals for performing the jobs are determined based on the computed availability probabilities and the improvements these time intervals would enable. The approach is experimentally evaluated on a variety of artificial benchmark scenarios, and different variants are compared with each other and to diverse baselines. Results show that an initial schedule can usually be quickly improved over few interaction rounds even when assuming a quite simple stochastic model, and the final schedule may come close to the solution of the full-knowledge case despite the strongly limited interaction.

关键词： Job scheduling Human machine interaction integer linear programming Active learning

来源：评论

学校读者我要写书评

暂无评论

Computing aperiodic tiling rhythmic canons via SAT models

引用

CONSTRAINTS 2024年第3-4期29卷 215-233页

作者： Auricchio, Gennaro Ferrarini, Luca Gualandi, Stefano Lanzarotto, Greta Pernazza, Ludovico Univ Bath Dept ECS Bath BA2 7AY Somerset England Univ Pavia Dept Math Via Adolfo Ferrata 5 I-27100 Pavia Italy Univ Milano Bicocca Dept Math & Its Applicat Piazza Ateneo Nuovo 1 I-20126 Milan Italy

In Mathematical Music theory, the Aperiodic Tiling Complements Problem consists in finding all the possible aperiodic complements of a given rhythm A. The complexity of this problem depends on the size of the period n of the canon and on the cardinality of the given rhythm A. The current state-of-the-art algorithms can solve instances with n smaller than 180\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varvec{180}$$\end{document}. In this paper, we propose an ILP formulation and a SAT Encoding to solve this mathemusical problem, and we use the Maplesat solver to enumerate all the aperiodic complements. We then enhance the SAT model in two different ways. First, we enforce the SAT model with a set of clauses that retrieves the solutions up to translation. Second, we propose a decomposition of the solution space that allows to parallelize the resolution of the problem. We validate our different models using several different periods and rhythms and we compute for the first time the complete list of aperiodic tiling complements of standard Vuza rhythms for canons with period n=180,420,900\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varvec{n} = \varvec{\left\{ 180, 420, 900 \right\} }$$\end{document}.

关键词： Mathematical models for music Aperiodic tiling rhythms SAT Encoding integer linear programming

来源：评论

学校读者我要写书评

暂无评论

A direct block scheduling model considering operational space requirement for strategic open-pit mine production planning

引用

OPTIMIZATION AND ENGINEERING 2024年第4期25卷 2149-2175页

作者： Nancel-Penard, Pierre Jelvez, Enrique Univ Chile Fac Phys & Math Sci Dept Min Engn Delphos Mine Planning Lab Beauchef 850 Santiago Chile Univ Chile Adv Min Technol Ctr Ave Tupper 2007 Santiago 8370451 Chile

Long-term block scheduling is a challenging problem that involves determining the best extraction period for blocks to maximize the net present value of the open-pit mining business. This process involves multiple constraints, mainly ensuring safe pit walls and imposing maximum limits on operational resource consumption. However, most of the models proposed in the literature do not sufficiently consider geometric constraints that ensure a minimum space for mining equipment to operate safely. These models overlook practical and operational constraints and generate solutions that are difficult to implement. Consequently, the promised net present value cannot be achieved. In this paper, we propose an integer linear programming model that considers minimum mining width requirements along with a decomposition heuristic method to solve *** proposed model determines which blocks should be mined and when to maximize net present value while ensuring safe pit walls and respecting limits on operational resources and geometric constraints. Geometric constraints require that the minimum operational distance be considered within each extraction period. Because the incorporation of geometric constraints in the proposed model makes it harder to solve, a time-space decomposition heuristic is implemented. This heuristic consists of successive time and space aggregation/disaggregation to generate simpler subproblems to be solved. This approach was applied on two case studies. The results show that the proposed methodology generates practical production plans that are more realistic to implement in mining operations, lowering the gap between factual and promised net present value.

关键词： Operational distance Minimum mining width Geometric constraints Direct block scheduling Mathematical modeling integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Enhancing Resource Utilization of Non-Terrestrial Networks Using Temporal Graph-Based Deterministic Routing

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2024年第6期73卷 9211-9216页

作者： Shi, Keyi Wang, Jingchao Li, Hongyan Wang, Kan Xidian Univ Sch Commun Engn Xian 710071 Peoples R China Peng Cheng Lab Shenzhen 518055 Peoples R China Xian Univ Technol Sch Comp Sci & Engn Xian 710048 Peoples R China

Deterministic routing has emerged as a promising technology for future non-terrestrial networks (NTNs), offering the potential to enhance service performance and optimize resource utilization. However, the dynamic nature of network topology and resources poses challenges in establishing deterministic routing. These challenges encompass the intricacy of jointly scheduling transmission links and cycles, as well as the difficulty of maintaining stable end-to-end (E2E) routing paths. To tackle these challenges, our work introduces an efficient temporal graph-based deterministic routing strategy. Initially, we utilize a time-expanded graph (TEG) to represent the heterogeneous resources of an NTN in a time-slotted manner. With TEG, we meticulously define each necessary constraint and formulate the deterministic routing problem. Subsequently, we transform this nonlinear problem equivalently into solvable integer linear programming (ILP), providing a robust yet time-consuming performance upper bound. To address the considered problem with reduced complexity, we extend TEG by introducing virtual nodes and edges. This extension facilitates a uniform representation of heterogeneous network resources and traffic transmission requirements. Consequently, we propose a polynomial-time complexity algorithm, enabling the dynamic selection of optimal transmission links and cycles on a hop-by-hop basis. Simulation results validate that the proposed algorithm yields significant performance gains in traffic acceptance, justifying its additional complexity compared to existing routing strategies.

关键词： Routing Delays Satellites Network topology Satellite broadcasting Resource management Complexity theory Non-terrestrial network deterministic routing temporal graph integer linear programming resource utilization

来源：评论

学校读者我要写书评

暂无评论

Alternative Approaches of Solving the Discrete Tomography

引用

programming AND COMPUTER SOFTWARE 2024年第SUPPL 1期50卷 S75-S81页

作者： Sahakyan, H. Aslanyan, L. Natl Acad Sci Republ Armenia Inst Informat & Automat Problems Yerevan 0014 Armenia Natl Acad Sci Republ Armenia Yerevan 0019 Armenia

In this paper, we consider a discrete tomography problem, which aims at characterizing given projections of a binary matrix assuming nonrepeatability property of the matrix rows. We discuss integer linear programming representation, and the ways of generating learning instances of this problem, to solve it using the machine learning methods.

关键词： integer linear programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：