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

Thread: help with implementation of Linear programming solver.

Threaded View

  1. #1
    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.
    Attached Files 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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center