Gap controlled Simplex

gsimplex is a lightweight Python package that implements a simplex solver governed by the primal-dual gap. It integrates directly with pulp and uses numpy for its linear algebra routines. The current release supports continuous linear programming problems; mixed-integer support may be added in a future version.

Features

This package provides three main solver implementations in gsimplex.solvers:

• PrimalSimplex

  • Standard primal simplex algorithm.
  • Parameters:
    • max_iterations: maximum number of simplex iterations (default configured by package).
    • abs_eps: absolute tolerance used for feasibility and optimality checks.
    • rel_eps: relative tolerance for numerical comparisons.
    • pivot_rule: pivot selection strategy, "dantzig" by default; "bland" to avoid cycling.

• DualSimplex

  • Dual simplex algorithm for problems with a dual-feasible starting basis.
  • Parameters:
    • max_iterations: maximum number of simplex iterations.
    • abs_eps: absolute tolerance for primal/dual feasibility checking.
    • rel_eps: relative tolerance for numerical comparisons.
    • pivot_rule: pivot selection strategy, "dantzig" by default; "bland" to avoid cycling.

• GapDoubleSimplex

  • Combined primal/dual gap-controlled solver.
  • Runs primal and dual simplex iterations together and stops when the primal-dual gap is small enough.
  • Parameters:
    • max_iterations: maximum total iterations before giving up.
    • abs_eps: absolute tolerance for feasibility and basis checks.
    • rel_eps: relative tolerance for numerical comparisons.
    • abs_gap: absolute gap threshold for early termination.
    • rel_gap: relative gap threshold for early termination.
    • pivot_rule: pivot selection strategy for both primal and dual steps.

• MutualPrimalDualSimplex

  • Mutual Primal-Dual Simplex algorithm proposed by Balinsky and Gomory in 1963.
  • Parameters:
    • max_iterations: maximum number of simplex iterations (default configured by package).
    • abs_eps: absolute tolerance used for feasibility and optimality checks.
    • rel_eps: relative tolerance for numerical comparisons.
    • pivot_rule: pivot selection strategy, "dantzig" by default; "bland" to avoid cycling.

• MutualPrimalDualSimplex

  • Variation of the previous algorithm with gap checks.
  • Parameters:
    • max_iterations: maximum number of simplex iterations (default configured by package).
    • abs_eps: absolute tolerance used for feasibility and optimality checks.
    • rel_eps: relative tolerance for numerical comparisons.
    • pivot_rule: pivot selection strategy, "dantzig" by default; "bland" to avoid cycling.
  • Additional parameters to solve():
    • lb: known lower bound to the objective function, in the form of value (float/int) or vector.
    • ub: known upper bound to the objective function, in the form of value (float/int) or vector.
    • Neither lb nor ub are mandatory, but at least one of them must be provided.

Installation

Install from PyPI:

python -m pip install gsimplex

Install from source for local development:

git clone https://github.com/Richie314/GapControlledSimplex.git
cd GapControlledSimplex
python -m pip install -e .
python -m pip install -e .[dev]

Run the test suite with:

python -m pytest

Usage

from pulp import LpVariable, LpProblem, LpMaximize
from gsimplex.solvers import PrimalSimplex

x1 = LpVariable("x1", lowBound=0, upBound=1)
x2 = LpVariable("x2", lowBound=0, upBound=3)

problem = LpProblem("Problem", LpMaximize)
problem += x1 + x2
problem += x1 + x2 <= 2
problem += x1 <= 1
problem += x2 <= 3
problem += x1 >= 0
problem += x2 >= 0

solver = PrimalSimplex()
problem.solve(solver)

print("Optimal value:", problem.objective.value()) # 2.0
print("Solution:", [var.varValue for var in problem.variables()]) # [1.0, 1.0]

Command-line usage

If the package is installed, you can run the solver from the command line using:

gsimplex --problem path/to/problem.mps --solver gsimplex --sense minimize

Available options:

• --problem PATH - path to the MPS problem file to solve
• --sense {minimize,maximize} - optimization sense (default: minimize)
• --solver {psimplex,dsimplex,gsimplex,msimplex} - solver algorithm to use (default: dsimplex)
• --abs-tol FLOAT - absolute tolerance for feasibility and optimality checks
• --rel-tol FLOAT - relative tolerance for numerical comparisons
• --pivot-type {dantzig,bland} - pivot selection strategy for simplex iterations
• --abs-gap FLOAT - absolute gap threshold for gap-controlled solvers (gsimplex and msimplex)
• --rel-gap FLOAT - relative gap threshold for gap-controlled solvers (gsimplex and msimplex)
• --quiet - suppress detailed output

Example:

python -m gsimplex --problem example.mps --solver gsimplex --sense minimize \
  --abs-tol 1e-8 --rel-tol 1e-10 --pivot-type bland --abs-gap 1e-8 --rel-gap 1e-10

This runs the selected solver with the specified tolerances and gap control settings. For non-gap solvers (psimplex and dsimplex), --abs-gap and --rel-gap are ignored.

Generate a random LP problem

This package installs a command-line helper called gsimplex-generate-lp to create a feasible LP in MPS format.

gsimplex-generate-lp --variables 10 --constraints 20 --output example.mps

• --variables, -n: number of decision variables
• --constraints, -m: number of constraints
• --output, -o: output MPS file path (default: generated_lp.mps)

Download benchmark problems

The package also contains a tool to download known hard academic problems from the web: gsimplex-download-benchmarks. It can download Plato, Netlib and MipLib benchmark sets into a local directory, so you can test the solver on real LP problems.

By default, benchmark files are saved under the benchmark/ directory in the current working directory. Plato files are stored in benchmark/plato/, Netlib files are stored in benchmark/netlib/ and MipLib files are stored in benchmark/miplib/.

A script is provided to download the desired benchmarks.

# Will download only Plato benchmarks
gsimplex-download-benchmarks --plato

# Will download only Netlib benchmarks
gsimplex-download-benchmarks --netlib

# Will download both Plato and MipLib benchmarks
gsimplex-download-benchmarks --plato --miplib

Change the destination directory

gsimplex-download-benchmarks --plato --dir benchmark

Quiet mode

gsimplex-download-benchmarks --plato --quiet

If you installed the package editable with pip install -e ., the command will be available immediately.