Add simple C++ linear program representation

- Constraints are expressed as lists of terms.
- Linear programs consist of only equalities and less-than-or-equal constraints.
- Solvers hide behind an abstract solution class that can evaluate
  linear expressions.

3 files changed, 144 insertions, 0 deletions

diff --git a/native/include/linprog/io.h b/native/include/linprog/io.h
new file mode 100644
index 0000000..1e9a3cc
--- /dev/null
+++ b/native/include/linprog/io.h
@@ -0,0 +1,10 @@
+#ifndef LINPROG_IO_H
+#define LINPROG_IO_H
+
+#include <ostream>
+
+#include "linprog/model.h"
+
+std::ostream& operator<<(std::ostream &os, const LinearExpression &exp);
+
+#endif
diff --git a/native/include/linprog/model.h b/native/include/linprog/model.h
new file mode 100644
index 0000000..27729dd
--- /dev/null
+++ b/native/include/linprog/model.h
@@ -0,0 +1,105 @@
+#ifndef LINPROG_MODEL_H
+#define LINPROG_MODEL_H
+
+#include <vector>
+#include <utility>
+
+#include "stl-helper.h"
+
+typedef std::pair<double, unsigned int> Term;
+typedef std::vector<Term> Terms;
+
+class LinearExpression
+{
+private:
+        Terms terms;
+
+public:
+        void add_term(double coefficient, unsigned int variable_index)
+        {
+                terms.push_back(Term(coefficient, variable_index));
+        }
+
+        // by default, assumes coefficient == 1
+        void add_var(unsigned int variable_index)
+        {
+                add_term(1.0, variable_index);
+        }
+
+        const Terms& get_terms(void) const
+        {
+                return terms;
+        }
+
+        bool has_terms(void) const
+        {
+                return !terms.empty();
+        }
+};
+
+typedef std::pair<LinearExpression *, double> Constraint;
+typedef std::vector<Constraint> Constraints;
+
+// builds a maximization problem piece-wise
+class LinearProgram
+{
+        // the function to be maximized
+        LinearExpression *objective;
+
+        // linear expressions constrained to an exact value
+        Constraints equalities;
+
+        // linear expressions constrained by an upper bound (exp <= bound)
+        Constraints inequalities;
+
+public:
+        LinearProgram() : objective(0) {};
+
+        ~LinearProgram()
+        {
+                delete objective;
+                foreach(equalities, eq)
+                        delete eq->first;
+                foreach(inequalities, ineq)
+                        delete ineq->first;
+        }
+
+        void set_objective(LinearExpression *exp)
+        {
+                delete objective;
+                objective = exp;
+        }
+
+        void add_inequality(LinearExpression *exp, double upper_bound)
+        {
+                if (exp->has_terms())
+                        inequalities.push_back(Constraint(exp, upper_bound));
+                else
+                        delete exp;
+        }
+
+        void add_equality(LinearExpression *exp, double equal_to)
+        {
+                if (exp->has_terms())
+                        inequalities.push_back(Constraint(exp, equal_to));
+                else
+                        delete exp;
+        }
+
+        const LinearExpression *get_objective() const
+        {
+                return objective;
+        }
+
+        const Constraints& get_equalities() const
+        {
+                return equalities;
+        }
+
+        const Constraints& get_inequalities() const
+        {
+                return inequalities;
+        }
+};
+
+#endif
diff --git a/native/include/linprog/solver.h b/native/include/linprog/solver.h
new file mode 100644
index 0000000..15e37e6
--- /dev/null
+++ b/native/include/linprog/solver.h
@@ -0,0 +1,29 @@
+#ifndef LINPROG_SOLVER_H
+#define LINPROG_SOLVER_H
+
+#include "linprog/model.h"
+
+class Solution
+{
+
+public:
+        virtual ~Solution() {};
+
+        virtual double get_value(unsigned int variable_index) const = 0;
+
+        virtual double evaluate(const LinearExpression &exp) const
+        {
+                double sum = 0;
+                foreach(exp.get_terms(), term)
+                {
+                        double coeff = term->first;
+                        double var   = term->second;
+                        sum += coeff * get_value(var);
+                }
+                return sum;
+        }
+};
+
+
+
+#endif