+ 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. */