Last active
October 4, 2016 00:09
-
-
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* 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