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

A POTENTIAL-FUNCTION REDUCTION ALGORITHM FOR SOLVING A linear program DIRECTLY FROM AN INFEASIBLE WARM START

MATHEMATICAL programMING 1991年第3期52卷 441-466页

作者： FREUND, RM 1. Sloan School of Management Massachusetts Institute of Technology 02139 Cambridge MA USA

This paper develops an algorithm for solving a standard-form linear program directly from an infeasible "warm start", i.e., directly from a given infeasible solution x that satisfies Ax = b but x not greater than or equal to 0. The algorithm is a potential function reduction algorithm, but the potential function is somewhat different than other interior-point method potential functions, and is given by F(x, B) = q ln(c(T)x - B) - SIGMA(j = 1)n. ln(x(j) + h(j)(c(T)x - B) where q = n + square-root n is a given constant, h is a given strictly positive shift vector used to shift the nonnegativity constraints, and B is a lower bound on the optimal value of the linear program. The duality gap c(T)x = B is used both in the leading tem as well as in the barrier term to help shift the nonnegativity constraints. The algorithm is shown under suitable conditions to achieve a constant decrease in the potential function and so achieves a constant decrease in the duality gap (and hence also in the infeasibility) in O(n) iterations. Under more restrictive assumptions regarding the dual feasible region, this algorithm is modified by the addition of a dual barrier term, and will achieve a constant decrease in the duality gap (and in the infeasibility) in O(square-root n) iterations.

关键词： linear program POTENTIAL FUNCTION SHIFTED BARRIER INTERIOR POINT ALGORITHM POLYNOMIAL TIME BOUND

来源：评论

学校读者我要写书评

暂无评论

STABILITY OF THE OPTIMAL BASIS OF A linear program UNDER UNCERTAINTY

引用

OPERATIONS RESEARCH LETTERS 1993年第1期13卷 9-12页

作者： ROHN, J Faculty of Mathematics and Physics Charles University Malostranske nam. 25 11800 Prague Czechoslovakia

We prove that the set of optimal basic variables of a linear program remains stable under mutually independent variations of all data within prescribed tolerances if and only if it is stable for a finite subset of explicitly described linear programs from this family. The cardinality of this subset is exponential in the number of constraints.

关键词： linear program UNCERTAINTY OPTIMAL BASIS STABILITY

来源：评论

学校读者我要写书评

暂无评论

Solving a Multiple Objective linear program using simulated annealing

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2001年第1期18卷 109-120页

作者： Sarker, R Newton, C Univ New S Wales ADFA Sch Comp Sci Operat Res Grp Canberra ACT 2600 Australia

Multiple Objective linear programs (MOLP) are often used in practice for managerial decision making. There are no well-accepted Operations Research (OR) techniques that can provide optimum solutions for MOLP. This paper reviews some of the popular MOLP techniques currently reported in the literature indicating their advantages and disadvantages. In addition, we investigate the use of simulated annealing for solving a constrained maximization problem with two objectives. The design of the algorithm is presented and experimental experiences are reported. Finally, the requirements of resources for different candidate solutions are discussed in the light of defining the term optimality in multiobjective optimization.

关键词： multiple objectives linear program simulated annealing

来源：评论

学校读者我要写书评

暂无评论

On the existence of a short pivoting sequence for a linear program

引用

OPERATIONS RESEARCH LETTERS 2020年第6期48卷 697-702页

作者： Forsgren, Anders Wang, Fei KTH Royal Inst Technol Dept Math Optimizat & Syst Theory SE-10044 Stockholm Sweden

We show that given a feasible primal-dual pair of linear programs in canonical form, there exists a sequence of pivots, whose length is bounded by the minimum dimension of the constraint matrix, leading from the origin to the optimum. The sequence of pivots give a sequence of square and nonsingular submatrices of the constraint matrix. Solving two linear equations involving such a submatrix give primal-dual optimal solutions to the corresponding linear program in canonical form. (C) 2020 The Authors. Published by Elsevier B.V.

关键词： linear program Pivoting method Short sequence of pivots

来源：评论

学校读者我要写书评

暂无评论

Solving linear program as linear system in polynomial time

引用

MATHEMATICAL AND COMPUTER MODELLING 2011年第5-6期53卷 1056-1073页

作者： Sen, Syamal K. Ramakrishnan, Suja Agarwal, Ravi P. Florida Inst Technol Dept Math Sci Melbourne FL 32901 USA

A physically concise polynomial-time iterative-cum-non-iterative algorithm is presented to solve the linear program (LP) Min c(t)chi subject to A chi = b, chi >= 0. The iterative part - a variation of Karmarkar projective transformation algorithm - is essentially due to Barnes only to the extent of detection of basic variables of the LP taking advantage of monotonic convergence. It involves much less number of iterations than those in the Karmarkar projective transformation algorithm. The shrunk linear system containing only the basic variables of the solution vector x resulting from A chi = b is then solved in the mathematically non-iterative part. The solution is then tested for optimality and is usually more accurate because of reduced computation and has less computational and storage complexity due to smaller order of the system. The computational complexity of the combination of these two parts of the algorithm is polynomial-time O(n(3)). The boundedness of the solution, multiple solutions, and no-solution (inconsistency) cases are discussed. The effect of degeneracy of the primal linear program and/or its dual on the uniqueness of the optimal solution is mentioned. The algorithm including optimality test is implemented in Matlab which is found to be useful for solving many real-world problems. (C) 2010 Elsevier Ltd. All rights reserved.

关键词： Barnes algorithm Error-free computation linear program linear system Matlab program Polynomial-time iterative-cum-non-iterative algorithm

来源：评论

学校读者我要写书评

暂无评论

A refined deterministic linear program for the network revenue management problem with customer choice behavior

引用

NAVAL RESEARCH LOGISTICS 2008年第6期55卷 563-580页

作者： Kunnumkal, Sumit Topaloglu, Huseyin Indian Sch Business Hyderabad 500032 Andhra Pradesh India Cornell Univ Sch Operat Res & Informat Engn Ithaca NY 14853 USA

We present a new deterministic linear program for the network revenue management problem with customer choice behavior. The novel aspect of our linear program is that it naturally generates bid prices that depend on how much time is left until the time of departure. Similar to the earlier linear program used by van Ryzin and Liu (2004), the optimal objective value of our linear program provides an upper bound on the optimal total expected revenue over the planning horizon. In addition, the percent gap between the optimal objective value of our linear program and the optimal total expected revenue diminishes in an asymptotic regime where the leg capacities and the number of time periods in the planning horizon increase linearly with the same rate. Computational experiments indicate that when compared with the linear program that appears in the existing literature, our linear program can provide tighter upper bounds, and the control policies that are based on our linear program can obtain higher total expected revenues. (C) 2008 Wiley Periodicals, Inc.

关键词： revenue management linear program customer choice

来源：评论

学校读者我要写书评

暂无评论

A POTENTIAL REDUCTION ALGORITHM WITH USER-SPECIFIED PHASE-I PHASE-II BALANCE FOR SOLVING A linear program FROM AN INFEASIBLE WARM START

引用

SIAM JOURNAL ON OPTIMIZATION 1995年第2期5卷 247-268页

作者： FREUND, RM CORNELL UNIV COLL ENGNSCH OPERAT RES & IND ENGNITHACANY 14853

This paper develops a potential reduction algorithm for solving a linear programming problem directly from a ''warm start'' initial point that is neither feasible nor optimal. The algorithm is an ''interior point'' variety that seeks to reduce a single potential function which simultaneously coerces feasibility improvement (Phase I) and objective value improvement (Phase II). The key feature of the algorithm is the ability to specify beforehand the desired balance between infeasibility and nonoptimality in the following sense. Given a prespecified balancing parameter beta > 0, the algorithm maintains the following Phase I-Phase II ''beta-balancing constraint'' throughout (c(T)x-z) < beta xi(T)x, where C(T)x is the objective function, z is the (unknown) optimal objective value of the linear program, and xi(T)x measures the infeasibility of the current iterate x. This balancing constraint can be used to either emphasize rapid attainment of feasibility (set beta large) at the possible expense of good objective function values or to emphasize rapid attainment of good objective values (set beta small) at the possible expense of a lower infeasibility gap. The algorithm seeks to minimize the feasibility gap while maintaining the beta-balancing condition, thus solving the original linear program as a consequence. The algorithm exhibits the following advantageous features: (i) the iterate solutions monotonically decrease the infeasibility measure, (ii) the iterate solutions satisfy the beta-balancing constraint, (iii) the iterate solutions achieve constant improvement in both Phase I and Phase II in O(n) iterations, (iv) there is always a possibility of finite termination of the Phase I problem, and (v) the algorithm is amenable to acceleration via linesearch of the potential function.

关键词： linear program POTENTIAL FUNCTION INTERIOR POINT ALGORITHM POLYNOMIAL TIME COMPLEXITY

来源：评论

学校读者我要写书评

暂无评论

Reformulation of a linear program to Reduce the Average Current in a Modular Multilevel Converter 9

Reformulation of a Linear Program to Reduce the Average Curr...

引用

9th International Conference on Power and Energy Systems (ICPES)

作者： Petranovic, Nikola Townsend, Chris Fernando, Tyrone Iu, Herbert Univ Western Australia Elect Elect & Comp Engn Crawley Australia

ISBN: (纸本)9781728126586

A modular multilevel converter contains many capacitor full-bridge converter cells. An increased capacitance in the converter means a large overall converter size and increased converter cost. Previous research has investigated methods to reduce converter cell capacitance. One paper presents an iterative linear program to reduce the capacitance while limiting the average currents. The work presented in this paper modifies the linear program to further reduce average currents for similar reduction in capacitance. Furthermore, the results presented here show root-mean-square currents will also be reduced.

关键词： Modular multilevel converter optimisation linear program capacitor energy variation average current

来源：评论

学校读者我要写书评

暂无评论

SEQUENCE OF linear program FOR ROBUST PHASE RETRIEVAL 49

SEQUENCE OF LINEAR PROGRAM FOR ROBUST PHASE RETRIEVAL

引用

49th IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP)

作者： Kim, Seonho Lee, Kiryung Ohio State Univ Columbus OH 43210 USA

ISBN: (纸本)9798350344868;9798350344851

We consider a robust phase retrieval problem that aims to recover a signal from its absolute measurements corrupted with sparse noise. The least absolute deviation (LAD) provides a robust estimation against outliers. However, the corresponding optimization problem is nonconvex. We propose an "unregularized" iterative convexification approach to LAD through a sequence of linear programs (SLP). We provide a non-asymptotic convergence analysis under the standard Gaussian assumption of the measurement vectors. The SLP algorithm, when suitably initialized, linearly converges to the ground truth at optimal sample complexity up to a numerical constant. Furthermore, SLP empirically outperforms existing methods that provide a comparable performance guarantee.

关键词： phase retrieval outliers least absolute deviation linear program convex optimization

来源：评论

学校读者我要写书评

暂无评论

Optimization of reservoir operation using linear program, case study of Riam Jerawi Reservoir, Indonesia

引用

INTERNATIONAL JOURNAL OF RIVER BASIN MANAGEMENT 2017年第2期15卷 187-198页

作者： Ginting, Bobby Minola Harlan, Dhemi Taufik, Ahmad Ginting, Herli Parahyangan Catholic Univ Dept Civil Engn Bandung Indonesia Bandung Inst Technol Dept Civil Engn Bandung Indonesia Bandung Inst Technol Ctr Res New & Renewable Energy Bandung Indonesia Univ Sumatera Utara Dept Phys Medan Indonesia

The pattern of water use operation is important to ensure the continuity of water supply system of a reservoir. This pattern, which is usually called power rule curve in a hydropower system, should be optimally obtained, so that the yielded electrical power also becomes optimal while the continuity of reservoir storage can also be tenable. In this study, in order to satisfy the main objective of Riam Jerawi Reservoir, where the energy of 6 MW should be provided every month, a linear optimization model is applied for three objective functions such as maximizing total energy, maximizing minimum energy and minimizing energy shortage. In addition, a simulation model is also presented for comparison purpose particularly to emphasize some disadvantages of using this model. The results show that the optimum energy can be achieved by applying this optimization model where the continuity of reservoir volume is also satisfied. Meanwhile, the simulation model produces the rule curve, which cannot satisfy the continuity criterion. This optimization model is expected to be applied for other similar cases and give the optimum power rule curve for the related stakeholders.

关键词： Objective functions optimization model power rule curve linear program

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：