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

Efficient configuration of heterogeneous multistatic sonar networks: A mixed-integer linear programming approach

COMPUTERS & OPERATIONS RESEARCH 2024年 167卷

作者： Thuillier, Owein Le Josse, Nicolas Olteanu, Alexandru-Liviu Sevaux, Marc Tanguy, Herve Thales Def & Mission Syst Brest France Univ Bretagne Sud Lab STICC CNRS UMR 6285 Lorient France

The work undertaken in this paper pertains to the optimal spatial configuration of a heterogeneous Wireless Sensor Network (WSN) for the Area Coverage (AC) problem. Specifically, this research falls under the heading of Anti -Submarine Warfare (ASW) with an emphasis on active sonar systems and, more pointedly still, on a specific type of sensor: sonobuoys (portmanteau word formed by "sonar"and "buoy"). These buoys are further divided into three main categories: transmitter-only (Tx), receiver-only (Rx) and transmitter-receiver (TxRx). In this paper, we will therefore try to determine the geographical location of the different buoys comprising a Multistatic Sonar Network (MSN), special case of WSN, so as to maximize the overall surface area covered. To do this, we discretize an Area of Interest (AoI) into regular cells using bathymetric and altimetric data, and place a deployment position and a fictitious target at the center of each cell so that we can evaluate the network's performance. More precisely, we are taking into account a limited number of sensors (buoys) with possible pairwise incompatibilities, variable performances, probabilistic detection models, an adverse masking effect (direct blast) as well as coastlines features. Finally, in order to solve this problem, we have developed several efficient mixed-integer linear Programs (MILPs), all of which have been thoroughly tried-and-tested on a benchmark set of 100 instances derived from real elevation data. This has led us to identify an ideal model, i.e. one that is significantly better than all the others in the statistical sense.

关键词： OR in defense Multistatic sonar networks Heterogeneous sensors Area coverage problem mixed-integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Exact Complexity Certification of Suboptimal Branch-and-Bound Algorithms for mixed-integer linear programming

引用

IFAC-PapersOnLine 2023年第2期56卷 7428-7435页

作者： Shamisa Shoja Daniel Axehill Division of Automatic Control Linköping University Sweden

In this paper, we present a method to exactly certify the computational complexity of standard suboptimal branch-and-bound (B&B) algorithms for computing suboptimal solutions to mixed-integer linear programming (MILP) problems. Three well-known approaches for suboptimal B&B are considered. This work shows that it is possible to exactly certify the computational complexity also when these approaches are used. Moreover, it also enables to compute exact bounds on the level of suboptimality actually to be obtained online, also for methods previously without any such guarantees. It additionally provides a novel deeper insight into how they affect the performance of the B&B algorithm in terms of the required computation time and memory storage. The exact bounds on the online worst-case computational complexity (e.g., the accumulated number of LP solver iterations or size of the B&B tree) and the worst-case suboptimality computed with the proposed method are very relevant for real-time applications such as Model Predictive Control (MPC) for hybrid systems. The numerical experiments confirm the correctness of the proposed method, and they demonstrate the usefulness of the certification method for certification of a standard online B&B-based MILP solver employing the three considered suboptimal techniques.

关键词： Numerical methods for optimal control Optimal control of hybrid systems mixed-integer linear programming Branch and bound method Complexity certification Suboptimal solutions

来源：评论

学校读者我要写书评

暂无评论

Scheduling of Multi-Robot Job Shop Systems in Dynamic Environments: mixed-integer linear programming and Constraint programming Approaches

引用

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 2023年 115卷

作者： Fatemi-Anaraki, Soroush Tavakkoli-Moghaddam, Reza Foumani, Mehdi Vahedi-Nouri, Behdin Univ Tehran Coll Engn Sch Ind Engn Tehran Iran Tech Univ Munich TUM Sch Management Arcisstr 21 D-80333 Munich Germany Univ Sydney Rio Tinto Ctr Mine Automat Australian Ctr Field Robot Sydney NSW Australia

This paper investigates a dynamic scheduling problem within a job shop robotic cell, wherein multiple robotic arms are responsible for material handling in a U-shaped arrangement. Each robotic arm has ac-cess to specific workstations based on their distance in the cell layout. Therefore, a part may need to be exchanged between several robots according to its process plan. For this purpose, intermediate buffers are positioned between each pair of consecutive robots. Due to the dynamic nature of the problem, new jobs arrive at unpredictable times, which in turn necessitates rescheduling taking the system's current state into account. To tackle this problem, firstly, a mixed-integer linear programming (MILP) model is devised. Secondly, three distinct Speed-up Constraints (SCs) derived from the problem's inherent charac-teristics are designed and implemented to accelerate the MILP model's solving procedure. Afterward, the problem is formulated using Constraint programming (CP) approach. The performance of the CP model and the MILP model in presence of all possible combinations of the SCs are evaluated and compared through solving various random instances. Next, an analysis is performed on the buffers' pick-up crite-rion and how it is affected by the problem's size. Besides, the impact of changes in the robots' speed on the productivity of the cell is assessed. Finally, the extent to which the rescheduling priority affects the output of the model is studied. (c) 2022 Elsevier Ltd. All rights reserved.

关键词： Job shop robotic cell Material handling Dynamic scheduling mixed-integer linear programming Constraint programming

来源：评论

学校读者我要写书评

暂无评论

Offline segmentation of spatio-temporal order trajectories by mixed-integer linear programming for determining process times in production systems

引用

Procedia CIRP 2022年 107卷 712-717页

作者： Maximilian Volk Carina Mieth Karlsruhe Institute of Technology Kaiserstraβe 12 76131 Karlsruhe Germany TRUMPF Machine Tools Inc. Johann-Maus-Straβe 2 71254 Ditzingen Germany TU Dortmund University Emil-Figge-Straβe 61 44227 Dortmund Germany

Real-time indoor positioning systems in manufacturing systems are used to track production orders. This generates spatio-temporal trajectories which can be segmented to determine process times. We present formulations of the offline segmentation problem as mixed-integer linear programs (MILPs) that utilize the sequence of processing steps from ERP systems. The MILP formulations are compared with online heuristics in terms of their accuracy and computational effort on data generated with features from a real job shop. We show that in terms of accuracy our offline segmentation formulations outperform the online heuristics with increasing measurement errors, justifying their higher computational effort.

关键词： indoor positiong systems mixed-integer linear programming process time estimation trajectory segmentation spatio-temporal production data

来源：评论

学校读者我要写书评

暂无评论

Formulating multi-class user equilibrium using mixed-integer linear programming

引用

EURO JOURNAL ON TRANSPORTATION AND LOGISTICS 2022年 11卷

作者： Lin, Xiao Leclercq, Ludovic Tavasszy, Lorant van Lint, Hans Delft Univ Technol Dept Transport & Planning Stevinweg 1 NL-2628 CN Delft Netherlands Univ Gustave Eiffel ENTPE LICIT Lyon France

We introduce an approach to formulate and solve the multi-class user equilibrium traffic assignment as a mixed-integer linear programming (MILP) problem. Compared to simulation approaches, the analytical MILP formulation makes the solution of network assignment problems more tractable. When applied in a multi -class context, it obviates the need to assume a symmetrical influence between classes and thereby allows richer traffic behavior to be taken into account. Also, it integrates naturally in optimization problems such as maintenance planning and traffic management. We develop the model and apply it for the Sioux Falls network, showing that it outperforms the traditional Beckmann-based and MSA approaches in smaller-scale problems. Further research opportunities lie in developing extensions of MILP-based assignment, with different variants of user equilibrium or dynamic assignment, and in improving the model and solution algorithms to allow large-scale application.

关键词： Traffic assignment User equilibrium Mathematical programming mixed-integer linear programming Multi-class

来源：评论

学校读者我要写书评

暂无评论

Optimal Coordination of Overcurrent Relays Using mixed integer linear programming

引用

IEEE LATIN AMERICA TRANSACTIONS 2016年第3期14卷 1289-1295页

作者： Kida, A. A. Gallego, L. A. Univ Estadual Londrina Londrina Parana Brazil

In distribution systems, the coordination and selectivity of protection devices are essential for improving reliability and security indicators. In these systems, the overcurrent relays are widely used. During a fault, the heat dissipation is high. Therefore, it is important that the relays act quickly. The problem of coordination is linear when the pickup currents are previously known. In this paper, a methodology for an optimal coordination of non-directional overcurrent relays in radial systems using mixed-integer linear programming (MILP) is proposed. The main objective is to compute the Time Dial Settings (TDSs) that minimize the relay operational times, without any loss of sensitivity, selectivity and reliability. The TDSs are considered as discrete variables, so the problem becomes discrete and is solved through MILP. The selectivity is guaranteed for a range of possible fault currents levels. The proposed methodology is successfully applied in a radial test system containing five overcurrent relays.

关键词： mixed-integer linear programming Feeder protection Overcurrent relay coordination

来源：评论

学校读者我要写书评

暂无评论

Modeling and solving mixed-model assembly line balancing problem with setups. Part I: A mixed integer linear programming model

引用

JOURNAL OF MANUFACTURING SYSTEMS 2014年第1期33卷 177-187页

作者： Akpinar, Sener Baykasoglu, Adil Dokuz Eylul Univ Fac Engn Dept Ind Engn Izmir Turkey

This paper is the first one of the two papers entitled "modeling and solving mixed-model assembly line balancing problem with setups", which has the aim of developing the mathematical programming formulation of the problem and solving it with a hybrid meta-heuristic approach. In this current part, a mixed-integer linear mathematical programming (MILP) model for mixed-model assembly line balancing problem with setups is developed. The proposed MILP model considers some particular features of the real world problems such as parallel workstations, zoning constraints, and sequence dependent setup times between tasks, which is an actual framework in assembly line balancing problems. The main endeavor of Part-I is to formulate the sequence dependent setup times between tasks in type-I mixed-model assembly line balancing problem. The proposed model considers the setups between the tasks of the same model and the setups because of the model switches in any workstation. The capability of our MILP is tested through a set of computational experiments. Part-II tackles the problem with a multiple colony hybrid bees algorithm. A set of computational experiments is also carried out for the proposed approach in Part-II.(C) 2013 The Society of Manufacturing Engineers. Published by Elsevier Ltd. All rights reserved.

关键词： mixed-model assembly line balancing mixed-integer linear programming Sequence dependent setup times Intra-station sequencing Zoning constraints Parallel workstations

来源：评论

学校读者我要写书评

暂无评论

Rigid Body Path Planning using mixed-integer linear programming

arXiv

引用

arXiv 2024年

作者： Yu, Mingxin Fan, Chuchu The Department of Aeronautics and Astronautics Massachusetts Institute of Technology CambridgeMA02139 United States

Navigating rigid body objects through crowded environments can be challenging, especially when narrow passages are presented. Existing sampling-based planners and optimization-based methods like mixed integer linear programming (MILP) formulations, suffer from limited scalability with respect to either the size of the workspace or the number of obstacles. In order to address the scalability issue, we propose a three-stage algorithm that first generates a graph of convex polytopes in the workspace free of collision, then poses a large set of small MILPs to generate viable paths between polytopes, and finally queries a pair of start and end configurations for a feasible path online. The graph of convex polytopes serves as a decomposition of the free workspace and the number of decision variables in each MILP is limited by restricting the subproblem within two or three free polytopes rather than the entire free region. Our simulation results demonstrate shorter online computation time compared to baseline methods and scales better with the size of the environment and tunnel width than sampling-based planners in both 2D and 3D environments. Copyright © 2024, The Authors. All rights reserved.

关键词： mixed-integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Hydro Unit Commitment via mixed integer linear programming: A Case Study of the Three Gorges Project, China

引用

IEEE TRANSACTIONS ON POWER SYSTEMS 2014年第3期29卷 1232-1241页

作者： Li, Xiang Li, Tiejian Wei, Jiahua Wang, Guangqian Yeh, William W. -G. Tsinghua Univ State Key Lab Hydrosci & Engn Beijing 100084 Peoples R China Univ Calif Los Angeles Dept Civil & Environm Engn Los Angeles CA 90095 USA

This paper develops a methodology for optimizing the hydro unit commitment (HUC) for the Three Gorges Project (TGP) in China. The TGP is the world's largest and most complex hydropower system in operation. The objective is to minimize the total operational cost. The decision variables are the startup or shutdown of each of the available units in the system and the power releases from the online units. The mathematical formulation must take into account the head variation over the operation periods as the net head changes from hour to hour and affects power generation. Additionally, the formulation must consider the operation of 32 heterogeneous generating units and the nonlinear power generation function of each unit. A three-dimensional interpolation technique is used to accurately represent the nonlinear power generation function of each individual unit, taking into account the time-varying head as well as the non-smooth limitations for power output and power release. With the aid of integer variables that represent the on/off and operation partition statuses of a unit, the developed HUC model for the TGP conforms to a standard mixed integer linear programming (MILP) formulation. We demonstrate the performance and utility of the model by analyzing the results from several scenarios for the TGP.

关键词： Hydro unit commitment hydropower mixed-integer linear programming Three Gorges Project (China)

来源：评论

学校读者我要写书评

暂无评论

Exact Verification of First-Order Methods via mixed-integer linear programming

arXiv

引用

arXiv 2024年

作者： Ranjan, Vinit Gualandi, Stefano Lodi, Andrea Stellato, Bartolomeo

We present exact mixed-integer programming linear formulations for verifying the performance of first-order methods for parametric quadratic optimization. We formulate the verification problem as a mixed-integer linear program where the objective is to maximize the infinity norm of the fixed-point residual after a given number of iterations. Our approach captures a wide range of gradient, projection, proximal iterations through affine or piecewise affine constraints. We derive tight polyhedral convex hull formulations of the constraints representing the algorithm iterations. To improve the scalability, we develop a custom bound tightening technique combining interval propagation, operator theory, and optimization-based bound tightening. Numerical examples, including linear and quadratic programs from network optimization and sparse coding using Lasso, show that our method provides several orders of magnitude reductions in the worst-case fixed-point residuals, closely matching the true worst-case performance. © 2024, CC BY.

关键词： mixed-integer linear programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：