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

系统工程理论与实践 2022年第5期42卷 1345-1365页

作者：苏志雄顾辉明乞建勋魏汉英南昌工程学院工商管理学院南昌330099 华北电力大学经济与管理学院北京102206

多技能资源受限项目调度问题(简称MS-RCPSP)是项目管理中颇具代表性的调度问题,一般性问题以“资源全局受限”为特征.本文从新视角,针对实际中广泛存在的资源局域受限情况,以及反应性和应急性等情况,研究局域性MS-RCPSP;并重点考虑一类... 详细信息

多技能资源受限项目调度问题(简称MS-RCPSP)是项目管理中颇具代表性的调度问题,一般性问题以“资源全局受限”为特征.本文从新视角,针对实际中广泛存在的资源局域受限情况,以及反应性和应急性等情况,研究局域性MS-RCPSP;并重点考虑一类典型问题:项目某部分的平行活动,可用的资源量极少,甚至为1,但具备各活动所需技能,且可重复使用,需安排该资源顺序完成这一众活动,使项目工期最小化.虽是局域性调度,但项目系统性使其“牵一发而动全身”,难度可能不亚于全局性调度.本文从探索问题“局域性”特征入手,量化局域调度导致的项目工期延迟,并发展整数线性优化强对偶理论,结合Dantzig-Wolfe分解法,开发出伪多项式时间精确算法求解该问题;通过仿真模拟测试,验证该算法计算大规模问题案例精确解的优势.

关键词：多技能资源受限项目调度 0-1混合线性优化整数优化强对偶伪多项式时间精确算法 Dantzig-Wolfe分解内点法

来源：评论

学校读者我要写书评

暂无评论

THE COMPUTATION OF APPROXIMATE FEEDBACK STACKELBERG EQUILIBRIA IN MULTI-PLAYER NONlinear CONSTRAINED DYNAMIC GAMES

arXiv

引用

arXiv 2024年

作者： Li, Jingqi Sojoudi, Somayeh Tomlin, Claire Fridovich-Keil, David Electrical Engineering and Computer Sciences University of California Berkeley BerkeleyCA94720 United States Aerospace Engineering and Engineering Mechanics University of Texas at Austin AustinTX78712-1221 United States

Solving feedback Stackelberg games with nonlinear dynamics and coupled constraints, a common scenario in practice, presents significant challenges. This work introduces an efficient method for computing approximate local feedback Stackelberg equilibria in multi-player general-sum dynamic games, with continuous state and action spaces. Different from existing (approximate) dynamic programming solutions that are primarily designed for unconstrained problems, our approach involves reformulating a feedback Stackelberg dynamic game into a sequence of nested optimization problems, enabling the derivation of Karush–Kuhn–Tucker (KKT) conditions and the establishment of a second-order sufficient condition for local feedback Stackelberg equilibria. We propose a Newton-style primal-dual interior point method for solving constrained linear quadratic (LQ) feedback Stackelberg games, offering provable convergence guarantees. Our method is further extended to compute local feedback Stackelberg equilibria for more general nonlinear games by iteratively approximating them using LQ games, ensuring that their KKT conditions are locally aligned with those of the original nonlinear games. We prove the exponential convergence of our algorithm in constrained nonlinear games. In a feedback Stackelberg game with nonlinear dynamics and (nonconvex) coupled costs and constraints, our experimental results reveal the algorithm’s ability to handle infeasible initial conditions and achieve exponential convergence towards an approximate local feedback Stackelberg equilibrium. © 2024, CC BY.

关键词： Iterative methods

来源：评论

学校读者我要写书评

暂无评论

A survey on conic relaxations of optimal power flow problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2020年第2期287卷 391-409页

作者： Zohrizadeh, Fariba Josz, Cedric Jin, Ming Madani, Ramtin Lavaei, Javad Sojoudi, Somayeh Univ Texas Arlington Arlington TX 76019 USA Columbia Univ New York NY 10027 USA Univ Calif Berkeley Berkeley CA 94720 USA

Conic optimization has recently emerged as a powerful tool for designing tractable and guaranteed algorithms for power system operation. On the one hand, tractability is crucial due to the large size of modern electricity transmission grids. This is a result of the numerous interconnections that have been built over time. On the other hand, guarantees are needed to ensure reliability and safety for consumers at a time when power systems are growing in complexity. This is in large part due to the high penetration of renewable energy sources and the advent of electric vehicles. The aim of this paper is to review the latest literature in order to demonstrate the success of conic optimization when applied to power systems. The main focus is on how linear programming, second-order cone programming, and semidefinite programming can be used to address a central problem named the optimal power flow problem. We describe how they are used to design convex relaxations of this highly challenging non-convex optimization problem. We also show how sum-of-squares can be used to strengthen these relaxations. Finally, we present advances in first-order methods, interior-point methods, and nonconvex methods for solving conic optimization. Challenges for future research are also discussed. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Optimal power flow Semidefinite programming Polynomial optimization Graph theory

来源：评论

学校读者我要写书评

暂无评论

Faster randomized infeasible interior point methods for tall/wide linear programs 34

Faster randomized infeasible interior point methods for tall...

引用

34th Conference on Neural Information Processing Systems, NeurIPS 2020

作者： Chowdhury, Agniva London, Palma Avron, Haim Drineas, Petros Department of Statistics Purdue University West LafayetteIN United States ORIE Department Cornell University IthacaNY United States School of Mathematical Sciences Tel Aviv University Tel Aviv Israel Department of Computer Science Purdue University West LafayetteIN United States

linear programming (LP) is used in many machine learning applications, such as l1-regularized SVMs, basis pursuit, nonnegative matrix factorization, etc. interior point methods (IPMs) are one of the most popular methods to solve LPs both in theory and in practice. Their underlying complexity is dominated by the cost of solving a system of linear equations at each iteration. In this paper, we consider infeasible IPMs for the special case where the number of variables is much larger than the number of constraints (i.e., wide), or vice-versa (i.e., tall) by taking the dual. Using tools from Randomized linear Algebra, we present a preconditioning technique that, when combined with the Conjugate Gradient iterative solver, provably guarantees that infeasible IPM algorithms (suitably modified to account for the error incurred by the approximate solver), converge to a feasible, approximately optimal solution, without increasing their iteration complexity. Our empirical evaluations verify our theoretical results on both real and synthetic data. © 2020 Neural information processing systems foundation. All rights reserved.

关键词： linear programming

来源：评论

学校读者我要写书评

暂无评论

检验数替换价值系数单纯形法的若干讨论

引用

运筹与管理 2023年第10期32卷 83-87页

作者：韩伟一乔立新刘松崧哈尔滨工业大学经济与管理学院黑龙江哈尔滨150001

用检验数替换价值系数来实施单纯形法是新近提出的一种方法,可以有效提高求解线性规划的计算效率,能够使单纯形法的一些性质和特征变得显而易见。本文将给出该方法的三个应用:(1)揭示原模型和对偶模型之间的直接联系,更深入地诠释对偶... 详细信息

用检验数替换价值系数来实施单纯形法是新近提出的一种方法,可以有效提高求解线性规划的计算效率,能够使单纯形法的一些性质和特征变得显而易见。本文将给出该方法的三个应用:(1)揭示原模型和对偶模型之间的直接联系,更深入地诠释对偶理论的无界性;(2)提出新的列消除规则,可有效降低单纯形法的计算规模,改进了计算大规模线性规划的列生成方法;(3)可以简化表上作业法之位势方法,使得其计算效率总可提升一倍。因此,这种新方法极大地丰富了单纯形法的理论,而且还可提高单纯形法的计算效率。

关键词：线性规划单纯形法列生成方法列消除表上作业法

来源：评论

学校读者我要写书评

暂无评论

A Scaling-Invariant Algorithm for linear programming Whose Running Time Depends Only on the Constraint Matrix 2020

A Scaling-Invariant Algorithm for Linear Programming Whose R...

引用

52nd Annual ACM SIGACT Symposium on theory of Computing (STOC)

作者： Dadush, Daniel Huiberts, Sophie Natura, Bento Vegh, Laszlo A. Ctr Wiskunde & Informat Amsterdam Netherlands London Sch Econ & Polit Sci London England

ISBN: (纸本)9781450369794

Following the breakthrough work of Tardos (Oper. Res. '86) in the bit-complexity model, Vavasis and Ye (Math. Prog. '96) gave the first exact algorithm for linear programming in the real model of computation with running time depending only on the constraint matrix. For solving a linear program (LP) max c(T)x, Ax = b, x >= 0, A is an element of R-mxn, Vavasis and Ye developed a primal-dual interior point method using a 'layered least squares' (LLS) step, and showed that O(n(3.5) log((chi) over bar (A) + n)) iterations suffice to solve (LP) exactly, where (chi) over bar (A)* is a condition measure controlling the size of solutions to linear systems related to A. Monteiro and Tsuchiya (SIAM J. Optim. '03), noting that the central path is invariant under rescalings of the columns of A and c, asked whether there exists an LP algorithm depending instead on the measure (chi) over bar (A)*, defined as the minimum (chi) over bar (AD) value achievable by a column rescaling AD of A, and gave strong evidence that this should be the case. We resolve this open question affirmatively. Our first main contribution is an O(m(2)n(2) + n(3)) time algorithm which works on the linear matroid of A to compute a nearly optimal diagonal rescaling D satisfying (chi) over bar (AD) <= n((chi) over bar*)(3). This algorithm also allows us to approximate the value of (chi)over bar>(A) up to a factor n((chi) over bar*)(2). This result is in (surprising) contrast to that of Tuncel (Math. Prog. '99), who showed NP -hardness for approximating (chi) over bar (A) to within 2(poly(rank(A))). The key insight for our algorithm is to work with ratios g(i)/g(j) of circuits of A-i.e., minimal linear dependencies Ag = 0 which allow us to approximate the value of (chi) over bar (A)* by a maximum geometric mean cycle computation in what we call the 'circuit ratio digraph' of A. While this resolves Monteiro and Tsuchiya's question by appropriate preprocessing, it falls short of providing either a truly scaling i

关键词： linear programming interior point methods condition number chi bar circuits linear matroids

来源：评论

学校读者我要写书评

暂无评论

Convergence Rates of Average-Reward Multi-agent Reinforcement Learning via Randomized linear programming

Convergence Rates of Average-Reward Multi-agent Reinforcemen...

引用

IEEE Conference on Decision and Control

作者： Alec Koppel Amrit Singh Bedi Bhargav Ganguly Vaneet Aggarwal JP Morgan AI Research NewYork NY U.S. Army Research Laboratory Adelphi MD University of Maryland College Park Maryland USA Purdue University USA King Abdullah University of Science and Technology Saudi Arabia

ISBN: (数字)9781665467612

ISBN: (纸本)9781665467629

In tabular multi-agent reinforcement learning with average-cost criterion, a team of agents sequentially interacts with the environment and observes local incentives. We focus on the case that the global reward is a sum of local rewards, the joint policy factorizes into agents’ marginals, and full state observability. To date, few global optimality guarantees exist even for this simple setting, as most results yield convergence to stationarity for parameterized policies in large/possibly continuous spaces. To solidify the foundations of MARL, we build upon linear programming (LP) reformulations, for which stochastic primal-dual methods yield a model-free approach to achieve optimal sample complexity in the centralized case. We develop multi-agent extensions, whereby agents solve their local saddle point problems and then perform local weighted averaging. We establish that the sample complexity to obtain near-globally optimal solutions matches tight dependencies on the cardinality of the state and action spaces, and exhibits classical scalings with respect to the network in accordance with multi-agent optimization. Experiments corroborate these results in practice.

关键词： Solid modeling Stochastic processes Reinforcement learning linear programming Picture archiving and communication systems Complexity theory Observability

来源：评论

学校读者我要写书评

暂无评论

Maximum Multiplicative programming: theory, Algorithms, and Applications

Maximum Multiplicative Programming: Theory, Algorithms, and ...

引用

作者： Ghasemi Saghand, Payman University of South Florida

学位级别：Ph.D.

This dissertation presents three different contributions to an important class of optimization problems known as Multiplicative Programs (MPs). The first group of contributions contains the development and analysis of several multi-objective optimization-based based algorithms designed to find the optimal solution of Mixed Integer linear MPs. As for the second group, the application of a special class of MPs in radiotherapy planning is presented. Finally, in the last group, a new technique for conducting the multiplication process in the objectives of MPs is presented. Using this technique, we introduce a family of novel solution methods that are capable of solving both maximum and minimum MPs. Regarding the first group of contributions, we show that MPs can be viewed as special cases of the problem of optimization over the efficient set in Multi-objective optimization. Based on this observation, we develop several solution approaches with their own unique properties. In the first solution approach, we embed an existing algorithm capable of solving continuous MPs with two multiplying terms in a branch-and-bound framework to solve mixed integer instances. In our second approach, we develop a criterion space search algorithm for solving any mixed integer MPs with any number of multiplying terms. In our last solution approach, we develop three different algorithms that, in addition to solving any mixed integer MPs with any number of multiplying terms, are capable of handling the multiplying terms with different powers. Specifically, the advantage of our last solution approach is that it handles the powers with the minimal impact on the computational complexity in practice. In the second group of contributions, we study the fluency map optimization problem in Intensity Modulated Radiation Therapy (IMRT) from a cooperative game theory point of view. We consider the cancerous and healthy organs in a patient's body as players of a game, where cancerous organs seek to elimi

关键词：

来源：评论

学校读者我要写书评

暂无评论

Voting power on a graph connected political space with an application to decision-making in the Council of the European Union

引用

SOCIAL CHOICE AND WELFARE 2021年第4期57卷 733-761页

作者： Benati, Stefano Vittucci Marzetti, Giuseppe Univ Trento Sch Int Studies Dept Sociol & Social Res Via Verdi 26 I-38122 Trento Italy Univ Milano Bicocca Dept Sociol & Social Res Via Bicocca Arcimboldi 8 I-20126 Milan Italy

We analyze the problem of computing the Banzhaf and Shapley power indices for graph restricted voting games, defined in a particular class of graphs, that we called line-clique. A line-clique graph is a model of a uni-dimensional political space in which voters with the same bliss point are the connected vertices of a clique and then other arcs connect nodes of consecutive cliques. The interest to this model comes from its correspondence to the spatial voting game: a model that has been proposed and used by political analysts to understand nations' behavior and the political outcome of the bargaining process within the EU Council. Broadly speaking, the computation of a power index of a graph restricted game is strongly #P-complete, as it includes the enumeration of all winning coalitions. Nevertheless, we show that in this special class of graph coalitions can be enumerated by dynamic programming, resulting in a pseudo-polynomial algorithm and proving that the problem only weakly #P-complete. After implementing our new algorithms and finding that they are very fast in practice, we analyze the voting behavior in the EU Council, as for this application previous research compiled a large data set concerning nations' political positions and political outcomes. We will test whether voting power has an effect on the political outcome, more precisely, whether nations that are favored by their weight and position can influence the political outcome to their advantages. Using linear regressions, we will see that unrestricted power indices are not capable of any predictive property, but graph restricted indices are. The statistic evidence shows that the combination of voting weight and network position is a source of power that affects the political outcome to the advantage of a country.

关键词： Economic theory/Quantitative Economics/Mathematical methods Public Finance International Political Economy Game theory Economics Social and Behav. Sciences Social Policy

来源：评论

学校读者我要写书评

暂无评论

Dynamic Non-diagonal Regularization in interior point methods for linear and Convex Quadratic programming

引用

JOURNAL OF OPTIMIZATION theory AND APPLICATIONS 2019年第3期181卷 905-945页

作者： Pougkakiotis, Spyridon Gondzio, Jacek Univ Edinburgh Sch Math Edinburgh Midlothian Scotland

In this paper, we present a dynamic non-diagonal regularization for interior point methods. The non-diagonal aspect of this regularization is implicit, since all the off-diagonal elements of the regularization matrices are cancelled out by those elements present in the Newton system, which do not contribute important information in the computation of the Newton direction. Such a regularization has multiple goals. The obvious one is to improve the spectral properties of the Newton system solved at each iteration of the interior point method. On the other hand, the regularization matrices introduce sparsity to the aforementioned linear system, allowing for more efficient factorizations. We also propose a rule for tuning the regularization dynamically based on the properties of the problem, such that sufficiently large eigenvalues of the non-regularized system are perturbed insignificantly. This alleviates the need of finding specific regularization values through experimentation, which is the most common approach in the literature. We provide perturbation bounds for the eigenvalues of the non-regularized system matrix and then discuss the spectral properties of the regularized matrix. Finally, we demonstrate the efficiency of the method applied to solve standard small- and medium-scale linear and convex quadratic programming test problems.

关键词： Primal-dual regularization interior point methods Generalized proximal point methods

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：