Google Summer of Code 2016 – JuliaOpt/Numfocus

Introduction

What is Pre-solve. And why is it important.

Pre-solving 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 two-fold 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 trade-off between time spent in the pre-solve 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 pre-solve (like CPLEX) but almost no open source solver has an efficient and exhaustive implementation of pre-solve for LP. To the best of our knowledge no first order solver has pre-solve of any kind for SDP problems. Thus adding a pre-solve to Julia-opt greatly increases the competition of open-source solvers.

I intend to write pre-solve routines for Julia-opt 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 first-order 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 pre-solve inbuilt and this would help resolve that issue. Also writing optimized Julia code is easier than re-writing in a lower-level 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 pre-solve routine written completely in Julia would fare against some of the support given in GLPK, CLP.

Timeline and Status

Latest Revision of Coding Timeline - July 8th.

Week Start Date Implementation Status
May 23rd Design Phase - Current Implementations Survey
May 30th Alternative Data Structures and Postsolving
June 6th Hash-based Sparse Format and Pre-solve utilities
June 13th Empty RowsColumns, Fixed Variables removal, Singleton Rows
June 20th JuliaCon & Correctness Testing
June 27th Column Singletons & TimeProfile Testing
July 4th Dominated Columns & Duplicate RowsColumns -
July 11th Forcing and Dominated Constraint -
July 18th Final LP Benchmarking & SDP Utilities -
July 25th Conic Approximations -
Aug 1st Conic Approximations -
Aug 8th Partial Facial Reduction -
Aug 15th Partial Facial Reduction and Documentation -

Weekly Updates

The 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 code-base. Usually such changes will be documented in later blog posts in the Implementation section.

Week Number Theoretical Implementation
0 Introduction -
1 - Sparse Matrix Data Structures
2 - Pre-solving Workflow
3 - Simple Redundancies
4 JuliaCon 2016 Slides JuliaCon 2016 Video
5 - Refactoring and Changes
6 - Testing and Analysis
7 - Time Profile Notebook