Implementing the Simplex Method: The Initial Basis

Robert E. Bixby
Robert E. Bixby
Department of Mathematical Sciences, Rice University, Houston, TX 77001
Search for more papers by this author

Department of Mathematical Sciences, Rice University, Houston, TX 77001

Published Online:1 Aug 1992https://doi.org/10.1287/ijoc.4.3.267

Abstract

This paper contains the first two parts of a planned series of papers on the CPLEX^TM implementation of the simplex method. Part I is introductory. It gives an elementary description of the bounded-variable simplex method as well as a rather detailed discussion of some of the numerical characteristics of the netlib test problems. These problems form the basis for the computational tests in the subsequent parts. Part II contains the main results of this paper, a description of the method used by CPLEX for constructing an initial basis.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Cited by
- Learning to select cutting planes in mixed integer linear programming solving
  Expert Systems with Applications, Vol. 298
- On Augmented Lagrangian for LP Feasibility
  28 May 2025
- Configuration-Adaptive Parallel Solver for Integer Programming Problems
  24 February 2026 | Journal of Computer and Systems Sciences International, Vol. 64, No. 6
- Reliable and economic operation of regional-community integrated energy systems: A hybrid game approach based on state similarity
  Energy, Vol. 336
- Accelerating Linear Programming Performance: A Hardware-Software Co-Design Approach for the Simplex Method
  25 May 2025
- Exploring the Potential of Graph Neural Networks-based Methods for General Linear Programs
  23 May 2025
- Traction optimization of locomotive startup considering axle load transfer
  6 May 2025 | Journal of Mechanical Science and Technology, Vol. 39, No. 5
- MILP Acceleration: A Survey from Perspectives of Simplex Initialization and Learning-Based Branch and Bound
  3 July 2023 | Journal of the Operations Research Society of China, Vol. 13, No. 1
- Learning to Cut via Hierarchical Sequence/Set Model for Efficient Mixed-Integer Programming
  IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 46, No. 12
- Random Projections for Linear Programming: An Improved Retrieval Phase
  14 October 2023 | ACM Journal of Experimental Algorithmics, Vol. 28
- Experiments with Active-Set LP Algorithms Allowing Basis Deficiency
  23 December 2022 | Computers, Vol. 12, No. 1
- An Adaptive Application Framework with Customizable Quality Metrics
  2 November 2021 | ACM Transactions on Design Automation of Electronic Systems, Vol. 27, No. 2
- Using Linear Programming for Builder Brigades Optimization
  2 March 2022
- A triangulation and fill-reducing initialization procedure for the simplex algorithm
  26 June 2020 | Mathematical Programming Computation, Vol. 13, No. 3
- Bibliography
  12 March 2021
- Some experimental results of station cone algorithm in comparison with simplex algorithm for linear programming
  Journal of Physics: Conference Series, Vol. 1489, No. 1
- Predicting the Execution Time of the Interior Point Method for Solving Linear Programming Problems Using Artificial Neural Networks
  22 January 2020
- Incremental Online Verification of Dynamic Cyber-Physical Systems
- Spiking Central Pattern Generators through Reverse Engineering of Locomotion Patterns
  30 May 2018
- A structure-preserving pivotal method for affine variational inequalities
  3 March 2017 | Mathematical Programming, Vol. 168, No. 1-2
- Introduction
  31 October 2017
- Exterior Point Simplex Algorithm
  31 October 2017
- Interior Point Methods
  31 October 2017
- Revised Primal Simplex Algorithm
  31 October 2017
- Revised Dual Simplex Algorithm
  31 October 2017
- Crash start of interior point methods
  European Journal of Operational Research, Vol. 255, No. 1
- Direct Methods for Linear Systems
  7 October 2014
- Input/state invariant LQ-optimal control: Application to competitive coexistence in a chemostat
  Evolution Equations and Control Theory, Vol. 4, No. <![CDATA[2]]>
- Introduction
  10 October 2013
- Integer Linear Programming (ILP)
  10 October 2013
- Pivot Rule
  10 October 2013
- Dual Pivot Rule
  10 October 2013
- Simplex Phase-I Method
  10 October 2013
- Dual Simplex Phase-l Method
  10 October 2013
- Reduced Simplex Method
  10 October 2013
- Improved Reduced Simplex Method
  10 October 2013
- D-Reduced Simplex Method
  10 October 2013
- Criss-Cross Simplex Method
  10 October 2013
- Generalizing Reduced Simplex Method
  10 October 2013
- Geometry of the Feasible Region
  10 October 2013
- Deficient-Basis Method
  10 October 2013
- Dual Deficient-Basis Method
  10 October 2013
- Face Method
  10 October 2013
- Dual Face Method
  10 October 2013
- Pivotal Interior-Point Method
  10 October 2013
- Special Topics
  10 October 2013
- Simplex Method
  10 October 2013
- Duality Principle and Dual Simplex Method
  10 October 2013
- Implementation of the Simplex Method
  10 October 2013
- Sensitivity Analysis and Parametric LP
  10 October 2013
- Variants of the Simplex Method
  10 October 2013
- Decomposition Method
  10 October 2013
- Interior-Point Method
  10 October 2013
- Modelling sediment transport over partially non‐erodible bottoms
  19 September 2011 | International Journal for Numerical Methods in Fluids, Vol. 70, No. 2
- An FPGA-based approach for parameter estimation in spiking neural networks
- Energy Wall Losses Estimation of a Gasoline Engine Using a Sliding Mode Observer
  16 April 2012
- A Two‐Phase Support Method for Solving Linear Programs: Numerical Experiments
  26 April 2012 | Mathematical Problems in Engineering, Vol. 2012, No. 1
- Implementing the Simplex Method
  15 February 2011
- The Simplex Method and Its Complexity
  15 February 2011
- Simplex‐Based LP Solvers
  15 February 2011
- LQ-optimal control of positive linear systems
  29 November 2010 | Optimal Control Applications and Methods, Vol. 31, No. 6
- Symbolic implementation of interior point method for linear programming problem
  International Journal of Computer Mathematics, Vol. 87, No. 10
- Mathematical programming via the least-squares method
  Open Mathematics, Vol. 8, No. 4
- 2-D Modeling of the Behavior of an Adhesive in an Assembly Using a Non-Associated Elasto-Visco-Plastic Model
  The Journal of Adhesion, Vol. 85, No. 4-5
- A MULTI-OBJECTIVE ASSESSMENT OF INPUT–OUTPUT MATRIX UPDATING METHODS
  Economic Systems Research, Vol. 21, No. 1
- On the Positive LQ-Problem for Linear Discrete Time Systems
- Inverse modeling of unsaturated flow parameters using dynamic geological structure conditioned by GPR tomography
  1 August 2008 | Water Resources Research, Vol. 44, No. 8
- Self-adjustment of resource allocation for grid applications
  Computer Networks, Vol. 52, No. 9
- THIS ARTICLE HAS BEEN RETRACTED  Modeling Responses of Leafy Spurge Dispersal to Control Strategies
  22 November 2007 | Journal of Integrative Plant Biology, Vol. 49, No. 12
- Greedy Basis Pursuit
  IEEE Transactions on Signal Processing, Vol. 55, No. 7
- Optimierung
- Supervised Adaptive Control of Unknown Nonlinear Systems Using Fuzzily Blended Time-Varying Canonical Model
- Accurate Calibration of a Robotic Positioning System Using the Evolutionary Search
- A Fuzzy Lyapunov Function Approach to Stabilize Uncertain Nonlinear Systems Using Improved Random Search Method
- The Effects of Solar Cell Capacitance on Calibration Accuracy When using a Flash Simulator
- An optimization approach to multiple sequence alignment
  Applied Mathematics Letters, Vol. 16, No. 5
- Random 3-SAT: The Plot Thickens
  Constraints, Vol. 8, No. 3
- The Wingulf Package
- Performance evaluation of a family of criss–cross algorithms for linear programming
  12 February 2003 | International Transactions in Operational Research, Vol. 10, No. 1
- Advances in design and implementation of optimization software
  European Journal of Operational Research, Vol. 140, No. 2
- Creating Advanced Bases For Large Scale Linear Programs Exploiting Embedded Network Structure
  Computational Optimization and Applications, Vol. 21, No. 1
- LPAKO: A Simplex-based Linear Programming Program
  Optimization Methods and Software, Vol. 17, No. 4
- Reoptimization With the Primal-Dual Interior Point Method
  SIAM Journal on Optimization, Vol. 13, No. 3
- A revised simplex method with integer Q-matrices
  1 September 2001 | ACM Transactions on Mathematical Software, Vol. 27, No. 3
- Limit analysis of frictional block assemblies as a mathematical program with complementarity constraints
  International Journal of Mechanical Sciences, Vol. 43, No. 1
- Random 3-SAT: The Plot Thickens
  1 June 2001
- Automatic data layout for distributed-memory machines
  1 July 1998 | ACM Transactions on Programming Languages and Systems, Vol. 20, No. 4
- A warm-start dual simplex solution algorithm for the minimum flow networks with postoptimality analyses
  Mathematical and Computer Modelling, Vol. 27, No. 12
- Strategies for Creating Advanced Bases for Large-Scale Linear Programming Problems
  István Maros,
  Gautam Mitra,
  1 May 1998 | INFORMS Journal on Computing, Vol. 10, No. 2
- Tools and techniques for automatic data layout: A case study
  Parallel Computing, Vol. 24, No. 3-4
- Parallel and hierarchical decomposition approaches for solving large-scale Data Envelopment Analysis models
  Annals of Operations Research, Vol. 73, No. 0
- Optimally synchronizing DOACROSS loops on shared memory multiprocessors
- Gigaflops in linear programming
  Operations Research Letters, Vol. 18, No. 4
- Illustrating constraint programming systems in logistic planning
  7 June 2005
- Finding Better Starting Bases for the Simplex Method
- Presolving in linear programming
  Mathematical Programming, Vol. 71, No. 2
- The singly constrained assignment problem: An AP basis algorithm
  Computational Optimization and Applications, Vol. 4, No. 4
- Intelligent transportation systems—Enabling technologies
  Mathematical and Computer Modelling, Vol. 22, No. 4-7
- A C++ Class Library for Mathematical Programming
- Solving a class of LP problems with a primal-dual logarithmic barrier method
  European Journal of Operational Research, Vol. 80, No. 1
- Chapter 10 Design of survivable networks
- A comprehensive simplex-like algorithm for network optimization and perturbation analysis
  Optimization, Vol. 32, No. 3
- Fullerene isomers of C60. Kekulé counts versus stability
  Chemical Physics Letters, Vol. 228, No. 4-5
- Recovering an optimal LP basis from an interior point solution
  Operations Research Letters, Vol. 15, No. 4
- Experience with interior point optimization software for a fuel planning application
  IEEE Transactions on Power Systems, Vol. 9, No. 2
- Computational Methods For Linear Programming
- The design and application of IPMLO. A FORTRAN library for linear optimization with interior point methods
  29 March 2011 | RAIRO - Operations Research, Vol. 28, No. 1
- Solving symmetric indefinite systems in an interior-point method for linear programming
  Mathematical Programming, Vol. 62, No. 1-3
- Finding an interior point in the optimal face of linear programs
  Mathematical Programming, Vol. 62, No. 1-3
- Experience with interior point optimization software for a fuel planning application

Volume 4, Issue 3

Summer 1992

Pages 225-356

Article Information

Metrics

Information

Published Online:August 01, 1992

Cite as

Robert E. Bixby, (1992) Implementing the Simplex Method: The Initial Basis. ORSA Journal on Computing 4(3):267-284.

https://doi.org/10.1287/ijoc.4.3.267

Keywords

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Implementing the Simplex Method: The Initial Basis

Abstract

Volume 4, Issue 3

Article Information

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News