GLPK/Sandbox (for content under development)

Software profiling and performance optimization

Background

At the end of 2012, a discussion on code development sparked on the [help-glpk] mailing list. The initial comments covered solver algorithms, including numerical methods, and multi-core execution. After some deliberation, it was agreed that concurrent processing was unlikely to yield much in the way of advantage, but that that algorithmic development under serial processing had a lot to offer. Andrew Makhorin suggested that the split was something like 20/80%.

The title of this page indicates a focus on improving the numerical methods specifically and the run-time performance more generally. This should not preclude improvements to the solver algorithms being considered, but the emphasis is classic software performance optimization.

The issue of thread-safe execution — related to multi-core execution but also different in important ways — was assign its own workflow and wikibook page entitled the thread-safety question. Unless circumstances dictate otherwise, this separation will be maintained.

Purpose of this page

The purpose of this page (and any subsequent sub-pages) is to summarize the discussion and any consensus decisions that arise. It is also a place where key literature can be recorded for easy reference.

Contentious issues should be debated and resolved on the [help-glpk] list first and should not be "discussed" here using this page as a vehicle.

General requirements

GLPK is multi-platform and solutions should also be applicable across common environments including Linux, the UNIXes, Mac OS X, and Microsoft Windows. These days, mobile platforms should be considered, including Google Android, Mac IOS, and Microsoft Windows Phone. The use of graphics processing units has been excluded.

Development tools

This section lists some of the development tool that have been suggested and that have also drawn a favorable response.

Version control

• git

Profiling tools

• OProfile
• perf

Code hosting

• github
• GNU savannah

Annotated literature

This section lists key literature. The subsections are given in order of increasing generality.

Linear programming methods

Maros, Istvan (2003). Computational techniques of the Simplex method. USA: Springer-Verlag. ISBN 978-1-4020-7332-8.

• a key reference on the performance of linear programming solvers