2 linear-programming.cc -- implement
4 source file of the GNU LilyPond music typesetter
6 (c) 1997--1998 Han-Wen Nienhuys <hanwen@cs.uu.nl>
11 #include "linear-programming.hh"
13 Linear_programming::Linear_programming (int n)
19 Linear_programming::dim () const
26 Linear_programming::add_constraint (Vector c, double r)
28 assert (c.dim () == cost_vec_);
29 constraints_.push (c);
30 constraint_rhss_.push (r);
34 Linear_programming::set_cost (Vector c)
36 assert (dim_ == c.dim ());
41 Linear_programming::print () const
43 DOUT << "cost: " << cost_vec_;
44 for (int i=0; constraints_.size (); i++)
46 DOUT << constraints_[i] << ". x = " << constraint_rhss_[i];
51 Linear_programming::OK () const
53 assert (constraint_rhss_.size () == constraints_.size ());
54 for (int i=0; constraints_.size (); i++)
55 constraints_[i].dim () == cost_vec_.dim ();
60 Linear_programming::check_constraints (Vector v) const
63 assert (v.dim () == dim_);
65 for (int i=0; is_cool && i < v.dim (); i++)
66 is_cool = is_cool && v[i] >= 0;
67 for (int i=0; is_cool && i < constraints_.size (); i++)
68 is_cool = is_cool && (constraints_[i] * v <= constraint_rhss_[i]);
76 Linear_programming::solve (Vector initial_basic_solution) const
78 assert (check_constraints (initial_basic_solution));
81 for (int i=0; i < dim_; i++)
82 basis.push (bool(initial_basic_solution[i]));
84 Vector x = initial_basic_solution;
85 Real current_cost = x * cost_vec_;
86 while (iter < MAXITER)
98 Array<int> binding, nonbinding;
100 assert (check_constraints (initial));
104 Real value (x * cost_vec_):
106 for (int i=0; i < constraints_.size ())