PaperlayerView exact revision on arXiv

Source-linked AI summary

Parallelizing the dual revised simplex method

Q. Huangfu, J. A. J. Hall

arXiv:1503.01889v1math.OCmath.NA

TL;DR

General large sparse LPs have resisted scalable parallelization of the efficient dual revised simplex method. This paper develops PAMI and SIP using complementary forms of parallelism, with PAMI outperforming Clp on the reference set and SIP helping when PAMI slows down.

  • Problem

    Parallelization of the revised simplex method has had limited success for general large sparse LPs, despite its computational efficiency and frequent preference for related problems.

  • Method

    The paper develops PAMI, which uses suboptimization across multiple iterations, and SIP, which overlaps computational components within single iterations.

  • Results

    PAMI achieves a mean speedup of 1.51 and outperforms Clp, while SIP achieves 1.15 and often complements PAMI when PAMI slows down.

  • Takeaways & Limitations

    The techniques formed the basis of refinements to the commercial FICO Xpress simplex solver and were used in FICO advertising copy.

  • Takeaways & Limitations

    SIP typically slows down on hyper-sparse LPs when ftran-dse dominates computation and competing task parallelism adds memory-access and setup costs.

Abstract

from arXiv · show

This paper introduces the design and implementation of two parallel dual simplex solvers for general large scale sparse linear programming problems. One approach, called PAMI, extends a relatively unknown pivoting strategy called suboptimization and exploits parallelism across multiple iterations. The other, called SIP, exploits purely single iteration parallelism by overlapping computational components when possible. Computational results show that the performance of PAMI is superior to that of the leading open-source simplex solver, and that SIP complements PAMI in achieving speedup when PAMI results in slowdown. One of the authors has implemented the techniques underlying PAMI within the FICO Xpress simplex solver and this paper presents computational results demonstrating their value. This performance increase is sufficiently valuable for the achievement to be used as the basis of promotional material by FICO. In developing the first parallel revised simplex solver of general utility and commercial importance, this work represents a significant achievement in computational optimization.

1 Introduction

The paper targets parallelization of the dual revised simplex method for large sparse LPs, where prior revised-simplex parallelization had limited success despite the method’s serial efficiency. It develops a sequential foundation and two parallel solvers for standard desktop architectures.

  • Motivation: Parallelization of the revised simplex method has achieved less speedup than standard simplex parallelization and was considered unsuitable for general large sparse LPs.The paper nevertheless argues that improvements remain worthwhile because revised simplex is computationally efficient for sparse problems.
  • Motivation: Dual simplex parallelization was motivated by limited prior work, missing BFRT and hyper-sparse techniques, and the widespread availability of multicore desktop computers.The authors identify Bixby and Martin as the only published dual-simplex parallelization work known to them.
  • Foundation: The authors implemented hsol from scratch as a sequential dual simplex foundation incorporating sparse factorization, hyper-sparse solves, LU updates, and sophisticated pivoting rules.They argue that parallelization should be based on an efficient sequential solver.
  • Contribution: Two parallel dual simplex solvers, pami and sip, were designed from components of hsol.The paper presents their designs and numerical performance analysis in subsequent sections.

2 Background

The background section frames efficient implementation as essential for evaluating new simplex developments and introduces the concepts needed to develop parallel dual simplex solvers.

  • Background: New simplex developments must be tested within an efficient implementation because effectiveness only in an inefficient implementation is not considered valuable.The paper places this requirement in the context of more than 60 years of simplex algorithmic improvements.
  • Background: The section introduces LP computational form, feasibility, the regular dual simplex algorithm, advanced components, suboptimization, and simplex update approaches.Suboptimization provides the starting point for the pami parallelization.

2.1 Linear programming problems

The paper formulates LPs in computational form using equality constraints and variable bounds, then partitions variables into basic and nonbasic sets. Feasibility conditions determine when a basis yields an optimal solution.

  • Formulation: The general LP form minimizes f = cT x subject to Ax = 0 and l ≤ x ≤ u.A is the coefficient matrix, while x, c, l, and u represent variables, costs, and bounds.
  • Basis partition: A full-rank matrix A is partitioned into a nonsingular basis B and remaining matrix N, with variables and costs split accordingly.The constraint equation becomes Ax = BxB + NxN = 0.
  • Feasibility: Simplex primal variables set nonbasic variables at finite bounds and compute xB = −B−1NxN, while reduced costs define the dual variables.Primal feasibility requires lB ≤ xB ≤ uB.
  • Feasibility: A basis is dual feasible when the stated reduced-cost sign conditions hold for nonbasic variables whose bounds differ.The supplied passages state that a basis both primal and dual feasible yields an optimal LP solution.

2.2 Dual revised simplex method

The dual simplex method maintains dual feasibility while seeking primal feasibility through optimality testing, ratio testing, and basis updates. Its revised implementation uses sparse linear algebra, advanced pivoting rules, and opportunities for data and task parallelism.

  • Dual simplex algorithm: The dual simplex algorithm starts from a dual feasible basis and iteratively seeks primal feasibility through three major operations.These are optimality testing, ratio testing, and updating.
  • Ratio test: The ratio test selects an entering nonbasic variable while preserving dual feasibility, using btran, spmv, Harris’s two-pass test, and BFRT.The advanced chuzc procedure separates candidate accumulation in chuzc1 from recursive selection in chuzc2 and determines primal and dual steps.
  • Updating: Basis updating exchanges leaving and entering indices and updates primal, dual, factorization, and DSE-weight information through ftran and related operations.BFRT may additionally flip variables and apply an ftran-bfrt update.
  • Revised representation: Revised simplex represents B−1 through sparse LU factorization and updates that representation until reinversion becomes advantageous or numerically necessary.Hyper-sparsity exploits sparse solutions of systems involving B or BT even when B−1 is dense.
  • Optimality test: The optimality test selects a primal infeasible basic variable to leave the basis, using dual steepest-edge weights and attractiveness to improve the choice.Hyper-sparse candidate selection maintains a short list of attractive variables for large sparse problems.
  • Scope for parallelisation: Data parallelism is available in chuzr, spmv, chuzc, and many update operations, while task parallelism can overlap ftran and ftran-dse.The component summary reports each major component’s percentage of overall solution time for the test set.

2.3 Dual suboptimization

Dual suboptimization organizes the dual revised simplex method into major and minor iterations, creating opportunities to parallelize candidate initialization, ratio tests, and updates. PAMI builds on this framework while retaining modern pivoting rules.

  • Dual suboptimization: Dual suboptimization uses a major-minor iteration scheme for the dual revised simplex method.The major iteration selects potential leaving variables, while minor iterations choose entering variables and update remaining candidates.
  • Major iteration: The major optimality test selects a set P of primal infeasible basic variables as potential leaving variables.If no such indices can be selected, the LP is solved to optimality.
  • Minor iterations: Minor iterations remove a candidate, perform a ratio test to identify an entering variable, and update primal and dual variables.The ratio test uses the reduced coefficient information through a sparse matrix-vector product.
  • Motivation: Although originally intended to improve pivot choices and data affinity, suboptimization is attractive for parallelization because it provides more computational scope.Modern implementations generally regard DSE and BFRT as the best pivotal rules, while suboptimization has been largely overlooked.
  • Parallelization opportunities: Dual suboptimization exposes parallel work through s btran operations during major initialization and multiple ftran operations during major updates.Here, s = |P| and the number of minor iterations satisfies t ≤ s.

2.4 Simplex update techniques

Simplex update techniques maintain the basis inverse representation after pivots. The paper compares PF, FT, APF, and collective FT updates, emphasizing their differing computational information and efficiency.

  • Overview: Basis-inverse updating is a crucial component of revised simplex implementations.The paper summarizes several update methods relevant to its parallel solver design.
  • Product form update: The product form update uses the ftran result baq to update the basis inverse representation.Its relevant inverse information is readily available.
  • Forrest-Tomlin update: The Forrest-Tomlin update factors Bk as LkUk and uses partial ftran and btran results to modify the factors.The update modifies Uk and augments Lk.
  • Alternate product form update: The alternate product form update uses the btran result beT_p and a column of B.The resulting transformation is readily inverted.
  • Collective update: Following suboptimization, the collective Forrest-Tomlin update updates the basis inverse representation across the accumulated pivotal sequence.For future simplex iterations, the collective FT update is preferred to PF and APF in efficiency terms.

3 Parallelism across multiple iterations

PAMI extends dual suboptimization by parallelizing work across multiple iterations, including candidate initialization, sparse ratio-test operations, vector updates, and selected ftran tasks. It leaves inexpensive or inherently serial operations unparallelized.

  • PAMI design: PAMI extends suboptimization with serial algorithmic techniques while exploiting parallelism across multiple iterations.Its design builds on the earlier ParISS prototype and incorporates more sophisticated updates and algorithmic features.
  • Major iteration: The major optimality test chooses s candidates with the DSE framework, where s equals the number of processors.This vector-based operation is easy to parallelize but is performed only once per major operation.
  • Minor initialization: Minor initialization computes btran results for up to s potential leaving candidates, providing the first task-parallel opportunity.The work arises directly from the suboptimization framework.
  • Minor ratio test: PAMI parallelizes spmv and chuzc1 in the minor ratio test by partitioning variables across processors before simplex iterations begin.The partitioning is randomized to target load balance in the sparse matrix-vector product; chuzc2 remains serial because it is relatively cheap and synchronization-heavy.
  • Minor update: Minor updates expose data parallelism through vector addition, btran-result updates, and recomputation of DSE weights.The updated dual variables are needed by the next minor ratio test.
  • Major update: Major updates combine ftran operations with vector updates and basis-representation updates, while reinversion remains serial and can cause processor idleness.The major update includes up to 3t ftran operations, where t is the number of minor iterations.

3.2 Parallelising three groups of ftran operations

PAMI parallelizes three groups of ftran operations and simplifies bound-flip calculations by combining related operations. This reduces forward linear-system solves and improves task distribution across processors.

  • Three ftran groups: The major update contains regular ftran, ftran-dse, and ftran-bfrt operations associated with the pivotal sequence from minor iterations.Together these groups account for up to 3t forward linear systems, with t ≤ s.
  • Regular and DSE ftran: Regular ftran and ftran-dse operations combine inverse solves with PF transformations, enabling task parallelism for multiple inverse parts.Data parallelism can also be used for individual PF updates when the relevant vector is large and dense.
  • BFRT ftran: BFRT ftran operations produce updates to the primal variables, but regular PF implementations cannot combine these closely related calculations.With APF updates, the operations can instead be expressed through a shared structure.
  • Operation simplification: Combining potential ftran-bfrt operations reduces the serial cost of forward solves and reduces the primal update to one operation.The combined approach applies a single B−1_k operation to the aggregated result.
  • Operation count: The combined implementation requires 2t + 1 forward linear systems, or 2t when no bound flips occur.When t ≤ s − 1, each processor solves at most two systems; when t = s with nontrivial BFRT, one processor solves three.
  • Task scheduling: All 2t + 1 ftran operations are launched simultaneously as parallel tasks, with processors selecting which tasks to perform.This task arrangement is illustrated in Figure 1.

3.3 Candidate persistence and quality control in chuzr

PAMI manages candidate persistence in suboptimization by controlling which candidates remain in the working set, balancing pivot quality against parallel workload. Experiments support choosing a cutoff ratio in [0.9, 0.999], with ψ = 0.95 used in PAMI.

  • Candidate persistence: Candidate persistence is challenging because less-attractive candidates may remain in P, wasting btran and update work or increasing simplex iterations.The initial set size and a strategy for assessing candidate persistence must therefore be chosen carefully.
  • Candidate persistence: PAMI fixes the initial candidate-set size at s = 8 because larger processor-aligned multiples increase parallel work but are outweighed by wasted computation and extra iterations.The choice is based on practical experience with PAMI prototypes.
  • Quality control: PAMI removes candidates whose attractiveness falls below the cutoff relative to its initial value, and always drops feasible or unattractive candidates.The cutoff factor is ψ > 0; candidates with αp ≤ 0 are removed regardless of ψ.
  • Experimental results: At ψ = 0.999, where candidates whose attractiveness decreases are dropped, PAMI achieves a mean speedup of 1.52.The special ψ = 1.001 setting, which selects only candidates with improved attractiveness, gives poor speedup.
  • Experimental results: For 0.9 ≤ ψ ≤ 0.999, PAMI's mean speedup and counts of larger speedups remain relatively stable; decreasing ψ below 0.9 reduces mean speedup.The larger-speedup counts remain stable until ψ = 0.5.
  • Experimental results: Experiments recommend any cutoff ratio in [0.9, 0.999], and PAMI uses the median value ψ = 0.95.The experiments used a reference set of 30 LP problems and measured geometric mean speedup plus counts reaching 1.6, 1.8, and 2.0 speedup.

4 Single iteration parallelism

SIP exploits parallelism within one dual revised simplex iteration by overlapping computational components according to their data dependencies. Its design extends earlier work that parallelized selected vector operations while avoiding inefficient overlap involving expensive ftran-dse.

  • Scheme overview: SIP is a single-iteration parallel scheme that overlaps computational components when possible, extending earlier parallelization of spmv, chuzc, and update-dual.The approach differs from task parallelism across multiple iterations.
  • Parallelization choices: Naively overlapping ftran-bfrt with ftran and ftran-dse is inefficient because ftran-dse is relatively expensive and ftran-bfrt is not required in every iteration.The cost difference arises because ftran-dse uses the relatively dense RHS bep, whereas ftran and ftran-bfrt use aq and aF.
  • Data dependencies: SIP separates chuzc1 operations for structural and logical variables, then overlaps ftran, any ftran-bfrt, and update-dual across processors.Logical variables correspond to an identity matrix in A.
  • Data dependencies: SIP assumes at least four processors; additional processors enhance only the parallelism in spmv and chuzc.The dependency structure limits the benefit of adding processors beyond four for the other components.

5 Computational results

Experiments on 30 diverse sparse LP problems compare pami and sip with sequential solvers and established codes. Pami generally delivers stronger parallel performance, while sip provides complementary speedups on cases where pami slows down.

  • 5.1 Test problems: The reference set contains 30 LP problems spanning varied dimensions, matrix densities, and hyper-sparsity characteristics.Half of the problems are classified as hyper-sparse using the criterion that more than 60% of ftran and btran results have density below 10%.
  • 5.2 Performance of pami: Pami on 8 cores is 1.51 times faster than hsol, while hsol is 2.29 times faster than Clp.These comparisons use mean relative solution times from the reference set.
  • 5.2 Performance of pami: For more than 65% of the reference set, pami is twice as fast in parallel, with a mean speedup of 2.34.Relative to hsol, wasted computation reduces the mean relative solution-time advantage to 1.51.
  • 5.2 Performance of pami: Pami's performance varies considerably across problems and is not strongly related to hyper-sparsity.Its most extreme performances occur on dense problems, while gains on some hyper-sparse problems reflect expensive spmv or ftran-dse components.
  • 5.3 Performance of sip: Sip has a mean speedup of 1.15 and generally similar iteration counts to hsol, but its limited parallelism makes it inferior to pami overall.Sip is nevertheless useful on dense instances where pami slows down, including speedups of 1.31 for Linf520c and 1.12 for maros-r7.
  • 5.4 Performance relative to Cplex and influence on Xpress: The better of pami8 and sip8 performs comparably with Cplex for most test problems, although direct comparison between research and commercial codes is qualified.Xpress results further show that, when parallel execution is advantageous, Xpress can match serial Cplex performance under preprocessing and crash.

6 Conclusions

The paper presents two parallel dual revised simplex implementations: PAMI uses suboptimization for parallelism across iterations, while SIP uses single-iteration parallelism. PAMI achieves a mean speedup of 1.51, SIP complements it when PAMI slows down, and the techniques have influenced commercial Xpress performance.

  • The paper introduces two parallel implementations of the dual revised simplex method.
  • PAMI uses suboptimization to expose parallelism across multiple iterations, but requires a 0.95 cutoff factor because pivot quality can decline.
  • 1.51 mean speedup is reported for PAMI on the reference set.
  • SIP exploits purely single-iteration parallelism and has a mean speedup of 1.15, lower than PAMI's.
  • SIP frequently complements PAMI by achieving speedup when PAMI results in slowdown.
  • The techniques formed the basis of Xpress refinements that raised its parallel revised simplex performance to that of the world's best commercial simplex solvers.
Loading 1503.01889v1…