Simple Redundacies

In this post, I will elaborate how some of the simple redundancies are removed.

Empty Rows If not infeasible, then the constraint can be ignored completely.

Empty Columns Column j is empty implies no restriction on variable x_j apart from the lower and upper bound, depending on the sign of the co-efficient in objective function it can be fixed at one of these bounds

Row-Singletons

  exists (i,k) textrm{ s.t. } a_{ij} = 0 hspace{0.1in} forall j neq k, a_{ik} neq 0

Here, the i^{th} constraint fixes the variable x_k at the value - frac{b_i}{a_{ik}}

Thus we can substitute x_k out of the system and reduce the number of variables by one

The following is the pseudo-code for the procedure followed to fix a row singleton redundancy

  1. Scan through row-view

  2. If row-singleton found at row i involving variable x_j,

    1. x_j to be fixed at value b_i/A_{ij} (by calling add_to_stack!())

    2. Other constraints that contain variable x_j, have their corresponding b value modified.

    3. A_{ij} set to 0 and Objective function is modified.

  3. End

Sample code -

function singleton_rows!(p::Presolve_Problem)
    singleton_row = false
    #srows = falses(p.originalm)
    svariable = zeros(p.originaln)

    for i in 1:p.originalm
        if(p.activeconstr[i] == false)
            continue
        end
        #if(length(p.rowindices[i])==1)
        if(p.rowcounter[i] == 1)
            #println("found a row singleton at row $i")
            #j = p.rowindices[i][1]
            j = find(p.bitmat[i,:])[1]
            if(p.independentvar[j] == false)
                continue
            end
            aij = p.dictA[rc(i,j,p.originaln)]
            aij == 0 && error("Unexpected Zero")
            xj = p.currentb[i]/aij
            add_to_stack!(LinearDependency(j,xj),p.independentvar,p.pstack)
            p.activeconstr[i] = false
            singleton_row = true
                    #    srows[i] = true
            svariable[j] = xj
         end
    end

    k = find(p.bitmat)

    for ind in 1:length(k)
        i = k[ind] % p.originalm == 0 ? p.originalm : k[ind]%p.originalm
        j = Int((k[ind] - i)/p.originalm + 1)
        key = rc(i,j,p.originaln)
        if(svariable[j]!=0)
            p.currentb[i] -= svariable[j]*p.dictA[key]
            delete!(p.dictA,key)
            p.bitmat[i,j] = false
            p.rowcounter[i] -= 1
            #splice!(p.rowindices[i],j)
        end
    end
    return singleton_row
end