+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> obj_coeff(n_rows, 0.0f);
+ vector<float> row_coeff(n_rows, 1.0f);
+ const vector<float> &constants = columns.back().values;
+ for(Column &c: columns)
+ if(c.values.size()>=2 && c.values.back()!=0.0f && (constants.size()<c.values.size() || c.values.back()*constants[c.values.size()-1]>=0.0f) && obj_coeff[c.values.size()-1]==0.0f)
+ {
+ bool basic = true;
+ for(size_t j=1; (basic && j+1<c.values.size()); ++j)
+ basic = (c.values[j]==0.0f);
+ if(basic)
+ {
+ c.basic = c.values.size()-1;
+ row_coeff[c.basic] = 1.0f/c.values.back();
+ obj_coeff[c.basic] = -c.values.front();
+ c.values.clear();
+ }
+ }
+
+ // Price out the newly-created basic variables.
+ for(Column &c: columns)
+ if(!c.values.empty())
+ {
+ for(size_t j=0; j<c.values.size(); ++j)
+ {
+ c.values[j] *= row_coeff[j];
+ c.values.front() += obj_coeff[j]*c.values[j];
+ }
+ }
+}
+
+void Layout::LinearProgram::add_artificial_variables()
+{
+ vector<size_t> artificial_rows(n_rows-1);
+ for(size_t i=0; i<artificial_rows.size(); ++i)
+ artificial_rows[i] = i+1;
+
+ for(const Column &c: columns)
+ if(c.basic)
+ artificial_rows[c.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(Column &c: columns)
+ if(!c.basic)
+ {
+ float objective = 0.0f;
+ if(!c.values.empty())
+ {
+ objective = c.values.front();
+ c.values.front() = 0.0f;
+ for(size_t r: artificial_rows)
+ if(r<c.values.size())
+ c.values.front() += c.values[r];
+ }
+ c.values.resize(n_rows+1, 0.0f);
+ c.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(size_t 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(size_t i=n_columns-1; i+1<columns.size(); ++i)
+ if(columns[i].basic && columns.back().values[columns[i].basic]==0.0f)
+ {
+ for(size_t 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);
+ for(Column &c: columns)
+ if(!c.basic)
+ {
+ c.values.front() = c.values.back();
+ c.values.pop_back();
+ }
+}
+
+size_t Layout::LinearProgram::find_minimal_ratio(size_t c)