-
1 Attachment(s)
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.
-
Re: help with implementation of Linear programming solver.
Quote:
Originally Posted by
navy1991
I want some help to parse all the constraints and bounds as inputs
First, use code tags when posting code. The code you posted is practically unreadable without code tags.
What is the exact problem do you have in parsing the input? Where are the data structures in your code to store the parsed input?
Code:
string line;
while(getline(ifs,line)) {
Parsing is much more than just reading a string -- you have to store that data in some structure and in some format, let alone devise a way to interpret the string in the way that satisfies your conditions. Did you have this designed in any way (not coded, but designed)? If not, you need to start with the design first.
Quote:
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.
First things first. Design and write the code to parse the input and place in proper structures and format so that the rest of the code you have knows what to do with the data.
Regards,
Paul McKenzie
-
Re: help with implementation of Linear programming solver.
Hi Paul,
Point noted. I will use code tags.I am trying to design the data structure so that I can manipulate it. Please give me some time to update the design.
Thanks,
navy1991.
-
Re: help with implementation of Linear programming solver.
Designing the data structure:
As the representation of a linear programming problem, I need to collect the pairs in Variables (ci, Xi) (RHS) and then K as real constant (LHS) and then the ratio between. So 3 things : RHS, LHS , Ratio between.
Code:
/*!
\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".
*/
Referring to the code below:
Code:
struct QSimplexConstraint
{
QSimplexConstraint() : constant(0), ratio(Equal), artificial(0) {}`
enum Ratio {
LessOrEqual = 0,
Equal,
MoreOrEqual
};
I understand that they have designed a struct named Qsimplexconstraint . Inside this data structure, they have QsimplexConstraint class (bit confusing -- I guess constant refer to 'K' (RHS) ; ratio refers to the connection between RHS and LHS of the equation. (= , >= , <=) ; artificial refers to the RHS (pairs in variables) ) and enum Ratio (enumerator to choose = , >= , <=).
QList<QSimplexConstraint *> constraints;
This helps me to understand that they have created QList Constraints (I guess it is a special type in c++ Qt ). Could you please explain more about QList ?
From
Code:
QHash<QSimplexVariable *, qreal> variables;
qreal constant;
Ratio ratio;
I understand that they have created a special QHash variables (Qhash means a way to search by splitting the data into equal halves and to continue)
From
Code:
QPair<QSimplexVariable *, qreal> helper;
QSimplexVariable * artificial;
I understand they have used Qpair to pair the QsimplexVariable pointer named artificial (RHS -- (c1, x1)) to qreal (LHS).
In summary, I am clear about three parts :
1.) RHS (right handside)
2.) LHS
3.) Ratio between.
This is what I have understood till now. Could you please tell me what should I do next.
Thanks.
-
Re: help with implementation of Linear programming solver.
Did you write that template class yourself? If not, then shouldn't there have been examples of how to use it? What good is a class if no one knows how it's used?
Quote:
This is what I have understood till now. Could you please tell me what should I do next.
Contact the author(s) of the class. Again, no one writes something like this without showing how to use it.
Regards,
Paul McKenzie
-
Re: help with implementation of Linear programming solver.
Hi paul,
This is an assignment problem in one of the research lab. I did not write the LP solver.It comes under Operations Research. I just want to use it to solve my problem. My problem is called Flux Balance Analysis. I managed to get the source file of the solver too (.cpp file). I have pasted it below :
Code:
QT_BEGIN_NAMESPACE
QSimplex::QSimplex() : objective(0), rows(0), columns(0), firstArtificial(0), matrix(0)
{
}
QSimplex::~QSimplex()
{
clearDataStructures();
}
void QSimplex::clearDataStructures()
{
if (matrix == 0)
return;
// Matrix
rows = 0;
columns = 0;
firstArtificial = 0;
free(matrix);
matrix = 0;
// Constraints
for (int i = 0; i < constraints.size(); ++i) {
delete constraints[i]->helper.first;
constraints[i]->helper.first = 0;
constraints[i]->helper.second = 0.0;
delete constraints[i]->artificial;
constraints[i]->artificial = 0;
}
constraints.clear();
// Other
variables.clear();
objective = 0;
}
void QSimplex::setConstraints(const QList<QSimplexConstraint *> newConstraints)
{
clearDataStructures();
if (newConstraints.isEmpty())
return;
constraints = newConstraints;
// Set Variables direct mapping
QSet<QSimplexVariable *> variablesSet;
for (int i = 0; i < constraints.size(); ++i)
variablesSet += \
QSet<QSimplexVariable *>::fromList(constraints[i]->variables.keys());
variables = variablesSet.toList();
// Set Variables reverse mapping
for (int i = 0; i < variables.size(); ++i) {
// The variable "0" goes at the column "1", etc...
variables[i]->index = i + 1;
}
// Normalize Constraints
int variableIndex = variables.size();
QList <QSimplexVariable *> artificialList;
for (int i = 0; i < constraints.size(); ++i) {
QSimplexVariable *slack;
QSimplexVariable *surplus;
QSimplexVariable *artificial;
Q_ASSERT(constraints[i]->helper.first == 0);
Q_ASSERT(constraints[i]->artificial == 0);
switch(constraints[i]->ratio) {
case QSimplexConstraint::LessOrEqual:
slack = new QSimplexVariable;
slack->index = ++variableIndex;
constraints[i]->helper.first = slack;
constraints[i]->helper.second = 1.0;
break;
case QSimplexConstraint::MoreOrEqual:
surplus = new QSimplexVariable;
surplus->index = ++variableIndex;
constraints[i]->helper.first = surplus;
constraints[i]->helper.second = -1.0;
// fall through
case QSimplexConstraint::Equal:
artificial = new QSimplexVariable;
constraints[i]->artificial = artificial;
artificialList += constraints[i]->artificial;
break;
}
}
firstArtificial = variableIndex + 1;
for (int i = 0; i < artificialList.size(); ++i)
artificialList[i]->index = ++variableIndex;
artificialList.clear();
// Matrix
// One for each variable plus the Basic and BFS columns (first and last)
columns = variableIndex + 2;
// One for each constraint plus the objective function
rows = constraints.size() + 1;
matrix = (qreal *)malloc(sizeof(qreal) * columns * rows);
if (!matrix) {
qWarning() << "QSimplex: Unable to allocate memory!";
return;
}
for (int i = columns * rows - 1; i >= 0; --i)
matrix[i] = 0.0;
// Fill Matrix
for (int i = 1; i <= constraints.size(); ++i) {
QSimplexConstraint *c = constraints[i - 1];
if (c->artificial) {
// Will use artificial basic variable
setValueAt(i, 0, c->artificial->index);
setValueAt(i, c->artificial->index, 1.0);
if (c->helper.second != 0.0) {
// Surplus variable
setValueAt(i, c->helper.first->index, c->helper.second);
}
} else {
// Slack is used as the basic variable
Q_ASSERT(c->helper.second == 1.0);
setValueAt(i, 0, c->helper.first->index);
setValueAt(i, c->helper.first->index, 1.0);
}
QHash<QSimplexVariable *, qreal>::const_iterator iter;
for (iter = c->variables.constBegin();
iter != c->variables.constEnd();
++iter) {
setValueAt(i, iter.key()->index, iter.value());
}
setValueAt(i, columns - 1, c->constant);
}
// Set temporary objective: -1 * sum_of_artificial_vars
for (int j = firstArtificial; j < columns - 1; ++j)
setValueAt(0, j, 1.0);
// Maximize our objective (artificial vars go to zero)
solveMaxHelper();
if (valueAt(0, columns - 1) != 0.0) {
qWarning() << "QSimplex: No feasible solution!";
clearDataStructures();
return;
}
// Remove artificial variables
clearColumns(firstArtificial, columns - 2);
}
void QSimplex::solveMaxHelper()
{
reducedRowEchelon();
while (iterate()) ;
}
void QSimplex::setObjective(QSimplexConstraint *newObjective)
{
objective = newObjective;
}
void QSimplex::clearRow(int rowIndex)
{
qreal *item = matrix + rowIndex * columns;
for (int i = 0; i < columns; ++i)
item[i] = 0.0;
}
void QSimplex::clearColumns(int first, int last)
{
for (int i = 0; i < rows; ++i) {
qreal *row = matrix + i * columns;
for (int j = first; j <= last; ++j)
row[j] = 0.0;
}
}
void QSimplex::dumpMatrix()
{
printf("---- Simplex Matrix ----\n");
printf(" ");
for (int j = 0; j < columns; ++j)
printf(" <% 2d >", j);
printf("\n");
for (int i = 0; i < rows; ++i) {
printf("Row %2d:", i);
qreal *row = matrix + i * columns;
for (int j = 0; j < columns; ++j) {
printf(" % 2.2f", row[j]);
}
printf("\n");
}
printf("------------------------\n\n");
}
void QSimplex::combineRows(int toIndex, int fromIndex, qreal factor)
{
if (!factor)
return;
qreal *from = matrix + fromIndex * columns;
qreal *to = matrix + toIndex * columns;
for (int j = 1; j < columns; ++j) {
qreal value = from[j];
// skip to[j] = to[j] + factor*0.0
if (value == 0.0)
continue;
to[j] += factor * value;
// ### Avoid Numerical errors
if (qAbs(to[j]) < 0.0000000001)
to[j] = 0.0;
}
}
int QSimplex::findPivotColumn()
{
qreal min = 0;
int minIndex = -1;
for (int j = 0; j < columns-1; ++j) {
if (valueAt(0, j) < min) {
min = valueAt(0, j);
minIndex = j;
}
}
return minIndex;
}
int QSimplex::pivotRowForColumn(int column)
{
qreal min = 999999999999.0; // ###
int minIndex = -1;
for (int i = 1; i < rows; ++i) {
qreal divisor = valueAt(i, column);
if (divisor <= 0)
continue;
qreal quotient = valueAt(i, columns - 1) / divisor;
if (quotient < min) {
min = quotient;
minIndex = i;
}
}
return minIndex;
}
void QSimplex::reducedRowEchelon()
{
for (int i = 1; i < rows; ++i) {
int factorInObjectiveRow = valueAt(i, 0);
combineRows(0, i, -1 * valueAt(0, factorInObjectiveRow));
}
}
bool QSimplex::iterate()
{
// Find Pivot column
int pivotColumn = findPivotColumn();
if (pivotColumn == -1)
return false;
// Find Pivot row for column
int pivotRow = pivotRowForColumn(pivotColumn);
if (pivotRow == -1) {
qWarning() << "QSimplex: Unbounded problem!";
return false;
}
// Normalize Pivot Row
qreal pivot = valueAt(pivotRow, pivotColumn);
if (pivot != 1.0)
combineRows(pivotRow, pivotRow, (1.0 - pivot) / pivot);
// Update other rows
for (int row=0; row < rows; ++row) {
if (row == pivotRow)
continue;
combineRows(row, pivotRow, -1 * valueAt(row, pivotColumn));
}
// Update first column
setValueAt(pivotRow, 0, pivotColumn);
// dumpMatrix();
// printf("------------ end of iteration --------------\n");
return true;
}
/*!
\internal
Both solveMin and solveMax are interfaces to this method.
The enum solverFactor admits 2 values: Minimum (-1) and Maximum (+1).
*/
qreal QSimplex::solver(solverFactor factor)
{
// Remove old objective
clearRow(0);
// Set new objective
QHash<QSimplexVariable *, qreal>::const_iterator iter;
for (iter = objective->variables.constBegin();
iter != objective->variables.constEnd();
++iter) {
setValueAt(0, iter.key()->index, -1 * factor * iter.value());
}
solveMaxHelper();
collectResults();
return factor * valueAt(0, columns - 1);
}
qreal QSimplex::solveMin()
{
return solver(Minimum);
}
qreal QSimplex::solveMax()
{
return solver(Maximum);
}
void QSimplex::collectResults()
{
// All variables are zero unless overridden below.
// ### Is this really needed? Is there any chance that an
// important variable remains as non-basic at the end of simplex?
for (int i = 0; i < variables.size(); ++i)
variables[i]->result = 0;
// Basic variables
// Update the variable indicated in the first column with the value
// in the last column.
for (int i = 1; i < rows; ++i) {
int index = valueAt(i, 0) - 1;
if (index < variables.size())
variables[index]->result = valueAt(i, columns - 1);
}
}
QT_END_NAMESPACE
and here goes the header file :
Code:
QT_BEGIN_NAMESPACE
struct QSimplexVariable
{
QSimplexVariable() : result(0), index(0) {}
qreal result;
int index;
};
/*!
\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;
}
}
#ifdef QT_DEBUG
QString toString() {
QString result;
result += QString::fromAscii("-- QSimplexConstraint %1 --").arg(quintptr(this), 0, 16);
QHash<QSimplexVariable *, qreal>::const_iterator iter;
for (iter = variables.constBegin(); iter != variables.constEnd(); ++iter) {
result += QString::fromAscii(" %1 x %2").arg(iter.value()).arg(quintptr(iter.key()), 0, 16);
}
switch (ratio) {
case LessOrEqual:
result += QString::fromAscii(" (less) <= %1").arg(constant);
break;
case MoreOrEqual:
result += QString::fromAscii(" (more) >= %1").arg(constant);
break;
default:
result += QString::fromAscii(" (eqal) == %1").arg(constant);
}
return result;
}
#endif
};
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;
}
QT_END_NAMESPACE
-
Re: help with implementation of Linear programming solver.
Quote:
Originally Posted by
navy1991
Hi paul,
This is an assignment problem in one of the research lab. I did not write the LP solver.
I didn't write the C++ standard library, but I have plenty of examples of how to use it. So it doesn't matter if you wrote it or not. It also doesn't matter what this class is supposed to do, as your problem is much more higher level than this.
Where is the simple main() program showing basic usage of this class? How are you supposed to know what to do if you don't have a simple example of how to use the class? A class just by itself with no guidance on how to use the public interface of the class is useless.
Regards,
Paul McKenzie
-
Re: help with implementation of Linear programming solver.
They have attached more comments in this source file :
Code:
/*!
\internal
\class QSimplex
The QSimplex class is a Linear Programming problem solver based on the two-phase
simplex method.
It takes a set of QSimplexConstraints as its restrictive constraints and an
additional QSimplexConstraint as its objective function. Then methods to maximize
and minimize the problem solution are provided.
The two-phase simplex method is based on the following steps:
First phase:
1.a) Modify the original, complex, and possibly not feasible problem, into a new,
easy to solve problem.
1.b) Set as the objective of the new problem, a feasible solution for the original
complex problem.
1.c) Run simplex to optimize the modified problem and check whether a solution for
the original problem exists.
Second phase:
2.a) Go back to the original problem with the feasibl (but not optimal) solution
found in the first phase.
2.b) Set the original objective.
3.c) Run simplex to optimize the original problem towards its optimal solution.
*/
/*!
\internal
*/
QSimplex::QSimplex() : objective(0), rows(0), columns(0), firstArtificial(0), matrix(0)
{
}
/*!
\internal
*/
QSimplex::~QSimplex()
{
clearDataStructures();
}
/*!
\internal
*/
void QSimplex::clearDataStructures()
{
if (matrix == 0)
return;
// Matrix
rows = 0;
columns = 0;
firstArtificial = 0;
free(matrix);
matrix = 0;
// Constraints
for (int i = 0; i < constraints.size(); ++i) {
delete constraints[i]->helper.first;
delete constraints[i]->artificial;
delete constraints[i];
}
constraints.clear();
// Other
variables.clear();
objective = 0;
}
/*!
\internal
Sets the new constraints in the simplex solver and returns whether the problem
is feasible.
This method sets the new constraints, normalizes them, creates the simplex matrix
and runs the first simplex phase.
*/
bool QSimplex::setConstraints(const QList<QSimplexConstraint *> newConstraints)
{
////////////////////////////
// Reset to initial state //
////////////////////////////
clearDataStructures();
if (newConstraints.isEmpty())
return true; // we are ok with no constraints
// Make deep copy of constraints. We need this copy because we may change
// them in the simplification method.
for (int i = 0; i < newConstraints.size(); ++i) {
QSimplexConstraint *c = new QSimplexConstraint;
c->constant = newConstraints[i]->constant;
c->ratio = newConstraints[i]->ratio;
c->variables = newConstraints[i]->variables;
constraints << c;
}
// Remove constraints of type Var == K and replace them for their value.
if (!simplifyConstraints(&constraints)) {
qWarning() << "QSimplex: No feasible solution!";
clearDataStructures();
return false;
}
///////////////////////////////////////
// Prepare variables and constraints //
///////////////////////////////////////
// Set Variables direct mapping.
// "variables" is a list that provides a stable, indexed list of all variables
// used in this problem.
QSet<QSimplexVariable *> variablesSet;
for (int i = 0; i < constraints.size(); ++i)
variablesSet += \
QSet<QSimplexVariable *>::fromList(constraints[i]->variables.keys());
variables = variablesSet.toList();
// Set Variables reverse mapping
// We also need to be able to find the index for a given variable, to do that
// we store in each variable its index.
for (int i = 0; i < variables.size(); ++i) {
// The variable "0" goes at the column "1", etc...
variables[i]->index = i + 1;
}
// Normalize Constraints
// In this step, we prepare the constraints in two ways:
// Firstly, we modify all constraints of type "LessOrEqual" or "MoreOrEqual"
// by the adding slack or surplus variables and making them "Equal" constraints.
// Secondly, we need every single constraint to have a direct, easy feasible
// solution. Constraints that have slack variables are already easy to solve,
// to all the others we add artificial variables.
//
// At the end we modify the constraints as follows:
// - LessOrEqual: SLACK variable is added.
// - Equal: ARTIFICIAL variable is added.
// - More or Equal: ARTIFICIAL and SURPLUS variables are added.
int variableIndex = variables.size();
QList <QSimplexVariable *> artificialList;
for (int i = 0; i < constraints.size(); ++i) {
QSimplexVariable *slack;
QSimplexVariable *surplus;
QSimplexVariable *artificial;
Q_ASSERT(constraints[i]->helper.first == 0);
Q_ASSERT(constraints[i]->artificial == 0);
switch(constraints[i]->ratio) {
case QSimplexConstraint::LessOrEqual:
slack = new QSimplexVariable;
slack->index = ++variableIndex;
constraints[i]->helper.first = slack;
constraints[i]->helper.second = 1.0;
break;
case QSimplexConstraint::MoreOrEqual:
surplus = new QSimplexVariable;
surplus->index = ++variableIndex;
constraints[i]->helper.first = surplus;
constraints[i]->helper.second = -1.0;
// fall through
case QSimplexConstraint::Equal:
artificial = new QSimplexVariable;
constraints[i]->artificial = artificial;
artificialList += constraints[i]->artificial;
break;
}
}
// All original, slack and surplus have already had its index set
// at this point. We now set the index of the artificial variables
// as to ensure they are at the end of the variable list and therefore
// can be easily removed at the end of this method.
firstArtificial = variableIndex + 1;
for (int i = 0; i < artificialList.size(); ++i)
artificialList[i]->index = ++variableIndex;
artificialList.clear();
/////////////////////////////
// Fill the Simplex matrix //
/////////////////////////////
// One for each variable plus the Basic and BFS columns (first and last)
columns = variableIndex + 2;
// One for each constraint plus the objective function
rows = constraints.size() + 1;
matrix = (qreal *)malloc(sizeof(qreal) * columns * rows);
if (!matrix) {
qWarning() << "QSimplex: Unable to allocate memory!";
return false;
}
for (int i = columns * rows - 1; i >= 0; --i)
matrix[i] = 0.0;
// Fill Matrix
for (int i = 1; i <= constraints.size(); ++i) {
QSimplexConstraint *c = constraints[i - 1];
if (c->artificial) {
// Will use artificial basic variable
setValueAt(i, 0, c->artificial->index);
setValueAt(i, c->artificial->index, 1.0);
if (c->helper.second != 0.0) {
// Surplus variable
setValueAt(i, c->helper.first->index, c->helper.second);
}
} else {
// Slack is used as the basic variable
Q_ASSERT(c->helper.second == 1.0);
setValueAt(i, 0, c->helper.first->index);
setValueAt(i, c->helper.first->index, 1.0);
}
QHash<QSimplexVariable *, qreal>::const_iterator iter;
for (iter = c->variables.constBegin();
iter != c->variables.constEnd();
++iter) {
setValueAt(i, iter.key()->index, iter.value());
}
setValueAt(i, columns - 1, c->constant);
}
// Set objective for the first-phase Simplex.
// Z = -1 * sum_of_artificial_vars
for (int j = firstArtificial; j < columns - 1; ++j)
setValueAt(0, j, 1.0);
// Maximize our objective (artificial vars go to zero)
solveMaxHelper();
// If there is a solution where the sum of all artificial
// variables is zero, then all of them can be removed and yet
// we will have a feasible (but not optimal) solution for the
// original problem.
// Otherwise, we clean up our structures and report there is
// no feasible solution.
if ((valueAt(0, columns - 1) != 0.0) && (qAbs(valueAt(0, columns - 1)) > 0.00001)) {
qWarning() << "QSimplex: No feasible solution!";
return false;
}
// Remove artificial variables. We already have a feasible
// solution for the first problem, thus we don't need them
// anymore.
clearColumns(firstArtificial, columns - 2);
return true;
}
/*!
\internal
Run simplex on the current matrix with the current objective.
This is the iterative method. The matrix lines are combined
as to modify the variable values towards the best solution possible.
The method returns when the matrix is in the optimal state.
*/
void QSimplex::solveMaxHelper()
{
reducedRowEchelon();
while (iterate()) ;
}
/*!
\internal
*/
void QSimplex::setObjective(QSimplexConstraint *newObjective)
{
objective = newObjective;
}
/*!
\internal
*/
void QSimplex::clearRow(int rowIndex)
{
qreal *item = matrix + rowIndex * columns;
for (int i = 0; i < columns; ++i)
item[i] = 0.0;
}
/*!
\internal
*/
void QSimplex::clearColumns(int first, int last)
{
for (int i = 0; i < rows; ++i) {
qreal *row = matrix + i * columns;
for (int j = first; j <= last; ++j)
row[j] = 0.0;
}
}
/*!
\internal
*/
void QSimplex::dumpMatrix()
{
qDebug("---- Simplex Matrix ----\n");
QString str(QLatin1String(" "));
for (int j = 0; j < columns; ++j)
str += QString::fromAscii(" <%1 >").arg(j, 2);
qDebug("%s", qPrintable(str));
for (int i = 0; i < rows; ++i) {
str = QString::fromAscii("Row %1:").arg(i, 2);
qreal *row = matrix + i * columns;
for (int j = 0; j < columns; ++j)
str += QString::fromAscii("%1").arg(row[j], 7, 'f', 2);
qDebug("%s", qPrintable(str));
}
qDebug("------------------------\n");
}
/*!
\internal
*/
void QSimplex::combineRows(int toIndex, int fromIndex, qreal factor)
{
if (!factor)
return;
qreal *from = matrix + fromIndex * columns;
qreal *to = matrix + toIndex * columns;
for (int j = 1; j < columns; ++j) {
qreal value = from[j];
// skip to[j] = to[j] + factor*0.0
if (value == 0.0)
continue;
to[j] += factor * value;
// ### Avoid Numerical errors
if (qAbs(to[j]) < 0.0000000001)
to[j] = 0.0;
}
}
/*!
\internal
*/
int QSimplex::findPivotColumn()
{
qreal min = 0;
int minIndex = -1;
for (int j = 0; j < columns-1; ++j) {
if (valueAt(0, j) < min) {
min = valueAt(0, j);
minIndex = j;
}
}
return minIndex;
}
/*!
\internal
For a given pivot column, find the pivot row. That is, the row with the
minimum associated "quotient" where:
- quotient is the division of the value in the last column by the value
in the pivot column.
- rows with value less or equal to zero are ignored
- if two rows have the same quotient, lines are chosen based on the
highest variable index (value in the first column)
The last condition avoids a bug where artificial variables would be
left behind for the second-phase simplex, and with 'good'
constraints would be removed before it, what would lead to incorrect
results.
*/
int QSimplex::pivotRowForColumn(int column)
{
qreal min = qreal(999999999999.0); // ###
int minIndex = -1;
for (int i = 1; i < rows; ++i) {
qreal divisor = valueAt(i, column);
if (divisor <= 0)
continue;
qreal quotient = valueAt(i, columns - 1) / divisor;
if (quotient < min) {
min = quotient;
minIndex = i;
} else if ((quotient == min) && (valueAt(i, 0) > valueAt(minIndex, 0))) {
minIndex = i;
}
}
return minIndex;
}
/*!
\internal
*/
void QSimplex::reducedRowEchelon()
{
for (int i = 1; i < rows; ++i) {
int factorInObjectiveRow = valueAt(i, 0);
combineRows(0, i, -1 * valueAt(0, factorInObjectiveRow));
}
}
/*!
\internal
Does one iteration towards a better solution for the problem.
See 'solveMaxHelper'.
*/
bool QSimplex::iterate()
{
// Find Pivot column
int pivotColumn = findPivotColumn();
if (pivotColumn == -1)
return false;
// Find Pivot row for column
int pivotRow = pivotRowForColumn(pivotColumn);
if (pivotRow == -1) {
qWarning() << "QSimplex: Unbounded problem!";
return false;
}
// Normalize Pivot Row
qreal pivot = valueAt(pivotRow, pivotColumn);
if (pivot != 1.0)
combineRows(pivotRow, pivotRow, (qreal(1.0) - pivot) / pivot);
// Update other rows
for (int row=0; row < rows; ++row) {
if (row == pivotRow)
continue;
combineRows(row, pivotRow, -1 * valueAt(row, pivotColumn));
}
// Update first column
setValueAt(pivotRow, 0, pivotColumn);
// dumpMatrix();
// qDebug("------------ end of iteration --------------\n");
return true;
}
/*!
\internal
Both solveMin and solveMax are interfaces to this method.
The enum solverFactor admits 2 values: Minimum (-1) and Maximum (+1).
This method sets the original objective and runs the second phase
Simplex to obtain the optimal solution for the problem. As the internal
simplex solver is only able to _maximize_ objectives, we handle the
minimization case by inverting the original objective and then
maximizing it.
*/
qreal QSimplex::solver(solverFactor factor)
{
// Remove old objective
clearRow(0);
// Set new objective in the first row of the simplex matrix
qreal resultOffset = 0;
QHash<QSimplexVariable *, qreal>::const_iterator iter;
for (iter = objective->variables.constBegin();
iter != objective->variables.constEnd();
++iter) {
// Check if the variable was removed in the simplification process.
// If so, we save its offset to the objective function and skip adding
// it to the matrix.
if (iter.key()->index == -1) {
resultOffset += iter.value() * iter.key()->result;
continue;
}
setValueAt(0, iter.key()->index, -1 * factor * iter.value());
}
solveMaxHelper();
collectResults();
#ifdef QT_DEBUG
for (int i = 0; i < constraints.size(); ++i) {
Q_ASSERT(constraints[i]->isSatisfied());
}
#endif
// Return the value calculated by the simplex plus the value of the
// fixed variables.
return (factor * valueAt(0, columns - 1)) + resultOffset;
}
/*!
\internal
Minimize the original objective.
*/
qreal QSimplex::solveMin()
{
return solver(Minimum);
/*!
\internal
Maximize the original objective.
*/
qreal QSimplex::solveMax()
{
return solver(Maximum);
}
/*!
\internal
Reads results from the simplified matrix and saves them in the
"result" member of each QSimplexVariable.
*/
void QSimplex::collectResults()
{
// All variables are zero unless overridden below.
// ### Is this really needed? Is there any chance that an
// important variable remains as non-basic at the end of simplex?
for (int i = 0; i < variables.size(); ++i)
variables[i]->result = 0;
// Basic variables
// Update the variable indicated in the first column with the value
// in the last column.
for (int i = 1; i < rows; ++i) {
int index = valueAt(i, 0) - 1;
if (index < variables.size())
variables[index]->result = valueAt(i, columns - 1);
}
}
/*!
\internal
Looks for single-valued variables and remove them from the constraints list.
*/
bool QSimplex::simplifyConstraints(QList<QSimplexConstraint *> *constraints)
{
QHash<QSimplexVariable *, qreal> results; // List of single-valued variables
bool modified = true; // Any chance more optimization exists?
while (modified) {
modified = false;
// For all constraints
QList<QSimplexConstraint *>::iterator iter = constraints->begin();
while (iter != constraints->end()) {
QSimplexConstraint *c = *iter;
if ((c->ratio == QSimplexConstraint::Equal) && (c->variables.count() == 1)) {
// Check whether this is a constraint of type Var == K
// If so, save its value to "results".
QSimplexVariable *variable = c->variables.constBegin().key();
qreal result = c->constant / c->variables.value(variable);
results.insert(variable, result);
variable->result = result;
variable->index = -1;
modified = true;
}
// Replace known values among their variables
QHash<QSimplexVariable *, qreal>::const_iterator r;
for (r = results.constBegin(); r != results.constEnd(); ++r) {
if (c->variables.contains(r.key())) {
c->constant -= r.value() * c->variables.take(r.key());
modified = true;
}
}
// Keep it normalized
if (c->constant < 0)
c->invert();
if (c->variables.isEmpty()) {
// If constraint became empty due to substitution, delete it.
if (c->isSatisfied() == false)
// We must ensure that the constraint soon to be deleted would not
// make the problem unfeasible if left behind. If that's the case,
// we return false so the simplex solver can properly report that.
return false;
delete c;
iter = constraints->erase(iter);
} else {
++iter;
}
}
}
return true;
}
void QSimplexConstraint::invert()
{
constant = -constant;
ratio = Ratio(2 - ratio);
QHash<QSimplexVariable *, qreal>::iterator iter;
for (iter = variables.begin(); iter != variables.end(); ++iter) {
iter.value() = -iter.value();
}
}
QT_END_NAMESPACE
-
Re: help with implementation of Linear programming solver.
Hi paul,
I have not seen the examples of how to use this LP solver. It would have been easier for me to understand if they had give me an example of implementation of this class. Any ways, Please give me some time . I will post some examples if I am able to find any.
Regards,
Naveen.
-
Re: help with implementation of Linear programming solver.
Hi paul,
I could not find any examples of implementation. My logic is to convert the string (lines that I parsed) into struct Qsimplexconstraint and then call the functions available in the LPsolver. I need to iterate this to parse all the lines of the file. Atlast, I should call collectResults() function to get the results. Is my logic correct?
Regards,
Naveen.
-
Re: help with implementation of Linear programming solver.
Quote:
Originally Posted by
navy1991
Hi paul,
I could not find any examples of implementation. My logic is to convert the string (lines that I parsed) into struct Qsimplexconstraint
All you need to do first is this:
Code:
#include <iostream>
#include <string>
#include <map>
typedef double qreal;
struct QSimplexVariable
{
QSimplexVariable() : result(0), index(0) {}
qreal result;
int index;
};
struct QSimplexConstraint
{
QSimplexConstraint() : constant(0), ratio(Equal), artificial(0) {}
enum Ratio {LessOrEqual = 0,Equal,MoreOrEqual};
float constant;
Ratio ratio;
std::pair<QSimplexVariable *, qreal> helper;
QSimplexVariable * artificial;
};
QSimplexConstraint parseMe(const std::string& str)
{
// you fill this in and return a QSimplexConstraint
}
using namespace std;
int main()
{
std::string constraintString;
cout << "Enter a constraint string: ";
getline(cin, constraintString);
QSimplexConstraint qc = parseMe( constraintString );
//...
}
Since I don't know anything about QTPair or qreal (these are not C++ types), I used standard types in place of them. Note that the entire code above compiles without any knowledge of Qt or anything to do with linear programming. The problem is now focused on your original question, regardless of all of the other stuff.
So your job is to take that string, call parseMe, and then return a QSimplexConstraint that contains the proper information. Once you have the simple case working, then and only then do you now consider file I/O and what to do next.
Regards,
Paul McKenzie
-
Re: help with implementation of Linear programming solver.
Hi Paul,
Code:
QSimplexConstraint parseMe(const std::string& str)
{
// you fill this in and return a QSimplexConstraint
}
What is this parseMe() function ? I tried to search about it in google but could not learn much.
The data in the file is of the format :
c1 * X1 + c2 * X2 + ... = K
or <= K
or >= K
Where (ci, Xi) are the pairs in "variables" and K the real "constant".
Now I want to parse
constant = K (RHS)
ratio = symbol in between RHS and LHS
QsimplexVariable = (ci,Xi) (LHS)
Could you please tell me how I can do this and get a QSimplexConstraint?
Regards,
Naveen.
-
Re: help with implementation of Linear programming solver.
Hi Paul,
As you have mentioned , I implemented your code as a stand alone program and it worked perfectly fine. In the place of " // you fill this in and return a QSimplexConstraint " I wrote "QSimplexConstraint() " . I got a message : "Enter a constraint string: " . After this , I entered a constraint like "+ a -b = 0" . It is similar to the constraint in the file.After that , the console window disappeared. I am thinking how should I use the parseMe() function. Unfortunately, I have not yet found a way.
Regards,
Naveen.
-
Re: help with implementation of Linear programming solver.
Quote:
Originally Posted by
navy1991
What is this parseMe() function ?
I just made it up.
I don't think you're understanding the general point. The issue is that you have a string, and now you want to take this string and turn it into something else, i.e. transform the string into something that fits into the problem domain.
For example, if the string represented a mathematical expression, the probable goal is to take that string, parse it, and place the tokens in some sort of syntax tree. If that string represented English words, you would parse the string and maybe place the indivdual words in a table, etc.
All that other stuff concerning linear programming is moot and not important.
Quote:
I tried to search about it in google but could not learn much.
No. The goal is for you to drop everything and concentrate on taking that string, doing soemthing to it, and returning a QSimplexConstraint based on that string. If you can't do that, then there is no need to write the rest of the program.
Quote:
The data in the file is of the format :
Forget about the file. It doesn't matter where the data comes from, and introducing file I/O is a waste of your time at this point. For one, you now have to spend precious hours making sure the file reading work. What good is reading from a file when you can't do a basic parsing of the string?
Just enter a string that reprsents one line of data. Then take that entered string and see if you can create a QSimplexConstraint from that string. That is how any programmer would start out -- I think your problem is that you want to complete this whole assignment in one shot, and not unit test or develop each piece.
Code:
The data in the file is of the format :
c1 * X1 + c2 * X2 + ... = K
or <= K
or >= K
Please post the actual file, not an interpretation. Are you saying that the word "or" is in the file?
Quote:
Could you please tell me how I can do this and get a QSimplexConstraint?
First post the real file, not a mock up. Second, parsing input may require you to first define in a general sense the rules of the syntax for the data. Then you may have to write a recursive descent parser to parse the data correctly, or if the rules are simple, a simple "linear" parser.
No one can just say "use this code to parse the file" -- that is impossible. You have to ascertain what constitutes a data line, and then assess what type of parser is needed to parse the data and store the data into the program's data structures.
Regards,
Paul McKenzie
-
Re: help with implementation of Linear programming solver.
Quote:
Originally Posted by
navy1991
I am thinking how should I use the parseMe() function. Unfortunately, I have not yet found a way.
That is because there is no way to do it by calling just a function. Parsing expressions is not trivial -- you have to know the general syntax of what to expect, probably then write a grammar that matches that syntax using production rules, and then write the recursive parser. I don't know if you knew that it isn't trivial or "automatic" to do these things.
Just because it looks easy by eyesight doesn't mean it's easy to write a program for what you see. Can you write an algebraic problem solver? We can solve algrebaic problems easy "by hand", but how hard is it to write a program to do it? Very difficult.
So just because it "looks easy" from a non-programmer perspective to interpret that data, it isn't easy to write a program to do what we can do easily with pencil and paper.
Regards,
Paul McKenzie
-
1 Attachment(s)
Re: help with implementation of Linear programming solver.
Hi Paul,
I totally agree with you. I had attached my file in the first post. Anyways, Here is the attachment: Attachment 31795
Ok,I will concentrate only on the string as you have said.
Regards,
Naveen.
-
Re: help with implementation of Linear programming solver.
Quote:
Originally Posted by
navy1991
Hi Paul,
I totally agree with you. I had attached my file in the first post. Anyways, Here is the attachment:
Attachment 31795
If what you attached is a data file, you can't just write a program to parse what is in that attachment. No way.
Things like this:
Quote:
\* Metabolism *\
\* Objective function *\
Maximize
-3.442882e-006 ADix -3.442882e-006 ADPix -3.442882e-006 AHCYSix -3.442882e-006 AMPix -3.442882e-006 cmnm5s2UMPix -3.442882e-006 CMPix -3.442882e-006 DR5Pix -3.442882e-006 FMETix -3.442882e-006 FORix -3.442882e-006 GDPix -3.442882e-006 GmMPix
-3.442882e-006 GMPix -3.442882e-006 GNix -3.442882e-006 Hix -3.442882e-006 k2CMPix -3.442882e-006 LIPOYLLYSix -3.442882e-006 m1GMPix -3.442882e-006 m2GMPix -3.442882e-006 m62AMPix -3.442882e-006 m7GMPix -3.442882e-006 NH3ix -3.442882e-006 NMNix
-3.442882e-006 PIix -3.442882e-006 PPIix -3.442882e-006 pSERix -3.442882e-006 PSIURIMPix -3.442882e-006 pTHRix -3.442882e-006 pTYRix -3.442882e-006 s4UMPix -3.442882e-006 SNGLYPix -3.442882e-006 THFix -3.442882e-006 THYix -3.442882e-006 UmMPix
-3.442882e-006 UMPix -3.442882e-006 URAix +0.2777778 Growth
\* Constraints *\
You have to know what is
1) A comment line
2) What is a data line.
3) Which data you're reading
4) Depending on the data, how to interpret each component of the data
...
etc..
In other words, you need to take that file, look at it, and write in pencil and paper, the rules that constitutes a valid data file, including how to skip over comments, etc.. That in itself is a large enough assignment, and it has nothing to do with linear programming.
Regards,
Paul McKenzie
-
Re: help with implementation of Linear programming solver.
Hi Paul,
What I have attached is indded a data file. You can also download the file from here : https://simtk.org/project/xml/downlo...l?group_id=714
In this link , you will find different formats of FBA metabolic model sub-model.I converted all the file formats into text file. Only 1 format made some sense and it was the file that I had attached above. It is from a Stanford systems biology lab. It models all the metabolites in a cell. If you have any other idea to solve this problem, please do share with me.
Regards,
Naveen.
-
Re: help with implementation of Linear programming solver.
If it is not possible with c++ , then I will try to use python for text processing. But ultimately, I need to parse this file into c++ because the linear programming solver is coded in c++.
-
Re: help with implementation of Linear programming solver.
Quote:
Originally Posted by
navy1991
If you have any other idea to solve this problem, please do share with me.
There is no "other idea". I stated exactly what you need to do to parse this file.
Again, if you expected a magical function to appear out of nowhere to parse such a file with this information, then you've been sadly mistaken. Unless you find an already written parser that parses this particular file, then the "solution" is exactly what I have stated in previous posts.
Regards,
Paul McKenzie
-
Re: help with implementation of Linear programming solver.
Quote:
Originally Posted by
navy1991
If it is not possible with c++ , then I will try to use python for text processing.
Again, the problem isn't "text processing", and it doesn't matter what language you use. You still will run into the same issue, and that is you need to know the syntax or file-layout rules of such a file before writiing a single line of code. Do you think python, C++, Java, or any language will know what is a comment? What is a variable? What is a coefficient?
Regards,
Paul McKenzie
-
Re: help with implementation of Linear programming solver.
Hi Paul,
Ok, if you have a close look at the file , we can easily delete the comments and have a structure like I posted in the first post:
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 can do some more refinement like deleting the starting word till colon " : " manually and then you have the format exactly like this:
Maximize:
obj: 3e-06 A - 3e-06 B + 2.7e-01 F
constraints:
-1 A + 1 B -1 C + 1 D -1 E -1 F = 0
-1 A + 1 B -1 C + 1 D -1 E -1 F = 0
-1 A + 1 B -1 C + 1 D -1 E -1 F = 0
-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 think that in this way, we have a text file , which is similar to the constraints specified in the Linear programming solver. But, As you have mentioned , there is no magic function to parse it directly. So, I need to create my own function to parse this string. The logic to parse this string is: split the string into 3 parts -- LHS, RHS and inbetween -- and then convert them into
constant = K (RHS)
ratio = symbol in between RHS and LHS
QsimplexVariable = (ci,Xi) (LHS)
data structures like this. But, It is not very easy. It will have some more steps. That is why, I am seeking your expert advice.
Regards,
Naveen.
-
Re: help with implementation of Linear programming solver.
-
Re: help with implementation of Linear programming solver.
Quote:
Originally Posted by
navy1991
Hi Paul,
Ok, if you have a close look at the file , we can easily delete the comments and have a structure like I posted in the first post:
Again, you're thinking in terms of what you see, and believing that because it looks obvious to do "by hand", it becomes an easy job to write a program to do it, and all it takes is simple code.
I will try and give you an example: What is the answer to this?
Of course by using order of operations and parens, we can do this easily "by hand" and state the answer is 11. Now write a computer program that takes that string and computes the answer? Get the point now?
If you stated to me "how to solve this problem", the solution would be to write a program that parses each of those tokens and use a operator / operand stack that maintains precedence which more than likely converts the Infix expression to postfix. Does that sound obvious to you?
That is exactly the situation you're in now. It isn't just writing a parser. You need to write the grammar rules formally as to the layout of a file. Do you know what grammar rules are? Are you familiar with a recursive descent parser?
Regards,
Paul McKenzie
-
Re: help with implementation of Linear programming solver.
Quote:
Originally Posted by
navy1991
Hi Paul,
What I have attached is indded a data file. You can also download the file from here :
https://simtk.org/project/xml/downlo...l?group_id=714
In this link , you will find different formats of FBA metabolic model sub-model.I converted all the file formats into text file. Only 1 format made some sense and it was the file that I had attached above.
If the data obtained from the given web site when converted into a text file produces a file in the format you require, have you considered that others might have had the same parsing requirement and that a c++ parser for this format has already been written? Have you thought about contacting the site and asking them about this? It may save you a whole heap of work as even writing the simplest one symbol look-ahead recursive descent parser is not trivial - and producing a correct syntax diagram (which has to be done before coding is even thought about) can be a complex task.
-
Re: help with implementation of Linear programming solver.
Quote:
Originally Posted by
navy1991
I will also keep trying
As 2kaud suggested, a parser of some sort was probably already written, if the file is one that is used by other programs/computer languages.
For example, no one (unless for some odd reason) writes an XML parser. The reason is because there are so many available.
If a parser is written for this file, more than likely it has created "hooks", so that for each token, component, etc. that the parser encounters in the file, the parser calls your "hook function" to store the data found in any way you see fit. An example would be the comments -- if the parser encounters a comment, it would call your "Comment Hook" function to handle the comment (which could mean simply to ignore it and continue parsing).
Regards,
Paul McKenzie
-
Re: help with implementation of Linear programming solver.
Hi Paul and 2kaud,
I have learnt about formal Grammar rules in Theory of Computation or Formal Languages. I guess we have a prebuilt lexer and parser to do this at my place. But, it will take time. I will be back to work after few hours . I will decide about next step if I should use the prebuilt Lexer and Parser.
Thanks Paul for explaining to me patiently.
Regards,
Naveen.
-
Re: help with implementation of Linear programming solver.
Hello Paul,
The file was created using this Matlab Code it seems : https://github.com/CovertLab/WholeCe.../FbaLPWriter.m
Regards,
Naveen.
-
Re: help with implementation of Linear programming solver.
Quote:
Originally Posted by
navy1991
So a project you need to make is a reader (or parser) for this file. From looking at the site, I don't even know if they considered that programs may want to try and read the data that's written. Maybe you're trying to use the file in ways it was never intended it to be used.
To be honest, maybe trying to turn that file into XML, and then using a C++ XML parser would be the better way to go. You still would need to translate and to coherently determine the XML tags and what data would go into the tags. But that is up to you as to how to set up the tags.
Regards,
Paul McKenzie
-
Re: help with implementation of Linear programming solver.
Quote:
Originally Posted by
navy1991
If you are familiar with matlab code, one other possibility would be to alter the matlab code to produce a file in a format more easy to import into a c++ program.
-
Re: help with implementation of Linear programming solver.
Quote:
Originally Posted by
navy1991
If you could alter the Malab code, maybe you can output 3 files, an "Objective function" file, a "Constraints" file, and a "Variable Bounds" file. For example, for the "Variable Bounds" file:
Code:
Name < <= == > >=
Adix x x 0 x x
AdPix x 0 x x -5.495024
AHCYSix x x 0 x x
AMPix x 0 x x -2.197701
...
The first line doesn't go in the file, it is to show you what each column denotes in the input file. The first column is the name of the variable. The <, <=, ==, >, >= are the relevant operations to describing the bounding condition (I used the C++ "==" to denote equal).
So for example, if you take a look at the AdPix variable bounds in your original input file:
Code:
ADPix >= -5.495024
ADPix <= 0
Then the entry in the variable bounds file would be :
Code:
AdPix x 0 x x -5.495024
The above is much easier to parse. Note that the "0" is in the <= column, and the "-5.495024" is in the >= column. The "x" means "ignore", no-op, i.e. whatever terminology to mean this operation doesn't apply.
This is just an idea. You need to come with a similar scheme for the maximization and constraints part of the file.
Regards,
Paul McKenzie
-
Re: help with implementation of Linear programming solver.
Hello Paul,
I do not have Matlab software suite. It is not open source too. I have 2 ideas:
1. To build a parser by splitting it(the string or line) and by assigning the values as coeffecients , variables, etc as you have mentioned before.. or
2. to use the Java code in this file : http://sourceforge.net/projects/lpso...solve/5.5.2.0/ and call the functions in c++ (so to create a java API in C++)
Which will be easier? I feel the second one will be easier?
Regards,
Naveen.
-
Re: help with implementation of Linear programming solver.
Quote:
I do not have Matlab software suite.
How, exactly, is this data file produced that you want to parse?
-
Re: help with implementation of Linear programming solver.
Hi 2Kaud,
I want to parse it like the representation shown in this header file:
/*!
\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".
*/
Please have a look at previous posts too : I have described about it
Regards,
Naveen.
-
Re: help with implementation of Linear programming solver.
Yes, I know that you want to parse a data file. I have been following these threads. I asked how this file was produced because in post #28 you say that the file was produced using Matlab code and then in post #32 you say that you don't have Matlab. Is someone producing the data file for you? Have you discussed your parsing requirements with them?
If, as Paul and myself have suggested, you can change the program that produces this data file to produce one in a format more easily parsed, then the task of writing the parser becomes much easier as Paul explained. How is this file produced?
Also, as per posts #25 and #26 have you explored the possibility that a parser for the format of the data file you have may already have been written?
-
Re: help with implementation of Linear programming solver.
Hi 2kaud,
I did not write the code in Matlab. It was written by Jonathan. I am working in a diiferent place but on the same topic : FBA (flux balance analysis) for whole cell model. I am working in a c++ platform to create this FBA solver.
Regards,
Naveen.
-
1 Attachment(s)
Re: help with implementation of Linear programming solver.
Attachment 31799 please have a look at this attachment too. It is better to parse as it has whitespace in between. I retrieved it from one of the file formats posted in that website.
Regards,
Naveen.
-
Re: help with implementation of Linear programming solver.
Quote:
Originally Posted by
navy1991
Hi 2kaud,
I did not write the code in Matlab. It was written by Jonathan. I am working in a diiferent place but on the same topic : FBA (flux balance analysis) for whole cell model. I am working in a c++ platform to create this FBA solver.
Regards,
Naveen.
It would make your job much easier if you could ask Jonathan to amend his Matlab code to produce an output data file similar in format to that suggested by Paul in post #31.
-
Re: help with implementation of Linear programming solver.
Yes, I will ask him. In the mean time, I downloaded another LP solver : http://docs.oracle.com/javase/1.5.0/...nvocation.html .
It has a source code in Java platform. I want to incorporate this into my c++ program. So, do you think incorporating this java lp solver is better? Or should I stick to the previous one and construct a parser with the new file I posted in post 37 Or wait for jonathan to amend his code like paul has mentioned?
Too many choices , Feeling confused .
Regards,
Naveen.
-
Re: help with implementation of Linear programming solver.
Quote:
Originally Posted by
navy1991
That link doesn't link to an LP solver.
Also, if you're looking for a linear programming solver in C++, I would think that it has been done already, with full source code. Do a google search, and I'm sure it has been done.
Regards,
Paul McKenzie
-
Re: help with implementation of Linear programming solver.
Sorry. This was the link which had the LPsolver : http://sourceforge.net/projects/lpso...solve/5.5.2.0/
It has an implementation in many languages except c++.I was trying to use this one because we have an input file in the same format (lpsolve format).
Anyways, I will search for other c++ LP solvers too.
Regards,
Naveen.
-
Re: help with implementation of Linear programming solver.
Quote:
Originally Posted by
navy1991
Sorry. This was the link which had the LPsolver :
http://sourceforge.net/projects/lpso...solve/5.5.2.0/
It has an implementation in many languages except c++.I was trying to use this one because we have an input file in the same format (lpsolve format).
Anyways, I will search for other c++ LP solvers too.
Regards,
Naveen.
As that link provides both an .exe and the source in c and you have an input file in the required format, what's the problem in using LPsolver?
-
Re: help with implementation of Linear programming solver.
Finally, I have found one. It is called clp : http://www.coin-or.org/download/source/Clp/
It seems to be very detailed . I will try to implement with this one. If I encounter any problem, I will come back.
Regards,
Naveen.
-
Re: help with implementation of Linear programming solver.
Hello 2Kaud,
It works perfectly fine. In fact, I solved my problem and got the result. (around 0.02) . At my place, I am trying to build / include a FBA solver in c++ platform (which will be incorporated into another suit). But, I think that the Clp Solver (post 43 ) will be good . It is implemented in c++.