summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--src/gui/graphicsview/qsimplex_p.cpp113
1 files changed, 108 insertions, 5 deletions
diff --git a/src/gui/graphicsview/qsimplex_p.cpp b/src/gui/graphicsview/qsimplex_p.cpp
index e3a991e..7de7da0 100644
--- a/src/gui/graphicsview/qsimplex_p.cpp
+++ b/src/gui/graphicsview/qsimplex_p.cpp
@@ -48,6 +48,32 @@
QT_BEGIN_NAMESPACE
+/*!
+ \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.
+*/
+
QSimplex::QSimplex() : objective(0), rows(0), columns(0), firstArtificial(0), matrix(0)
{
}
@@ -84,15 +110,31 @@ void QSimplex::clearDataStructures()
objective = 0;
}
+/*!
+ 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
constraints = newConstraints;
- // Set Variables direct mapping
+ ///////////////////////////////////////
+ // 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 += \
@@ -100,12 +142,25 @@ bool QSimplex::setConstraints(const QList<QSimplexConstraint *> newConstraints)
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;
@@ -138,12 +193,18 @@ bool QSimplex::setConstraints(const QList<QSimplexConstraint *> newConstraints)
}
}
+ // 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();
- // Matrix
+ /////////////////////////////
+ // Fill the Simplex matrix //
+ /////////////////////////////
// One for each variable plus the Basic and BFS columns (first and last)
columns = variableIndex + 2;
@@ -188,24 +249,42 @@ bool QSimplex::setConstraints(const QList<QSimplexConstraint *> newConstraints)
setValueAt(i, columns - 1, c->constant);
}
- // Set temporary objective: -1 * sum_of_artificial_vars
+ // 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) {
qWarning() << "QSimplex: No feasible solution!";
clearDataStructures();
return false;
}
- // Remove artificial variables
+ // 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();
@@ -320,6 +399,12 @@ void QSimplex::reducedRowEchelon()
}
}
+/*!
+ \internal
+
+ Does one iteration towards a better solution for the problem.
+ See 'solveMaxHelper'.
+*/
bool QSimplex::iterate()
{
// Find Pivot column
@@ -361,7 +446,13 @@ bool QSimplex::iterate()
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
@@ -381,16 +472,28 @@ qreal QSimplex::solver(solverFactor factor)
return factor * valueAt(0, columns - 1);
}
+/*!
+ Minimize the original objective.
+*/
qreal QSimplex::solveMin()
{
return solver(Minimum);
}
+/*!
+ 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.