TITLE

A NOTE ON THE CRISS-CROSS ALGORITHM

AUTHOR(S)
Shields, W. S.
PUB. DATE
September 1976
SOURCE
Management Science;Sep76, Vol. 23 Issue 1, p103
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
The article comments on the article "The Criss-Cross Method for Solving Linear Programming Problems," by Sanley Zionts in the March 1969 issue. According to the author, Zionts offers an effective "Criss-cross" linear programming method for solving small problems, but it becomes increasingly difficult as the problem increases in size. It is shown how the algorithm in the original article can be salvaged by changing a minor pivot rule. This altered algorithm was tested on 5 real world problems and 23 simulated problems, and converged all the problems with considerably less pivots than Zionts' algorithm.
ACCESSION #
11155101

 

Related Articles

  • A NOTE ON THE CRISS-CROSS ALGORITHM. Shields, W. S. // Management Science;Sep76, Vol. 23 Issue 1, p103 

    The article comments on the article "The Criss-Cross Method for Solving Linear Programming Problems," by Sanley Zionts in the March 1969 issue. According to the author, Zionts offers an effective "Criss-cross" linear programming method for solving small problems, but it becomes increasingly...

  • Comments on the 'Classical' Derivation by Taha and Curry of Optimality Conditions in Linear Programming. Raike, William M.; Taylor, James G. // Operations Research;Jan/Feb73, Vol. 21 Issue 1, p371 

    This note points out some deficiencies in a recent paper [Opt. Res. 19 (1971), pages 1045–1050] concerning the classical derivation of optimality conditions in linear programming.

  • SCHEDULE OF FUTURE SOCIETY MEETINGS.  // Operations Research;Mar/Apr68, Vol. 16 Issue 2, p456 

    The article presents a calendar of meetings of the Operations Research Society of America. The meeting in Miami, Florida will be held from November 10 to 12, 1969 and will be chaired by Richard L. Patterson from the University of Florida-Gainesville. George W. Morgenthaler of Martin Marietta...

  • New Conical Internal Evolutive Linear Programming Algorithm. D'ALESSANDRO, P. // Journal of Optimization Theory & Applications;Nov2006, Vol. 131 Issue 2, p195 

    Optimality in the range space is expressed as a tangency condition for an affine set and a cone. In a previous paper, an algorithm was introduced that reaches tangency keeping the two sets nonintersecting. Here,we introduce an exact finite-convergence evolutive algorithm that reaches tangency...

  • MULTIPARAMETRIC LINEAR PROGRAMMING. Gal, Tomas; Nedoma, Josef // Management Science;Mar72, Vol. 18 Issue 7, p406 

    The multiparametric linear programming (MLP) problem for the right-hand sides (RHS) is to maximize z = cT x subject to Ax = b (λ), x ≧ 0, where b(λ) can be expressed in the form b(λ) = b* + Fλ, where F is a matrix of constant coefficients, and λ is a vector-parameter. The...

  • The Use of Cuts in Complementary Programming. Ibaraki, Toshihide // Operations Research;Jan/Feb73, Vol. 21 Issue 1, p353 

    A complementary programming problem is a linear programming problem with the additional restriction that xpxq=0 holds for each specified pair (xp, xq). This paper obtains constraints called C-cuts from the restriction xpxq=0, and uses them to facilitate the computation of the branch-and-bound...

  • Explicit Solutions of Interval Linear Programs. Xlobec, S.; Ben-Israel, A. // Operations Research;Jan/Feb73, Vol. 21 Issue 1, p390 

    This note gives conditions for an explicit (noniterative) representation of the set of optimal solutions of interval programming problems: maximize {(c, x): a≦Ax≦b} and standard programming problems: maximize {(c, x): Ax=b,0≦x≦u}.

  • New Branch-and-Cut Algorithm for Bilevel Linear Programming. Audet, C.; Savard, G.; Zghal, W. // Journal of Optimization Theory & Applications;Aug2007, Vol. 134 Issue 2, p353 

    Linear mixed 0-1 integer programming problems may be reformulated as equivalent continuous bilevel linear programming (BLP) problems. We exploit these equivalences to transpose the concept of mixed 0-1 Gomory cuts to BLP. The first phase of our new algorithm generates Gomory-like cuts. The...

  • Dual-Optimal Inequalities for Stabilized Column Generation. Ben Amor, Hatem; Desrosiers, Jacques; Valério de Carvalho, José Manuel // Operations Research;May/Jun2006, Vol. 54 Issue 3, p454 

    Column generation is one of the most successful approaches for solving large-scale linear programming problems. However, degeneracy difficulties and long-tail effects are known to occur as problems become larger. In recent years, several stabilization techniques of the dual variables have proven...

  • On the existence of a minimum integer representation for weighted voting systems. Freixas, Josep; Molinero, Xavier // Annals of Operations Research;2009, Vol. 166 Issue 1, p243 

    A basic problem in the theory of simple games and other fields is to study whether a simple game (Boolean function) is weighted (linearly separable). A second related problem consists in studying whether a weighted game has a minimum integer realization. In this paper we simultaneously analyze...

Share

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics