GLPK/Using the GLPK callable library
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).
Contents
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 | |
subject to | |
/* 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 and 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/env/tls.c). In a reenterable version of glpk these two routines should be replaced with platform-specific ones.
The current version of tls.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;
}
This commit makes the library re-rentrant on Windows and Linux.
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 |