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

Effect of Inertia Force on the Interface Stability of a Tangential-Velocity Discontinuity in Porous Media

学校读者我要写书评

暂无评论

SSRN

SSRN 2023年

作者： Le, Thi Thai Koch, Thorsten Zuse Institute Berlin Applied Algorithmic Intelligence Methods Department Takustr. 7 Berlin14195 Germany TU Berlin Chair of Software and Algorithms for Discrete Optimization Str. des 17. Juni 135 Berlin10623 Germany

The present study investigates the stability of a tangential-velocity discontinuity in porous media during the withdrawing and injecting processes of natural gases from and into underground gas storages. The focus is on analyzing the impact of inertia forces on the interface stability using the Forchheimer equations. Other publications have relied primarily on Darcy's law to describe flow stability in porous media. However, Darcy's law only adequately describes flows in which viscous forces dominate over inertia forces. As the flow rate increases, the significance of inertia forces becomes more pronounced, and Darcy's law becomes insufficient for describing such flows. Our findings indicate that even a slight consideration of the inertia effect leads to permanent destabilization of the discontinuity interface, regardless of the fluid viscosity or the Mach number. In contrast, when the inertia effect is neglected, the interface is stabilized across the entire Mach number range if the fluid viscosity is strong enough. © 2023, The Authors. All rights reserved.

关键词： Porous materials

Resolving Infeasibility of Linear Systems: A Parameterized Approach

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Bérczi, Kristóf Göke, Alexander Mendoza-Cadena, Lydia Mirabel Mnich, Matthias MTA-ELTE Momentum Matroid Optimization Research Group MTA-ELTE Egerváry Research Group Department of Operations Research Eötvös Loránd University Budapest Hungary Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany MTA-ELTE Momentum Matroid Optimization Research Group Department of Operations Research Eötvös Loránd University Budapest Hungary

Deciding feasibility of large systems of linear equations and inequalities is one of the most fundamental algorithmic tasks. However, due to data inaccuracies or modeling errors, in practical applications one often faces linear systems that are infeasible. Extensive theoretical and practical methods have been proposed for post-infeasibility analysis of linear systems. This generally amounts to detecting a feasibility blocker of small size k, which is a set of equations and inequalities whose removal or perturbation from the large system of size m yields a feasible system. This motivates a parameterized approach towards post-infeasibility analysis, where we aim to find a feasibility blocker of size at most k in fixed-parameter time f(k) · mO(1). We establish parameterized intractability (W[1]- and NP-hardness) results already in very restricted settings for different choices of the parameters maximum size of a deletion set, number of positive/negative right-hand sides, treewidth, pathwidth and treedepth. Additionally, we rule out a polynomial compression for MinFB parameterized by the size of a deletion set and the number of negative right-hand sides. Furthermore, we develop fixed-parameter algorithms parameterized by various combinations of these parameters when every row of the system corresponds to a difference constraint. Our algorithms capture the case of Directed Feedback Arc Set, a fundamental parameterized problem whose fixed-parameter tractability was shown by Chen et al. (STOC 2008). Copyright © 2022, The Authors. All rights reserved.

关键词： Linear systems

Envy-free dynamic pricing schemes

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Bérczi, Kristóf Codazzi, Laura Golak, Julian Grigoriev, Alexander MTA-ELTE Momentum Matroid Optimization Research Group MTA-ELTE Egerváry Research Group Department of Operations Research Eötvös Loránd University Budapest Hungary Institute of Algorithms and Complexity Hamburg University of Technology Hamburg Germany Department of Data Analytics and Digitalisation Maastricht University Maastricht Netherlands

A combinatorial market consists of a set of indivisible items and a set of agents, where each agent has a valuation function that specifies for each subset of items its value for the given agent. From an optimization point of view, the goal is usually to determine a pair of pricing and allocation of the items that provides an efficient distribution of the resources, i.e., maximizes the social welfare, or is as profitable as possible for the seller, i.e., maximizes the revenue. To overcome the weaknesses of mechanisms operating with static prices, a recent line of research has concentrated on dynamic pricing schemes. In this model, agents arrive in an unspecified sequential order, and the prices can be updated between two agent-arrivals. Though the dynamic setting is capable of maximizing social welfare in various scenarios, the assumption that the agents arrive one after the other eliminates the standard concept of fairness. In this paper, we study the existence of optimal dynamic prices under fairness constraints in unit-demand markets. We propose four possible notions of envy-freeness of different strength depending on the time period over which agents compare themselves to others: the entire time horizon, only the past, only the future, or only the present. For social welfare maximization, while the first definition leads to Walrasian equilibria, we give polynomial-time algorithms that always find envy-free optimal dynamic prices in the remaining three cases. In contrast, for revenue maximization, we show that the corresponding problems are APX-hard if the ordering of the agents is fixed. On the positive side, we give polynomial-time algorithms for the setting when the seller can choose the order in which agents arrive. © 2023, CC BY.

关键词： Polynomial approximation

Communication - A ware processor allocation for supercomputers

学校读者我要写书评

暂无评论

Communication - A ware processor allocation for supercompute...

9th International Workshop on algorithms and Data Structures, WADS 2005

作者： Bender, Michael A. Bunde, David P. Demaine, Erik D. Fekete, Sándor P. Leung, Vitus J. Meijer, Henk Phillips, Cynthia A. Department of Computer Science SUNY Stony Brook Stony Brook NY 11794-4400 United States Department of Computer Science University of Illinois Urbana IL 61801 United States MIT Computer Science and Artificial Intelligence Laboratory Cambridge MA 02139 United States Dept. of Mathematical Optimization Braunschweig University of Technology 38106 Braunschweig Germany Discrete Algorithms and Math Department Sandia National Laboratories Albuquerque NM 87185-1110 United States Dept. of Computing and Information Science Queen's University Kingston Ont. K7L 3N6 Canada

We give processor-allocation algorithms for grid architectures, where the objective is to select processors from a set of available processors to minimize the average number of communication hops. The associated clustering problem is as follows: Given n points in Rd, find a size-k subset with minimum average pairwise L1 distance. We present a natural approximation algorithm and show that it is a 7/4-approximation for 2D grids. In d dimensions, the approximation guarantee is 2 - 1/2d, which is tight. We also give a polynomial-time approximation scheme (PTAS) for constant dimension d and report on experimental results. © Springer-Verlag Berlin Heidelberg 2005.

关键词： Program processors

ADAPTIVE CUT SELECTION IN MIXED-INTEGER LINEAR PROGRAMMING

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Turner, Mark Koch, Thorsten Serrano, Felipe Winkler, Michael Software and Algorithms for Discrete Optimization Institute of Mathematics Technische Universität Berlin Straße des 17. Juni 135 Berlin10623 Germany Zuse Institute Berlin Department of Mathematical Optimization Takustr. 7 Berlin14195 Germany I2DAMO GmbH Englerallee 19 Berlin14195 Germany Gurobi GmbH Ulmenstr. 37-39 Frankfurt am Main60325 Germany

Cutting plane selection is a subroutine used in all modern mixed-integer linear programming solvers with the goal of selecting a subset of generated cuts that induce optimal solver performance. These solvers have millions of parameter combinations, and so are excellent candidates for parameter tuning. Cut selection scoring rules are usually weighted sums of different measurements, where the weights are parameters. We present a parametric family of mixed-integer linear programs together with infinitely many family-wide valid cuts. Some of these cuts can induce integer optimal solutions directly after being applied, while others fail to do so even if an infinite amount are applied. We show for a specific cut selection rule, that any finite grid search of the parameter space will always miss all parameter values, which select integer optimal inducing cuts in an infinite amount of our problems. We propose a variation on the design of existing graph convolutional neural networks, adapting them to learn cut selection rule parameters. We present a reinforcement learning framework for selecting cuts, and train our design using said framework over MIPLIB 2017 and a neural network verification data set. Our framework and design show that adaptive cut selection does substantially improve performance over a diverse set of instances, but that finding a single function describing such a rule is difficult. Code for reproducing all experiments is available at https://***/Opt-Mucca/*** Codes 90-05 © 2022, CC BY.

关键词： Reinforcement learning

Sustainable Welding Process Selection Based on Weight Space Partitions

学校读者我要写书评

暂无评论

Procedia CIRP 2016年 40卷 127-132页

作者： Gunther Sproesser Sebastian Schenker Andreas Pittner Ralf Borndörfer Michael Rethmeier Ya-Ju Chang Matthias Finkbeiner Chair of Safety of Joined Components Institute of Machine Tools and Factory Management Technische Universität Berlin Pascalstr. 8-9 10587 Berlin Germany Department of Mathematical Optimization Zuse Institute Berlin Takustr. 7 14195 Berlin Germany Chair of Combinatorial Optimization and Graph algorithms TU Berlin Straße des 17. Juni 136 10623 Berlin Germany Group of Welding Technology Department of Component Safety Federal Institute for Materials Research and Testing Unter den Eichen 87 12205 Berlin Germany Chair of Sustainable Engineering Department of Environmental Technology Technische Universität Berlin Straße des 17. Juni 135 10623 Berlin Germany

Selecting a welding process for a given application is crucial with respect to the sustainability of part manufacturing. Unfortunately, since welding processes are evaluated by a number of criteria, preferences for one or the other process can be contradictory. However, the prevalent procedure of weight assignment for each criterion is subjective and does not provide information about the entire solution space. From the perspective of a decision maker it is important to be able to assess the entire set of possible weightings and answer the question which welding process is optimal for which set of weights. This issue is investigated by means of a weight space partitioning approach. Two welding processes are considered with respect to three criteria that reflect their economic and environmental performance. In order to find the most sustainable welding process the underlying weight space partition is evaluated.

关键词： Welding process selection multi-criteria decision support LCA GMAW multi-attribute decision method welding costs

Two-stage adaptive PMD compensation in 40-Gb/s OTDM optical communication system

学校读者我要写书评

暂无评论

Chinese Optics Letters 2004年第6期2卷 316-319页

作者：张晓光席丽霞于丽周光涛张建忠张娜吴斌苑铁成陈林张洪明陈硕姚敏玉杨伯君 Department of Physics School of Science. Beijing University of Pouts and Telecommunications. Beijing 100876 Department of Electronic Engineering. Tsinghua University Beijing 100084 Department of Physics School of Science. Beijing University of Posts and Tclecommunications Beijing 100876n experiment of two-stage adaptive compensation for polarization mode dispersion (PMD) iu a 40-Gb/s optical time-division multiplexed communication system is reported. The PMD monitoring technique based on degree of polarization was adopted. The particle swarm optimization (PSO) algorithm was introduced in adaptive PMD compensation. The comparison was made to estimate the effectiveness between PSO algorithms with global neighborhood structure (GPSO) and with local neighborhood structure (LPSO). The LPSO algorithm is shown to be more effective to search global optimum for PMD compensation than GPSO algorithm. The two-stage PMD compensator is shown to be effective for both first- and second-order PMD and he compensator is shown to be bit rate independent. The optimum searching time is within one huudred milliseconds.

An experiment of two-stage adaptive compensation for polarization mode dispersion (PMD) iu a 40-Gb/s optical time-division multiplexed communication system is reported. The PMD monitoring technique based on degree of polarization was adopted. The particle swarm optimization (PSO) algorithm was introduced in adaptive PMD compensation. The comparison was made to estimate the effectiveness between PSO algorithms with global neighborhood structure (GPSO) and with local neighborhood structure (LPSO). The LPSO algorithm is shown to be more effective to search global optimum for PMD compensation than GPSO algorithm. The two-stage PMD compensator is shown to be effective for both first- and second-order PMD, and he compensator is shown to be bit rate independent. The optimum searching time is within one huudred milliseconds.

关键词： PMD Two-stage adaptive PMD compensation in 40-Gb/s OTDM optical communication system OTDM DOP

Biased random-key genetic algorithm for nonlinearly-constrained global optimization

学校读者我要写书评

暂无评论

Biased random-key genetic algorithm for nonlinearly-constrai...

Congress on Evolutionary Computation

作者： Ricardo M. A. Silva Mauricio G. C. Resende Panos M. Pardalos João L. Facó Centro de Informática Universidade Federal de Pernambuco Recife Pernambuco Brazil Algorithms and Optimization Research Department AT&T Laboratories Research Florham Park NJ USA Department of Industrial and Systems Engineering University of Florida FL USA Departamento de Ciência da Computação Universidade Federal do Rio de Janeiro Rio de Janeiro Brazil

ISBN: (纸本)9781479904532

Global optimization seeks a minimum or maximum of a multimodal function over a discrete or continuous domain. In this paper, we propose a biased random key genetic algorithm for finding approximate solutions for bound-constrained continuous global optimization problems subject to nonlinear constraints. Experimental results illustrate its effectiveness on some functions from CEC2006 benchmark (Liang et al. [2006]).

关键词： Vectors Sociology Statistics optimization Linear programming Decoding Genetic algorithms

Delta-modular ILP Problems of Bounded Codimension, Discrepancy, and Convolution

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Gribanov, Dmitry V. Malyshev, Dmitry S. Pardalos, Panos M. Laboratory of Discrete and Combinatorial Optimization Moscow Institute of Physics and Technology Institutsky lane 9 Moscow region Dolgoprudny141700 Russia Laboratory of Algorithms and Technologies for Network Analysis HSE University 136 Rodionova Ulitsa Nizhny Novgorod603093 Russia Department of Industrial and Systems Engineering University of Florida 401 Weil Hall GainesvilleFL116595 United States

For k, n ≥ 0, and c ∈ Zn, we consider ILP problems max(c+x: Ax = b, x ∈ Zn≥0+} with A ∈ Zk×n, rank(A) = k, b ∈ Zk and max{cTx: Ax ≤ b, x ∈ Zn} with A ∈ Z(n+k)×n, rank(A) = n, b ∈ Zn+k. The first pr... 详细信息

For k, n ≥ 0, and c ∈ Zn, we consider ILP problems max(c+x: Ax = b, x ∈ Zn≥0+} with A ∈ Zk×n, rank(A) = k, b ∈ Zk and max{cTx: Ax ≤ b, x ∈ Zn} with A ∈ Z(n+k)×n, rank(A) = n, b ∈ Zn+k. The first problem is called an ILP problem in the standard form of the codimension k, and the second problem is called an ILP problem in the canonical form with n+k constraints. We show that, for any sufficiently large ∆, both problems can be solved with 2O(k) · (fk,d · ∆)2/2Ω(√log(fk,d·∆)) operations, where fk,d = min n kk/2, (log k · log(d + k))k/2o , d is the dimension of a corresponding polyhedron and ∆ is the maximum absolute value of rank(A) × rank(A) sub-determinants of A. Our result improves the best previously known computational complexity bound (log k)O(k2) · ∆2 · polylog(∆, n, k). As our second main result, we show that the feasibility variants of both problems can be solved with 2O(k) · fk,d · ∆ · log3(fk,d · ∆) operations. The constant fk,d can be replaced by other constant gk,∆ = (log k · log(k∆))k/2 that depends only on k and ∆. Additionally, we consider different partial cases with k = 0 and k = 1, which have interesting applications: the expected ILP computational complexity with respect to a varying right-hand side b, ILP problems with generic constraint matrices, ILP problems on simplices. Based on our results with respect to small k, we present refined computational complexity bounds for these applications. As a result of independent interest, we propose an n2/2Ω(√log n) -time algorithm for the tropical convolution problem on sequences, indexed by elements of a finite Abelian group of the order n. This result is obtained, reducing the above problem to the matrix multiplication problem on a tropical semiring and using seminal algorithm by R. Williams. Additionally, we give a complete, self-contained error analysis of the generalized Discrete Fourier Transform for Abelian groups with respect to the Word-RAM computational model. Copyright © 2024, The Authors. All rig

关键词： Convolution