Add CPLEX integration

This patch introduces a concrete subclass of Solution that implements the actual
solving of linear programs by means of invoking the CPLEX Concert Technology API.

The project can still be compiled on systems that do not have CPLEX installed.

3 files changed, 203 insertions, 3 deletions

diff --git a/native/Makefile b/native/Makefile
index aa8f75c..71a6835 100644
--- a/native/Makefile
+++ b/native/Makefile
@@ -45,6 +45,24 @@ ifeq ($(OS),Linux)
 LIBS += -lrt
 endif
 
+# #### CPLEX Support ####
+
+# See if we can find a CPLEX installation.
+CPLEX := ${realpath ${shell which cplex}}
+ifneq ($(CPLEX),)
+# Yes, we seem to have something that looks like 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)}/../..}
+
+${info Found CPLEX installation in $(CPLEX_DIR).}
+
+# Add headers, libraries, and definitions.
+INCLUDES += -I$(CPLEX_DIR)/include/
+LIBS     += -lilocplex -lcplex -lconcert
+DEFS     += -DCONFIG_HAVE_CPLEX
+endif
 
 # #### Debug support ####
 ifeq ($(DEBUG),y)
@@ -61,8 +79,9 @@ endif
 CXXFLAGS  = -Wall -Wextra -Werror $(DISABLED_WARNINGS) -fPIC $(INCLUDES) $(DEFS)
 LDFLAGS   = $(LIBS)
 SWIGFLAGS = -python -c++ -outdir . -includeall -Iinclude
+
 vpath %.cc interface
-vpath %.cpp src src/edf src/blocking
+vpath %.cpp src src/edf src/blocking src/linprog
 
 # #### Common C++ source files ####
 
@@ -79,6 +98,11 @@ 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    = cplex.o io.o
+endif
+
 .PHONY: all clean
 
 all: ${ALL}
@@ -87,8 +111,8 @@ clean:
         rm -f interface/*.cc interface/*.o *.py
         rm -f *.o ${ALL}
 
-testmain: testmain.o ${CORE_OBJ} ${SYNC_OBJ} ${EDF_OBJ} ${SCHED_OBJ}
-        $(CXX) -o $@ $+ $(LDFLAGS) 
+testmain: testmain.o ${CORE_OBJ} ${SYNC_OBJ} ${EDF_OBJ} ${SCHED_OBJ} ${LP_OBJ}
+        $(CXX) -o $@ $+ $(LDFLAGS)
 
 # #### Python libraries ####
 
diff --git a/native/include/linprog/cplex.h b/native/include/linprog/cplex.h
new file mode 100644
index 0000000..c68bd24
--- /dev/null
+++ b/native/include/linprog/cplex.h
@@ -0,0 +1,8 @@
+#ifndef LINPROG_CPLEX_H
+#define LINPROG_CPLEX_H
+
+#include "linprog/solver.h"
+
+Solution *cplex_solve(const LinearProgram& lp, unsigned int max_num_vars);
+
+#endif
diff --git a/native/src/linprog/cplex.cpp b/native/src/linprog/cplex.cpp
new file mode 100644
index 0000000..b5565d4
--- /dev/null
+++ b/native/src/linprog/cplex.cpp
@@ -0,0 +1,168 @@
+#define IL_STD // required by CPLEX when using STL classes.
+
+#include <ilcplex/ilocplex.h>
+
+#include "cpu_time.h"
+
+#include "linprog/cplex.h"
+
+class CPLEXSolution : public Solution
+{
+private:
+        IloEnv ilo_env;
+        IloEnv& get_env()
+        {
+                return ilo_env;
+        }
+
+        IloNumArray     cplex_values;
+
+        const LinearProgram &linprog;
+
+        bool solved;
+
+        void solve_model(unsigned int max_num_vars,
+                         double var_lb, double var_ub);
+
+        IloObjective make_objective(const IloNumVarArray& vars);
+        IloRangeArray make_constraints(const IloNumVarArray& vars);
+
+        IloRange make_constraint(const IloNumVarArray &vars,
+                                 const LinearExpression *exp, double bound,
+                                 bool is_exact_bound);
+
+public:
+        CPLEXSolution(const LinearProgram &lp, unsigned int max_num_vars,
+                      double var_lb = 0.0, double var_ub = 1.0);
+        ~CPLEXSolution();
+
+        double get_value(unsigned int var) const
+        {
+                return cplex_values[var];
+        }
+
+        bool is_solved() const
+        {
+                return solved;
+        }
+};
+
+CPLEXSolution::CPLEXSolution(const LinearProgram& lp, unsigned int max_num_vars,
+                             double var_lb, double var_ub)
+        : ilo_env(),
+          cplex_values(get_env(), max_num_vars),
+          linprog(lp),
+          solved(false)
+{
+        get_env().setNormalizer(IloFalse);
+        get_env().setOut(get_env().getNullStream());
+
+        if (max_num_vars > 0)
+                solve_model(max_num_vars, var_lb, var_ub);
+        else
+                // Trivial case: no variables.
+                solved = true;
+}
+
+
+void CPLEXSolution::solve_model(unsigned int max_num_vars,
+                                double var_lb, double var_ub)
+{
+        try
+        {
+                IloNumVarArray cplex_vars = IloNumVarArray(get_env(), max_num_vars,
+                                                           var_lb, var_ub);
+
+                IloObjective objective = make_objective(cplex_vars);
+                IloRangeArray constraints = make_constraints(cplex_vars);
+
+                IloModel model = IloModel(get_env());
+
+                model.add(objective);
+                model.add(constraints);
+
+
+                IloCplex cplex = IloCplex(model);
+
+                cplex.solve();
+
+                cplex.getValues(cplex_vars, cplex_values);
+                solved = true;
+
+        } catch (IloException &ex)
+        {
+                // Improve me: we should export some kind of error info.
+                std::cerr << "CPLEX failed: " << ex << std::endl;
+                solved = false;
+        }
+}
+
+IloObjective CPLEXSolution::make_objective(const IloNumVarArray &vars)
+{
+        const LinearExpression *obj = linprog.get_objective();
+
+        IloObjective goal = IloObjective(get_env(), 0,  IloObjective::Maximize);
+        IloNumArray coeffs = IloNumArray(get_env(), vars.getSize());
+
+        assert((int) obj->get_terms().size() <= coeffs.getSize());
+
+        coeffs.add(vars.getSize(), 0);
+
+        // Set coefficient for each variable in the objective function.
+        foreach(obj->get_terms(), term)
+        {
+                double coefficient   = term->first;
+                unsigned int var_idx = term->second;
+                coeffs[var_idx] = coefficient;
+        }
+
+        goal.setLinearCoefs(vars, coeffs);
+
+        return goal;
+}
+
+IloRangeArray CPLEXSolution::make_constraints(const IloNumVarArray &vars)
+{
+        IloRangeArray constraints(get_env());
+
+        foreach (linprog.get_equalities(), exp)
+                constraints.add(make_constraint(vars, exp->first, exp->second, true));
+
+        foreach (linprog.get_inequalities(), exp)
+                constraints.add(make_constraint(vars, exp->first, exp->second, false));
+
+        return constraints;
+}
+
+IloRange CPLEXSolution::make_constraint(const IloNumVarArray &vars,
+                                        const LinearExpression *exp, double bound,
+                                        bool is_exact_bound)
+{
+        IloRange r = IloRange(get_env(), -IloInfinity, bound);
+
+        if (is_exact_bound)
+                r.setLB(bound);
+
+        foreach (exp->get_terms(), term)
+                r.setLinearCoef(vars[term->second], term->first);
+
+        return r;
+}
+
+CPLEXSolution::~CPLEXSolution()
+{
+        get_env().end();
+}
+
+
+Solution *cplex_solve(const LinearProgram& lp, unsigned int max_num_vars)
+{
+        CPLEXSolution *sol =  new CPLEXSolution(lp, max_num_vars);
+        if (sol->is_solved())
+                return sol;
+        else
+        {
+                delete sol;
+                return NULL;
+        }
+}