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

LinA: a faster approach to piecewise linear approximations using corridors and its application to mixed-integer optimization

引用

MATHEMATICAL PROGRAMMING COMPUTATION 2025年第2期17卷 265-306页

作者： Codsi, Julien Ngueveu, Sandra Ulrich Gendron, Bernard Univ Montreal Dept Informat & Rech Operat Montreal PQ Canada Princeton Univ Princeton NJ 08544 USA Univ Toulouse LAAS CNRS CNRS INP Toulouse France Univ Montreal CIRRELT Montreal PQ Canada

In this paper, we address the problem of approximating and over/under-estimating univariate functions with piecewise linear (PWL) functions with the minimum number of linear segments given a bound on the allowed pointwise approximation error. Through a new geometric approach and building on the work of Ngueveu (Eur J Oper Res 275:1058-1071, 2019), we develop new algorithms that can solve the problem in quasi-logarithmic time on a very broad class of error types. Such algorithms find many applications, mostly related to solving certain classes of (mixed-integer) nonlinear and nonconvex programming (MINLP) problems by mixed-integer linear programming (MILP) techniques. An efficient implementation of our algorithms is available as a Julia package. Benchmarks are also provided to showcase how our method outperforms the state-of-the-art for this problem. Finally, we show how our algorithms can be used to efficiently solve certain classes of MINLP problems through a case study on multicommodity network design problems with congestion.

关键词： piecewise linear functions Approximation Overestimation Underestimation Guaranteed tolerance piecewise linear regression with bounded error MINLP MILP Julia package

来源：评论

学校读者我要写书评

暂无评论

A TROPICAL ANALOGUE OF THE LEMMA ON THE LOGARITHMIC DERIVATIVE

引用

BULLETIN OF THE AUSTRALIAN MATHEMATICAL SOCIETY 2024年第2期110卷 303-312页

作者： Halonen, Juho Univ Eastern Finland Dept Phys & Math POB 111 FI-80101 Joensuu Finland

The tropical analogue of the lemma on the logarithmic derivative is generalised for noncontinuous tropical meromorphic functions, that is, piecewise linear functions that may have discontinuities. In addition, two Borel type results are generalised for piecewise continuous functions. With the generalisation of the tropical analogue of the lemma on the logarithmic derivative, several tropical analogues of Clunie and Mohon'ko type results are also automatically generalised for noncontinuous tropical meromorphic functions.

关键词： tropical Nevanlinna theory tropical meromorphic functions piecewise linear functions lemma on the logarithmic derivative

来源：评论

学校读者我要写书评

暂无评论

On the Upper Bounds of Number of linear Regions and Generalization Error of Deep Convolutional Neural Networks

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2025年第6期47卷 5014-5022页

作者： Chen, Degang Liu, Jiayu Che, Xiaoya North China Elect Power Univ Sch Math & Phys Beijing 102206 Peoples R China North China Elect Power Univ Hebei Key Lab Phys & Energy Technol Baoding 071000 Peoples R China

Understanding the effect of hyperparameters of the network structure on the performance of Convolutional Neural Networks (CNNs) remains the most fundamental and urgent issue in deep learning, and we attempt to address this issue based on the piecewise linear (PWL) function nature of CNNs in this paper. Firstly, the operations of convolutions, ReLUs and Max pooling in a CNN are represented as the multiplication of multiple matrices for a fixed sample in order to obtain an algebraic expression of CNNs, this expression clearly suggests that CNNs are PWL functions. Although such representation has high time complexity, it provides a more convenient and intuitive way to study the mathematical properties of CNNs. Secondly, we develop a tight bound of the number of linear regions and the upper bounds of generalization error for CNNs, both taking into account factors such as the number of layers, dimension of pooling, and the width in the network. The above research results provide a possible guidance for designing and training CNNs.

关键词： Upper bound Vectors Training Complexity theory Power systems Physics Lower bound Convolutional neural networks Symbols Measurement uncertainty Convolutional neural network generalization error bound linear region piecewise linear functions

来源：评论

学校读者我要写书评

暂无评论

Augmented Sparsifiers for Generalized Hypergraph Cuts

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2023年第1期24卷 1-50页

作者： Veldt, Nate Benson, Austin R. Kleinberg, Jon Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA Cornell Univ Dept Comp Sci Ithaca NY USA

Hypergraph generalizations of many graph cut problems and algorithms have recently been introduced to better model data and systems characterized by multiway relationships. Recent work in machine learning and theoretical computer science uses a generalized cut function for a hypergraph H = (V, epsilon) that associates each hyperedge e is an element of epsilon with a splitting function w(e), which assigns a penalty to each way of separating the nodes of e. When each w(e) satisfies w(e)(S) = g(|S|) for some concave function g, previous work has shown how to reduce the generalized hypergraph cut problem to a directed graph cut problem, although the resulting graph may be very dense. We introduce a framework for sparsifying hypergraph-to-graph reductions, where the hypergraph cut function is (1+ epsilon)-approximated by a cut on a directed graph. For epsilon > 0 we need at most O(epsilon(-1)|e| log |e|) edges to reduce any hyperedge e, while only O(|e|epsilon(-1/2) log log 1/epsilon ) edges are needed to approximate the clique expansion, a widely used heuristic in hypergraph clustering. Our framework leads to im-proved results for solving cut problems in co-occurrence graphs, decomposable submodular function minimization problems, and localized hypergraph clustering problems.

关键词： hypergraphs sparsification decomposable submodular function minimiza tion piecewise linear functions concave function approximation co-occurrence graphs

来源：评论

学校读者我要写书评

暂无评论

Accuracy study of linearization methods for quadratic cost curves of thermal units in unit commitment problems

引用

IET GENERATION TRANSMISSION & DISTRIBUTION 2022年第11期16卷 2198-2207页

作者： Dong, Jizhe Li, Yuanhan Lu, Yu Han, Shunjie Changchun Univ Technol Sch Elect & Elect Engn Changchun Peoples R China State Grid Jilin Elect Power Co Ltd Changchun Peoples R China

To solve the unit commitment (UC) problems with efficient mixed-integer linear programming solvers, the quadratic cost functions (QCFs) of thermal units are always approximated to piecewise linear (PWL) functions. This study examines the accuracies of different approximation methods for piecewise linearizing the QCFs of units in UC problems. We use five piecewise linearization methods-evenly spaced PWL interpolation, evenly spaced PWL tangent, evenly spaced PWL-e(max)/2 shifted interpolation, tighter PWL interpolation, and evenly spaced PWL least-squares fit-to approximate the QCFs of units. The authors first perform a series of reproductivity studies to verify the program. Then, numerical tests are conducted using different methods on the systems with 10, 100, and 800 units. The results show that different approximation methods lead to considerable differences in operating costs and the tighter PWL interpolation, compared with the other methods, is preferred in terms of approximation accuracy.

关键词： piecewise linearization methods unit commitment problems evenly spaced PWL tangent reproductivity studies power generation dispatch UC problems integer programming linear programming approximation methods QCFs numerical tests approximation accuracy piecewise linear techniques interpolation approximation theory mixed-integer linear programming solvers piecewise linear functions thermal power stations thermal units -2 shifted interpolation quadratic cost curves PWL least-squares power generation scheduling tighter PWL interpolation quadratic cost functions evenly spaced PWL-ɛ

来源：评论

学校读者我要写书评

暂无评论

Estimation of cost efficiency with piecewise linear cost function in integer-valued data envelopment analysis

引用

MATHEMATICAL SCIENCES 2022年第1期16卷 1-11页

作者： Mirzaeian, Fatemeh Fallahnejad, Reza Islamic Azad Univ Dept Math Khorramabad Branch Khorramabad Iran

The cost efficiency is one of the types of the used efficiency concepts in the data envelopment analysis (DEA). In the literature of the cost efficiency, the prices are often applied to the units in a fixed and linear form, while in some cases, as the subjects of the savings and observance of the consumption patterns, the prices are usually considered in terms of stepwise (piecewise linear) and not fixed (linear). This paper proposes the new models to evaluate of the cost efficiency in the fully competitive setting by using the costs in a piecewise linear form. The models are developed for the non-fully competitive and integer-valued inputs cases. Finally, the proposed models are used to determine the cost efficiency of the confectioneries in Islam Abad Gharb city from Iran country in the case study.

关键词： Data envelopment analysis piecewise linear functions Cost efficiency Mixed integer programming

来源：评论

学校读者我要写书评

暂无评论

piecewise linear Valued CSPs Solvable by linear Programming Relaxation

引用

ACM TRANSACTIONS ON COMPUTATIONAL LOGIC 2022年第1期23卷 1-35页

作者： Bodirsky, Manuel Mamino, Marcello Viola, Caterina Tech Univ Dresden Inst Algebra D-01062 Dresden Germany Univ Pisa Dipartimento Matemat I-56127 Pisa Italy Univ Oxford Dept Comp Sci Oxford OX1 3QD England

Valued constraint satisfaction problems (VCSPs) are a large class of combinatorial optimisation problems. The computational complexity of VCSPs depends on the set of allowed cost functions in the input. Recently, the computational complexity of all VCSPs for finite sets of cost functions over finite domains has been classified. Many natural optimisation problems, however, cannot be formulated as VCSPs over a finite domain. We initiate the systematic investigation of the complexity of infinite-domain VCSPs with piecewise linear homogeneous cost functions. Such VCSPs can be solved in polynomial time if the cost functions are improved by fully symmetric fractional operations of all arities. We showthis by reducing the problem to a finite-domain VCSP which can be solved using the basic linear program relaxation. It follows that VCSPs for submodular PLH cost functions can be solved in polynomial time;in fact, we show that submodular PLH functions form a maximally tractable class of PLH cost functions.

关键词： Valued constraint satisfaction rational domain linear programming relaxation piecewise linear functions submodularity

来源：评论

学校读者我要写书评

暂无评论

Vehicle routing with time-dependent travel times: Theory, practice, and benchmarks

引用

DISCRETE OPTIMIZATION 2024年 53卷

作者： Blauth, Jannis Held, Stephan Mueller, Dirk Schlomberg, Niklas Traub, Vera Trobst, Thorben Vygen, Jens Univ Bonn Res Inst Discrete Math Bonn Germany Univ Bonn Hausdorff Ctr Math Bonn Germany Univ Calif Irvine Irvine CA USA

We develop theoretical foundations and practical algorithms for vehicle routing with time- dependent travel times. We also provide new benchmark instances and experimental results. First, we study basic operations on piecewise linear arrival time functions. In particular, we devise a faster algorithm to compute the pointwise minimum of a set of piecewise linear functions and a monotonicity-preserving variant of the Imai-Iri algorithm to approximate an arrival time function with fewer breakpoints. Next, we show how to evaluate insertion and deletion operations in tours efficiently and update the underlying data structure faster than previously known when a tour changes. Evaluating a tour also requires a scheduling step which is non-trivial in the presence of time windows and time-dependent travel times. We show how to perform this in linear time. Based on these results, we develop a local search heuristic to solve real-world vehicle routing problems with various constraints efficiently and report experimental results on classical benchmarks. Since most of these do not have time-dependent travel times, we generate and publish new benchmark instances that are based on real-world data. This data also demonstrates the importance of considering time-dependent travel times in instances with tight time windows.

关键词： Vehicle routing Time-dependent travel times piecewise linear functions Data structures

来源：评论

学校读者我要写书评

暂无评论

Augmented sparsifiers for generalized hypergraph cuts

The Journal of Machine Learning Research

引用

The Journal of Machine Learning Research 2023年第1期24卷 9901-9950页

作者： Nate Veldt Austin R. Benson Jon Kleinberg Department of Computer Science and Engineering Texas A&M University College Station TX Department of Computer Science Cornell University Ithaca NY

Hypergraph generalizations of many graph cut problems and algorithms have recently been introduced to better model data and systems characterized by multiway relationships. Recent work in machine learning and theoretical computer science uses a generalized cut function for a hypergraph ℌ = (V, ℇ) that associates each hyperedge e ∈ ℇ with a splitting function we, which assigns a penalty to each way of separating the nodes of e. When each we satisfies we(S) = g(|S|) for some concave function g, previous work has shown how to reduce the generalized hypergraph cut problem to a directed graph cut problem, although the resulting graph may be very dense. We introduce a framework for sparsifying hypergraph-to-graph reductions, where the hypergraph cut function is (1+ε)-approximated by a cut on a directed graph. For ε > 0 we need at most O(ε-1|e| log |e|) edges to reduce any hyperedge e, while only O(|e|ε-1/2 log log 1/ε ) edges are needed to approximate the clique expansion, a widely used heuristic in hypergraph clustering. Our framework leads to improved results for solving cut problems in co-occurrence graphs, decomposable submodular function minimization problems, and localized hypergraph clustering problems.

关键词： hypergraphs sparsification decomposable submodular function minimization piecewise linear functions concave function approximation co-occurrence graphs

来源：评论

学校读者我要写书评

暂无评论

A Spike-based Cellular-Neural Network Architecture for Spatiotemporal filtering 55

A Spike-based Cellular-Neural Network Architecture for Spati...

引用

55th Annual Conference on Information Sciences and Systems (CISS)

作者： Sengupta, Jonah P. Villemur, Martin Andreou, Andreas G. Johns Hopkins Univ Baltimore MD 21218 USA

ISBN: (纸本)9781665412681

The foundation and architecture for a spike-based, neuromorphic cellular neural network is presented. Spike information from an event-based, dynamic vision sensor is processed asynchronously by the architecture in parallel. An array of N-2 processing elements (PEs) with eight neighbor clique is the primitive unit of the processor. Spatiotemporal filtering of spike data is accomplised via mixed-signed, embedded morphological processing using a simplicial piecewise linear approximation. Preliminary simulation and modeling on data acquired from event-based sensors show a clear pathway towards the realization of the architecture in hardware.

关键词： Neuromorphic embedded computing morphological processing piecewise linear functions

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：