GLPK/Third-party API wrappers

This page describes "wrapper" classes which interface with the native GLPK API set to provide additional functionality. This page will be mostly of interest to programmers developing large applications.

The GLPK APIs are, in many respects, relatively low-level and not particularly smart (but they are improving). C++ developers, in particular, sometimes write wrapper classes to interface between GLPK and their client code. Their motivation normally stems from a desire for one or both features:

• the provision of a higher-level and perhaps more tailored and more intelligent client call set
• the ability to switch solvers without disturbing client code — as defined by the need to relink but not recompile.

Intelligence, in this context, includes the ability to maintain row and column counts internally, to recognize incomplete models, to select particular solver calls, to fail gracefully, and other related adaptive behaviors.

Both of the above aspects require design trade-offs, which means that API wrappers tend to be situation-specific to some degree. For instance, the ability to switch solvers may need to exclude specialist solver features in the interests of maintaining commonality.

COIN-OR Open solver interface (Osi)

The key initiative for solver switching is the COIN-OR Osi project.

GLPK is supported through the derived wrapper class OsiGlpk. Tested environments include (no mention of Mac 0S X):

• Windows using Microsoft Visual C++ V6 and V7
• Windows using the Cygwin toolchain
• Linux using g++ 2.95.2 and higher.

Given the ongoing GLPK initiative to update its API set, the OsiGlpk code currently relies on depreciated APIs (as at December 2010, a 2008 ticket seeking alignment remains open ). This may not be an issue for LP problems but could be an issue for branch-and-cut methods. Developers are advised to confirm (and perhaps revise) this interface class before proceeding. COIN-OR Osi is otherwise under steady development.

Osi codebase changes are tracked at projects.coin-or.org/Osi/changeset.

Generic Linear Optimization Package (Glop)

Glop, the Generic Linear Optimization Package, is a library package that provides functions to create, manipulate and solve linear programs (LPs) from within your C or C++ program. Glop is mainly a wrapper library which allows the user to access different existing LP solvers through the same API. Glop supports GLPK and was written by Francois Galea.

LEMON graph library

LEMON is the Library for Efficient Modeling and Optimization in Networks. This is a C++ template library providing a wide range of data structures and algorithms for "combinatorial optimization tasks connected mainly with graphs". GLPK is one of several solvers supported by LEMON.

The LEMON project was launched in 2003 by the Egerváry Research Group on Combinatorial Optimization (EGRES) at the Department of Operations Research, Eötvös Loránd University, Budapest, Hungary. LEMON is a member of the COIN-OR initiative, a collection of OR related open source projects. LEMON is distributed under the Boost Software License version 1.0, a permissive license enabling both commercial and non-commercial use. The Boost license is GPL-compatible. The project maintains an extensive website with user documentation, source browsing, and bug-tracking. It also operates several mailing lists.

IAJAAR.H project

IAJAAR.H is a small project that offers the programmer a specialized triple (3-tuple) container class named IAJAAR. The project is described locally in more detail.

Using C++ vectors

Some users may prefer to use vectors from the C++ standard library rather than C-style arrays.

Take, for example, the standard GLPK tutorial problem. This may be recoded as follows:

// system headers
...
#include <vector>             // STL sequence container

// declare variables
glp_prob *lp;
std::vector<int>    iav;
std::vector<int>    jav;
std::vector<double> arv;
iav.reserve(1001);            // was: int ia[1+1000]
jav.reserve(1001);            // was: int ja[1+1000]
arv.reserve(1001);            // was: double ar[1+1000]
double Z, x1, x2, x3;
int solver_ret;               // exit status of solver
// create problem
lp = glp_create_prob();
glp_set_prob_name(lp, "example using std::vector");
glp_set_obj_dir(lp, GLP_MAX);
// fill problem
glp_add_rows(lp, 3);
...
glp_load_matrix(lp, 9, &iav[0], &jav[0], &arv[0]);  // was: glp_load_matrix(lp, 9, ia, ja, ar)
solver_ret = glp_simplex(lp, NULL);
...

The reason this works is that the C++ standard mandates a std::vector be held in contiguous memory. To this end, Josuttis (1999 p155) writes:

"this example shows that whenever you need an array of type T for any reason (such as for an existing C library) you can use a std::vector<T> and pass it the address of the first element"

This idiom will fail just as surely as a C-style array if you try to read or write out-of-range — but it will throw a C++ exception with a more understandable error message. You can even catch the exception and then exit a little more gracefully if you wish. For example:

glp_prob *lp;
try
  {
    // most of the above code in here
  }
catch(const std::out_of_range& e)
  {
    std::cout << "e.what()" << std::endl;
    // any mopping up
  }
glp_delete_prob(lp);
glp_free_env();

Do not be tempted to reserve more capacity in your vectors at a later point — reallocation will automatically invalidate all references, pointers, and iterators!

If programming under the C++11 standard, you can use initialization lists (to save all the std::vector::push_back calls):

// load the structural matrix data using initialization lists
std::vector<int>    iat = {  1,   1,   2,   2};
std::vector<int>    jat = {  1,   2,   1,   2};
std::vector<double> art = {1.0, 2.0, 3.0, 1.0};

// now prepend the required position zero placeholder (any value will do but zero is safe)
// first create length one vectors using default member construction
std::vector<int>    iav(1);
std::vector<int>    jav(1);
std::vector<double> arv(1);

// then concatenate these with the original data vectors
iav.insert(iav.end(), iat.begin(), iat.end());
jav.insert(jav.end(), jat.begin(), jat.end());
arv.insert(arv.end(), art.begin(), art.end());

// then load the structural matrix data
glp_load_matrix(lp, 9, &iav[0], &jav[0], &arv[0]);  // was: glp_load_matrix(lp, 9, ia, ja, ar)

The std::vector::insert calls are required because GLPK indexes from unity but C++ indexes from zero. Note too that std::deque containers do not guarantee contiguous use of memory.