第一阶段原有单纯形和对偶单纯形算法的计算比较

线性最优化广泛应用于经济与管理的各个领域.在线性规划问题的求解中,如果一个初始基本可行解没有直接给出,则常采用经典的两阶段法求解.对含有"≥"不等式约束的线性规划问题,讨论了第一阶段原有单纯形法和对偶单纯形法两种算法形式,并根据第一阶段问题的特点提出了改进的对偶单纯形枢轴准则.最后,通过大规模数值试验对两种算法进行计算比较,结果表明,改进后的对偶单纯形算法在计算效率上明显优于原有单纯形算法.     

变量有广义界线性规划的直接对偶单纯形法

本文讨论变量有广义界线性规划问题借助标准形线性规划同单纯形法技术，建立问题的一个直接对偶单纯形法。分析了方法的性质，给出了初始对偶可行基的计算方法，并用实例说明方法的具体操作。     

对于单纯形法矩阵描述的认识

从修正单纯形法的提出、对偶单纯形法的出现、对偶问题最优解的确定以及灵敏度分析的基本依据等四个方面阐述了对单纯形法矩阵描述的认识,充分显示出单纯形法矩阵描述在线性规划发展中的重要性.     

修正单纯形法的计算量的注记

对文献［１］、［２］指出的修正单纯形法的计算量提出了异议,并给出了修正单纯形法应有的计算量。     

线性规划单纯形法主元规则的几何分析

本文研究了线性规划单纯形法和对偶单纯形法主元规则的性质.利用直观的几何方法,结合对偶理论和灵敏度分析,得到了主元规则的特点,针对针对三种最常见的主元规则构造出不同的二维和三维例子,以此说明对每种主元规则都容易构造出其不优的反例,以及迭代次数多于约束个数的例子.所得结果有助于对单纯形法和对偶单纯形法的理解和研究.     

线性规划两阶段法的改进算法

将单纯形法与对偶单纯形法及其思想结合运用,对两阶段法引进人工变量的方式进行了改进,探索出一种最多引入一个人工变量,即可求得线性规划初始可行基的新算法,能有效地节约计算机的存储量和计算量。     

基于语言真值格蕴涵代数中对偶分子的推理性质

众所周知,代数结构已成功应用于经典与非经典逻辑中。沿袭这种思想,徐扬教授为语言真值格值命题逻辑的代数语义解释找到了一个语言真值格蕴涵代数(L-LIA)的方法。本文进一步研究L-LIA中对偶分子的推理性质,证明了对偶分子在一定程度上对算子∨、∧、→具有闭性,得到了一些有趣的新结果,特别是给出了它的一些推理性质,并验证了在Lv(9×2)中的相应结果,进而对蕴涵进行了拓展,得到了预线性性的逻辑推理性质,并证明了此推理性质的正确性。     

伪仿射对偶框架

对于给定冗余的仿射框架X（Ф）={Ф1,…,ФL）,存在对偶Y（ψ）={ψ1,…,ψL）,这个对偶可能不是仿射框架,因为它不满足Bessel条件．这样的对偶我们称为伪仿射对偶,并给出伪仿射对偶框架的一种构造公式．     

对偶双代数

在文献[1]中,作者引入了扭曲积（twistingproduct）概念,并指出量子偶（Drinfel’ddouble）D（H）为张量积代数的扭曲积．本文把扭曲积加以推广为扭曲模,并给出它的基本结构定理．同时,我们引进对偶Hopf模,它是[2]中对偶Hopf模的发展．     

一种新的对偶空间描述

本文描述了一种保持张量积的对偶空间．对有限维线性空间，它与经典对偶空间一致．在代数状态，它与Ｓｗｅｅｄｌｅｒ的代数对偶一致     

Computer algebra methods in the study of nonlinear differential systems

Some issues concerning computer algebra methods as applied to the qualitative analysis of differential equations with first integrals are discussed. The problems of finding stationary sets and analyzing their stability and bifurcations are considered. Special attention is given to algorithms for finding and analyzing peculiar stationary sets. It is shown that computer algebra tools, combined with qualitative analysis methods for differential equations, make it possible not only to enhance the computational efficiency of classical algorithms, but also to implement new approaches to the solution of well-known problems and, in this way, to obtain new results.     

Interior projection-like methods for monotone variational inequalities

We propose new interior projection type methods for solving monotone variational inequalities. The methods can be viewed as a natural extension of the extragradient and hyperplane projection algorithms, and are based on using non Euclidean projection-like maps. We prove global convergence results and establish rate of convergence estimates. The projection-like maps are given by analytical formulas for standard constraints such as box, simplex, and conic type constraints, and generate interior trajectories. We then demonstrate that within an appropriate primal-dual variational inequality framework, the proposed algorithms can be applied to general convex constraints resulting in methods which at each iteration entail only explicit formulas and do not require the solution of any convex optimization problem. As a consequence, the algorithms are easy to implement, with low computational cost, and naturally lead to decomposition schemes for problems with a separable structure. This is illustrated through examples for convex programming, convex-concave saddle point problems and semidefinite programming.The work of this author was partially supported by the United States–Israel Binational Science Foundation, BSF Grant No. 2002-2010.     

Auction algorithms for network flow problems: A tutorial introduction

This paper surveys a new and comprehensive class of algorithms for solving the classical linear network flow problem and its various special cases such as shortest path, max-flow, assignment, transportation, and transhipment problems. The prototype method, from which the other algorithms can be derived, is the auction algorithm for the assignment problem. This is an intuitive method that operates like a rel auction where persons compete for objects by raising their prices through competitive bidding; the prices can be viewed as dual variables. Conceptually, auction algorithms represent a significant departure from the cost improvement idea that underlies primal simplex and dual ascent methods; at any one iteration, they may deteriorate both the primal and the dual cost. Auction algorithms perform very well for several important types of problems, both in theory and in practice, and they are also well suited for parallel computation.     

A Frisch-Newton Algorithm for Sparse Quantile Regression

Recent experience has shown that interior-point methods using a log barrier approach are far superior to classical simplex methods for computing solutions to large parametric quantile regression problems. In many large empirical applications, the design matrix has a very sparse structure. A typical example is the classical fixed-effect model for panel data where the parametric dimension of the model can be quite large, but the number of non-zero elements is quite small. Adopting recent developments in sparse linear algebra we introduce a modified version of the Prisch-Newton algorithm for quantile regression described in Portnoy and Koenker~([28]). The new algorithm substantially reduces the storage (memory) requirements and increases computational speed. The modified algorithm also facilitates the development of nonparametric quantile regression methods. The pseudo design matrices employed in nonparametric quantile regression smoothing are inherently sparse in both the fidelity and roughness penalty components. Exploiting the sparse structure of these problems opens up a whole range of new possibilities for multivariate smoothing on large data sets via ANOVA-type decomposition and partial linear models.     

Steepest-edge simplex algorithms for linear programming

We present several new steepest-edge simplex algorithms for solving linear programming problems, including variants of both the primal and the dual simplex method. These algorithms differ depending upon the space in which the problem is viewed as residing, and include variants in which this space varies dynamically. We present computational results comparing steepest-edge simplex algorithms and approximate versions of them against simplex algorithms that use standard pivoting rules on truly large-scale realworld linear programs with as many as tens of thousands of rows and columns. These results demonstrate unambiguously the superiority of steepest-edge pivot selection criteria to other pivot selection criteria in the simplex method.The research of this author was supported in part by NSF Grants DMS 85-12277, DMS 91-0619 and CDR 84-21402.     

Parallelization Strategies for Rollout Algorithms

Rollout algorithms are innovative methods, recently proposed by Bertsekas et al. [3], for solving NP-hard combinatorial optimization problems. The main advantage of these approaches is related to their capability of magnifying the effectiveness of any given heuristic algorithm. However, one of the main limitations of rollout algorithms in solving large-scale problems is represented by their computational complexity. Innovative versions of rollout algorithms, aimed at reducing the computational complexity in sequential environments, have been proposed in our previous work [9]. In this paper, we show that a further reduction can be accomplished by using parallel technologies. Indeed, rollout algorithms have very appealing characteristics that make them suitable for efficient and effective implementations in parallel environments, thus extending their range of relevant practical applications.We propose two strategies for parallelizing rollout algorithms and we analyze their performance by considering a shared-memory paradigm. The computational experiments have been carried out on a SGI Origin 2000 with 8 processors, by considering two classical combinatorial optimization problems. The numerical results show that a good reduction of the execution time can be obtained by exploiting parallel computing systems.     

Parallel Asynchronous Schwarz and Multisplitting Methods for a Nonlinear Diffusion Problem

Parallel asynchronous subdomain algorithms with flexible communication for the numerical solution of nonlinear diffusion problems are presented. The discrete maximum principle is considered and the Schwarz alternating method and multisplitting methods are studied. A connection is made with M-functions for a classical nonlinear diffusion problem. Finally, computational experiments carried out on a shared memory multiprocessor are presented and analyzed.     

A GENERATOR AND A SIMPLEX SOLVER FOR NETWORK PIECEWISE LINEAR PROGRAMS

ＡＧＥＮＥＲＡＴＯＲＡＮＤＡＳＩＭＰＬＥＸＳＯＬＶＥＲＦＯＲＮＥＴＷＯＲＫＰＩＥＣＥＷＩＳＥＬＩＮＥＡＲＰＲＯＧＲＡＭＳＳＵＮＪＩＥ（孙捷）（ＩｎｓｔｉｔｕｔｅｏｆＡｐｐｌｉｅｄＭａｔｈｅｍｅｍａｔｉｃｓ，ｔｈｅＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉ...     

A dual ascent procedure for the set partitioning problem

The set partitioning problem is a fundamental model for many important real-life transportation problems, including airline crew and bus driver scheduling and vehicle routing.In this paper we propose a new dual ascent heuristic and an exact method for the set partitioning problem. The dual ascent heuristic finds an effective dual solution of the linear relaxation of the set partitioning problem and it is faster than traditional simplex based methods. Moreover, we show that the lower bound achieved dominates the one achieved by the classic Lagrangean relaxation of the set partitioning constraints. We describe a simple exact method that uses the dual solution to define a sequence of reduced set partitioning problems that are solved by a general purpose integer programming solver. Our computational results indicate that the new bounding procedure is fast and produces very good dual solutions. Moreover, the exact method proposed is easy to implement and it is competitive with the best branch and cut algorithms published in the literature so far.