An exterior point simplex algorithm for (general) linear programming problems

We present an exterior point simplex type algorithm that possesses a new monotonic property. A dual feasible basic solution is required to start with. Intermediate solutions are neither primal nor dual feasible. Cycling-free pivoting rules and an exponentional example are presented.     

An infeasible interior-point algorithm with full-Newton step for linear optimization

Recently, Roos (SIAM J Optim 16(4):1110–1136, 2006) presented a primal-dual infeasible interior-point algorithm that uses full-Newton steps and whose iteration bound coincides with the best known bound for infeasible interior-point algorithms. In the current paper we use a different feasibility step such that the definition of the feasibility step in Mansouri and Roos (Optim Methods Softw 22(3):519–530, 2007) is a special case of our definition, and show that the same result on the order of iteration complexity can be obtained.      

An O（rL） Infeasible Interior-point Algorithm for Symmetric Cone LCP via CHKS Function

In this paper, we propose a theoretical framework of an infeasible interior-point algorithm for solving monotone linear cornplementarity problems over symmetric cones （SCLCP）. The new algorithm gets Newton-like directions from the Chen-Harker-Kanzow-Smale （CHKS） smoothing equation of the SCLCP. It possesses the following features： The starting point is easily chosen; one approximate Newton step is computed and accepted at each iteration; the iterative point with unit stepsize automatically remains in the neighborhood of central path; the iterative sequence is bounded and possesses （9（rL） polynomial-time complexity under the monotonicity and solvability of the SCLCP.     

Dual simplex method for GUB problems

The dual simplex method for generalized upper bound (GUB) problems is presented. One of the major operations in the dual simplex method is to update the elements of therth row, wherer is the index for the leaving basic variable. Those updated elements are used for the ratio test to determine the entering basic variabble. A very simple formula for therth row update for the dual simplex method for a GUB problem is derived, which is similar to the formula for the standard linear program. This derivation is based on the change key operation, which is to exchange the key column and its counterpart in the nonkey section. The change key operation is possible because of a theorem that guarantees the existence of such a counterpart.     

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

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

Eliminating columns in the simplex method for linear programming

We propose a column-eliminating technique for the simplex method of linear programming. A pricing criterion is developed for checking whether a dual hyperplane corresponding to a column intersects a simplex containing all of the optimal dual feasible solutions. If the dual hyperplane has no intersection with this simplex, we can eliminate the corresponding column from further computation during the course of the simplex method.The author is grateful for many discussions with Professor G. B. Dantzig, Stanford University, and for his valuable suggestions about this work. The author also gratefully acknowledges the editor and two referees for their very helpful comments, corrections, and remarks.     

An algorithm for the generalized quadratic assignment problem

This paper reports on a new algorithm for the Generalized Quadratic Assignment problem (GQAP). The GQAP describes a broad class of quadratic integer programming problems, wherein M pair-wise related entities are assigned to N destinations constrained by the destinations’ ability to accommodate them. This new algorithm is based on a Reformulation Linearization Technique (RLT) dual ascent procedure. Experimental results show that the runtime of this algorithm is as good or better than other known exact solution methods for problems as large as M=20 and N=15. Current address of P.M. Hahn: 2127 Tryon Street, Philadelphia, PA 19146-1228, USA.     

An approximation algorithm for multidimensional assignment problems minimizing the sum of squared errors

Given a complete k-partite graph G=(V₁,V₂,…,V_k;E) satisfying |V₁|=|V₂|=?=|V_k|=n and weights of all  k-cliques of G, the  k-dimensional assignment problem finds a partition of vertices of G into a set of (pairwise disjoint) n k-cliques that minimizes the sum total of weights of the chosen cliques. In this paper, we consider a case in which the weight of a clique is defined by the sum of given weights of edges induced by the clique. Additionally, we assume that vertices of G are embedded in the d-dimensional space Q^d and a weight of an edge is defined by the square of the Euclidean distance between its two endpoints. We describe that these problem instances arise from a multidimensional Gaussian model of a data-association problem.We propose a second-order cone programming relaxation of the problem and a polynomial time randomized rounding procedure. We show that the expected objective value obtained by our algorithm is bounded by (5/2−3/k) times the optimal value. Our result improves the previously known bound (4−6/k) of the approximation ratio.     

An in-core/out-of-core method for solving large scale assignment problems

We describe how the shortest augmenting path method can be used as basis for a so called in-core/out-of-core approach for solving large assignment problems in which the data cannot be kept in central memory of a computer. Here we start by solving the assignment problem on a sparse subgraph and then we introduce the remaining edges in an outpricing/reoptimization phase. We introduce several strategies which enable to keep the working subgraph sparse throughout the procedure and even lead to an all in-core code which is faster than the basic shortest augmenting path code.

---

Zusammenfassung Wir beschreiben einen sogenannten In-Core/Out-of-Core Ansatz auf der Basis der kürzesten erweiternden Wege Methode für die Lösung gro\er Zuordnungsprobleme, für die die gesamte Kostenmatrix nicht im Zentralspeicher des Rechners gehalten werden kann. Bei diesem Ansatz wird in einer ersten Phase ein Zuordnungsproblem über einem dünnen Teilgraph optimal gelöst. In einer zweiten Phase werden dann die nicht berücksichtigen Kanten mittels der optimalen Duallösung bewertet (outpricing) und gegebenenfalls eine Reoptimierung durchgeführt. Durch Anwendung spezieller Strategien wird es möglich, während der gesamten Lösung den im Zentralspeicher abzuspeichernden Teilgraphen dünn zu halten. Weiterhin zeigt sich, da\ dieser Ansatz zu einem neuen Verfahren führt, das der zugrunde liegenden kürzesten erweiternden Wege Methode überlegen ist.

     

An alternative approach for unbalanced assignment problem via genetic algorithm

This paper presents an alternative approach using genetic algorithm to a new variant of the unbalanced assignment problem that dealing with an additional constraint on the maximum number of jobs that can be assigned to some agent(s). In this approach, genetic algorithm is also improved by introducing newly proposed initialization, crossover and mutation in such a way that the developed algorithm is capable to assign optimally all the jobs to agents. Computational results with comparative performance of the algorithm are reported for four test problems.     

Markov decision processes for infinite horizon problems solved with the cosine simplex method

This article presents a new method of linear programming (LP) for solving Markov decision processes (MDPs) based on the simplex method (SM). SM has shown to be the most efficient method in many practical problems; unfortunately, classical SM has an exponential complexity. Therefore, new SMs have emerged for obtaining optimal solutions in the most efficient way. The cosine simplex method (CSM) is one of them. CSM is based on the Karush Kuhn Tucker conditions, and is able to efficiently solve general LP problems. This work presents a new method named the Markov Cosine Simplex Method (MCSM) for solving MDP problems, which is an extension of CSM. In this article, the efficiency of MCSM is compared to the traditional revised simplex method (RSM); experimental results show that MCSM is far more efficient than RSM.     

A ROBUST SUPERLINEARLY CONVERGENT ALGORITHM FOR LINEARLY CONSTRAINED OPTIMIZATION PROBLEMS UNDER DEGENERACY

1.IntroductionTheproblemconsideredinthispaperiswhereX={xER"laTx5hi,jEI={l,.'.,m}},ajeR"(jEI)areallcolumn*ThisresearchissupportedbytheNationalNaturalSciencesFoundationofChinaandNaturalSciencesFoundationofHunanProvince.vectors,hiERI(j6I)areallscalars,andf:R"-- Risacontinuouslydifferentiablefunction.Weonlyconsiderinequalityconstraintsheresinceanyequalitycanbeexpressedastwoinequalities.Withoutassumingregularityofthelinearconstraints,thereisnotanydifficultyinextendingtheresultstothegenera…     

An approximation algorithm for the generalized assignment problem

The generalized assignment problem can be viewed as the following problem of scheduling parallel machines with costs. Each job is to be processed by exactly one machine; processing jobj on machinei requires timep _ij and incurs a cost ofc _ij ; each machinei is available forT _i time units, and the objective is to minimize the total cost incurred. Our main result is as follows. There is a polynomial-time algorithm that, given a valueC, either proves that no feasible schedule of costC exists, or else finds a schedule of cost at mostC where each machinei is used for at most 2T _i time units.We also extend this result to a variant of the problem where, instead of a fixed processing timep _ij , there is a range of possible processing times for each machine—job pair, and the cost linearly increases as the processing time decreases. We show that these results imply a polynomial-time 2-approximation algorithm to minimize a weighted sum of the cost and the makespan, i.e., the maximum job completion time. We also consider the objective of minimizing the mean job completion time. We show that there is a polynomial-time algorithm that, given valuesM andT, either proves that no schedule of mean job completion timeM and makespanT exists, or else finds a schedule of mean job completion time at mostM and makespan at most 2T. Research partially supported by an NSF PYI award CCR-89-96272 with matching support from UPS, and Sun Microsystems, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.Research supported in part by a Packard Fellowship, a Sloan Fellowship, an NSF PYI award, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.     

An infeasible interior-point algorithm for solving primal and dual geometric programs

In this paper an algorithm is presented for solving the classical posynomial geometric programming dual pair of problems simultaneously. The approach is by means of a primal-dual infeasible algorithm developed simultaneously for (i) the dual geometric program after logarithmic transformation of its objective function, and (ii) its Lagrangian dual program. Under rather general assumptions, the mechanism defines a primal-dual infeasible path from a specially constructed, perturbed Karush-Kuhn-Tucker system.Subfeasible solutions, as described by Duffin in 1956, are generated for each program whose primal and dual objective function values converge to the respective primal and dual program values. The basic technique is one of a predictor-corrector type involving Newton’s method applied to the perturbed KKT system, coupled with effective techniques for choosing iterate directions and step lengths. We also discuss implementation issues and some sparse matrix factorizations that take advantage of the very special structure of the Hessian matrix of the logarithmically transformed dual objective function. Our computational results on 19 of the most challenging GP problems found in the literature are encouraging. The performance indicates that the algorithm is effective regardless of thedegree of difficulty, which is a generally accepted measure in geometric programming. Research supported in part by the University of Iowa Obermann Fellowship and by NSF Grant DDM-9207347.     

An extension of Karmarkar's projective algorithm for convex quadratic programming

We present an extension of Karmarkar's linear programming algorithm for solving a more general group of optimization problems: convex quadratic programs. This extension is based on the iterated application of the objective augmentation and the projective transformation, followed by optimization over an inscribing ellipsoid centered at the current solution. It creates a sequence of interior feasible points that converge to the optimal feasible solution in O(Ln) iterations; each iteration can be computed in O(Ln ³) arithmetic operations, wheren is the number of variables andL is the number of bits in the input. In this paper, we emphasize its convergence property, practical efficiency, and relation to the ellipsoid method.     

An improved origin-based algorithm for solving the combined distribution and assignment problem

This paper is to further study the origin-based (OB) algorithm for solving the combined distribution and assignment (CDA) problem, where the trip distribution follows a gravity model and the traffic assignment is a user-equilibrium model. Recently, the OB algorithm has shown to be superior to the Frank–Wolfe (FW) algorithm for the traffic assignment (TA) problem and better than the Evans’ algorithm for the CDA problem in both computational time and solution accuracy. In this paper, a modified origin–destination (OD) flow update strategy proposed by Huang and Lam [Huang, H.J., Lam, W.H.K., 1992. Modified Evans’ algorithms for solving the combined trip distribution and assignment problem. Transportation Research B 26 (4), 325–337] for CDA with the Evans’ algorithm is adopted to improve the OB algorithm for solving the CDA problem. Convergence proof of the improved OB algorithm is provided along with some preliminary computational results to demonstrate the effect of the modified OD flow update strategy embedded in the OB algorithm.     

Finite algorithm for generalized linear multiplicative programming

The nonconvex problem of minimizing the sum of a linear function and the product of two linear functions over a convex polyhedron is considered. A finite algorithm is proposed which either finds a global optimum or shows that the objective function is unbounded from below in the feasible region. This is done by means of a sequence of primal and/or dual simplex iterations.The first author gratefully acknowledges the research support received as Visiting Professor of the Dipartimento di Statistica e Matematica Applicata all' Economia, Universitá di Pisa, Pisa, Italy, Spring 1992.     

An inertial shrinking projection algorithm for split common fixed point problems

In this paper, the purpose is to introduce and study a new modified shrinking projection algorithm with inertial effects, which solves split common fixed point problems in Banach spaces. The corresponding strong convergence theorems are obtained without the assumption of semi-compactness on mappings. Finally, some numerical examples are presented to illustrate the results in this paper.     

A new pivoting algorithm for the linear complementarity problem allowing for an arbitrary starting point

The linear complementarity problem is to find nonnegative vectors which are affinely related and complementary. In this paper we propose a new complementary pivoting algorithm for solving the linear complementarity problem as a more efficient alternative to the algorithms proposed by Lemke and by Talman and Van der Heyden. The algorithm can start at an arbitrary nonnegative vector and converges under the same conditions as Lemke's algorithm.This research is part of the VF-program Competition and Cooperation.     

A new algorithm for pole assignment of single-input linear systems using state feedback

In this paper we present a new algorithm for the single-input pole assignment problem using state feedback. This algorithm is based on the Schur decomposition of the closed-loop system matrix, and the numerically stable unitary transformations are used whenever possible, and hence it is numerically reliable.The good numerical behavior of this algorithm is also illustrated by numerical examples.