Refactoring and Changes

I will discuss some of the changes made after discussions with my mentor Madeleine and some others. First off the code review resulted in changes in spacing,naming and structure and some suggestions are yet to be effected.

The major refactoring from before was the introduction of a Bit-matrix (BitArray{2}) to store which elements of the matrix are non-zero. This will replace rowindices,colindices going forward for all calculations. The storage is about the same with the bit-matrix storing a bit for every row-column index in the matrix and rowindices, colindices are compressed but of type Int.

Previously, there was a need to splice the rowindices and colindices and the index which needs to be removed from splicing forced me into a double for loop and hence increased complexity. This has resulted in time-improvements but can probably be further optimized. Some relevent helpful work was done in IndexableBitVectors.jl last year but it now seems to be defunct.

The motivation for looking at IndexableBitVectors.jl was to find the true elements faster as problem size scales, and to reduce function calls to the find function. Earlier this was done by function calls to length function for rowindices or colindices. Now we have two vectors - rowcounter and colcounter which hold the number of non-zeros in the corresponding row/column.

The calls to row singletons procedure were way too costly as it seemed to be O(n^2) and its not as bad now, but there still needs to be a more efficient way of doing the row singleton procedure. The improvement can be either Julia-specific code style or just plain time complexity algorithmic improvement.

After multiple versions of my attempts to improve , I seem to have converged to the current speed. The current speed will discussed further in the next post.

The other change was introduction of a type - Presolve_Problem which contained all the relevant data fields. This made the code less wordy while passing input to functions elsewhere. It also follows the traditional way of defining a problem type as in MathProgBase.

Another change was the method to generate LP instances. The first (very naive) method was to generate random c,A,b until they had a feasible optimal solution and then take this as the instance. Which was quite unnecessary and rightly removed with the new method that generates c,x,A randomly and then calculates b = A*x.

Work to be done in Future -

  1. Improve Commenting

  2. Further code-review for style

  3. Implement a verbose option for debugging instead of manually modifying the print statements.