Google Summer of Code 2016 – JuliaOpt/NumfocusIntroductionWhat is Presolve. And why is it important. Presolving is the process of detecting redundancies in an optimization problem and removing them so that the problems that are fed to solvers are properly formulated. The reduced optimization problem is now solved by the solver. This has the twofold benefit of speeding up the optimization process, and higher accuracy in solutions. Since smaller problems are fed to the solver (eg. SCS), the bottleneck call to the solver has now become significantly faster. Ideally, we would want to remove the types of redundancy which lead to reduction in total solution time. But this isn't possible. There is also a tradeoff between time spent in the presolve procedure and the amount of redundancy detected by our procedure.
Therefore, our essential goal would be to find simple forms of redundancies, and in as less time as possible. Motto  Find simple forms of redundancies and find them quick. Many commercial solver include presolve (like CPLEX) but almost no open source solver has an efficient and exhaustive implementation of presolve for LP.
To the best of our knowledge no first order solver has presolve of any kind for SDP problems. Thus adding a presolve to Juliaopt greatly increases the competition of opensource solvers. I intend to write presolve routines for Juliaopt rather than write interfaces to Frank Permenter's frlib for SDP or GLPK for LP. Why? The presolve support for LP in other open source solvers is not as exhaustive as proposed. The presolve support for SDP in frlib, uses SeDuMi, but firstorder solver like SCS (the default solver in Convex.jl) has been shown to be considerably faster when the problem size scales from a recent paper. SCS currently has no presolve inbuilt and this would help resolve that issue. Also writing optimized Julia code is easier than rewriting in a lowerlevel language like C and more easily maintained for further improvements in future. This could have the added side benefit of yet another benchmark against other 'fast’ languages and give feedback on how the presolve routine written completely in Julia would fare against some of the support given in GLPK, CLP. Timeline and StatusLatest Revision of Coding Timeline  July 8th.
Weekly UpdatesThe table contains links to posts that elaborate on my work. They are logically organized into Theoretical and Implementation Theoretical Mathematical theorems and outline of facts that provide the backbone reasoning for the algorithms. Mostly written to document m*y understanding for future purposes. You may skip it if you already know them or are primarily interested in actual Julia code. Implementation Discussions oriented towards Data Structures and Julia implementation of algorithms with occasional code snippets. Will briefly outlay reasons for design decisions for future reference. Note that, refactoring of code could mean that there is a different implementation currently in codebase. Usually such changes will be documented in later blog posts in the Implementation section.
