[haiku-commits] r40285 - in haiku/trunk: headers/libs/alm headers/libs/linprog src/libs/alm src/libs/linprog
- From: clemens.zeidler@xxxxxxxxxxxxxx
- To: haiku-commits@xxxxxxxxxxxxx
- Date: Tue, 25 Jan 2011 05:59:40 +0100 (CET)
Author: czeidler
Date: 2011-01-25 05:59:40 +0100 (Tue, 25 Jan 2011)
New Revision: 40285
Changeset: http://dev.haiku-os.org/changeset/40285
Added:
haiku/trunk/src/libs/linprog/ActiveSetSolver.cpp
haiku/trunk/src/libs/linprog/ActiveSetSolver.h
haiku/trunk/src/libs/linprog/LayoutOptimizer.cpp
haiku/trunk/src/libs/linprog/LayoutOptimizer.h
Removed:
haiku/trunk/headers/libs/linprog/PenaltyFunction.h
haiku/trunk/src/libs/linprog/PenaltyFunction.cpp
Modified:
haiku/trunk/headers/libs/alm/ALMLayout.h
haiku/trunk/headers/libs/alm/Area.h
haiku/trunk/headers/libs/linprog/Constraint.h
haiku/trunk/headers/libs/linprog/LinearSpec.h
haiku/trunk/headers/libs/linprog/Summand.h
haiku/trunk/src/libs/alm/ALMLayout.cpp
haiku/trunk/src/libs/alm/Area.cpp
haiku/trunk/src/libs/linprog/Constraint.cpp
haiku/trunk/src/libs/linprog/Jamfile
haiku/trunk/src/libs/linprog/LPSolveInterface.cpp
haiku/trunk/src/libs/linprog/LPSolveInterface.h
haiku/trunk/src/libs/linprog/LinearSpec.cpp
haiku/trunk/src/libs/linprog/Summand.cpp
Log:
Add an alternative solver to lp_solve. The solver based on Ingo's active set
solver but is able to handle arbitrary hard and soft constraints. The advantage
to lp_solve is that the active set solver can optimize variable in respect to a
quadratic objective function. This makes it possible to minimise the quadratic
derivation to a desired value e.g. \Sum_i(x_i - x_{i,pref})^2 -> min.
The solver part has been refactored in this way that both solver can be used
with the same layout specifications. The active set solver is default now; the
performance is not as good as lp_solve, though.
Modified: haiku/trunk/headers/libs/alm/ALMLayout.h
===================================================================
--- haiku/trunk/headers/libs/alm/ALMLayout.h 2011-01-24 22:50:46 UTC (rev
40284)
+++ haiku/trunk/headers/libs/alm/ALMLayout.h 2011-01-25 04:59:40 UTC (rev
40285)
@@ -124,8 +124,6 @@
/*! Add a view without initialize the Area. */
BLayoutItem* _CreateLayoutItem(BView* view);
- void _SolveLayout();
-
void
_UpdateAreaConstraints();
BSize _CalculateMinSize();
@@ -152,8 +150,10 @@
Area* fCurrentArea;
+#if USE_SCALE_VARIABLE
Variable* fScaleWidth;
Variable* fScaleHeight;
+#endif
};
} // namespace BALM
Modified: haiku/trunk/headers/libs/alm/Area.h
===================================================================
--- haiku/trunk/headers/libs/alm/Area.h 2011-01-24 22:50:46 UTC (rev 40284)
+++ haiku/trunk/headers/libs/alm/Area.h 2011-01-25 04:59:40 UTC (rev 40285)
@@ -20,6 +20,9 @@
#include "Tab.h"
+#define USE_SCALE_VARIABLE 1
+
+
class Constraint;
@@ -106,6 +109,7 @@
private:
Area(BLayoutItem* item);
+#if USE_SCALE_VARIABLE
void _Init(LinearSpec* ls,
XTab* left, YTab* top,
XTab*
right, YTab* bottom,
Variable* scaleWidth,
@@ -113,6 +117,11 @@
void _Init(LinearSpec* ls,
Row* row, Column* column,
Variable* scaleWidth,
Variable* scaleHeight);
+#else
+ void _Init(LinearSpec* ls,
XTab* left, YTab* top,
+ XTab*
right, YTab* bottom);
+ void _Init(LinearSpec* ls,
Row* row, Column* column);
+#endif
void _DoLayout();
@@ -152,9 +161,10 @@
double fContentAspectRatio;
Constraint* fContentAspectRatioC;
+#if USE_SCALE_VARIABLE
Variable* fScaleWidth;
Variable* fScaleHeight;
-
+#endif
public:
friend class BALMLayout;
Modified: haiku/trunk/headers/libs/linprog/Constraint.h
===================================================================
--- haiku/trunk/headers/libs/linprog/Constraint.h 2011-01-24 22:50:46 UTC
(rev 40284)
+++ haiku/trunk/headers/libs/linprog/Constraint.h 2011-01-25 04:59:40 UTC
(rev 40285)
@@ -27,7 +27,6 @@
* May render a specification infeasible.
*/
class Constraint {
-
public:
int32 Index() const;
@@ -57,24 +56,26 @@
const char* Label();
void SetLabel(const char*
label);
- void WriteXML(BFile* file);
-
Variable* DNeg() const;
Variable* DPos() const;
+ bool IsSoft() const;
+
bool IsValid();
void Invalidate();
operator
BString() const;
void GetString(BString&
string) const;
+ void PrintToStream();
~Constraint();
protected:
Constraint(LinearSpec* ls,
SummandList* summands, OperatorType op,
- double
rightSide, double penaltyNeg,
- double
penaltyPos);
+ double
rightSide,
+ double
penaltyNeg = -1,
+ double
penaltyPos = -1);
private:
LinearSpec* fLS;
@@ -92,6 +93,7 @@
public:
friend class LinearSpec;
+ friend class LPSolveInterface;
};
Modified: haiku/trunk/headers/libs/linprog/LinearSpec.h
===================================================================
--- haiku/trunk/headers/libs/linprog/LinearSpec.h 2011-01-24 22:50:46 UTC
(rev 40284)
+++ haiku/trunk/headers/libs/linprog/LinearSpec.h 2011-01-25 04:59:40 UTC
(rev 40285)
@@ -11,47 +11,51 @@
#include <List.h>
#include <OS.h>
+#include <Size.h>
#include <String.h>
#include <SupportDefs.h>
#include "Constraint.h"
#include "LinearProgrammingTypes.h"
-#include "PenaltyFunction.h"
#include "Summand.h"
#include "Variable.h"
namespace LinearProgramming {
+
+class LinearSpec;
+
+
+const BSize kMinSize(0, 0);
+const BSize kMaxSize(B_SIZE_UNLIMITED, B_SIZE_UNLIMITED);
+
+
class SolverInterface {
public:
+
SolverInterface(LinearSpec* linSpec);
+
virtual ~SolverInterface() {}
- virtual ResultType Solve(VariableList& variables)
= 0;
- virtual double GetObjectiveValue() = 0;
+ virtual ResultType Solve() = 0;
- virtual bool AddVariable() = 0;
- virtual bool RemoveVariable(int variable) =
0;
- virtual bool SetVariableRange(int variable,
double min,
- double
max) = 0;
+ virtual bool VariableAdded(Variable*
variable) = 0;
+ virtual bool VariableRemoved(Variable*
variable) = 0;
+ virtual bool VariableRangeChanged(Variable*
variable) = 0;
- virtual bool AddConstraint(int nElements,
- double*
coefficients, int* variableIndices,
-
OperatorType op, double rightSide) = 0;
- virtual bool RemoveConstraint(int
constraint) = 0;
- virtual bool SetLeftSide(int constraint, int
nElements,
- double*
coefficients,
- int*
variableIndices) = 0;
- virtual bool SetRightSide(int constraint,
double value) = 0;
- virtual bool SetOperator(int constraint,
-
OperatorType op) = 0;
+ virtual bool ConstraintAdded(Constraint*
constraint) = 0;
+ virtual bool ConstraintRemoved(Constraint*
constraint) = 0;
+ virtual bool LeftSideChanged(Constraint*
constraint) = 0;
+ virtual bool RightSideChanged(Constraint*
constraint) = 0;
+ virtual bool OperatorChanged(Constraint*
constraint) = 0;
- virtual bool SetObjectiveFunction(int
nElements,
- double*
coefficients,
- int*
variableIndices) = 0;
- virtual bool
SetOptimization(OptimizationType value) = 0;
-
virtual bool SaveModel(const char* fileName)
= 0;
+
+ virtual BSize MinSize(Variable* width,
Variable* height) = 0;
+ virtual BSize MaxSize(Variable* width,
Variable* height) = 0;
+
+protected:
+ LinearSpec* fLinearSpec;
};
@@ -113,31 +117,22 @@
OperatorType op, double rightSide,
double
penaltyNeg, double penaltyPos);
- PenaltyFunction* AddPenaltyFunction(Variable*
var, BList* xs,
- BList*
gs);
+ BSize MinSize(Variable*
width, Variable* height);
+ BSize MaxSize(Variable*
width, Variable* height);
- SummandList* ObjectiveFunction();
- //! Caller takes ownership of the Summand's and the
SummandList.
- SummandList* SwapObjectiveFunction(
-
SummandList* objFunction);
- void
SetObjectiveFunction(SummandList* objFunction);
- void
UpdateObjectiveFunction();
-
ResultType Solve();
bool Save(const char*
fileName);
int32 CountColumns() const;
- OptimizationType Optimization() const;
- void
SetOptimization(OptimizationType value);
ResultType Result() const;
- double ObjectiveValue() const;
- double SolvingTime() const;
+ bigtime_t SolvingTime() const;
operator BString() const;
void GetString(BString&
string) const;
const ConstraintList& Constraints() const;
+ const VariableList& Variables() const;
protected:
friend class Constraint;
@@ -152,14 +147,10 @@
OperatorType op, double rightSide,
double
penaltyNeg, double penaltyPos);
- OptimizationType fOptimization;
-
- SummandList* fObjFunction;
VariableList fVariables;
ConstraintList fConstraints;
ResultType fResult;
- double fObjectiveValue;
- double fSolvingTime;
+ bigtime_t fSolvingTime;
SolverInterface* fSolver;
};
Modified: haiku/trunk/headers/libs/linprog/Summand.h
===================================================================
--- haiku/trunk/headers/libs/linprog/Summand.h 2011-01-24 22:50:46 UTC (rev
40284)
+++ haiku/trunk/headers/libs/linprog/Summand.h 2011-01-25 04:59:40 UTC (rev
40285)
@@ -27,6 +27,7 @@
Variable* Var();
void SetVar(Variable* var);
+ int32 VariableIndex();
private:
double fCoeff;
Variable* fVar;
Modified: haiku/trunk/src/libs/alm/ALMLayout.cpp
===================================================================
--- haiku/trunk/src/libs/alm/ALMLayout.cpp 2011-01-24 22:50:46 UTC (rev
40284)
+++ haiku/trunk/src/libs/alm/ALMLayout.cpp 2011-01-25 04:59:40 UTC (rev
40285)
@@ -19,8 +19,6 @@
const BSize kUnsetSize(B_SIZE_UNSET, B_SIZE_UNSET);
-const BSize kMinSize(0, 0);
-const BSize kMaxSize(B_SIZE_UNLIMITED, B_SIZE_UNLIMITED);
/*!
@@ -42,7 +40,8 @@
fTop = AddYTab();
fBottom = AddYTab();
- // the Left tab is always at x-position 0, and the Top tab is always at
y-position 0
+ // the Left tab is always at x-position 0, and the Top tab is always at
+ // y-position 0
fLeft->SetRange(0, 0);
fTop->SetRange(0, 0);
@@ -54,15 +53,19 @@
fPerformancePath = NULL;
+#if USE_SCALE_VARIABLE
fScaleWidth = fSolver->AddVariable();
fScaleHeight = fSolver->AddVariable();
+#endif
}
BALMLayout::~BALMLayout()
{
+#if USE_SCALE_VARIABLE
delete fScaleWidth;
delete fScaleHeight;
+#endif
}
@@ -484,7 +487,11 @@
return NULL;
fCurrentArea = area;
+#if USE_SCALE_VARIABLE
area->_Init(fSolver, left, top, right, bottom, fScaleWidth,
fScaleHeight);
+#else
+ area->_Init(fSolver, left, top, right, bottom);
+#endif
return area;
}
@@ -499,7 +506,11 @@
return NULL;
fCurrentArea = area;
+#if USE_SCALE_VARIABLE
area->_Init(fSolver, row, column, fScaleWidth, fScaleHeight);
+#else
+ area->_Init(fSolver, row, column);
+#endif
return area;
}
@@ -701,7 +712,7 @@
Right()->SetRange(area.right, area.right);
Bottom()->SetRange(area.bottom, area.bottom);
- _SolveLayout();
+ fSolver->Solve();
// if new layout is infeasible, use previous layout
if (fSolver->Result() == kInfeasible)
@@ -786,36 +797,6 @@
}
-void
-BALMLayout::_SolveLayout()
-{
- // Try to solve the layout until the result is kOptimal or kInfeasible,
- // maximally 15 tries sometimes the solving algorithm encounters
numerical
- // problems (NUMFAILURE), and repeating the solving often helps to
overcome
- // them.
- BFile* file = NULL;
- if (fPerformancePath != NULL) {
- file = new(std::nothrow) BFile(fPerformancePath,
- B_READ_WRITE | B_CREATE_FILE | B_OPEN_AT_END);
- }
-
- ResultType result;
- for (int32 tries = 0; tries < 15; tries++) {
- result = fSolver->Solve();
- if (fPerformancePath != NULL) {
- /*char buffer [100];
- file->Write(buffer, sprintf(buffer,
"%d\t%fms\t#vars=%ld\t"
- "#constraints=%ld\n", result,
fSolver->SolvingTime(),
- fSolver->Variables()->CountItems(),
- fSolver->Constraints()->CountItems()));*/
- }
- if (result == kOptimal || result == kInfeasible)
- break;
- }
- delete file;
-}
-
-
/**
* Caculates the miminum size.
*/
@@ -824,24 +805,7 @@
{
_UpdateAreaConstraints();
- SummandList* newObjFunction = new(std::nothrow) SummandList(2);
- newObjFunction->AddItem(new(std::nothrow) Summand(1.0, fRight));
- newObjFunction->AddItem(new(std::nothrow) Summand(1.0, fBottom));
- SummandList* oldObjFunction = fSolver->SwapObjectiveFunction(
- newObjFunction);
- _SolveLayout();
- fSolver->SetObjectiveFunction(oldObjFunction);
-
- if (fSolver->Result() == kUnbounded)
- return kMinSize;
- if (fSolver->Result() != kOptimal) {
- fSolver->Save("failed-layout.txt");
- printf("Could not solve the layout specification (%d). "
- "Saved specification in file failed-layout.txt",
fSolver->Result());
- }
-
- return BSize(Right()->Value() - Left()->Value(),
- Bottom()->Value() - Top()->Value());
+ return fSolver->MinSize(Right(), Bottom());
}
@@ -853,24 +817,7 @@
{
_UpdateAreaConstraints();
- SummandList* newObjFunction = new(std::nothrow) SummandList(2);
- newObjFunction->AddItem(new(std::nothrow) Summand(-1.0, fRight));
- newObjFunction->AddItem(new(std::nothrow) Summand(-1.0, fBottom));
- SummandList* oldObjFunction = fSolver->SwapObjectiveFunction(
- newObjFunction);
- _SolveLayout();
- fSolver->SetObjectiveFunction(oldObjFunction);
-
- if (fSolver->Result() == kUnbounded)
- return kMaxSize;
- if (fSolver->Result() != kOptimal) {
- fSolver->Save("failed-layout.txt");
- printf("Could not solve the layout specification (%d). "
- "Saved specification in file failed-layout.txt",
fSolver->Result());
- }
-
- return BSize(Right()->Value() - Left()->Value(),
- Bottom()->Value() - Top()->Value());
+ return fSolver->MaxSize(Right(), Bottom());
}
@@ -882,7 +829,7 @@
{
_UpdateAreaConstraints();
- _SolveLayout();
+ fSolver->Solve();
if (fSolver->Result() != kOptimal) {
fSolver->Save("failed-layout.txt");
printf("Could not solve the layout specification (%d). "
Modified: haiku/trunk/src/libs/alm/Area.cpp
===================================================================
--- haiku/trunk/src/libs/alm/Area.cpp 2011-01-24 22:50:46 UTC (rev 40284)
+++ haiku/trunk/src/libs/alm/Area.cpp 2011-01-25 04:59:40 UTC (rev 40285)
@@ -599,19 +599,24 @@
/**
* Initialize variables.
*/
+#if USE_SCALE_VARIABLE
void
Area::_Init(LinearSpec* ls, XTab* left, YTab* top, XTab* right, YTab* bottom,
Variable* scaleWidth, Variable* scaleHeight)
{
+ fScaleWidth = scaleWidth;
+ fScaleHeight = scaleHeight;
+#else
+void
+Area::_Init(LinearSpec* ls, XTab* left, YTab* top, XTab* right, YTab* bottom)
+{
+#endif
fLS = ls;
fLeft = left;
fRight = right;
fTop = top;
fBottom = bottom;
- fScaleWidth = scaleWidth;
- fScaleHeight = scaleHeight;
-
// adds the two essential constraints of the area that make sure that
the
// left x-tab is really to the left of the right x-tab, and the top
y-tab
// really above the bottom y-tab
@@ -621,6 +626,7 @@
fConstraints.AddItem(fMinContentWidth);
fConstraints.AddItem(fMinContentHeight);
+#if USE_SCALE_VARIABLE
fPreferredContentWidth = fLS->AddConstraint(-1.0, fLeft, 1.0, fRight,
-1.0,
fScaleWidth, kEQ, 0, fShrinkPenalties.Width(),
fGrowPenalties.Width());
@@ -628,18 +634,34 @@
fPreferredContentHeight = fLS->AddConstraint(-1.0, fTop, 1.0, fBottom,
-1.0,
fScaleHeight, kEQ, 0, fShrinkPenalties.Height(),
fGrowPenalties.Height());
+#else
+ BSize preferredSize = fLayoutItem->PreferredSize();
+ fPreferredContentWidth = fLS->AddConstraint(-1.0, fLeft, 1.0, fRight,
kEQ,
+ 0, fShrinkPenalties.Width(), fGrowPenalties.Width());
+ _UpdatePreferredWidthConstraint(preferredSize);
+ fPreferredContentHeight = fLS->AddConstraint(-1.0, fTop, 1.0, fBottom,
kEQ,
+ 0, fShrinkPenalties.Height(), fGrowPenalties.Height());
+ _UpdatePreferredHeightConstraint(preferredSize);
+#endif
fConstraints.AddItem(fPreferredContentWidth);
fConstraints.AddItem(fPreferredContentHeight);
}
+#if USE_SCALE_VARIABLE
void
Area::_Init(LinearSpec* ls, Row* row, Column* column, Variable* scaleWidth,
Variable* scaleHeight)
{
_Init(ls, column->Left(), row->Top(), column->Right(), row->Bottom(),
scaleWidth, scaleHeight);
+#else
+void
+Area::_Init(LinearSpec* ls, Row* row, Column* column)
+{
+ _Init(ls, column->Left(), row->Top(), column->Right(), row->Bottom());
+#endif
fRow = row;
fColumn = column;
}
@@ -723,22 +745,28 @@
void
Area::_UpdatePreferredWidthConstraint(BSize& preferred)
{
- float width = 32000;
+ float width = 0;
if (preferred.width > 0)
width = preferred.Width() + LeftInset() + RightInset();
-
+#if USE_SCALE_VARIABLE
fPreferredContentWidth->SetLeftSide(-1.0, fLeft, 1.0, fRight, -width,
fScaleWidth);
+#else
+ fPreferredContentWidth->SetRightSide(width);
+#endif
}
void
Area::_UpdatePreferredHeightConstraint(BSize& preferred)
{
- float height = 32000;
+ float height = 0;
if (preferred.height > 0)
height = preferred.Height() + TopInset() + BottomInset();
-
+#if USE_SCALE_VARIABLE
fPreferredContentHeight->SetLeftSide(-1.0, fTop, 1.0, fBottom, -height,
fScaleHeight);
+#else
+ fPreferredContentHeight->SetRightSide(height);
+#endif
}
Added: haiku/trunk/src/libs/linprog/ActiveSetSolver.cpp
===================================================================
--- haiku/trunk/src/libs/linprog/ActiveSetSolver.cpp
(rev 0)
+++ haiku/trunk/src/libs/linprog/ActiveSetSolver.cpp 2011-01-25 04:59:40 UTC
(rev 40285)
@@ -0,0 +1,542 @@
+#include "ActiveSetSolver.h"
+
+#include <stdio.h>
+
+#include "LayoutOptimizer.h"
+
+
+//#define DEBUG_ACTIVE_SOLVER
+
+#ifdef DEBUG_ACTIVE_SOLVER
+#include <stdio.h>
+#define TRACE(x...) printf(x)
+#else
+#define TRACE(x...) /* nothing */
+#endif
+
+
+using namespace LinearProgramming;
+using namespace BPrivate::Layout;
+
+
+template<typename Type>
+static inline void
+swap(Type& a, Type& b)
+{
+ Type c = a;
+ a = b;
+ b = c;
+}
+
+
+EquationSystem::EquationSystem(int32 rows, int32 columns)
+ :
+ fRows(rows),
+ fColumns(columns)
+{
+ fMatrix = allocate_matrix(fRows, fColumns);
+ fB = new double[fColumns];
+ // better init all values to prevent side cases where not all variables
+ // needed to solve the problem, coping theses values to the results
could
+ // cause problems
+ for (int i = 0; i < fColumns; i++)
+ fB[i] = 0;
+ zero_matrix(fMatrix, fRows, fColumns);
+
+ fRowIndices = new int32[fRows];
+ fColumnIndices = new int32[fColumns];
+ for (int i = 0; i < fRows; i++)
+ fRowIndices[i] = i;
+ for (int i = 0; i < fColumns; i++)
+ fColumnIndices[i] = i;
+}
+
+
+EquationSystem::~EquationSystem()
+{
+ free_matrix(fMatrix);
+ delete[] fB;
+ delete[] fRowIndices;
+ delete[] fColumnIndices;
+}
+
+
+void
+EquationSystem::SetRows(int32 rows)
+{
+ fRows = rows;
+}
+
+
+int32
+EquationSystem::Rows()
+{
+ return fRows;
+}
+
+
+int32
+EquationSystem::Columns()
+{
+ return fColumns;
+}
+
+
+double&
+EquationSystem::A(int32 row, int32 column)
+{
+ return fMatrix[fRowIndices[row]][fColumnIndices[column]];
+}
+
+
+double&
+EquationSystem::B(int32 row)
+{
+ return fB[row];
+}
+
+
+void
+EquationSystem::Results(double* results, int32 size)
+{
+ for (int i = 0; i < size; i++)
+ results[i] = 0;
+ for (int i = 0; i < fColumns; i++) {
+ int32 index = fColumnIndices[i];
+ if (index < fRows)
+ results[index] = fB[i];
+ }
+}
+
+
+void
+EquationSystem::SwapColumn(int32 i, int32 j)
+{
+ swap(fColumnIndices[i], fColumnIndices[j]);
+}
+
+
+void
+EquationSystem::SwapRow(int32 i, int32 j)
+{
+ swap(fRowIndices[i], fRowIndices[j]);
+ swap(fB[i], fB[j]);
+}
+
+
+bool
+EquationSystem::GaussJordan()
+{
+ // basic solve
+ for (int i = 0; i < fRows; i++) {
+ // find none zero element
+ int swapRow = -1;
+ for (int r = i; r < fRows; r++) {
+ double& value =
fMatrix[fRowIndices[r]][fColumnIndices[i]];
+ if (fuzzy_equals(value, 0))
+ continue;
+ swapRow = r;
+ break;
+ }
+ if (swapRow == -1) {
+ int swapColumn = -1;
+ for (int c = i + 1; c < fColumns; c++) {
+ double& value =
fMatrix[fRowIndices[i]][fColumnIndices[c]];
+ if (fuzzy_equals(value, 0))
+ continue;
+ swapRow = i;
+ swapColumn = c;
+ break;
+ }
+ if (swapColumn == -1) {
+ printf("can't solve column %i\n", i);
+ return false;
+ }
+ SwapColumn(i, swapColumn);
+ }
+ if (i != swapRow)
+ SwapRow(i, swapRow);
+
+ // normalize
+ GaussJordan(i);
+ }
+ return true;
+}
+
+
+void
+EquationSystem::GaussJordan(int32 i)
+{
+ double value = fMatrix[fRowIndices[i]][fColumnIndices[i]];
+ for (int j = 0; j < fColumns; j++)
+ fMatrix[fRowIndices[i]][fColumnIndices[j]] /= value;
+ fB[i] /= value;
+
+ for (int r = 0; r < fRows; r++) {
+ if (r == i)
+ continue;
+ double q = -fMatrix[fRowIndices[r]][fColumnIndices[i]];
+ // don't need to do nothing, since matrix is typically sparse
this
+ // should save some work
+ if (fuzzy_equals(q, 0))
+ continue;
+ for (int c = 0; c < fColumns; c++)
+ fMatrix[fRowIndices[r]][fColumnIndices[c]]
+ += fMatrix[fRowIndices[i]][fColumnIndices[c]] *
q;
+
+ fB[r] += fB[i] * q;
+ }
+}
+
+
+void
+EquationSystem::RemoveLinearlyDependentRows()
+{
+ double oldB[fRows];
+ for (int r = 0; r < fRows; r++)
+ oldB[r] = fB[r];
+
+ double** temp = allocate_matrix(fRows, fColumns);
+ bool independentRows[fRows];
+
+ // copy to temp
+ copy_matrix(fMatrix, temp, fRows, fColumns);
+ int nIndependent = compute_dependencies(temp, fRows, fColumns,
+ independentRows);
+ if (nIndependent == fRows)
+ return;
+
+ // remove the rows
+ for (int i = 0; i < fRows; i++) {
+ if (!independentRows[i]) {
+ int lastDepRow = -1;
+ for (int d = fRows - 1; d > i; d--) {
+ if (independentRows[d]) {
+ lastDepRow = d;
+ break;
+ }
+ }
+ if (lastDepRow < 0)
+ break;
+ SwapRow(i, lastDepRow);
+ fRows--;
+ }
+ }
+ fRows = nIndependent;
+
+ free_matrix(temp);
+}
+
+
+void
+EquationSystem::RemoveUnusedVariables()
+{
+ for (int c = 0; c < fColumns; c++) {
+ bool used = false;
+ for (int r = 0; r < fRows; r++) {
+ if (!fuzzy_equals(fMatrix[r][fColumnIndices[c]], 0)) {
+ used = true;
+ break;
+ }
+ }
+ if (used)
+ continue;
+
+ //MoveColumnRight(c, fColumns - 1);
+ SwapColumn(c, fColumns - 1);
+ fColumns--;
+ c--;
+ }
+}
+
+
+void
+EquationSystem::MoveColumnRight(int32 i, int32 target)
+{
+ int32 index = fColumnIndices[i];
+ for (int c = i; c < target; c++)
+ fColumnIndices[c] = fColumnIndices[c + 1];
+ fColumnIndices[target] = index;
+}
+
+
+void
+EquationSystem::Print()
+{
+ for (int m = 0; m < fRows; m++) {
+ for (int n = 0; n < fColumns; n++)
+ printf("%.1f ",
fMatrix[fRowIndices[m]][fColumnIndices[n]]);
+ printf("= %.1f\n", fB[m]);
+ }
+}
+
+
+ActiveSetSolver::ActiveSetSolver(LinearSpec* linearSpec)
+ :
+ SolverInterface(linearSpec),
+
+ fVariables(linearSpec->Variables()),
+ fConstraints(linearSpec->Constraints())
+{
+
+}
+
+
+ActiveSetSolver::~ActiveSetSolver()
+{
+
+}
+
+
+/* Using algorithm found in:
+Solving Inequalities and Proving Farkas's Lemma Made Easy
+David Avis and Bohdan Kaluzny
+The American Mathematical Monthly
+Vol. 111, No. 2 (Feb., 2004), pp. 152-157 */
+bool
+solve(EquationSystem& system)
+{
+ // basic solve
+ if (!system.GaussJordan())
+ return false;
+
+ bool done = false;
+ while (!done) {
+ double smallestB = HUGE_VALF;
+ int smallestBRow = -1;
+ for (int row = 0; row < system.Rows(); row++) {
+ if (system.B(row) > 0 || fuzzy_equals(system.B(row), 0))
+ continue;
+
+ double bValue = fabs(system.B(row));
+ if (bValue < smallestB) {
+ smallestB = bValue;
+ smallestBRow = row;
+ }
+ }
+ if (smallestBRow == -1) {
+ done = true;
+ break;
+ }
+
+ int negValueCol = -1;
+ for (int col = system.Rows(); col < system.Columns(); col++) {
+ double value = system.A(smallestBRow, col);
+ if (value > 0 || fuzzy_equals(value, 0))
+ continue;
+ negValueCol = col;
+ break;
+ }
+ if (negValueCol == -1) {
+ printf("can't solve\n");
+ return false;
+ }
+
+ system.SwapColumn(smallestBRow, negValueCol);
+
+ // eliminate
+ system.GaussJordan(smallestBRow);
+ }
+
+ return true;
+}
+
+
+ResultType
+ActiveSetSolver::Solve()
+{
+ int32 nConstraints = fConstraints.CountItems();
+ int32 nVariables = fVariables.CountItems();
+
+ if (nVariables > nConstraints) {
+ printf("More variables then constraints! vars: %i, constraints:
%i\n",
+ (int)nVariables, (int)nConstraints);
+ return kInfeasible;
+ }
+
+ /* First find an initial solution and then optimize it using the active
set
+ method. */
+ EquationSystem system(nConstraints, nVariables + nConstraints);
+
+ int32 slackIndex = nVariables;
+ // setup constraint matrix and add slack variables if necessary
+ int32 rowIndex = 0;
+ for (int32 c = 0; c < nConstraints; c++) {
+ Constraint* constraint = fConstraints.ItemAt(c);
+ if (constraint->IsSoft())
+ continue;
+ SummandList* leftSide = constraint->LeftSide();
+ system.B(rowIndex) = constraint->RightSide();
+ for (int32 sIndex = 0; sIndex < leftSide->CountItems();
sIndex++ ) {
+ Summand* summand = leftSide->ItemAt(sIndex);
+ int32 coefficient = summand->Coeff();
+ system.A(rowIndex, summand->VariableIndex()) =
coefficient;
+ }
+ if (constraint->Op() == kLE) {
+ system.A(rowIndex, slackIndex) = 1;
+ slackIndex++;
+ } else if (constraint->Op() == kGE) {
+ system.A(rowIndex, slackIndex) = -1;
+ slackIndex++;
+ }
+ rowIndex++;
+ }
+
+ system.SetRows(rowIndex);
+
+ system.RemoveLinearlyDependentRows();
+ system.RemoveUnusedVariables();
+
+ if (!solve(system))
+ return kInfeasible;
+
+ double results[nVariables + nConstraints];
+ system.Results(results, nVariables + nConstraints);
+ printf("base system solved\n");
+
+ LayoutOptimizer optimizer(fConstraints, nVariables);
+ optimizer.Solve(results);
+
+ // back to the variables
+ for (int32 i = 0; i < nVariables; i++)
+ fVariables.ItemAt(i)->SetValue(results[i]);
+
+ for (int32 i = 0; i < nVariables; i++)
+ TRACE("var %f\n", results[i]);
+
+ return kOptimal;
+}
+
+
+bool
+ActiveSetSolver::VariableAdded(Variable* variable)
+{
+ // TODO: error checks
+ fVariableGEConstraints.AddItem(NULL);
+ fVariableLEConstraints.AddItem(NULL);
+ return true;
+}
+
+
+bool
+ActiveSetSolver::VariableRemoved(Variable* variable)
+{
+ fVariableGEConstraints.RemoveItemAt(variable->Index());
+ fVariableLEConstraints.RemoveItemAt(variable->Index());
+ return true;
+}
+
+
+bool
+ActiveSetSolver::VariableRangeChanged(Variable* variable)
+{
+ double min = variable->Min();
+ double max = variable->Max();
+ int32 variableIndex = variable->Index();
+
+ Constraint* constraintGE = fVariableGEConstraints.ItemAt(variableIndex);
+ Constraint* constraintLE = fVariableLEConstraints.ItemAt(variableIndex);
+ if (constraintGE == NULL && min > -20000) {
+ constraintGE = fLinearSpec->AddConstraint(1, variable, kGE, 0);
+ if (constraintGE == NULL)
+ return false;
+ fVariableGEConstraints.RemoveItemAt(variableIndex);
[... truncated: 2482 lines follow ...]
Other related posts:
- » [haiku-commits] r40285 - in haiku/trunk: headers/libs/alm headers/libs/linprog src/libs/alm src/libs/linprog - clemens . zeidler
