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

Serial and Parallel Two-Column Probing for mixed-integer programming

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Dai, Yongzheng Chen, Chen ISE The Ohio State University ColumbusOH United States

Probing in mixed-integer programming (MIP) is a technique of temporarily fixing variables to discover implications that are useful to branch- and-cut solvers. Such fixing is typically performed one variable at a time—this paper develops instead a two-column probing scheme that instead fixes a pair of variables per iteration. Although the scheme involves more work per iteration compared to the one-column approach, stronger implied bounds as well as more conflicts identified may compensate. Indeed, our prototype implementation was awarded first prize at the MIP Workshop 2024 Computational Competition on novel presolving approaches. This paper presents the aforementioned (serial) prototype and additionally develops an efficient parallelization, leveraging hardware acceleration to further improve overall solve times. Compared to serial two-column probing, our parallel version sacrifices some strength per-pair probed in exchange for greatly increasing the total number of such probings;computational experiments demonstrate its *** Codes 90C10 © 2024, CC BY-NC-ND.

关键词： mixed-integer linear programming

Proximity results in convex mixed-integer programming

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Kocuk, Burak Morán, R. Diego A. Industrial Engineering Program Sabanci University Istanbul34956 Turkey Industrial and Systems Engineering Department Rensselaer Polytechnic Institute TroyNY12180-3590 United States

We study proximity (resp. integrality gap), that is, the distance (resp. difference) between the optimal solutions (resp. optimal values) of convex integer programs (IP) and the optimal solutions (resp. optimal values) of their continuous relaxations. We show that these values can be upper bounded in terms of the recession cone of the feasible region of the continuous relaxation when the recession cone is fulldimensional. If the recession cone is not full-dimensional we give sufficient conditions to obtain a finite integrality gap. We then specialize our analysis to second-order conic IPs. In the case the feasible region is defined by a single Lorentz cone constraint, we give upper bounds on proximity and integrality gap in terms of the data of the problem (the objective function vector, the matrix defining the conic constraint, the right-hand side, and the covering radius of a related lattice). We also give conditions for these bounds to be independent of the right-hand side, akin to the linear IP case. Finally, in the case the feasible region is defined by multiple Lorentz cone constraints, we show that, in general, we cannot give bounds that are independent of the corresponding right-hand side. Although our results are presented for the integer lattice Zn, the bounds can be easily adapted to work for any general lattice, including the usual mixed-integer lattice Zn1 × Rn2 , by considering the appropriate covering radius when needed. Copyright © 2024, The Authors. All rights reserved.

关键词： mixed-integer linear programming

BICERT: A BIlinear mixed integer programming FORMULATION FOR PRECISE CERTIFIED BOUNDS AGAINST DATA POISONING ATTACKS

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Lorenz, Tobias Kwiatkowska, Marta Fritz, Mario CISPA Helmholtz Center for Information Security Saarbrücken Germany Department of Computer Science University of Oxford Oxford United Kingdom

Data poisoning attacks pose one of the biggest threats to modern AI systems, necessitating robust defenses. While extensive efforts have been made to develop empirical defenses, attackers continue to evolve, creating sophisticated methods to circumvent these measures. To address this, we must move beyond empirical defenses and establish provable certification methods that guarantee robustness. This paper introduces a novel certification approach, BiCert, using Bilinear mixed integer programming (BMIP) to compute sound deterministic bounds that provide such provable robustness. Using BMIP, we compute the reachable set of parameters that could result from training with potentially manipulated data. A key element to make this computation feasible is to relax the reachable parameter set to a convex set between training iterations. At test time, this parameter set allows us to predict all possible outcomes, guaranteeing robustness. BiCert is more precise than previous methods, which rely solely on interval and polyhedral bounds. Crucially, our approach overcomes the fundamental limitation of prior approaches where parameter bounds could only grow, often uncontrollably. We show that BiCert’s tighter bounds eliminate a key source of divergence issues, resulting in more stable training and higher certified accuracy. Copyright © 2024, The Authors. All rights reserved.

关键词： mixed-integer linear programming

UniAP: Unifying Inter- and Intra-Layer Automatic Parallelism by mixed integer Quadratic programming

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Lin, Hao Wu, Ke Li, Jie Li, Jun Li, Wu-Jun National Key Laboratory for Novel Software Technology School of Computer Science Nanjing University Nanjing210023 China

Distributed learning is commonly used for training deep learning models, especially large models. In distributed learning, manual parallelism (MP) methods demand considerable human effort and have limited flexibility. Hence, automatic parallelism (AP) methods have recently been proposed for automating the parallel strategy optimization process. Existing AP methods suffer from sub-optimal solutions because they do not jointly optimize the two categories of parallel strategies (i.e., inter-layer parallelism and intra-layer parallelism). In this paper, we propose a novel AP method called UniAP, which unifies inter- and intra-layer automatic parallelism by mixed integer quadratic programming. To the best of our knowledge, UniAP is the first parallel method that can jointly optimize the two categories of parallel strategies to find an optimal solution. Experimental results show that UniAP outperforms state-of-the-art methods by up to 3.80× in throughput and reduces strategy optimization time by up to 107× across five Transformer-based models. Copyright © 2023, The Authors. All rights reserved.

关键词： mixed-integer linear programming

Change-Point Detection in Time Series Using mixed integer programming

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Prokhorov, Artem Radchenko, Peter Semenov, Alexander Skrobotov, Anton University of Sydney Business School Australia University of Florida United States Russian Presidential Academy of National Economy and Public Administration Russia St. Petersburg State University Russia University of Montreal Canada

We use cutting-edge mixed integer optimization (MIO) methods to develop a framework for detection and estimation of structural breaks in time series regression models. The framework is constructed based on the least squares problem subject to a penalty on the number of breakpoints. We restate the l0-penalized regression problem as a quadratic programming problem with integer- and real-valued arguments and show that MIO is capable of finding provably optimal solutions using a well-known optimization solver. Compared to the popular l1-penalized regression (LASSO) and other classical methods, the MIO framework permits simultaneous estimation of the number and location of structural breaks as well as regression coefficients, while accommodating the option of specifying a given or minimal number of breaks. We derive the asymptotic properties of the estimator and demonstrate its effectiveness through extensive numerical experiments, confirming a more accurate estimation of multiple breaks as compared to popular non-MIO alternatives. Two empirical examples demonstrate usefulness of the framework in applications from business and economic statistics. © 2024, CC BY-NC-ND.

关键词： mixed-integer linear programming

Designing an optimized fueling infrastructure for a hydrogen railway system

学校读者我要写书评

暂无评论

Journal of Rail Transport Planning & Management 2025年 35卷

作者： Alessio Trivella Amina Balha Daniela Guericke Industrial Engineering and Business Information Systems University of Twente Hallenweg 17 7522 NH Enschede Netherlands

Hydrogen use is increasing in transportation, including within the railway sector. In collaboration with a governmental institution in the Netherlands, we study how to design an efficient hydrogen fueling infrastructure for a railway system. The problem involves selecting yards in a network for hydrogen fueling, assigning trains to these yards, locating hydrogen storage and fueling stations, and connecting them via pipelines. This key planning phase must avoid oversizing costly fueling infrastructure while accounting for track availability at yards and costs due to fueling operations. We formulate this novel problem, which has the structure of a nested facility location problem, as a mixed-integer linear program to minimize total annualized investment and operational costs. Due to the complexity of real-sized instances, we propose a matheuristic that estimates the infrastructural costs for each yard and train assignment by combining a constructive algorithm with a set covering model. It then solves a single-stage facility location problem to select yards and assign trains, followed by a yard-level improvement phase. Numerical experiments on a real Dutch case show that our approach delivers high-quality solutions quickly and offer insights into the optimal infrastructure design depending on the discretization of yard areas, number of trains, and other parameters.

关键词： Railway systems Hydrogen trains Fueling infrastructure Facility location problem mixed-integer linear programming Matheuristic

A Model Predictive Control for Microgrids Considering Battery Aging

学校读者我要写书评

暂无评论

Journal of Modern Power Systems and Clean Energy 2020年第2期8卷 296-304页

作者： Ugur Can Yilmaz Mustafa Erdem Sezgin Murat Gol Department of Electrical and Electronics Engineering Middle East Technical UniversityAnkaraTurkey

The increasing number of distributed energy resources(DERs),advancing communication and computation technologies,and reliability concerns of the customers have caused an intense interest in the concept of *** DERs are the biggest motivation of the microgrids due to their intermittent generation characteristics,they constitute a risk for system *** storage systems(BSSs)stand as one of the most effective solutions for this reliability ***,the inappropriate use of BSS creates other operational problems in power *** order to deal with these concerns explicitly in microgrids,an optimized microgrid central controller(MGCC)is the key factor,which controls the realtime operation of a *** work proposes a model predictive control(MPC)based MGCC that will provide optimal control of the microgrid,considering economic and operational *** proposed system will minimize the energy cost of the microgrid by utilizing mixed-integer linear programming(MILP)assuming the presence of DERs and BSS as well as the bi-directional grid ***,the aging effect of BSS will be considered in the proposed optimization problem which will provide an up-to-date system *** proposed method is evaluated using real load and photovoltaic(PV)generation data.

关键词： Microgrid optimization battery storage model predictive control mixed-integer linear programming

A new inventory routing problem with route and schedule unpredictability

学校读者我要写书评

暂无评论

Applied Mathematical Modelling 2025年 147卷

作者： Marlize H. Visser Jan H. van Vuuren Stellenbosch Unit for Operations Research in Engineering Department of Industrial Engineering Stellenbosch University Private Bag XI Matieland 7602 South Africa

The inventory routing problem (IRP) in a retail supply chain setting allows for the simultaneous optimisation of delivery schedules, vehicle routes, and delivery quantities. The IRP relies on the adoption of a vendor-managed inventory strategy which has the potential to reduce transportation, inventory, and stock-out costs in a supply chain. In this paper, we introduce a mathematical model for a new IRP variant, the heterogeneous fixed fleet IRP with time-windows (HeFIRPTW) with route and schedule unpredictability, in the form of a bi-objective mixed-integer linear programming problem. This model simultaneously incorporates route and schedule unpredictability aimed at mitigating inherent safety and security threats experienced during the transportation of valuable goods. Delivery routes and schedules are generated that minimise the operational costs incurred whilst also ensuring that route segments are not traversed too regularly and that customers are not visited during overlapping daily time intervals. The feasibility of adopting an exact ϵ -constrained model solution method is investigated empirically by solving small, adapted benchmark instances of the problem. An investigation into the model solution complexity for varying problem sizes reveals that unpredictability, particularly with tightened constraints, increases the computational time. The complexity implications of multiple vehicles and the imposition of time-windows are also examined. The results highlight the computational demands of the proposed model, demonstrating a clear need for a faster, perhaps approximate, solution approach capable of generating high-quality solutions for realistic problem instances within reasonable time-frames.

关键词： Inventory routing problem mixed-integer linear programming Multi-objective optimisation Route unpredictability Schedule unpredictability

A linear AC-OPF Formulation for Unbalanced Distribution Networks

学校读者我要写书评

暂无评论

IEEE TRANSACTIONS ON INDUSTRY APPLICATIONS 2021年第5期57卷 4462-4472页

作者： Giraldo, Juan S. Vergara, Pedro P. Lopez, Juan Camilo Nguyen, Phuong Hong Pateralds, Nikolaos G. Univ Twente EEMCS Fac Math Operat Res Grp NL-7522 NB Enschede Netherlands Delft Univ Technol Intelligent Elect Power Grids Grp NL-2628 CD Delft Netherlands Univ Estadual Campinas Sch Elect & Comp Engn BR-13083970 Campinas Brazil Eindhoven Univ Technol Energy Syst Grp NL-5612 AP Eindhoven Netherlands

linear optimal power flow (OPF) formulations are powerful tools applied to a large number of problems in power systems, e.g., economic dispatch, expansion planning, state estimation, congestion management, electricity markets, among others. This article proposes a novel mixed-integer linear programming formulation for the ac-OPF of three-phase unbalanced distribution networks. The model aims to minimize the total energy production cost while guaranteeing the network's voltage and current magnitude operational limits. New approximations of the Euclidean norm, which is present in the calculation of nodal voltage and branch current magnitudes, are introduced by applying a linear transformation of weighted norms and a set of intersecting planes. The accuracy, optimality, feasibility, and scalability of the proposed linearizations are compared with common linear approximations in the literature using two unbalanced distribution test systems. The obtained results show that the proposed formulation is computationally more efficient (almost twice) while being as accurate and more conservative than the benchmarked approaches with maximum errors lower than 0.1%. Thus, its potential application in a variety of distribution systems operation and planning optimization problems is endorsed.

关键词： Substations programming Computational modeling Scalability Reactive power Distribution networks Admittance Ac optimal power flow Euclidean norm approximation mixed-integer linear programming unbalanced distribution networks