From 673f367fc5835ebce3357dfebee9c0e414e5c09b Mon Sep 17 00:00:00 2001
From: Bjoern Brandenburg <bbb@mpi-sws.org>
Date: Tue, 7 Aug 2012 20:10:06 +0200
Subject: 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.
---
 native/include/linprog/io.h     |  10 ++++
 native/include/linprog/model.h  | 105 ++++++++++++++++++++++++++++++++++++++++
 native/include/linprog/solver.h |  29 +++++++++++
 3 files changed, 144 insertions(+)
 create mode 100644 native/include/linprog/io.h
 create mode 100644 native/include/linprog/model.h
 create mode 100644 native/include/linprog/solver.h

(limited to 'native/include')

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
-- 
cgit v1.2.2