GLPK/Using the GLPK callable library

From Wikibooks, open books for an open world
Jump to: navigation, search

This page describes issues related to the use of GLPK as a callable library. As such this page should be primarily of interest to developers writing application programs in C or C++ and making use of the GLPK application programming interface (API).

Official documentation[edit]

The official GLPK documentation file doc/glpk.pdf contains a full reference for the GLPK API. That material is therefore not repeated here. See obtaining GLPK.

Short example[edit]

The following API example implements the linear constrained optimization model:

maximize 0.6 x_1 + 0.5 x_2
subject to x_1 + 2 x_2 \le 1
3 x_1 + x_2 \le 2
/* short.c */
 
#include <stdio.h>            /* C input/output                       */
#include <stdlib.h>           /* C standard library                   */
#include <glpk.h>             /* GNU GLPK linear/mixed integer solver */
 
int main(void)
{
  /* declare variables */
  glp_prob *lp;
  int ia[1+1000], ja[1+1000];
  double ar[1+1000], z, x1, x2;
  /* create problem */
  lp = glp_create_prob();
  glp_set_prob_name(lp, "short");
  glp_set_obj_dir(lp, GLP_MAX);
  /* fill problem */
  glp_add_rows(lp, 2);
  glp_set_row_name(lp, 1, "p");
  glp_set_row_bnds(lp, 1, GLP_UP, 0.0, 1.0);
  glp_set_row_name(lp, 2, "q");
  glp_set_row_bnds(lp, 2, GLP_UP, 0.0, 2.0);
  glp_add_cols(lp, 2);
  glp_set_col_name(lp, 1, "x1");
  glp_set_col_bnds(lp, 1, GLP_LO, 0.0, 0.0);
  glp_set_obj_coef(lp, 1, 0.6);
  glp_set_col_name(lp, 2, "x2");
  glp_set_col_bnds(lp, 2, GLP_LO, 0.0, 0.0);
  glp_set_obj_coef(lp, 2, 0.5);
  ia[1] = 1, ja[1] = 1, ar[1] = 1.0; /* a[1,1] = 1 */
  ia[2] = 1, ja[2] = 2, ar[2] = 2.0; /* a[1,2] = 2 */
  ia[3] = 2, ja[3] = 1, ar[3] = 3.0; /* a[2,1] = 3 */
  ia[4] = 2, ja[4] = 2, ar[4] = 1.0; /* a[2,2] = 1 */
  glp_load_matrix(lp, 4, ia, ja, ar);
  /* solve problem */
  glp_simplex(lp, NULL);
  /* recover and display results */
  z = glp_get_obj_val(lp);
  x1 = glp_get_col_prim(lp, 1);
  x2 = glp_get_col_prim(lp, 2);
  printf("z = %g; x1 = %g; x2 = %g\n", z, x1, x2);
  /* housekeeping */
  glp_delete_prob(lp);
  glp_free_env();
  return 0;
}

Production code would, of course, check the return value from function glp_simplex and react accordingly.

Linux[edit]

These instructions relate to Linux (the details for other operating systems should be similar).

Build short using your system compiler, in this case GNU GCC:

$ gcc -Wall short.c -lglpk -o short

Run the resulting binary:

$ ./short 
*     0: obj =   0.000000000e+00  infeas =  0.000e+00 (0)
*     2: obj =   4.600000000e-01  infeas =  0.000e+00 (0)
OPTIMAL SOLUTION FOUND
z = 0.46; x1 = 0.6; x2 = 0.2

You should obtain x_1 = 0.6 and x_2 = 0.2 as part of the terminal output from your program.

The GLPK runtime reporting format (the lines starting *) are covered in the callable library part of the official GLPK documentation and also here.

The same problem is coded in MathProg.

Submitting patches[edit]

GLPK patches are best submitted by posting them to the most appropriate of the two GLPK mailing lists. Note that the GLPK project does not maintain a web-based source code repository.

If creating source file patches, please refrain from using tabs and restrict line lengths to 72 chars.

Thread safety[edit]

GLPK is not inherently thread safe. Please consult the GLPK newsgroup archives for more information about the use of GLPK APIs under concurrent execution. In particular, see this discussion and, more latterly, this discussion.

If your problem involves multiple LPs (or can be structured thus), then consider running each LP as a separate processes. This makes sense only for multi-core hardware.

Reenterability[edit]

Andrew said that reenterability is a property of the code that allows running several instances of the same program in parallel using the only copy of that program in the memory. This property requires the program not to alter its own code and statically allocated data. See also Wikipedia definition of reentrancy.

The glpk code is reenterable except two internal routines tls_set_ptr and tls_get_ptr (see src/glpenv02.c). In a reenterable version of glpk these two routines should be replaced with platform-specific ones.

The current version of glpenv02.c is not reentrant:

static void *tls = NULL;
 
void tls_set_ptr(void *ptr)
{     tls = ptr;
      return;
}
 
void *tls_get_ptr(void)
{     void *ptr;
      ptr = tls;
      return ptr;
}

Andrew suggested reentrant version:

#include <pthread.h>
pthread_key_t _glp_pth_key;
/* must be initialized in the main program */
 
void tls_set_ptr(void *ptr)
{     pthread_setspecific(_glp_pth_key, ptr);
      return;
}
 
void *tls_get_ptr(void)
{     void *ptr;
      ptr = pthread_getspecific(_glp_pth_key);
      return ptr;
}

Latest GCC compilers have storage class keyword __thread :

static __thread void *tls = NULL;
 
void tls_set_ptr(void *ptr)
{     tls = ptr;
}
 
void *tls_get_ptr(void)
{     return tls;
}

Visual Studio 2005 compiler has similar storage-class modifier __declspec( thread ):

static __declspec( thread ) void *tls = NULL;
 
void tls_set_ptr(void *ptr)
{     tls = ptr;
}
 
void *tls_get_ptr(void)
{     return tls;
}

Deprecated GLPK APIs[edit]

A number of GLPK APIs have been recently deprecated and replaced. Unless otherwise stated, the lpx_ prefix has been replaced with a glp_ prefix. In all cases, developers should double check with the official documentation.

As of version 4.49, developers must migrate to these new APIs. The old API routines, whose names begin with lpx_, have now been removed from the GLPK API and are no longer available.

GLPK Deprecated Comment
4.16 lpx_add_cols
lpx_add_rows
lpx_create_index
lpx_create_prob
lpx_del_cols
lpx_del_rows
lpx_delete_index
lpx_delete_prob
lpx_find_col
lpx_find_row
lpx_get_col_dual
lpx_get_col_kind
lpx_get_col_lb
lpx_get_col_name
lpx_get_col_prim
lpx_get_col_stat
lpx_get_col_type
lpx_get_col_ub
lpx_get_mat_col
lpx_get_mat_row
lpx_get_num_bin
lpx_get_num_cols
lpx_get_num_int
lpx_get_num_nz
lpx_get_num_rows
lpx_get_obj_coef
lpx_get_obj_dir
lpx_get_obj_name
lpx_get_obj_val
lpx_get_prob_name
lpx_get_row_dual
lpx_get_row_lb
lpx_get_row_name
lpx_get_row_prim
lpx_get_row_stat
lpx_get_row_type
lpx_get_row_ub
lpx_ipt_col_dual
lpx_ipt_col_prim
lpx_ipt_obj_val
lpx_ipt_row_dual
lpx_ipt_row_prim
lpx_load_matrix
lpx_mip_col_val
lpx_mip_obj_val
lpx_mip_row_val
lpx_set_col_bnds
lpx_set_col_kind
lpx_set_col_name
lpx_set_col_stat
lpx_set_mat_col
lpx_set_mat_row
lpx_set_obj_coef
lpx_set_obj_dir
lpx_set_obj_name
lpx_set_prob_name
lpx_set_row_bnds
lpx_set_row_name
lpx_set_row_stat
4.18 lpx_simplex
4.20 lpx_integer see: glp_iotopt
4.29 lpx_read_mps
lpx_read_freemps
lpx_write_mps
lpx_write_freemps
lpx_read_cpxlp
lpx_write_cpxlp
4.31 lpx_scale_prob
lpx_std_basis
lpx_adv_basis
lpx_cpx_basis
4.32 lpx_integer
lpx_intopt
4.33 lpx_exact
lpx_get_ray_info see: glp_unbnd_ray
lpx_interior
lpx_read_model
4.37 lpx_print_sol
lpx_print_ips see: lpx_print_ipt
lpx_print_mip
lpx_print_prob see: glp_print_lp
4.41 lpx_transform_row
lpx_transform_col
lpx_prim_ratio_test
lpx_dual_ratio_test
4.42 lpx_print_sens_bnds see: glp_print_ranges
4.49 lpx_check_kkt see: glp_check_kkt

Recently added GLPK APIs[edit]

New APIs get added to GLPK from time to time. These are listed below. If appropriate, a new API may also be exposed by an associated GLPSOL command-line option in the same or a subsequent release.

Note: this information only dates back as far as release 4.31 in February 2007.

GLPK Added Comment
4.49 glp_check_kkt replaces lpx_check_kkt
glp_mincost_relax4 solve minimum cost flow problem using RELAX-IV code
4.47 glp_intfeas1 solve CNF-SAT problem instance with GLPK code (tentative)
4.46 glp_read_cnfsat read CNF-SAT problem data in DIMACS format
glp_write_cnfsat write CNF-SAT problem data in DIMACS format
glp_check_cnfsat check CNF-SAT problem instance
glp_minisat1 solve CNF-SAT problem instance with MiniSat
4.44 glp_cpp solve critical path problems
4.42 glp_check_dup check for duplicate elements in sparse matrix
glp_sort_matrix sort elements of the constraint matrix
glp_read_prob read problem data in GLPK format
glp_write_prob write problem data in GLPK format
glp_analyze_bound analyze active bound of non-basic variable
glp_analyze_coef analyze objective coefficient at basic variable
glp_print_ranges print sensitivity analysis report
4.41 glp_transform_row transform explicitly specified row
glp_transform_col transform explicitly specified column
glp_prim_rtest perform primal ratio test
glp_dual_rtest perform dual ratio test
4.40 glp_del_vertices remove vertices from graph
glp_del_arc remove arc from graph
glp_wclique_exact find maximum weight clique with the exact algorithm developed by Prof P Ostergard
glp_read_ccdata read graph in DIMACS clique/coloring format
glp_write_ccdata write graph in DIMACS clique/coloring format
4.39 glp_warm_up "warm up" LP basis
glp_set_vertex_name assign (change) vertex name
glp_create_v_index create vertex name index
glp_find_vertex find vertex by its name
glp_delete_v_index delete vertex name index
glp_read_asnprob read assignment problem data in DIMACS format
glp_write_asnprob write assignment problem data in DIMACS format
glp_check_asnprob check correctness of assignment problem data
glp_asnprob_lp convert assignment problem to LP
glp_asnprob_okalg solve assignment problem with the out-of-kilter algorithm
glp_asnprob_hall find bipartite matching of maximum cardinality with Hall's algorithm
4.37 glp_print_sol write basic solution in printable format
glp_print_ipt write interior-point solution in printable format
glp_print_mip write MIP solution in printable format
glp_read_graph read (di)graph from plain text file
glp_write_graph write (di)graph to plain text file
glp_weak_comp find all weakly connected components
glp_strong_comp find all strongly connected components
4.36 glp_mincost_okalg find minimum-cost flow with out-of-kilter algorithm
glp_maxflow_ffalg find maximal flow with Ford-Fulkerson algorithm
4.35 glp_create_graph create graph
glp_set_graph_name assign (change) graph name
glp_add_vertices add new vertices to graph
glp_add_arc add new arc to graph
glp_erase_graph erase graph content
glp_delete_graph delete graph
glp_read_mincost read minimum cost flow problem data in DIMACS format
glp_write_mincost write minimum cost flow problem data in DIMACS format
glp_mincost_lp convert minimum cost flow problem to LP
glp_netgen Klingman's network problem generator
glp_gridgen grid-like network problem generator
glp_read_maxflow read maximum flow problem data in DIMACS format
glp_write_maxflow write maximum flow problem data in DIMACS format
glp_maxflow_lp convert maximum flow problem to LP
glp_rmfgen Goldfarb's maximum flow problem generator
4.33 glp_copy_prob copy problem object content
glp_exact solve LP in exact arithmetic (makes lpx_exact deprecated)
glp_get_unbnd_ray determine variable causing unboundedness (makes lpx_get_ray_info deprecated)
glp_interior solve LP with interior-point method (makes lpx_interior deprecated)
4.32 glp_ios_row_attr determine additional row attributes
glp_ios_pool_size determine current size of the cut pool
glp_ios_add_row add constraint to the cut pool
glp_ios_del_row delete constraint from the cut pool
glp_ios_clear_pool delete all constraints from the cut pool
4.31 glp_scale_prob automatic scaling of problem data
glp_std_basis construct standard initial LP basis
glp_adv_basis construct advanced initial LP basis
glp_cpx_basis construct Bixby's initial LP basis