A note on splitting the bump in an elimination factorization

This exposition presents a method for incorporating a technique known as “splitting the bump” within an elimination form reinversion algorithm. This procedure is designed to reduce fill-in during reinversion and should improve the efficiency of linear programming systems which already use the superior elimination form of the inverse.     

Expedients for solving some specially structured mixed-integer programs

In this paper we consider dual angular and angular structured mixed integer programs which arise in some practical applications. For these problems we describe efficient methods for generating a desirable set of Benders' cuts with which one may initialize the partitioning scheme of Benders. Our research is motivated by the computational experience of McDaniel and Devine who have shown that the set of Benders' cuts which are binding at the optimum to the linear relaxation of the mixed integer program, play an important role in determining an optimal mixed integer solution. As incidental results in our development, we provide some useful remarks regarding Benders' and Dantzig-Wolfe's decomposition procedures. The computational experience reported seems to support the expedients recommended in this paper.     

Capacity expansion and cost efficiency improvement in the warehouse problem

The warehouse problem with deterministic production cost, selling prices, and demand was introduced in the 1950s and there is a renewed interest recently due to its applications in energy storage and arbitrage. In this paper, we consider two extensions of the warehouse problem and develop efficient computational algorithms for finding their optimal solutions. First, we consider a model where the firm can invest in capacity expansion projects for the warehouse while simultaneously making production and sales decisions in each period. We show that this problem can be solved with a computational complexity that is linear in the product of the length of the planning horizon and the number of capacity expansion projects. We then consider a problem in which the firm can invest to improve production cost efficiency while simultaneously making production and sales decisions in each period. The resulting optimization problem is non‐convex with integer decision variables. We show that, under some mild conditions on the cost data, the problem can be solved in linear computational time. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 367–373, 2016     

A face search heuristic algorithm for optimizing over the efficient set

The problem of optimizing a linear function over the efficient set of a multiple objective linear program is an important but difficult problem in multiple criteria decision making. In this article we present a flexible face search heuristic algorithm for the problem. Preliminary computational experiments indicate that the algorithm gives very good estimates of the global optimum with relatively little computational effort. © 1993 John Wiley & Sons, Inc.     

Nonadjacent extreme point methods for solving linear programs

In this article we present some advanced basis or block-pivoting, relaxation, and feasible direction methods for solving linear programming problems. Preliminary computational results appear to indicate that the former two types of simplex-based procedures may hold promise for solving linear programming problems, unlike the third type of scheme which is shown to be computationally unattractive.     

基于多路归并的演绎故障模拟方法

提出了一个基于多路归并技术的演绎故障模拟方法,该方法对于集合运算∪,∩,-的计算复杂性是拟线性的,从而保证本文所提出的故障模拟方法的计算复杂性是拟线性的。     

一种针对基因识别的GHMM简化算法

广义隐Markov模型是计算机基因识别的一种重要模型,它克服了传统隐Markov模型的状态段长成几何分布的缺陷,更加适合于计算机基因识别。其缺点在于计算量大,需要采用有效的简化算法。利用基因的结构特点,在不附加额外限制条件的情况下,提出了一种新的简化算法,其计算复杂度是序列长度的线性函数。对实际生物序列数据的测试结果表明了此简化算法的有效性。     

攻击大目标子母弹射击概率的分析与估算

射击概率是子母弹武器效能分析的重要参数,本文以攻击大（线）目标子母弹为对象,提出一种计算命中概率的简便的近似法,计算结果表明该方法计算量小,计算精度工程上可接受;本文还引出了子母弹封锁概率的概念,并作了初步分析。本文结果对子母弹武器论证与设计使用将提供有益的参考。     

Duality in fractional programming

This paper develops theoretical and computational aspects of the dual problem in linear fractional programming. This is done on the basis of two alternative methods for solving the primal fractional programming problem, both of which were presented in earlier literature. Parametric changes in the resource-vector are considered, and attention is given to infinitesimal as well as to discrete changes.     

An exact network flow formulation for cell‐based evacuation in urban areas

In the literature two common macroscopic evacuation planning approaches exist: The dynamic network flow approach and the Cell–Transmission–Based approach. Both approaches have advantages and disadvantages. Many efficient solution approaches for the dynamic network flow approach exist so that realistic problem instances can be considered. However, the consideration of (more) realistic aspects (eg, density dependent travel times) results in non‐linear model formulations. The Cell‐Transmission‐Based approach on the other hand considers realistic traffic phenomena like shock waves and traffic congestion, but this approach leads to long computational times for realistic problem instances. In this article, we combine the advantages of both approaches: We consider a Cell‐Transmission‐Based Evacuation Planning Model (CTEPM) and present a network flow formulation that is equivalent to the cell‐based model. Thus, the computational costs of the CTEPM are enormously reduced due to the reformulation and the detailed representation of the traffic flow dynamics is maintained. We investigate the impacts of various evacuation scenario parameters on the evacuation performance and on the computational times in a computational study including 90 realistic instances.     

A generalized euclidean procedure for integer linear programs

This paper investigates a new procedure for solving the general-variable pure integer linear programming problem. A simple transformation converts the problem to one of constructing nonnegative integer solutions to a system of linear diophantine equations. Rubin's sequential algorithm, an extension of the classic Euclidean algorithm, is used to find an integer solution to this system of equations. Two new theorems are proved on the properties of integer solutions to linear systems. This permits a modified Fourier-Motzkin elimination method to be used to construct a nonnegative integer solution. An experimental computer code was developed for the algorithm to solve some test problems selected from the literature. The computational results, though limited, are encouraging when compared with the Gomory all-integer algorithm.     

A finite algorithm for concave minimization over a polyhedron

We present a new algorithm for solving the problem of minimizing a nonseparable concave function over a polyhedron. The algorithm is of the branch-and-bound type. It finds a globally optimal extreme point solution for this problem in a finite number of steps. One of the major advantages of the algorithm is that the linear programming subproblems solved during the branch-and-bound search each have the same feasible region. We discuss this and other advantages and disadvantages of the algorithm. We also discuss some preliminary computational experience we have had with our computer code for implementing the algorithm. This computational experience involved solving several bilinear programming problems with the code.     

Application of generalized benders decomposition to a nonlinear distribution system design problem

The Benders decomposition method has been successfully applied to a classic multistage, multiproduct distribution-system design problem with fixed and linear variable costs. In other applications, however, distribution-center variable throughput costs often show nonlinearity due to economies of scale. This article extends the standard problem formulation to a nonlinear distribution-system design problem and incorporates the generalized Benders decomposition method in an efficient solution algorithm. Approximate dual prices are generated by solving linear instead of concave subproblems. Thereafter these prices are adjusted to induce a more accurate representation of the concave cost function before they are incorporated in the Benders cuts, which are used to generate new binary solutions. The computational results are encouraging.     

Application of disjunctive programming to the linear complementarity problem

In this article we address the question of developing deep cuts for disjunctive programs using rectilinear distance measures. The method is applied to linear complementarity problems where the matrix M need not be copositive plus. Some modifications that are needed as a computational expediency are discussed. The computation results for matrix M of size up to 30 × 30 are discussed.     

WENO格式权重分析与改进

为了优化WENO格式计算性能,在对Jiang和Shu的经典WENO格式(记为WENO-JS)加权方法分析的基础上,通过引入间接光滑指数,构造出一种新的WENO格式——WENO-E格式,取得减小间断区耗散的效果。理论分析表明,该格式与WENO-JS格式计算效率基本相同,可达到相同阶的计算精度;但在相同网格下,较之WENO-JS格式,该格式对光滑区域的求解有更小的截断误差,对间断的捕捉有更高的分辨率。与WENO-JS格式相比,采用WENO-E格式进行线性迁移方程、非线性Burgers方程、欧拉方程等相关问题的数值实验,均能取得更好的数值结果。     

基于时滞分割法的具有leakage项时滞的离散型神经网络状态估计

摘要：研究一类具有leakage时滞的离散型神经网络的状态估计问题．通过构造新的Lyapunov泛函得到保证估计误差全局渐近稳定的充分条件,并通过求解一个线性矩阵不等式（LMI）得到状态估计器的增益矩阵．采用一种新的时滞分割方法将变时滞区间分割为多个子区间,使该结果在获得更小的保守性同时也降低了计算的复杂度．     

A streamlined simplex approach to the singly constrained transportation problem

A primal simplex procedure is developed to solve transportation problems with an arbitrary additional linear constraint. The approach is a specialization of the Double Reverse Method of Charnes and Cooper. Efficient procedures for pricing-out the basis, determining representations, and implementing the change of basis are presented. These procedures exploit the pure transportation substructure in such a manner that full advantage may be taken of the computational schemes and list structures used to store and update the basis in codifying the MODI method. Furthermore, the pricing-out and change-of-basis procedures are organized in a manner that permits the calculations for one to be utilized in the other. Computational results are presented which indicate that this method is at least 50 times faster than the state-of-the-art LP code, APEX-III. Methods for obtaining basic primal “feasible” starts and “good” feasible integer solutions are also presented.     

基于正交最小二乘估计的非线性时间序列的预测

在对非线性时间序列的短期预测中经常采用局部线性化的预测算法 ,原有的算法使用普通最小二乘法 (LS)估计近似线性模型的参数。对于存在噪声的数据 ,该算法的数值稳定性较差。本文在对非线性空间进行局部线性化的基础上 ,采用正交最小二乘方法 (OLS)对线性模型同时进行结构选择与参数辨识 ,改善了数值的病态特性 ,增强了算法的稳定性     

An assumption-free convergence analysis for a perturbation of the scaling algorithm for linear programs,with application to the L1 estimation problem

This article is concerned with the scaling variant of Karmarkar's algorithm for linear programming problems. Several researchers have presented convergence analyses for this algorithm under various nondegeneracy types of assumptions, or under assumptions regarding the nature of the sequence of iterates generated by the algorithm. By employing a slight perturbation of the algorithm, which is computationally imperceptible, we are able to prove without using any special assumptions that the algorithm converges finitely to an ε-optimal solution for any chosen ε > 0, from which it can be (polynomically) rounded to an optimum, for ε > 0 small enough. The logarithmic barrier function is used as a construct for this analysis. A rounding scheme which produces an optimal extreme point solution is also suggested. Besides the non-negatively constrained case, we also present a convergence analysis for the case of bounded variables. An application in statistics to the L₁ estimation problem and related computational results are presented.     

Concise RLT forms of binary programs: A computational study of the quadratic knapsack problem

The reformulation‐linearization technique (RLT) is a methodology for constructing tight linear programming relaxations of mixed discrete problems. A key construct is the multiplication of “product factors” of the discrete variables with problem constraints to form polynomial restrictions, which are subsequently linearized. For special problem forms, the structure of these linearized constraints tends to suggest that certain classes may be more beneficial than others. We examine the usefulness of subsets of constraints for a family of 0–1 quadratic multidimensional knapsack programs and perform extensive computational tests on a classical special case known as the 0–1 quadratic knapsack problem. We consider RLT forms both with and without these inequalities, and their comparisons with linearizations derived from published methods. Interestingly, the computational results depend in part upon the commercial software used. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2010