[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