Is there any cycling example for steepest edge pivoting rule in Simplex method, when there is a finite optimal solution

108 Views Asked by At

First, the steepest edge pivot rule is the rule in A practicable steepest-edge simplex algorithm , and Steepest-edge simplex algorithms for linear programming.

The cycling examples founded, are all unbounded, but the algorithm itself detects unbounded case and stops, thus those are not a true cycling

Unbounded (no solution) example: Systematic construction of examples for cycling in the simplex method

The example in Myths and Counterexamples in Mathematical Programming is not using steepest rule, but "reduced cost divided by the Euclidean norm of the tableau column vector" , called A largest-distance pivot rule for the simplex algorithm

Edit: Example 6.1 in Systematic construction of examples for cycling in the simplex method. A debug into Julia code shows that no cycle as {5, 6, 7}, {1, 6, 7}, {1, 2, 7} {2, 3, 7}, {3, 4, 7}, {4, 5, 7}, {5, 6, 7}, but {5, 6, 7}, {1, 6, 7}, {2, 6, 7} and return with unbounded status.

    using StatusSwitchingQP
    using LinearAlgebra

    c = [-7 / 100, -3 / 50, 11 / 50, 133 / 12500]
    G = [33/25 1/2 -53/25 -9/20
        -44 -24/5 6 33/100
        1319/1000 -40 2123/10 1173/100]
    g = [0.0, 0, 0]
    A = zeros(0, 4)
    b = zeros(0)
    P = LP(c, A, b; G=G, g=g)

    #=
    settings = Settings(; rule=:stpEdgeLP)
    ts = @elapsed res = SimplexLP(P; settings=settings)
    println("steepest edge:  ", ts, "  seconds")
    display(res)
    =#

    #Example 6.1, after {5, 6, 7} and {1, 6, 7}, not {1, 2, 7}, but {2, 6, 7}
    status, c, A, b, d, u = cAbdu(P)
    q = [0.0, 0, 0]
    S = Status[DN, DN, DN, DN, IN, IN, IN]
    B = [5, 6, 7]
    invB = Matrix{Float64}(I, 3, 3)
    tol = 2^-26

    iH, x, invB = StatusSwitchingQP.stpEdgeLP(c, A, b, d, u, B, S; invB=invB, q=q, tol=tol)
    display((iH, x, S))

more detail: Steepest-Edge.pdf