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

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

Neural networks in day-ahead electricity price forecasting: single vs. multiple outputs

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Marcjasz, Grzegorz Lago, Jesus Weron, Rafal Department of Operations Research Wroclaw University of Science and Technology Wroclaw Poland Delft Center for Systems and Control Delft University of Technology Delft Netherlands Algorithms Modeling and Optimization Energyville Genk Belgium Mol Belgium

Recent advancements in the fields of artificial intelligence and machine learning methods resulted in a significant increase of their popularity in the literature, including electricity price forecasting. Said methods cover a very broad spectrum, from decision trees, through random forests to various artificial neural network models and hybrid approaches. In electricity price forecasting, neural networks are the most popular machine learning method as they provide a non-linear counterpart for well-tested linear regression models. Their application, however, is not straightforward, with multiple implementation factors to consider. One of such factors is the network’s structure. This paper provides a comprehensive comparison of two most common structures when using the deep neural networks – one that focuses on each hour of the day separately, and one that reflects the daily auction structure and models vectors of the prices. The results show a significant accuracy advantage of using the latter, confirmed on data from five distinct power exchanges. Copyright © 2020, The Authors. All rights reserved.

关键词： Risk management

Forecasting day-ahead electricity prices: A review of state-of-the-art algorithms, best practices and an open-access benchmark

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Lago, Jesus Marcjasz, Grzegorz De Schutter, Bart Weron, Rafal Delft Center for Systems and Control Delft University of Technology Delft Netherlands Algorithms Modeling and Optimization Energyville Genk Belgium Mol Belgium Department of Operations Research and Business Intelligence Wroclaw University of Science and Technology Wroclaw Poland

While the field of electricity price forecasting has benefited from plenty of contributions in the last two decades, it arguably lacks a rigorous approach to evaluating new predictive algorithms. The latter are often compared using unique, not publicly available datasets and across too short and limited to one market test samples. The proposed new methods are rarely benchmarked against well established and well performing simpler models, the accuracy metrics are sometimes inadequate and testing the significance of differences in predictive performance is seldom conducted. Consequently, it is not clear which methods perform well nor what are the best practices when forecasting electricity prices. In this paper, we tackle these issues by comparing state-of-the-art statistical and deep learning methods across multiple years and markets, and by putting forward a set of best practices. In addition, we make available the considered datasets, forecasts of the state-of-the-art models, and a specifically designed python toolbox, so that new algorithms can be rigorously evaluated in future studies. Copyright © 2020, The Authors. All rights reserved.

关键词： Power markets

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

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

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

ECONOMICS OF DECLINING WATER-SUPPLIES IN THE OGALLALA AQUIFER

学校读者我要写书评

暂无评论

GROUND WATER 1982年第1期20卷 73-79页

作者： WARREN, J MAPP, H RAY, D KLETKE, D WANG, C Assistant Professor Professors and Research Associate Department of Agricultural Economics Agricultural Hall Room 555 Stillwater Oklahoma 74074. Harry P. Mapp Jr. received a Ph.D. in Agricultural Economics from Oklahoma State University in 1972 and has been a member of the faculty at Cornell University and Oklahoma State University. He has been involved in several research projects and has a number of publications on the economics of irrigation from ground-water sources. Daryll E. Ray received his Ph.D. in Economics from Iowa State University in 1971. He has been with Oklahoma State University since October 1971. He is the developer of the National Agricultural Policy Simulator (POLYSIM) and is the author of numerous journal articles and professional publications in the public policy and production economics areas. Darrel D. Kletke received the B.S. degree in Agriculture Education and M.S. and Ph.D. degrees in Agricultural Economics from Oklahoma State University. Research emphasis is farm level optimization algorithms irrigation cost estimation and decision model design and development. He has numerous publications in these areas.

A large portion of northwest Oklahoma is situated over the Ogallala Aquifer. Economic growth in the region has been tied closely to irrigated agriculture which depends on declining ground-water resources in the Ogallala formation. As part of an integrated six-State study, Oklahoma researchers developed a computer model of the agricultural sector of northwestern Oklahoma and estimated irrigated and dryland cropping patterns, farm output and farm income over a 40-year planning horizon. Projections were made for a “baseline” situation, and the sensitivity of these results to alternative assumptions on energy costs, commodity prices and technological development was also analyzed. Preliminary results of the baseline analysis suggest a favorable outlook for irrigated agriculture in the area through the near to mid-term, with increases in irrigated acreage, production, and returns to land and management. However, the baseline case is dependent on several relatively optimistic assumptions regarding future fuel prices, yields, and agricultural commodity prices. Even fairly large changes in fuel prices and yields are not particularly critical for model results, but if agricultural commodity prices are substantially lower than projected, the outlook for irrigated agriculture in the area is not favorable.

关键词：

PUTTING AN OIL-SPILL CLEANUP COMPUTER-MODEL TO WORK FOR THE NAVY

学校读者我要写书评

暂无评论

NAVAL ENGINEERS JOURNAL 1983年第3期95卷 165-172页

作者： NYHART, JD PSARAFTIS, HN YAROSCHAK, PJ Mr. J. D. Nyhart:is professor of management at the Sloan School of Management and the Department of Ocean Engineering at the Massachusetts Institute of Technology. His current research and writing focus on the use of scientific and technical material in formal judicial and administrative proceedings as well as the development of economic and regulatory models appropriate for deep ocean mining and oil-spill control. Harilaos N. Psaraftis:is Assistant Professor of Marine Systems at the Department of Ocean Engineering at the Operations Research Center at M.I.T. Professor Psaraftis received two M.Sc. degrees in 1977 (in Naval Architecture and Marine Engineering and in Shipping and Shipbuilding Management) and a Ph.D. in 1979 (in Ocean Systems Operations Research) all from M.I.T. Professor Psaraftis has been conducting research in problem areas such as the probabilistic modeling of underwater detection and optimal sensor allocation (project sponsored by ONR) the optimization of oil spill cleanup operations (project sponsored by a consortium of government and industry organizations) the development of routing and scheduling algorithms in transportation problems (project sponsored by DOT) and the analysis and solution algorithms of sealift routing and scheduling problems (project sponsored by ONR and the Military Sealift Command). Professor Psaraftis has published in various journals and is currently the Chairman of the Ocean Systems Management Program at M.I.T. Mr. Paul J. Yaroschak:received his Bachelors Degree in Civil Engineering from Villanova University and his Masters Degree in Environmental Engineering from Northeastern University. He has served in the Civil Engineer Corps U.S. Navy in Public Works and Construction Management and as a Project Engineer for Navy-wide Water and Wastewater Treatment Projects for the Naval Facilities Engineering Command. He is currently Head of the Environmental Engineering Branch of the Naval Facilities Engineering Command. Mr. Yaroschak is a Registered Professional Engineer i

A research group at the Massachusetts Institute of Technology has completed the first phase of the development of a computer assisted model for analyzing complex decisions and policies regarding oil spill cleanup. The model is the product of an ongoing MIT Sea Grant project, sponsored by a consortium of government and industry organizations, including the National Oceanic and Atmospheric Administration, the U.S. C oast G uard , the U.S. N avy , the Commonwealth of Massachusetts, the Spill Control Association of America, JFB Scientific Corporation, the Doherty Foundation, Petro-Canada and Texaco. The model can be used, among other things, in strategic planning for the long-term oil spill response needs of a region, in assisting On Scene Coordinators in responding to a specific spill (tactical/operational setting), in evaluating the environmental and economic damages of a spill versus the cost of cleanup, in simulation and training, and in the analysis of various policy and regulatory issues such as the effects of delays, the use of dispersants and the investigation of liability and compensation issues. The paper describes the model in detail, focuses on its potential uses and presents experience with its application in conjunction with pollution control efforts of the U.S. Navy. Specifically, we outline the application of the model in the Port of Charleston, South Carolina, an ongoing project sponsored by the Naval Facilities Engineering Command. The difficulty of gathering data for such an application is discussed.

关键词：

The SCIP optimization suite 8.0

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Bestuzheva, Ksenia Besançon, Mathieu Chen, Wei-Kun Chmiela, Antonia Donkiewicz, Tim Van Doornmalen, Jasper Eifler, Leon Gaul, Oliver Gamrath, Gerald Gleixner, Ambros Gottwald, Leona Graczyk, Christoph Halbig, Katrin Hoen, Alexander Hojny, Christopher Van Der Hulst, Rolf Koch, Thorsten Lübbecke, Marco Maher, Stephen J. Matter, Frederic Mühmer, Erik Müller, Benjamin Pfetsch, Marc E. Rehfeldt, Daniel Schlein, Steffan Schlösser, Franziska Serrano, Felipe Shinano, Yuji Sofranac, Boro Turner, Mark Vigerske, Stefan Wegscheider, Fabian Wellner, Philipp Weninger, Dieter Witzig, Jakob Zuse Institute Berlin Department AIS2T Takustr. 7 Berlin14195 Germany School of Mathematics and Statistics Beijing Institute of Technology Beijing100081 China RWTH Aachen University Lehrstuhl für Operations Research Kackertstr. 7 Aachen52072 Germany Technische Universiteit Eindhoven Department of Mathematics and Computer Science P.O. Box 513 Eindhoven5600 MB Netherlands I2DAMO GmbH Englerallee 19 Berlin14195 Germany Friedrich-Alexander Universität Erlangen-Nürnberg Department of Data Science Cauerstr. 11 Erlangen91058 Germany University of Twente Department of Discrete Mathematics and Mathematical Programming P.O. Box 217 Enschede7500 AE Netherlands Technische Universität Berlin Software and Algorithms for Discrete Optimization Straße des 17. Juni 135 Berlin10623 Germany Zuse Institute Berlin Department A2IM Takustr. 7 Berlin14195 Germany University of Exeter College of Engineering Mathematics and Physical Sciences Exeter United Kingdom Technische Universität Darmstadt Fachbereich Mathematik Dolivostr. 15 Darmstadt64293 Germany Technische Universität Berlin Straße des 17. Juni 135 Berlin10623 Germany Software and Algorithms for Discrete Optimization Institute of Mathematics Technische Universität Berlin Straße des 17. Juni 135 Berlin10623 Germany GAMS Software GmbH C/o Zuse Institute Berlin Department AIS2T Takustr. 7 Berlin14195 Germany

The SCIP optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 8.0 of the SCIP optimization Suite. Major updates in SCIP include improvements in symmetry handling and decomposition algorithms, new cutting planes, a new plugin type for cut selection, and a complete rework of the way nonlinear constraints are handled. Additionally, SCIP 8.0 now supports interfaces for Julia as well as Matlab. Further, UG now includes a unified framework to parallelize all solvers, a utility to analyze computational experiments has been added to GCG, dual solutions can be postsolved by PaPILO, new heuristics and presolving methods were added to SCIP-SDP, and additional problem classes and major performance improvements are available in *** Codes 90C05, 90C10, 90C11, 90C30, 90C90, 65Y05 Copyright © 2021, The Authors. All rights reserved.

关键词： Integer programming