Pre-solving Workflow.

Me 

The code that I write will live in the repository Convex.jl in the presolve.jl file and the post-solving procedure will be a function in the solution.jl

First the data provided by the user is used to construct the dictionary (hash-map) that will contain all the non-zero entries of matrix A. This will be used to access the non-zero entries during the subroutines. Along with the dictionary we also build row view and column view of A that store the indices of the non-zero entries of matrix A. This will be used to determine whether a particular rowcolumn has a rowcolumn singleton.

We define a new abstract type - PresolveStack which will have two subtypes - LinearDependency and Duplicated. The definition for the LinearDependency subtype is given below

type LinearDependency <: PresolveStack
    index :: Int
    vec1 :: Vector{Int}
    vec2 :: Vector{Int}
    value :: Int

    function LinearDependency(ind :: Int,val :: Int)
        index = ind
        vec1 = vec2 = Array{Int,1}()
        value = val
    end
end

Here, each LinearDependency element represents the mathematical equation x_{textrm{index}} = textrm{val} + sum left(x[textrm{vec}1[i]] * textrm{vec}2[i]right). We are fixing the variable x_{textrm{index}} in terms of the other variables. textrm{val} is the corresponding scalar from the b vector. The vector vec1 represents the indices of the variables that are present in the constraint we are trying to remove. The vector vec2 represents the appropriate ratios of the non-zero entries of A.

Some other data for book-keeping are

  1. independentvar - A boolean array of the original number of variables which represent whether a variable is independent or dependent on other variables

  2. pstack - A stack of elements of type PresolvingStack.

Fixing the Variables.

Fixing a variable involves two things - recording the reduction done in a stack and changing the value of the variable and marking it as a dependant variable.

function add_to_stack!(l :: LinearDependency,independentvar :: BitArray{1}, pstack :: Array{PresolveStack,1})
    if (length(l.vec1) != length(l.vec2))
        error("vector1 size not equal to vector 2 size for LD element")
    end
    independentvar[l.index] = false
    push!(pstack,l)
end

function post_solve!(post_solvedX :: Vector{Int}, l::LinearDependency)
    for i in 1:length(l.vec1)
        post_solvedX[this.index] += this.vec2[i]*post_solvedX[this.vec1[i]]
    end
        post_solvedX[this.index] += val
end

# this has to be added in the solution.jl file
# the x that is fed in has to be the solution obtained from the Solver.
function return_postsolved(x :: Array{Int,1},pstack :: Array{PresolveStack,1})
    postsolvedX = Vector{Int}[originaln]
    for i in length(x)
        postsolvedX[presolvedX[i]] = x[i]
    end
    for i in reverse(collect(1:length(pstack)))
        pstack[i].post_solve!(postsolvedX)
    end
end

The solution to the modified optimization problem is fed as input to the function return_postsolved(…) which converts this back into a feasible optimal solution for the original problem. The function post_solve! resolves one element of LinearDependency.

Internal Tests

The function check_progress asserts whether the constraints and bounds are satisfied along with consistency in the non-zero entries stored as dictionary as compared to the row/column view

function check_progress(c,A,b,lb,ub,ylb,yub,zlb,zub)
    #checking rows
    for i in 1:N
        for nnz in 1:length(rowindices[i])
            if(dictA[rc(i,nnz)] == 0)
                error("Zero error in row")
            end
        end
    end

    # checking columns
    for j in 1:M
        for nnz in 1:length(colindices[j])
            if(dictA[rc(nnz,j)]==0)
                error("Zero error in col")
            end
        end
    end
    # checking Aij
    for key in keys(dictA)
        j = key%M == 0 ? 4 : key%M
        i = Int((key -j)/M + 1)
        if(dictA[key] != 0)
            if(!in(rowindices[i]),j)
                error("Error")
            end
            if(!in(colindices[j]),i)
                error("Error")
            end
        end
    end
    #TODO.. check Ax = b


    #TODO.. upper and lower check
end