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

Generation planning and operation under power stability constraints: A Hydro-Quebec use case

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Besner, Alexandre Massé, Alexandre Blondin Bani, Abderrahman Morabit, Mouad Berthaut, François Charest, Luc Ialongo, David Mbeutcha, Yves Couture-Gagnon, Simon Fournier, Julien VarennesQCJ3X 1S1 Canada Hydro-Quebec Operation and Planning Department MontrealQCH3A 3S7 Canada

Hydro-Quebec (HQ) is a vertically integrated utility that produces, transmits, and distributes most of the electricity in the province of Quebec. The power grid it operates has a particular architecture created by large hydroelectric dams located far north and the extensive 735kV transmission grid that allows the generated power to reach the majority of the load located thousands of kilometers away in the southern region of Quebec. The specificity of the grid has led HQ to develop monitoring tools responsible for generating so-called stability limits. Those stability limits take into account several nonlinear phenomena such as angular stability, frequency stability, or voltage stability. Since generation planning and operation tools rely mostly on mixed integer linear programming formulation, HQ had to adapt its tools to integrate stability limits into them. This paper presents the challenges it faced, especially considering its reserve monitoring tool and unit commitment tool. © 2024, CC BY-NC-SA.

关键词： mixed-integer linear programming

Event-based MILP models for ridepooling applications

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Gaul, Daniela Klamroth, Kathrin Stiglmayr, Michael School of Mathematics and Natural Sciences University of Wuppertal Wuppertal42119 Germany

Ridepooling services require efficient optimization algorithms to simultaneously plan routes and pool users in shared rides. We consider a static dial-a-ride problem (DARP) where a series of origin-destination requests have to be assigned to routes of a fleet of vehicles. Thereby, all requests have associated time windows for pick-up and delivery, and may be denied if they can not be serviced in reasonable time or at reasonable cost. Rather than using a spatial representation of the transportation network we suggest an event-based formulation of the problem, resulting in significantly improved computational times. While the corresponding MILP formulations require more variables than standard models, they have the advantage that capacity, pairing and precedence constraints are handled implicitly. The approach is tested and validated using a standard IP-solver on benchmark data from the literature. Moreover, the impact of, and the trade-off between, different optimization goals is evaluated on a case study in the city of Wuppertal (Germany). © 2021, CC BY.

关键词： mixed-integer linear programming

Predicting Lagrangian Multipliers for mixed integer linear Programs

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Demelas, Francesco Le Roux, Joseph Lacroix, Mathieu Parmentier, Axel Laboratoire d’Informatique de Paris-Nord Université Sorbonne Paris Nord CNRS France CERMICS École des Ponts France

Lagrangian Relaxation stands among the most efficient approaches for solving mixed integer linear Programs (MILPs) with difficult constraints. Given any duals for these constraints, called Lagrangian Multipliers (LMs), it returns a bound on the optimal value of the MILP, and Lagrangian methods seek the LMs giving the best such bound. But these methods generally rely on iterative algorithms resembling gradient descent to maximize the concave piecewise linear dual function: the computational burden grows quickly with the number of relaxed constraints. We introduce a deep learning approach that bypasses the descent, effectively amortizing per instance optimization. A probabilistic encoder based on a graph neural network computes, given a MILP instance and its Continuous Relaxation (CR) solution, high-dimensional representations of relaxed constraints, which are turned into LMs by a decoder. We train the encoder and the decoder jointly by directly optimizing the bound obtained from the predicted multipliers. Our method is applicable to any problem with a compact MILP formulation, and to any Lagrangian Relaxation providing a tighter bound than CR. Experiments on two widely known problems, Multi-Commodity Network Design and Generalized Assignment, show that our approach closes up to 85 % of the gap between the continuous relaxation and the best Lagrangian bound, and provides a high-quality warm-start for descent-based Lagrangian methods. © 2023, CC BY.

关键词： mixed-integer linear programming

Bias correction for quantile regression estimators

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Franguridi, Grigory Gafarov, Bulat Wüthrich, Kaspar University of Southern California United States Department of Agricultural and Resource Economics University of California Davis United States Department of Economics University of Michigan CESifo United States

We study the bias of classical quantile regression and instrumental variable quantile regression estimators. While being asymptotically first-order unbiased, these estimators can have non-negligible second-order biases. We derive a higher-order stochastic expansion of these estimators using empirical process theory. Based on this expansion, we derive an explicit formula for the second-order bias and propose a feasible bias correction procedure that uses finite-difference estimators of the bias components. The proposed bias correction method performs well in simulations. We provide an empirical illustration using Engel’s classical data on household food expenditure. Copyright © 2020, The Authors. All rights reserved.

关键词： mixed-integer linear programming

QoS-Aware and Routing-Flexible Network Slicing for Service-Oriented Networks

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Chen, Wei-Kun Liu, Ya-Feng Dai, Yu-Hong Luo, Zhi-Quan The School of Mathematics and Statistics Beijing Key Laboratory on MCAACI Beijing Institute of Technology Beijing100081 China The State Key Laboratory of Scientific and Engineering Computing Institute of Computational Mathematics and Scientific/Engineering Computing Academy of Mathematics and Systems Science Chinese Academy of Sciences Beijing100190 China The Shenzhen Research Institute of Big Data The Chinese University of Hong Kong Shenzhen518172 China

In this paper, we consider the network slicing (NS) problem which attempts to map multiple customized virtual network requests (also called services) to a common shared network infrastructure and manage network resources to meet diverse quality of service (QoS) requirements. We propose a mixed-integer nonlinear programming (MINLP) formulation for the considered NS problem that can flexibly route the traffic flow of the services on multiple paths and provide end-to-end delay and reliability guarantees for all services. To overcome the computational difficulty due to the intrinsic nonlinearity in the MINLP formulation, we transform the MINLP formulation into an equivalent mixed-integer linear programming (MILP) formulation and further show that their continuous relaxations are equivalent. In sharp contrast to the continuous relaxation of the MINLP formulation which is a nonconvex nonlinear programming problem, the continuous relaxation of the MILP formulation is a polynomial-time solvable linear programming problem, which significantly facilitates the algorithmic design. Based on the newly proposed MILP formulation, we develop a customized column generation (cCG) algorithm for solving the NS problem. The proposed cCG algorithm is a decomposition-based algorithm and is particularly suitable for solving large-scale NS problems. Numerical results demonstrate the efficacy of the proposed formulations and the proposed cCG algorithm. Copyright © 2024, The Authors. All rights reserved.

关键词： mixed-integer linear programming

Regular bipartite decompositions of pseudorandom graphs

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ferber, Asaf Frederickson, Bryce Mao, Dingjia Yepremyan, Liana Zhu, Yizhe Department of Mathematics University of California Irvine United States Department of Mathematics Emory University United States Department of Mathematics University of Southern California United States

In 1972, Kotzig proved that for every even n, the complete graph Kn can be decomposed into ⌈log2 n⌉ edge-disjoint regular bipartite spanning subgraphs, which is best possible. In this paper, we study regular bipartite decompositions of (n, d, λ)-graphs, where n is an even integer and d0 ≤ d ≤ n − 1 for some absolute constant d0. With a randomized algorithm, we prove that such an (n, d, λ)-graph with λ ≤ d/12 can be decomposed into at most log2 d + 36 regular bipartite spanning subgraphs. This is best possible up to the additive constant term. As a consequence, we also improve the best known bounds on λ = λ(d) by Ferber and Jain (2020) to guarantee that an (n, d, λ)-graph on an even number of vertices admits a 1-factorization, showing that λ ≤ cd is sufficient for some absolute constant c > *** Codes 05C80 (Primary) 05C48, 05C85 (Secondary) © 2024, CC BY.

关键词： mixed-integer linear programming

A CONVEXIFICATION-BASED OUTER-APPROXIMATION METHOD FOR CONVEX AND NONCONVEX MINLP

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Peng, Zedong Cao, Kaiyu Furman, Kevin C. Li, Can Grossmann, Ignacio E. Bernal Neira, David E. Davidson School of Chemical Engineering Purdue University 480 Stadium Mall Drive West LafayetteIN47907 United States ExxonMobil Upstream Research Co 22777 Springwoods Village Parkway SpringTX77389 United States Department of Chemical Engineering Carnegie Mellon University PittsburghPA15213 United States Research Institute for Advanced Computer Science Universities Space Research Association Mountain ViewCA United States NASA Ames Research Center Mountain ViewCA United States

The advancement of domain reduction techniques has significantly enhanced the performance of solvers in mathematical programming. This paper delves into the impact of integrating convexification and domain reduction techniques within the Outer- Approximation method. We propose a refined convexification-based Outer-Approximation method alongside a Branch-and-Bound method for both convex and nonconvex mixed-integer Nonlinear programming problems. These methods have been developed and incorporated into the open-source mixed-integer Nonlinear Decomposition Toolbox for Pyomo-MindtPy. Comprehensive benchmark tests were conducted, validating the effectiveness and reliability of our proposed algorithms. These tests highlight the improvements achieved by incorporating convexification and domain reduction techniques into the Outer-Approximation and Branch-and-Bound methods. © 2024, CC BY-NC-ND.

关键词： mixed-integer linear programming

Optimal mixed integer linear Optimization Trained Multivariate Classification Trees

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Alston, Brandon Hicks, Illya V. Computational Applied Mathematics and Operations Research Rice University HoustonTX77005 United States

Multivariate decision trees are powerful machine learning tools for classification and regression that attract many researchers and industry professionals. An optimal binary tree has two types of vertices, (i) branching vertices which have exactly two children and where datapoints are assessed on a set of discrete features and (ii) leaf vertices at which datapoints are given a prediction, and can be obtained by solving a biobjective optimization problem that seeks to (i) maximize the number of correctly classified datapoints and (ii) minimize the number of branching vertices. Branching vertices are linear combinations of training features and therefore can be thought of as hyperplanes. In this paper, we propose two cut-based mixed integer linear optimization (MILO) formulations for designing optimal binary classification trees (leaf vertices assign discrete classes). Our models leverage on-the-fly identification of minimal infeasible subsystems (MISs) from which we derive cutting planes that hold the form of packing constraints. We show theoretical improvements on the strongest flow-based MILO formulation currently in the literature and conduct experiments on publicly available datasets to show our models’ ability to scale, strength against traditional branch and bound approaches, and robustness in out-of-sample test performance. Our code and data are available on GitHub. © 2024, CC BY.

关键词： mixed-integer linear programming

Analytical Heterogeneous Die-to-Die 3D Placement with Macros

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Zhao, Yuxuan Liao, Peiyu Liu, Siting Jiang, Jiaxi Lin, Yibo Yu, Bei Department of Computer Science and Engineering The Chinese University of Hong Kong NT Hong Kong School of Integrated Circuits Peking University China Institute of Electronic Design Automation Peking University Wuxi China Beijing Advanced Innovation Center for Integrated Circuits Beijing China

This paper presents an innovative approach to 3D mixed-size placement in heterogeneous face-to-face (F2F) bonded 3D ICs. We propose an analytical framework that utilizes a dedicated density model and a bistratal wirelength model, effectively handling macros and standard cells in a 3D solution space. A novel 3D preconditioner is developed to resolve the topological and physical gap between macros and standard cells. Additionally, we propose a mixed-integer linear programming (MILP) formulation for macro rotation to optimize wirelength. Our framework is implemented with full-scale GPU acceleration, leveraging an adaptive 3D density accumulation algorithm and an incremental wirelength gradient algorithm. Experimental results on ICCAD 2023 contest benchmarks demonstrate that our framework can achieve 5.9% quality score improvement compared to the first-place winner with 4.0× runtime speedup. Additional experiments on modern RISC-V designs further validate the generalizability and superiority of our framework. © 2024, CC BY-NC-ND.

关键词： mixed-integer linear programming