Skip to content

Instantly share code, notes, and snippets.

@andrewandrepowell
Last active October 4, 2016 00:09
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save andrewandrepowell/086883b20818cfe8716fa1bb04f16b60 to your computer and use it in GitHub Desktop.
Save andrewandrepowell/086883b20818cfe8716fa1bb04f16b60 to your computer and use it in GitHub Desktop.
Solves a basic linear programming problem with the GPLK ( GNU MathProg ) API. Don't really see too many examples online, so I plan to add a bunch of these.
/* Purpose: Solves the following GNU MathProg program:
*
var x;
var y;
s.t. A: x + 2*y <= 14;
s.t. B: 3*x - y >= 0;
s.t. C: x - y <= 2;
maximize z: 3*x + 4*y;
*
* References:
* GPLK API/DOC: http://kam.mff.cuni.cz/~elias/glpk.pdf
* Example MathProgs: https://www3.nd.edu/~jeff/mathprog/#
* Short Book on Linear Programming: http://www.math.ucla.edu/~tom/LP.pdf
*
* Created on: Oct 3, 2016
* Author: andrewandrepowell2
* Contact: andrewandrepowell2@gmail.com
*/
#include <iostream>
#include <stdexcept>
#include <glpk.h>
#define xstr(s) str(s)
#define str(s) #s
#define assert( i ) if ( ( i )!=0 ) { throw std::runtime_error( "Error on line: " xstr(__LINE__) ); }
/* Wrapper to enforce raii for C-style classes. */
template <typename T_ >
class raii_wrap
{
public:
raii_wrap( T_* ptr, void (*des)( T_* ) ) : ptr ( ptr ), des( des ) { }
~raii_wrap() { des( ptr ); }
operator T_*() { return ptr; }
private:
T_* ptr;
void (*des)( T_* );
raii_wrap( raii_wrap& ref ) : ptr( NULL ), des( NULL ) { }
raii_wrap& operator=( raii_wrap& ref ) { return *this; }
};
int main()
{
try
{
/* Create linear programming problem and associated with cleanup function. */
raii_wrap<glp_prob> lp ( glp_create_prob(), glp_delete_prob );
/* Declare constructs for linear programming problem. */
glp_set_prob_name( lp, "lpex" ); // Name problem.
glp_set_obj_dir( lp, GLP_MAX ); // Define objective of objective function.
{
glp_add_rows( lp, 3 ); // Define number of inequalities ( constraints, soe ).
glp_set_row_name( lp, 1, "A" ); // Name inequality A.
glp_set_row_bnds( lp, 1, GLP_UP, 0.0, 14.0 ); // "A <= 14"
glp_set_row_name( lp, 2, "B" ); // Name inequality B.
glp_set_row_bnds( lp, 2, GLP_LO, 0.0, 0.0 ); // "B >= 0"
glp_set_row_name( lp, 3, "C" ); // Name inequality C.
glp_set_row_bnds( lp, 3, GLP_UP, 0.0, 2.0 ); // "C <= 14"
}
{
glp_add_cols( lp, 2 ); // Define number of dependent variables.
glp_set_col_name( lp, 1, "x" ); // Name variable x.
glp_set_col_bnds( lp, 1, GLP_LO, 0.0, 0.0 ); // "x >= 0"
glp_set_col_name( lp, 2, "y" ); // Name variable y.
glp_set_col_bnds( lp, 2, GLP_LO, 0.0, 0.0 ); // "y >= 0"
}
/* Finally, initialize the constructs. */
int ia[] = { 0, 1, 1, 2, 2, 3, 3 }; // row indices.
int ja[] = { 0, 1, 2, 1, 2, 1, 2 }; // col indices.
double ar[] = { 0.0, 1.0, 2.0, 3.0, -1.0, 1.0, -1.0 }; // values.
glp_load_matrix( lp, 6, ia, ja, ar ); // Load constraints as matrix.
{ // Define objective function.
glp_set_obj_coef( lp, 1, 3.0 ); // "3*x"
glp_set_obj_coef( lp, 2, 4.0 ); // "4*y"
}
/* Solve the problem with Simplex Method. */
assert( glp_simplex( lp, NULL ) );
/* Acquire the results. */
double z = glp_get_obj_val( lp );
double x = glp_get_col_prim( lp, 1 );
double y = glp_get_col_prim( lp, 2 );
std::cout << "z: " << z << "\nx: " << x << "\ny: " << y << std::endl;
}
catch ( std::exception& e )
{
std::cerr << e.what();
}
catch ( ... )
{
std::cerr << "This line should never reach." << std::endl;
}
/* Ensure resources are deallocated. */
glp_free_env();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment