Make LinearProgram robust against degenerate solutions

If the container is exactly the size required by the widgets, there will
be redundant equations, which causes a degeneracy in the phase 1 solution.

diff --git a/source/layout.cpp b/source/layout.cpp
index 2972ec8567829a9faabe9caa7d7ab09733a26914..34afd7284a35878b409dd95f8b4bc34ebd6c4299 100644 (file)
--- a/source/layout.cpp
+++ b/source/layout.cpp
@@ -1,3 +1,4 @@
+#include <algorithm>
 #include <limits>
 #include "container.h"
 #include "layout.h"
@@ -45,9 +46,12 @@ public:
        Row add_row();
        Row operator[](unsigned);
        Row get_objective_row();
-       bool solve();
        float get_variable(unsigned);
+       bool solve();
 private:
+       void prepare_columns();
+       void add_artificial_variables();
+       void remove_artificial_variables();
        unsigned find_minimal_ratio(unsigned);
        void make_basic_column(unsigned, unsigned);
        bool pivot();
@@ -380,34 +384,9 @@ bool Layout::LinearProgram::solve()
        objective variable is kept implicit, as it would never change during the
        execution of the algorithm. */
 
-       /* Force all columns fully into existence and relocate objective row to
-       bottom in preparation of phase 1.  A new objective row is calculated by
-       pricing out the constraint rows. */
-       for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
-       {
-               float objective = 0.0f;
-               if(!i->values.empty())
-               {
-                       objective = i->values.front();
-                       i->values.front() = 0.0f;
-                       for(vector<float>::iterator j=i->values.begin(); j!=i->values.end(); ++j)
-                               i->values.front() += *j;
-               }
-               i->values.resize(n_rows+1, 0.0f);
-               i->values.back() = objective;
-       }
+       prepare_columns();
 
-       /* Create artificial variables for phase 1.  This ensures that each row has
-       a basic variable associated with it.  The original objective row already
-       contains the implicit objective variable, which is basic. */
-       columns.resize(n_columns+n_rows-1);
-       columns.back() = columns[n_columns-1];
-       columns[n_columns-1].values.clear();
-       for(unsigned i=1; i<n_rows; ++i)
-       {
-               Column &column = columns[n_columns+i-2];
-               column.basic = i;
-       }
+       add_artificial_variables();
 
        // Solve the phase 1 problem.
        while(pivot()) ;
@@ -421,6 +400,109 @@ bool Layout::LinearProgram::solve()
                return false;
        }
 
+       remove_artificial_variables();
+
+       // Solve the phase 2 problem.  We already know it to be feasible.
+       while(pivot()) ;
+
+       solved = true;
+
+       return true;
+}
+
+void Layout::LinearProgram::prepare_columns()
+{
+       /* See if any variables are already basic.  A basic variable must only have
+       a nonzero coefficient on one row, and its product with the constant column
+       must not be negative.  Only one variable can be basic for any given row. */
+       vector<float> basic_coeff(n_rows, 0.0f);
+       const vector<float> &constants = columns.back().values;
+       for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
+       {
+               if(i->values.size()>=2 && i->values.back()!=0.0f && (constants.size()<i->values.size() || i->values.back()*constants[i->values.size()-1]>=0.0f) && basic_coeff[i->values.size()-1]==0.0f)
+               {
+                       bool basic = true;
+                       for(unsigned j=1; (basic && j+1<i->values.size()); ++j)
+                               basic = (i->values[j]==0.0f);
+                       if(basic)
+                       {
+                               i->basic = i->values.size()-1;
+                               basic_coeff[i->basic] = -i->values.front()/i->values.back();
+                               i->values.clear();
+                       }
+               }
+       }
+
+       // Price out the newly-created basic variables.
+       for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
+               if(!i->values.empty())
+               {
+                       for(unsigned j=0; j<i->values.size(); ++j)
+                               i->values.front() += basic_coeff[j]*i->values[j];
+               }
+}
+
+void Layout::LinearProgram::add_artificial_variables()
+{
+       vector<unsigned> artificial_rows(n_rows-1);
+       for(unsigned i=0; i<artificial_rows.size(); ++i)
+               artificial_rows[i] = i+1;
+
+       for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
+               if(i->basic)
+                       artificial_rows[i->basic-1] = 0;
+       artificial_rows.erase(std::remove(artificial_rows.begin(), artificial_rows.end(), 0), artificial_rows.end());
+
+       /* Force all non-basic columns fully into existence and relocate objective
+       row to bottom in preparation of phase 1.  A new objective row is calculated
+       by pricing out the constraint rows. */
+       for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
+               if(!i->basic)
+               {
+                       float objective = 0.0f;
+                       if(!i->values.empty())
+                       {
+                               objective = i->values.front();
+                               i->values.front() = 0.0f;
+                               for(vector<unsigned>::iterator j=artificial_rows.begin(); j!=artificial_rows.end(); ++j)
+                                       if(*j<i->values.size())
+                                               i->values.front() += i->values[*j];
+                       }
+                       i->values.resize(n_rows+1, 0.0f);
+                       i->values.back() = objective;
+               }
+
+       if(artificial_rows.empty())
+               return;
+
+       /* Create artificial variables for phase 1.  This ensures that each row has
+       a basic variable associated with it.  The original objective row already
+       contains the implicit objective variable, which is basic. */
+       columns.resize(n_columns+artificial_rows.size());
+       columns.back() = columns[n_columns-1];
+       columns[n_columns-1].values.clear();
+       for(unsigned i=0; i<artificial_rows.size(); ++i)
+               columns[n_columns+i-1].basic = artificial_rows[i];
+}
+
+void Layout::LinearProgram::remove_artificial_variables()
+{
+       /* See if any artificial variables are still basic.  This could be because
+       the program is degenerate.  To avoid trouble later on, use pivots to make
+       some of the original variables basic instead.
+
+       I don't fully understand why this is needed, but it appears to work. */
+       for(unsigned i=n_columns-1; i+1<columns.size(); ++i)
+               if(columns[i].basic && columns.back().values[columns[i].basic]==0.0f)
+               {
+                       for(unsigned j=0; j+1<n_columns; ++j)
+                               if(!columns[j].basic && columns[j].values[columns[i].basic]!=0.0f)
+                               {
+                                       make_basic_column(j, columns[i].basic);
+                                       break;
+                               }
+               }
+
        /* Get rid of the artificial variables and restore the original objective
        row to form the phase 2 problem. */
        columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
@@ -430,13 +512,6 @@ bool Layout::LinearProgram::solve()
                        i->values.front() = i->values.back();
                        i->values.pop_back();
                }
-
-       // Solve the phase 2 problem.  We already know it to be feasible.
-       while(pivot()) ;
-
-       solved = true;
-
-       return true;
 }
 
 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)