The Colourful Linear Programming Homepage

In 1996, Bárány and Onn introduced colourful linear programming, which they described as "an outstanding problem on the border line between tractible and intractible problems". We concur, and feel that such a problem deserves it's own homepage. The point of this page is to offer some useful code and benchmarks. We include MATLAB software for generating and solving colourful linear programs and results of computational experiments using this software.

The background on our experiments and softwate is included in the paper The Colourful Feasibility Problem (ps, pdf) by Antoine Deza, Sui Huang, Tamon Stephen and Tamás Terlaky. In particular, we include here the full appendices that contain data tables with our experimental results: ps pdf. A fuller exposition is contained in Sui Huang's Master's thesis, available here.

Software

MATLAB software for colourful linear program was written in by Sui Huang.
This code is copyrighted, but it is available for non-commercial use free of charge under the GNU General Public License.

The entire suite of codes is available as a .zip or a .tar.gz file. Also available are the test results and infeasible cases used in the thesis.

Overview of the generators and algorithms available:

Generators Initial solution Heurstics Solvers
Random (uniform) generator Random initial simplex Bárány's algorithm
Tube generator Bárány and Onn initialization Bárány and Onn's algorithm
Many solutions generator Maximum angles initial simplex Multi-update Bárány
Regular simplex generator Maximum distances initial simplex Multi-update Bárány and Onn
Few solutions generator Multi-update hybrid
Infeasible case generator Maximum volume heuristic
Guess and check
Enumeration with geometric heuristic
Relaxation with semidefinite programming

This page maintained by Tamon Stephen. Last modified June 2nd, 2008.