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;
+}