help with implementation of Linear programming solver.
 CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: help with implementation of Linear programming solver.

1. Member
Join Date
Sep 2013
Posts
36

## 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.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•