UNB/ CS/ David Bremner/ research/ sparks lp

This page contains examples of linear programs compiled from pseudocode. This pseudocode is called SPARKS in honour of pseudocode in Horowitz and Sahni's book "Fundementals of Algorithms", which inspired it. For details of the construction see the paper by Avis, myself, Tiwary, and Watanabe.

UPDATE: The software to compile to LPs is available on gitlab

How to run the examples

Currently we are just providing compiled LPs. You can run these using glpsol (part of glpk). You need a model file (common to all inputs of a given size) and a data file (specific to each input, e.g. specific to each graph). Both of these files are written in the GNU MathProg modeling language. In our examples the model files have the extension ".gmpl" and the data files have the extension ".dat". Once you have installed the solver and downloaded the model and data files, you can run, e.g.

glpsol -m PM4_1.gmpl -d PM4_14.dat