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). Official documentation 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 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 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 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 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 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 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 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