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

A mixed-integer Conic Program for the Moving-Target Traveling Salesman Problem based on a Graph of Convex Sets

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Philip, Allen George Ren, Zhongqiang Rathinam, Sivakumar Choset, Howie Department of Mechanical Engineering Texas A&M University College StationTX77843-3123 United States Shanghai Jiao Tong University 800 Dongchuan Road Shanghai China Carnegie Mellon University 5000 Forbes Ave. PittsburghPA15213 United States

This paper introduces a new formulation that finds the optimum for the Moving-Target Traveling Salesman Problem (MT-TSP), which seeks to find a shortest path for an agent, that starts at a depot, visits a set of moving targets exactly once within their assigned time-windows, and returns to the depot. The formulation relies on the key idea that when the targets move along lines, their trajectories become convex sets within the space-time coordinate system. The problem then reduces to finding the shortest path within a graph of convex sets, subject to some speed constraints. We compare our formulation with the current state-of-the-art mixed integer Conic Program (MICP) formulation for the MT-TSP. The experimental results show that our formulation outperforms the MICP for instances with up to 20 targets, with up to two orders of magnitude reduction in runtime, and up to a 60% tighter optimality gap. We also show that the solution cost from the convex relaxation of our formulation provides significantly tighter lower-bounds for the MT-TSP than the ones from the MICP. Copyright © 2024, The Authors. All rights reserved.

关键词： mixed-integer linear programming

Reachability analysis for piecewise affine systems with neural network-based controllers

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Teichrib, Dieter Darup, Moritz Schulze The Control and Cyber-physical Systems Group Faculty of Mechanical Engineering TU Dortmund University Germany

Neural networks (NN) have been successfully applied to approximate various types of complex control laws, resulting in low-complexity NN-based controllers that are fast to evaluate. However, when approximating control laws using NN, performance and stability guarantees of the original controller may not be preserved. Recently, it has been shown that it is possible to provide such guarantees for linear systems with NN-based controllers by analyzing the approximation error with respect to a stabilizing base-line controller or by computing reachable sets of the closed-loop system. The latter has the advantage of not requiring a base-line controller. In this paper, we show that similar ideas can be used to analyze the closed-loop behavior of piecewise affine (PWA) systems with an NN-based controller. Our approach builds on computing over-approximations of reachable sets using mixed-integer linear programming, which allows to certify that the closed-loop system converges to a small set containing the origin while satisfying input and state constraints. We also show how to modify a given NN-based controller to ensure asymptotic stability for the controlled PWA system. © 2024, CC BY-NC-ND.

关键词： mixed-integer linear programming

RETHINKING THE CAPACITY OF GRAPH NEURAL NETWORKS FOR BRANCHING STRATEGY

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Chen, Ziang Liu, Jialin Chen, Xiaohan Wang, Xinshang Yin, Wotao Department of Mathematics Massachusetts Institute of Technology CambridgeMA02139 United States Department of Statistics and Data Science University of Central Florida OrlandoFL32816 United States Decision Intelligence Lab Damo Academy Alibaba US BellevueWA98004 United States

Graph neural networks (GNNs) have been widely used to predict properties and heuristics of mixed-integer linear programs (MILPs) and hence accelerate MILP solvers. This paper investigates the capacity of GNNs to represent strong branching (SB), the most effective yet computationally expensive heuristic employed in the branch-and-bound algorithm. In the literature, message-passing GNN (MP-GNN), as the simplest GNN structure, is frequently used as a fast approximation of SB and we find that not all MILPs’s SB can be represented with MP-GNN. We precisely define a class of "MP-tractable" MILPs for which MP-GNNs can accurately approximate SB scores. Particularly, we establish a universal approximation theorem: for any data distribution over the MP-tractable class, there always exists an MP-GNN that can approximate the SB score with arbitrarily high accuracy and arbitrarily high probability, which lays a theoretical foundation of the existing works on imitating SB with MP-GNN. For MILPs without the MP-tractability, unfortunately, a similar result is impossible, which can be illustrated by two MILP instances with different SB scores that cannot be distinguished by any MP-GNN, regardless of the number of parameters. Recognizing this, we explore another GNN structure called the second-order folklore GNN (2-FGNN) that overcomes this limitation, and the aforementioned universal approximation theorem can be extended to the entire MILP space using 2-FGNN, regardless of the MP-tractability. A small-scale numerical experiment is conducted to directly validate our theoretical findings. Copyright © 2024, The Authors. All rights reserved.

关键词： mixed-integer linear programming

Cut Selection in MILP based on Supervised Learning

学校读者我要写书评

暂无评论

Procedia Computer Science 2023年 221卷 1408-1415页

作者： ShengChao Wang Sheng-Jie Chen Liang Chen

With the increasing popularity of deep learning techniques, there has been a growing interest in combining learning methods with mixed-integer linear programming (MILP) solving processes. A promising approach is to incorporate the learning model as a module in traditional methods. Cut selection is a fundamental subroutine in modern MILP solvers used to select a subset of generated cuts and enhance solver performance. In this work, we present a supervised learning framework to improve the effectiveness of cut selection. Cut selection scoring rules are typically weighted sums of different metrics, and we have developed weighted cut selection metrics based on Machine Learning (ML) techniques for different problems. We propose a novel Neural Network (NN) architecture that incorporates a Graph Convolutional Neural Network (GCN) with a self-attention mechanism to determine appropriate weights. The resulting model serves as a component of the solver and is evaluated through controlled experiments on real-world MILPs. The numerical results demonstrate that our approach outperforms the standard SCIP cut selection strategy, especially on datasets containing the same class of problems.

关键词： mixed-integer linear programming cutting plane cut selection supervised learning

The value of electricity storage arbitrage on day-ahead markets across Europe

学校读者我要写书评

暂无评论

ENERGY ECONOMICS 2023年第1期123卷

作者： Mercier, Thomas Olivier, Mathieu De Jaeger, Emmanuel Catholic Univ Louvain Mechatron Elect Energy & Dynam Syst B-1348 Louvain La Neuve Belgium Univ Laval Dept Mech Engn Quebec City PQ G1V 0A6 Canada

This paper investigates the historical value of electricity storage from the perspective of the storage owner in day-ahead markets (DAM) across Europe. A technology-neutral formulation is used, where the storage is modelled based on its round-trip efficiency and storage duration. A mixed-integer linear program (MILP) is built to compute the perfect-foresight value of a price-taker storage from arbitrage, using historical hourly DAM prices in all the bidding zones of the EU-28 countries, Norway, Switzerland, and Turkey. Depending on the bidding zones, the DAM price data starts between 2000 and 2017, and spans to 2021. The model is solved for varying round-trip efficiencies (50% to 100%) and storage durations (1 to 10 h) for every bidding zone and every year in the dataset. The results reveal significant variations in storage value from arbitrage, both geographically and temporally, with round-trip efficiency having a major impact on arbitrage value and storage duration having very low marginal value beyond 4 to 6 h. Additionally, the paper investigates the impact of variable grid fees on arbitrage value, using the case of Belgium, where fees depend on storage system size. The initial MILP is therefore augmented to account for the complex dependencies between storage size and the resulting grid fees. The augmented MILP shows that grid fees can decrease storage arbitrage value by 20% to 50%, and that they can also dramatically decrease storage participation in DAMs.

关键词： Energy storage Arbitrage Day-ahead market mixed-integer linear programming Grid fees

Power minimization and resource allocation in HetNets with uncertain channel-gains

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ferreira, Gabriel O. Ravazzi, Chiara Dabbene, Fabrizio Calafiore, Giuseppe C. IEIIT CNR Institute Torino Italy DET Politecnico di Torino Italy CECS VinUniversity Viet Nam

We propose an optimization problem to minimize the base stations transmission powers in OFDMA heterogeneous networks, while respecting users' individual throughput demands. The decision variables are the users' working bandwidths, their association, and the base stations transmission powers. To deal with wireless channel uncertainty, the channel gains are treated as random variables respecting a log-normal distribution, leading to a non-convex chance constrained mixed-integer optimization problem, which is then formulated as a mixed-integer Robust Geometric Program. The efficacy of the proposed method is shown in a real-world scenario of a large European city. © 2024, CC BY.

关键词： mixed-integer linear programming

Fair Least Core: Efficient, Stable and Unique Game-Theoretic Reward Allocation in Energy Communities by Row-Generation

学校读者我要写书评

暂无评论

IEEE Transactions on Energy Markets, Policy and Regulation

IEEE Transactions on Energy Markets, Policy and Regulation 2024年第2期3卷 170-181页

作者： Fioriti, Davide Bigi, Giancarlo Frangioni, Antonio Passacantando, Mauro Poli, Davide University of Pisa Department of Energy Systems Territory and Construction Engineering PI Pisa56122 Italy University of Pisa Dipartimento di Informatica PI Pisa56127 Italy University of Milano-Bicocca Department of Business and Law MI Milan20126 Italy

Energy Communities are increasingly proposed as a tool to boost renewable penetration and maximize citizen participation in energy matters. These policies enable the formation of legal entities that bring together power system members, enabling collective investment and operation of energy assets. However, designing appropriate reward schemes is crucial to fairly foster individuals to join, as well to ensure collaborative and stable aggregation, maximizing community benefits. Cooperative Game Theory, emphasizing coordination among members, has been extensively proposed for ECs and microgrids;however, it is still perceived as obscure and difficult to compute due to its exponential computational requirements. This study proposes a novel framework for stable fair benefit allocation, named Fair Least Core, that provides uniqueness, reproducibility, stability and fairness. A novel row-generation algorithm is also proposed that allows to efficiently compute the imputations for coalitions of practical size. A case study of ECs with up to 100 members shows the stability, reproducibility, fairness and efficiency properties of proposed model. The results also highlight how the market power of individual users changes as the community grows larger, which can steer the development of practical reliable, robust and fair reward allocations for energy system applications © 2023 IEEE.

关键词： mixed-integer linear programming

Upgrading edges in the Maximal Covering Location Problem

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Baldomero-Naranjo, Marta Kalcsics, Jörg Marín, Alfredo Rodríguez-Chía, Antonio M. 11510 Spain School of Mathematics University of Edinburgh EdinburghEH9 3FD United Kingdom Departamento de Estadística e Investigación Operativa Universidad de Murcia Facultad de Matemáticas Murcia30100 Spain

We study the upgrading version of the maximal covering location problem with edge length modifications on networks. This problem aims at locating p facilities on the vertices (of the network) so as to maximise coverage, considering that the length of the edges can be reduced at a cost, subject to a given budget. Hence, we have to decide on: the optimal location of p facilities and the optimal edge length reductions. This problem is NP-hard on general graphs. To solve it, we propose three different mixed-integer formulations and a preprocessing phase for fixing variables and removing some of the constraints. Moreover, we strengthen the proposed formulations including valid inequalities. Finally, we compare the three formulations and their corresponding improvements by testing their performance over different datasets. © 2024, CC BY-NC-ND.

关键词： mixed-integer linear programming

Improving Community-Participated Patrol for Anti-Poaching

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Wu, Yufei Xu, Yixuan Even Zhang, Xuming Liu, Duo Zhu, Shibing Fang, Fei Shanghai Jiao Tong University China Carnegie Mellon University United States World Wide Fund For Nature China Heilongjiang Academy of Sciences China

Community engagement plays a critical role in anti-poaching efforts, yet existing mathematical models aimed at enhancing this engagement often overlook direct participation by community members as alternative patrollers. Unlike professional rangers, community members typically lack flexibility and experience, resulting in new challenges in optimizing patrol resource allocation. To address this gap, we propose a novel game-theoretic model for community-participated patrol, where a conservation agency strategically deploys both professional rangers and community members to safeguard wildlife against a best-responding poacher. In addition to a mixed-integer linear program formulation, we introduce a Two-Dimensional Binary Search algorithm and a novel Hybrid Waterfilling algorithm to efficiently solve the game in polynomial time. Through extensive experiments and a detailed case study focused on a protected tiger habitat in Northeast China, we demonstrate the effectiveness of our algorithms and the practical applicability of our model. Copyright © 2024, The Authors. All rights reserved.

关键词： mixed-integer linear programming