Add GLPK Integration

Add a bridge to the GLPK library. Availability is auto-discovered by
the build system. Most of the code is solver-agnostic.

8 files changed, 267 insertions, 12 deletions

diff --git a/native/Makefile b/native/Makefile
index 6d2a144..36cb08f 100644
--- a/native/Makefile
+++ b/native/Makefile
@@ -55,15 +55,33 @@ ifneq ($(CPLEX),)
 # The CPLEX variable now contains the canonicalized path to the cplex
 # binary. From this, we can extract the include and library paths.
 CPLEX_DIR := ${realpath ${dir $(CPLEX)}/../..}
+CPLEX_PATH ?= $(CPLEX_DIR)
+endif
 
-${info Found CPLEX installation in $(CPLEX_DIR).}
-
+ifneq ($(CPLEX_PATH),)
+${info Linking with CPLEX installation in $(CPLEX_DIR).}
 # Add headers, libraries, and definitions.
-INCLUDES += -I$(CPLEX_DIR)/include/
+INCLUDES += -I$(CPLEX_PATH)/include/
 LIBS     += -lilocplex -lcplex -lconcert
 DEFS     += -DCONFIG_HAVE_CPLEX
 endif
 
+
+# #### GLPK Support ####
+
+GLPK := ${realpath ${shell which glpsol}}
+ifneq ($(GLPK),)
+GLPK_DIR :=${realpath ${dir $(GLPK)}/..}
+GLPK_PATH ?= $(GLPK_DIR)
+endif
+
+ifneq ($(GLPK_PATH),)
+${info Linking with GLPK installed at prefix=$(GLPK_DIR).}
+INCLUDES += -I$(GLPK_PATH)/include
+LIBS     += -L$(GLPK_PATH)/lib -lglpk
+DEFS     += -DCONFIG_HAVE_GLPK
+endif
+
 # #### Debug support ####
 ifeq ($(DEBUG),y)
 DEFS += -g -DDEBUG
@@ -99,9 +117,16 @@ SYNC_OBJ += rw-phase-fair.o rw-task-fair.o
 ALL = testmain _sched.so _locking.so _sim.so
 
 # Compile LP-based code only if we have a solver.
-ifneq ($(CPLEX),)
-LP_OBJ    = lp_common.o lp_dflp.o lp_dpcp.o
-LP_OBJ   += cplex.o io.o
+ifneq ($(CPLEX_PATH)$(GLPK_PATH),)
+LP_OBJ    = lp_common.o io.o lp_dflp.o lp_dpcp.o
+
+ifneq ($(CPLEX_PATH),)
+LP_OBJ   += cplex.o
+endif
+
+ifneq ($(GLPK_PATH),)
+LP_OBJ   += glpk.o
+endif
 
 ALL += _lp_analysis.so
 endif
diff --git a/native/include/linprog/glpk.h b/native/include/linprog/glpk.h
new file mode 100644
index 0000000..fa2aec9
--- /dev/null
+++ b/native/include/linprog/glpk.h
@@ -0,0 +1,8 @@
+#ifndef LINPROG_GLPK_H
+#define LINPROG_GLPK_H
+
+#include "linprog/solver.h"
+
+Solution *glpk_solve(const LinearProgram& lp, unsigned int max_num_vars);
+
+#endif
diff --git a/native/include/linprog/solver.h b/native/include/linprog/solver.h
index 15e37e6..0129903 100644
--- a/native/include/linprog/solver.h
+++ b/native/include/linprog/solver.h
@@ -24,6 +24,21 @@ public:
         }
 };
 
+#if defined(CONFIG_HAVE_GLPK)
 
+#include "linprog/glpk.h"
+#define linprog_solve(lp, vars) glpk_solve((lp), (vars))
+
+#elif defined(CONFIG_HAVE_CPLEX)
+
+#include "linprog/cplex.h"
+#define linprog_solve(lp, vars) cplex_solve((lp), (vars))
+
+#else
+
+#warning No LP solver available.
+#define linprog_solve(lp, vars) assert(0)
+
+#endif
 
 #endif
diff --git a/native/include/lp_common.h b/native/include/lp_common.h
index d5a8a60..16aad8a 100644
--- a/native/include/lp_common.h
+++ b/native/include/lp_common.h
@@ -10,7 +10,7 @@
 #include "stl-hashmap.h"
 
 #include "linprog/model.h"
-#include "linprog/cplex.h"
+#include "linprog/solver.h"
 
 enum blocking_type
 {
diff --git a/native/src/blocking/linprog/lp_dflp.cpp b/native/src/blocking/linprog/lp_dflp.cpp
index 6198825..0370358 100644
--- a/native/src/blocking/linprog/lp_dflp.cpp
+++ b/native/src/blocking/linprog/lp_dflp.cpp
@@ -153,7 +153,7 @@ static BlockingBounds* _lp_dflp_bounds(const ResourceSharingInfo& info,
 #endif
 
         // Solve the big, combined LP.
-        Solution *sol = cplex_solve(lp, var_idx);
+        Solution *sol = linprog_solve(lp, var_idx);
 
         assert(sol != NULL);
 
@@ -225,7 +225,7 @@ static void apply_dflp_bounds_for_task(
         solver_cost.start();
 #endif
 
-        Solution *sol = cplex_solve(lp, vars.get_num_vars());
+        Solution *sol = linprog_solve(lp, vars.get_num_vars());
 
 #if DEBUG_LP_OVERHEADS >=2
         solver_cost.stop();
diff --git a/native/src/blocking/linprog/lp_dpcp.cpp b/native/src/blocking/linprog/lp_dpcp.cpp
index 1b1cf32..bec131b 100644
--- a/native/src/blocking/linprog/lp_dpcp.cpp
+++ b/native/src/blocking/linprog/lp_dpcp.cpp
@@ -371,7 +371,7 @@ static BlockingBounds* _lp_dpcp_bounds(const ResourceSharingInfo& info,
 #endif
 
         // Solve the big, combined LP.
-        Solution *sol = cplex_solve(lp, var_idx);
+        Solution *sol = linprog_solve(lp, var_idx);
 
         assert(sol != NULL);
 
@@ -445,7 +445,7 @@ static void apply_dpcp_bounds_for_task(
         solver_cost.start();
 #endif
 
-        Solution *sol = cplex_solve(lp, vars.get_num_vars());
+        Solution *sol = linprog_solve(lp, vars.get_num_vars());
 
 #if DEBUG_LP_OVERHEADS >= 2
         solver_cost.stop();
diff --git a/native/src/linprog/glpk.cpp b/native/src/linprog/glpk.cpp
new file mode 100644
index 0000000..9ddf2c6
--- /dev/null
+++ b/native/src/linprog/glpk.cpp
@@ -0,0 +1,206 @@
+#include <assert.h>
+#include <glpk.h>
+
+#include <iostream>
+
+#include "cpu_time.h"
+
+#include "linprog/glpk.h"
+
+class GLPKSolution : public Solution
+{
+private:
+        glp_prob *glpk;
+        const LinearProgram &linprog;
+        const unsigned int num_cols;
+        const unsigned int num_rows;
+        unsigned int num_coeffs;
+
+        bool solved;
+
+        void solve(double var_lb, double var_ub);
+        void set_objective();
+        void set_bounds(double col_lb, double col_ub);
+        void set_coefficients();
+public:
+
+        GLPKSolution(const LinearProgram &lp, unsigned int max_num_vars,
+                     double var_lb = 0.0, double var_ub = 1.0);
+
+        ~GLPKSolution();
+
+        double get_value(unsigned int var) const
+        {
+                return glp_get_col_prim(glpk, var + 1);
+        }
+
+        bool is_solved() const
+        {
+                return solved;
+        }
+};
+
+GLPKSolution::GLPKSolution(const LinearProgram& lp, unsigned int max_num_vars,
+                           double var_lb, double var_ub)
+        : glpk(glp_create_prob()),
+          linprog(lp),
+          num_cols(max_num_vars),
+          num_rows(lp.get_equalities().size() +
+                   lp.get_inequalities().size()),
+          num_coeffs(0),
+          solved(false)
+{
+        if (num_cols)
+                solve(var_lb, var_ub);
+        else
+                // Trivial case: no variables.
+                // This can happen if a task set does not
+                // contain any shared resources.
+                solved = true;
+}
+
+void GLPKSolution::solve(double var_lb, double var_ub)
+{
+#if DEBUG_LP_OVERHEADS >= 3
+        static DEFINE_CPU_CLOCK(init_costs);
+        static DEFINE_CPU_CLOCK(model_costs);
+        static DEFINE_CPU_CLOCK(solver_costs);
+
+        init_costs.start();
+#endif
+        glp_term_out(GLP_OFF);
+        glp_set_obj_dir(glpk, GLP_MAX);
+        glp_add_cols(glpk, num_cols);
+        glp_add_rows(glpk, num_rows);
+
+#if DEBUG_LP_OVERHEADS >= 3
+        init_costs.stop();
+        model_costs.start();
+#endif
+
+        set_objective();
+        set_bounds(var_lb, var_ub);
+        set_coefficients();
+
+#if DEBUG_LP_OVERHEADS >= 3
+        model_costs.stop();
+        solver_costs.start();
+#endif
+
+        glp_smcp glpk_params;
+
+        glp_init_smcp(&glpk_params);
+
+        glpk_params.presolve = GLP_ON;
+
+        solved = glp_simplex(glpk, &glpk_params) == 0 &&
+                glp_get_status(glpk) == GLP_OPT;
+
+#if DEBUG_LP_OVERHEADS >= 3
+        solver_costs.stop();
+
+        std::cout << init_costs << std::endl
+                  << model_costs << std::endl
+                  << solver_costs << std::endl;
+#endif
+}
+
+GLPKSolution::~GLPKSolution()
+{
+        glp_delete_prob(glpk);
+}
+
+void GLPKSolution::set_objective()
+{
+        assert(linprog.get_objective()->get_terms().size() == num_cols);
+
+        foreach (linprog.get_objective()->get_terms(), term)
+                glp_set_obj_coef(glpk, term->second + 1, term->first);
+}
+
+
+void GLPKSolution::set_bounds(double col_lb, double col_ub)
+{
+        unsigned int r = 1;
+
+        foreach(linprog.get_equalities(), equ)
+        {
+                glp_set_row_bnds(glpk, r++, GLP_FX,
+                                 equ->second, equ->second);
+
+                num_coeffs += equ->first->get_terms().size();
+        }
+
+        foreach(linprog.get_inequalities(), inequ)
+        {
+                glp_set_row_bnds(glpk, r++, GLP_UP,
+                                 0, inequ->second);
+
+                num_coeffs += inequ->first->get_terms().size();
+        }
+
+        for (unsigned int c = 1; c <= num_cols; c++)
+                glp_set_col_bnds(glpk, c, GLP_DB, col_lb, col_ub);
+}
+
+void GLPKSolution::set_coefficients()
+{
+        int *row_idx, *col_idx;
+        double *coeff;
+
+        row_idx = new int[1 + num_coeffs];
+        col_idx = new int[1 + num_coeffs];
+        coeff   = new double[1 + num_coeffs];
+
+        unsigned int r = 1, k = 1;
+
+        foreach(linprog.get_equalities(), equ)
+        {
+                foreach(equ->first->get_terms(), term)
+                {
+                        assert(k <= num_coeffs);
+
+                        row_idx[k] = r;
+                        col_idx[k] = 1 + term->second;
+                        coeff[k]   = term->first;
+
+                        k += 1;
+                }
+                r += 1;
+        }
+
+
+        foreach(linprog.get_inequalities(), inequ)
+        {
+                foreach(inequ->first->get_terms(), term)
+                {
+                        assert(k <= num_coeffs);
+
+                        row_idx[k] = r;
+                        col_idx[k] = 1 + term->second;
+                        coeff[k]   = term->first;
+
+                        k += 1;
+                }
+                r += 1;
+        }
+
+        glp_load_matrix(glpk, num_coeffs, row_idx, col_idx, coeff);
+
+        delete[] row_idx;
+        delete[] col_idx;
+        delete[] coeff;
+}
+
+
+Solution *glpk_solve(const LinearProgram& lp, unsigned int max_num_vars)
+{
+        GLPKSolution *sol =  new GLPKSolution(lp, max_num_vars);
+        if (sol->is_solved())
+                return sol;
+        else
+        {
+                delete sol;
+                return NULL;
+        }
+}
diff --git a/native/src/testmain.cpp b/native/src/testmain.cpp
index 767af02..a68b786 100644
--- a/native/src/testmain.cpp
+++ b/native/src/testmain.cpp
@@ -930,7 +930,8 @@ int main(int argc, char** argv)
 
         delete results;
 
-#if defined(CONFIG_HAVE_CPLEX)
+
+#if defined(CONFIG_HAVE_CPLEX) || defined(CONFIG_HAVE_GLPK)
 
         results = lp_dpcp_bounds(rsi, loc, false);