# linux.conf.au Presentations

## Working with GLPK

Tutorial

"Linear programming is a tool for solving optimization problems. In 1947, George Dantzig developed an efficient method, the simplex algorithm, for solving linear programming problems. Since the development of the simplex algorithm, linear programming has been used to solve optimization problems in industries as diverse as banking, education, forestry, petroleum, and trucking. In a survey of Fortune 500 firms, 85% of the respondents said they had used linear programming." From: Wayne L. Winston, Operations Research Tools have been developed to solve linear optimization problems. They implement scientific methods described in operations research bibliography. GLPK is one of these tools. The objective of this tutorial is to provide the audience an introduction on how to use GLPK to solve a set of optimization problems: linear programming problems (LP), integer problems (IP), mixed integer programming problems (MIP) and a few other related problems. The tutorial is focused on the following aspects: * Brief description of GLPK: scientific methods implemented, callable library (APIs) * Presenting the GNU MathProg Language through the examples * How to use glpsol * Analyzing GLPK results through the examples * Using Branch & Bound Canonical Operations Research examples written in GNU MathProg: * Very simple two-variable LP * Diet problem * Work-scheduling problem * Short-term financial problem * Blending problem * Production process problem * Set covering problem * Knapsack problem References: - GLPK: http://www.gnu.org/software/glpk/glpk.html Observation: some knowlegde on formulating optimization problems is desired but is not a requisite for the audience. About the tutorial: the author sympathizes with the idea of showing the world that a free software tool to solve optimization problems exists. He has been invited to present this tutorial at the State University of Campinas (SP, Brazil) and LacFREE 2005 (PE, Brazil). Links: - State University of Campinas: http://www.unicamp.br -LacFREE 2005: - http://www.lacfree2005.org/

### Rodrigo Ceron Ferreira de Castro

Rodrigo Ceron was born in São Paulo, Brazil. He studied computer engineering in the State University of Campinas where he also participated in digital speech synthesis researches. He got the ``Instituto de Engenharia'' (Engineering Institute) prize and CREA-SP (Engineering Council) Certification of Honor to the Merit when he graduated. The author has been a free software lover since 2000 and has contributed to open source projects during his free time. He works at IBM Linux Technology Center since 2004.