QSimplex Class Reference

The QSimplex class is a Linear Programming problem solver based on the two-phase simplex method. More...

#include <qsimplex_p.h>

Public Functions
void	dumpMatrix ()
	QSimplex ()
bool	setConstraints (const QList< QSimplexConstraint *> constraints)
	Sets the new constraints in the simplex solver and returns whether the problem is feasible. More...
void	setObjective (QSimplexConstraint *objective)
qreal	solveMax ()
	Maximize the original objective. More...
qreal	solveMin ()
	Minimize the original objective. More...
virtual	~QSimplex ()

Private Types
enum	solverFactor { Minimum = -1, Maximum = 1 }

Private Functions
void	clearColumns (int first, int last)
void	clearDataStructures ()
void	clearRow (int rowIndex)
void	collectResults ()
	Reads results from the simplified matrix and saves them in the "result" member of each QSimplexVariable. More...
void	combineRows (int toIndex, int fromIndex, qreal factor)
int	findPivotColumn ()
bool	iterate ()
	Does one iteration towards a better solution for the problem. More...
int	pivotRowForColumn (int column)
	For a given pivot column, find the pivot row. More...
void	reducedRowEchelon ()
void	setValueAt (int row, int column, qreal value)
bool	simplifyConstraints (QList< QSimplexConstraint *> *constraints)
	Looks for single-valued variables and remove them from the constraints list. More...
void	solveMaxHelper ()
	Run simplex on the current matrix with the current objective. More...
qreal	solver (solverFactor factor)
	Both solveMin and solveMax are interfaces to this method. More...
qreal	valueAt (int row, int column)

Properties
int	columns
QList< QSimplexConstraint * >	constraints
int	firstArtificial
qreal *	matrix
QSimplexConstraint *	objective
int	rows
QList< QSimplexVariable * >	variables

Detailed Description

The QSimplex class is a Linear Programming problem solver based on the two-phase simplex method.

Warning

This function is not part of the public interface.

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.

Definition at line 149 of file qsimplex_p.h.

Enumerations

solverFactor

enum QSimplex::solverFactor

private

Enumerator
Minimum
Maximum

Definition at line 181 of file qsimplex_p.h.

{ Minimum = -1, Maximum = 1 };

Constructors and Destructors

QSimplex()

QSimplex::QSimplex

(

)

Warning

This function is not part of the public interface.

Definition at line 84 of file qsimplex_p.cpp.

                   : objective(0), rows(0), columns(0), firstArtificial(0), matrix(0)
{
}

~QSimplex()

QSimplex::~QSimplex ( )

virtual

Warning

This function is not part of the public interface.

Definition at line 91 of file qsimplex_p.cpp.

{
    clearDataStructures();
}

Functions

clearColumns()

void QSimplex::clearColumns ( int  first, int  last  )

private

Warning

This function is not part of the public interface.

Definition at line 350 of file qsimplex_p.cpp.

Referenced by setConstraints().

{
    for (int i = 0; i < rows; ++i) {
        qreal *row = matrix + i * columns;
        for (int j = first; j <= last; ++j)
            row[j] = 0.0;
    }
}

clearDataStructures()

void QSimplex::clearDataStructures ( )

private

Warning

This function is not part of the public interface.

Definition at line 99 of file qsimplex_p.cpp.

Referenced by setConstraints(), and ~QSimplex().

{
    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;
}

clearRow()

void QSimplex::clearRow ( int  rowIndex )

private

Warning

This function is not part of the public interface.

Definition at line 340 of file qsimplex_p.cpp.

Referenced by solver().

{
    qreal *item = matrix + rowIndex * columns;
    for (int i = 0; i < columns; ++i)
        item[i] = 0.0;
}

collectResults()

void QSimplex::collectResults ( )

private

Reads results from the simplified matrix and saves them in the "result" member of each QSimplexVariable.

Warning

This function is not part of the public interface.

Definition at line 608 of file qsimplex_p.cpp.

Referenced by solver().

{
    // 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);
    }
}

combineRows()

void QSimplex::combineRows ( int  toIndex, int  fromIndex, qreal  factor  )

private

Warning

This function is not part of the public interface.

Definition at line 384 of file qsimplex_p.cpp.

Referenced by iterate(), and reducedRowEchelon().

{
    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;
    }
}

dumpMatrix()

void QSimplex::dumpMatrix

(

)

Warning

This function is not part of the public interface.

Definition at line 362 of file qsimplex_p.cpp.

{
    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");
}

findPivotColumn()

int QSimplex::findPivotColumn ( )

private

Warning

This function is not part of the public interface.

Definition at line 410 of file qsimplex_p.cpp.

Referenced by iterate().

{
    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;
}

iterate()

bool QSimplex::iterate ( )

private

Does one iteration towards a better solution for the problem.

Warning

This function is not part of the public interface.

See 'solveMaxHelper'.

Definition at line 487 of file qsimplex_p.cpp.

Referenced by solveMaxHelper().

{
    // 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;
}

pivotRowForColumn()

int QSimplex::pivotRowForColumn ( int  column )

private

For a given pivot column, find the pivot row.

Warning

This function is not part of the public interface.

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.

Definition at line 445 of file qsimplex_p.cpp.

Referenced by iterate().

{
    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;
}

reducedRowEchelon()

void QSimplex::reducedRowEchelon ( )

private

Warning

This function is not part of the public interface.

Definition at line 470 of file qsimplex_p.cpp.

Referenced by solveMaxHelper().

{
    for (int i = 1; i < rows; ++i) {
        int factorInObjectiveRow = valueAt(i, 0);
        combineRows(0, i, -1 * valueAt(0, factorInObjectiveRow));
    }
}

setConstraints()

bool QSimplex::setConstraints

(

const QList< QSimplexConstraint *>

newConstraints

)

Sets the new constraints in the simplex solver and returns whether the problem is feasible.

Warning

This function is not part of the public interface.

This method sets the new constraints, normalizes them, creates the simplex matrix and runs the first simplex phase.

Definition at line 135 of file qsimplex_p.cpp.

Referenced by QGraphicsAnchorLayoutPrivate::solveMinMax(), and QGraphicsAnchorLayoutPrivate::solvePreferred().

{
    // 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!";
        clearDataStructures();
        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;
}

setObjective()

void QSimplex::setObjective

(

QSimplexConstraint *

newObjective

)

Warning

This function is not part of the public interface.

Definition at line 332 of file qsimplex_p.cpp.

Referenced by QGraphicsAnchorLayoutPrivate::solveMinMax(), and QGraphicsAnchorLayoutPrivate::solvePreferred().

{
    objective = newObjective;
}

setValueAt()

void QSimplex::setValueAt ( int  row, int  column, qreal  value  )

inlineprivate

Definition at line 201 of file qsimplex_p.h.

Referenced by iterate(), setConstraints(), and solver().

{
    matrix[rowIndex * columns + columnIndex] = value;
}

simplifyConstraints()

bool QSimplex::simplifyConstraints ( QList< QSimplexConstraint *> *  constraints )

private

Looks for single-valued variables and remove them from the constraints list.

Warning

This function is not part of the public interface.

Definition at line 635 of file qsimplex_p.cpp.

Referenced by setConstraints().

{
    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;
}

solveMax()

qreal QSimplex::solveMax

(

)

Maximize the original objective.

Warning

This function is not part of the public interface.

Definition at line 594 of file qsimplex_p.cpp.

Referenced by QGraphicsAnchorLayoutPrivate::solveMinMax().

{
    return solver(Maximum);
}

solveMaxHelper()

void QSimplex::solveMaxHelper ( )

private

Run simplex on the current matrix with the current objective.

Warning

This function is not part of the public interface.

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.

Definition at line 323 of file qsimplex_p.cpp.

Referenced by setConstraints(), and solver().

{
    reducedRowEchelon();
    while (iterate()) ;
}

solveMin()

qreal QSimplex::solveMin

(

)

Minimize the original objective.

Warning

This function is not part of the public interface.

Definition at line 582 of file qsimplex_p.cpp.

Referenced by QGraphicsAnchorLayoutPrivate::solveMinMax(), and QGraphicsAnchorLayoutPrivate::solvePreferred().

{
    return solver(Minimum);
}

solver()

qreal QSimplex::solver ( solverFactor  factor )

private

Both solveMin and solveMax are interfaces to this method.

Warning

This function is not part of the public interface.

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.

Definition at line 538 of file qsimplex_p.cpp.

Referenced by solveMax(), and solveMin().

{
    // 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;
}

valueAt()

qreal QSimplex::valueAt ( int  row, int  column  )

inlineprivate

Definition at line 196 of file qsimplex_p.h.

Referenced by collectResults(), findPivotColumn(), iterate(), pivotRowForColumn(), reducedRowEchelon(), setConstraints(), and solver().

{
    return matrix[rowIndex * columns + columnIndex];
}

Properties

columns

int QSimplex::columns

private

Definition at line 190 of file qsimplex_p.h.

Referenced by clearColumns(), clearDataStructures(), clearRow(), collectResults(), combineRows(), dumpMatrix(), findPivotColumn(), pivotRowForColumn(), setConstraints(), and solver().

constraints

QList<QSimplexConstraint *> QSimplex::constraints

private

Definition at line 185 of file qsimplex_p.h.

Referenced by clearDataStructures(), setConstraints(), and solver().

firstArtificial

int QSimplex::firstArtificial

private

Definition at line 191 of file qsimplex_p.h.

Referenced by clearDataStructures(), and setConstraints().

matrix

qreal* QSimplex::matrix

private

Definition at line 193 of file qsimplex_p.h.

Referenced by clearColumns(), clearDataStructures(), clearRow(), combineRows(), dumpMatrix(), and setConstraints().

objective

QSimplexConstraint* QSimplex::objective

private

Definition at line 187 of file qsimplex_p.h.

Referenced by clearDataStructures(), setObjective(), and solver().

rows

int QSimplex::rows

private

Definition at line 189 of file qsimplex_p.h.

Referenced by clearColumns(), clearDataStructures(), collectResults(), dumpMatrix(), iterate(), pivotRowForColumn(), reducedRowEchelon(), and setConstraints().

variables

QList<QSimplexVariable *> QSimplex::variables

private

Definition at line 186 of file qsimplex_p.h.

Referenced by clearDataStructures(), collectResults(), QSimplexConstraint::invert(), and setConstraints().

---

The documentation for this class was generated from the following files:

• /src/gui/graphicsview/qsimplex_p.h
• /src/gui/graphicsview/qsimplex_p.cpp