September 17th, 2013, 10:05 AM
#1
help with implementation of Linear programming solver.
I am trying to implement the linear programming solver.
This is the header file of the linear programming solver :
/*!
\internal
Representation of a LP constraint like:
(c1 * X1) + (c2 * X2) + ... = K
or <= K
or >= K
Where (ci, Xi) are the pairs in "variables" and K the real "constant".
*/
struct QSimplexConstraint
{
QSimplexConstraint() : constant(0), ratio(Equal), artificial(0) {}`
enum Ratio {
LessOrEqual = 0,
Equal,
MoreOrEqual
};
QHash<QSimplexVariable *, qreal> variables;
qreal constant;
Ratio ratio;
QPair<QSimplexVariable *, qreal> helper;
QSimplexVariable * artificial;
void invert();
bool isSatisfied() {
qreal leftHandSide(0);
QHash<QSimplexVariable *, qreal>::const_iterator iter;
for (iter = variables.constBegin(); iter != variables.constEnd(); ++iter) {
leftHandSide += iter.value() * iter.key()->result;
}
Q_ASSERT(constant > 0 || qFuzzyCompare(1, 1 + constant));
if ((leftHandSide == constant) || qAbs(leftHandSide - constant) < 0.0000001)
return true;
switch (ratio) {
case LessOrEqual:
return leftHandSide < constant;
case MoreOrEqual:
return leftHandSide > constant;
default:
return false;
}
}
class QSimplex
{
public:
QSimplex();
virtual ~QSimplex();
qreal solveMin();
qreal solveMax();
bool setConstraints(const QList<QSimplexConstraint *> constraints);
void setObjective(QSimplexConstraint *objective);
void dumpMatrix();
private:
// Matrix handling
qreal valueAt(int row, int column);
void setValueAt(int row, int column, qreal value);
void clearRow(int rowIndex);
void clearColumns(int first, int last);
void combineRows(int toIndex, int fromIndex, qreal factor);
// Simplex
bool simplifyConstraints(QList<QSimplexConstraint *> *constraints);
int findPivotColumn();
int pivotRowForColumn(int column);
void reducedRowEchelon();
bool iterate();
// Helpers
void clearDataStructures();
void solveMaxHelper();
enum solverFactor { Minimum = -1, Maximum = 1 };
qreal solver(solverFactor factor);
void collectResults();
QList<QSimplexConstraint *> constraints;
QList<QSimplexVariable *> variables;
QSimplexConstraint *objective;
int rows;
int columns;
int firstArtificial;
qreal *matrix;
};
inline qreal QSimplex::valueAt(int rowIndex, int columnIndex)
{
return matrix[rowIndex * columns + columnIndex];
}
inline void QSimplex::setValueAt(int rowIndex, int columnIndex, qreal value)
{
matrix[rowIndex * columns + columnIndex] = value;
}
I have a text file with some data like:
Maximize:
obj: 3e-06 A - 3e-06 B + 2.7e-01 F
constraints:
RXN1: -1 A + 1 B -1 C + 1 D -1 E -1 F = 0
RXN2: -1 A + 1 B -1 C + 1 D -1 E -1 F = 0
RXN3: -1 A + 1 B -1 C + 1 D -1 E -1 F = 0
RXN4: -1 A + 1 B -1 C + 1 D -1 E -1 F = 0
... many constraints like this
Bounds:
A >= 0
B <= 100
C >= 0
.....
...........many bounds like this.
I wrote a small program to get the data from this file:
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int main()
{
ifstream ifs("Metabolism.txt");
string line;
while(getline(ifs,line)) {
cout << "[ " << line << " ]" << endl;
}
system("PAUSE");
}
I want some help to parse all the constraints and bounds as inputs and get the maximum value of the objective function as the output using the above lpsolver header file.I have also attached the sample file below.
Thanks.
Attached Files
Posting Permissions
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
Forum Rules
Click Here to Expand Forum to Full Width