ABS methods and ABSPACK for linear systems and optimization: A review

ABS methods are a large class of methods, based upon the Egervary rank reducing algebraic process, first introduced in 1984 by Abaffy, Broyden and Spedicato for solving linear algebraic systems, and later extended to nonlinear algebraic equations, to optimization problems and other fields; software based upon ABS methods is now under development. Current ABS literature consists of about 400 papers. ABS methods provide a unification of several classes of classical algorithms and more efficient new solvers for a number of problems. In this paper we review ABS methods for linear systems and optimization, from both the point of view of theory and the numerical performance of ABSPACK.Work partially supported by ex MURST 60% 2001 funds.E. Spedicato     

Fast algorithms for scheduling with learning effects and time-dependent processing times on a single machine

We consider scheduling problems with learning/deterioration effects and time-dependent processing times on a single machine, with or without due date assignment considerations. By reducing them to a special assignment problem on product matrices, we solve all these problems in near-linear time. This improves the time complexity of previous algorithms for some scheduling problems and establishes the fast polynomial solvability for several other problems.     

正交约束优化问题的一阶算法

带有正交约束的矩阵优化问题在材料计算、统计及数据分析等领域中有着广泛的应用.由于正交约束的可行域是Stiefel流形,一直以来流形上的优化方法是求解这一问题的主要方法.近年来,随着实际应用问题所要求的变量规模的扩大,传统的流形优化方法在计算上的劣势显现出来,而一些迭代简单、收敛快的新算法逐渐被提出.通过收缩方法、非收缩可行方法、不可行方法三个类别分别来介绍求解带有正交约束的矩阵优化问题的最新算法.通过分析这些方法的主要特性,以及应用问题的要求,对这类问题算法设计的研究进行了展望.     

A comparison between a primal and a dual cutting plane algorithm for posynomial geometric programming problems

In this paper, primal and dual cutting plane algorithms for the solution of posynomial geometric programming problems are presented. It is shown that these cuts are deepest, in the sense that they cut off as much of the infeasible set as possible. Problems of nondifferentiability in the dual cutting plane are circumvented by the use of a subgradient. Although the resulting dual problem seems easier to solve, the computational experience seems to show that the primal cutting plane outperforms the dual.     

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.     

Global Convergence Analysis of Algorithms for Finding Feasible Points in Norm-Relaxed MFD

This paper introduces two new algorithms for finding initial feasible points from initial infeasible points for the recently developed norm-relaxed method of feasible directions (MFD). Their global convergence is analyzed. The theoretical results show that both methods are globally convergent; one of them guarantees finding a feasible point in a finite number of steps. These two methods are very convenient to implement in the norm-relaxed MFD. Numerical experiments are carried out to demonstrate their performance on some classical test problems and to compare them with the traditional method of phase I problems. The numerical results show that the methods proposed in this paper are more effective than the method of phase I problems in the norm-relaxed MFD. Hence, they can be used for finding initial feasible points for other MFD algorithms and other nonlinear programming methods.     

线性规划的单纯形法及其发展

本文给出了一种新的原对偶单纯形法,并通过它分析了隐藏在经典单纯形法中的对偶信息．我们重新评价经典单纯形法并详细讨论了它与现代单纯形法之间的联系．两个修改版本一并给出．新算法具有计算量小和实施简单等特点,计算效果也不错．初步数值实验表明现代单纯形法比经典方法具有明显的优越性．     

A warm-start dual simplex solution algorithm for the minimum flow networks with postoptimality analyses

This paper presents an algorithm for finding the minimum flow in general (s, t) networks with m directed arcs. The minimum flow problem (MFP) arises in many transportation and communication systems. Here, we construct a linear programming (LP) formulation of MFP and develop a simplex-type algorithm to find a minflow. Unlike other simplex-like algorithms, the algorithm developed here starts with an incomplete Basic Variable Set (BVS) initially and then fills-up the BVS completely while pushing toward an optimal vertex. If this results in pushing too far into infeasibility, the next step pulls the solution back to feasibility. Both phases use the Gauss-Jordan pivoting transformation used in the standard simplex and dual simplex algorithms.

The proposed approach has some common features with Dantzig's self-dual simplex algorithm. We have avoided, however, the need for extra variables (slack and surplus) for equality constraints, as well as an artificial constraint for the self-dual algorithm for initial phase and the dual simplex, respectively. The proposed Push phase takes at most 2m − 1 iterations to complete a tree (this augmentation may not be feasible). An infeasible path to the optimal solution contains at most 2m − 1 iterations; therefore in theory, the algorithm needs a sequence of at most 4m − 2 iterations.

Furthermore, the algorithm developed here makes available the full power of LP perturbation analysis and facilitates introducing network structural changes and side constraints also. It can also detect clerical errors in data entry which may make the problem infeasible or unbounded. It is assumed that the reader is familiar with LP terminology.     

An infeasible interior-point arc-search algorithm for nonlinear constrained optimization

Numerical Algorithms - In this paper, we propose an infeasible arc-search interior-point algorithm for solving nonlinear programming problems. Most algorithms based on interior-point methods are...     

Two phase algorithms for the bi-objective assignment problem

In this paper, we present several algorithms for the bi-objective assignment problem. The algorithms are based on the two phase method, which is a general technique to solve multi-objective combinatorial optimisation (MOCO) problems.     

An Heuristic Method for Solving Time-Sensitive Routeing Problems

Many vehicle scheduling situations require careful monitoring and control of the time a vehicle is on the road. Setting time limits as rigid constraints on a vehicle scheduling problem is usually not appropriate since minor violations of such constraints do not really imply that a solution is infeasible. An heuristic method for solving vehicle scheduling problems in which time is an important factor has been developed. The heuristic creates routes based on a "time density function" which identifies clusters of stops and chooses stops from these clusters to form a route. Important considerations balancing overtime costs, overnight route costs and travel costs to and from far clusters of stops are part of the heuristic. The method has been tested on 10 days of data from a large food distributor in the midwestern United States and found to affect significantly both variable and fixed costs in these commercial problems. The smallest of these problems had 110 stops, while the largest had 223. A modest amount of computer time (under 15 seconds in every case) was required to generate the assignment of stops to trucks and produce routes for the vehicles.     

Differential evolution with multi-constraint consensus methods for constrained optimization

Constrained optimization is an important research topic that assists in quality planning and decision making. To solve such problems, one of the important aspects is to improve upon any constraint violation, and thus bring infeasible individuals to the feasible region. To achieve this goal, different constraint consensus methods have been introduced, but no single method performs well for all types of problems. Hence, in this research, for solving constrained optimization problems, we introduce different variants of the Differential Evolution algorithm, with multiple constraint consensus methods. The proposed algorithms are tested and analyzed by solving a set of well-known bench mark problems. For further improvements, a local search is applied to the best variant. We have compared our algorithms among themselves, as well as with other state of the art algorithms. Those comparisons show similar, if not better performance, while also using significantly lower computational time.     

关于可靠性设施布局问题的近似算法

设施布局问题的研究始于20世纪60年代,主要研究选择修建设施的位置和数量,以及与需要得到服务的城市之间的分配关系,使得设施的修建费用和设施与城市之间的连接费用之和达到最小.现实生活中, 受自然灾害、工人罢工、恐怖袭击等因素的影响,修建的设施可能会出现故障, 故连接到它的城市无法得到供应,这就直接影响到了整个系统的可靠性.针对如何以相对较小的代价换取设施布局可靠性的提升,研究人员提出了可靠性设施布局问题.参考经典设施布局问题的贪婪算法、原始对偶算法和容错性问题中分阶段分层次处理的思想,设计了可靠性设施布局问题的一个组合算法.该算法不仅在理论上具有很好的常数近似度,而且还具有运算复杂性低的优点.这对于之前的可靠性设施布局问题只有数值实验算法, 是一个很大的进步.     

A New Infeasible Mehrotra-Type Predictor–Corrector Algorithm for Nonlinear Complementarity Problems Over Symmetric Cones

This paper establishes a theoretical framework of infeasible Mehrotra-type predictor–corrector algorithm for nonmonotone nonlinear complementarity problems over symmetric cones which can be regarded as an extension the Mehrotra’s algorithm proposed by Salahi et al. (On Mehrotra-type predictor–corrector algorithms. SIAM J Optim 18(4):1377–1397, 2005) from nonnegative orthant to symmetric cone. The iteration complexity of the algorithm is estimated, and some numerical results are provided. The numerical results show that the algorithm is efficient and reliable.     

Efficient dual simplex algorithms for the assignment problem

Efficient algorithms based upon Balinski's signature method are described for solving then × n assignment problem. These algorithms are special variants of the dual simplex method and are shown to have computational bounds of O(n ³). Variants for solving sparse assignment problems withm arcs that require O(m) space and O(mn + n ² logn) time in the worst case are also presented.This research was supported in part by the National Science Foundation under Grant No. MCS-8006064 and by the Army Research Office under Contracts No. DAAG 29-82-K0163 and DAAG 29-83-K0106     

On strongly polynomial dual simplex algorithms for the maximum flow problem

Several pivot rules for the dual network simplex algorithm that enable it to solve a maximum flow problem on ann-node,m-arc network in at most 2nm pivots and O(n ² m) time are presented. These rules are based on the concept of apreflow and depend upon the use of node labels which are either the lengths of a shortestpseudoaugmenting path from those nodes to the sink node orvalid underestimates of those lengths. Extended versions of our algorithms are shown to solve an important class of parametric maximum flow problems with no increase in the worst-case pivot and time bounds of these algorithms. This research was supported in part by NSF Grants DMS 91-06195, DMS 94-14438, and CDR 84-21402 and DOE Grant DE-FG02-92ER25126.     

Computer Codes for the Analysis of Infeasible Linear Programs

As linear programs have grown larger and more complex, infeasible models are appearing more frequently. Because of the scale and complexity of the models, automated assistance is very often needed in determining the cause of the infeasibility so that model repairs can be made. Fortunately, researchers have developed algorithms for analysing infeasible LPs in recent years, and these have lately found their way into commercial LP computer codes. This paper briefly reviews the underlying algorithms, surveys the computer codes, and compares their performance on a set of test problems.     

An alternative formulation for the fuzzy assignment problem

The existing assignment problems for assigning n jobs to n individuals are limited to the considerations of cost or profit measured as crisp. However, in many real applications, costs are not deterministic numbers. This paper develops a procedure based on Data Envelopment Analysis method to solve the assignment problems with fuzzy costs or fuzzy profits for each possible assignment. It aims to obtain the points with maximum membership values for the fuzzy parameters while maximizing the profit or minimizing the assignment cost. In this method, a discrete approach is presented to rank the fuzzy numbers first. Then, corresponding to each fuzzy number, we introduce a crisp number using the efficiency concept. A numerical example is used to illustrate the usefulness of this new method.     

Multisection in Interval Branch-and-Bound Methods for Global Optimization II. Numerical Tests

We have investigated variants of interval branch-and-bound algorithms for global optimization where the bisection step was substituted by the subdivision of the current, actual interval into many subintervals in a single iteration step. The results are published in two papers, the first one contains the theoretical investigations on the convergence properties. An extensive numerical study indicates that multisection can substantially improve the efficiency of interval global optimization procedures, and multisection seems to be indispensable in solving hard global optimization problems in a reliable way.     

A sparse proximal implementation of the LP dual active set algorithm

We present an implementation of the LP Dual Active Set Algorithm (LP DASA) based on a quadratic proximal approximation, a strategy for dropping inactive equations from the constraints, and recently developed algorithms for updating a sparse Cholesky factorization after a low-rank change. Although our main focus is linear programming, the first and second-order proximal techniques that we develop are applicable to general concave–convex Lagrangians and to linear equality and inequality constraints. We use Netlib LP test problems to compare our proximal implementation of LP DASA to Simplex and Barrier algorithms as implemented in CPLEX. This material is based upon work supported by the National Science Foundation under Grant No. 0203270.