lily/include/qlpsolve.hh

   1 /*
   2   qlpsolve.hh -- declare  Active_constraints, Inactive_iter
   3
   4   source file of the GNU LilyPond music typesetter
   5
   6   (c)  1997--1999 Han-Wen Nienhuys <hanwen@cs.uu.nl>
   7 */
   8
   9
  10 #ifndef QLPSOLVE_HH
  11 #define QLPSOLVE_HH
  12
  13 #include "matrix.hh"
  14
  15
  16 /**
  17     This class represents the set of active (binding) constraints
  18     which can be active while the QLP algorithm is in a feasible
  19     point. The active constraints are numbered.
  20     If the constraints are of the form
  21
  22       A^T*x >= b
  23
  24     then the binding constraints are those where the >= is equality.
  25
  26   */
  27
  28 class Active_constraints {
  29   friend class Inactive_iter;
  30
  31
  32   Matrix A,H;
  33   Array<int> active;
  34   Array<int> inactive;          // actually this is a set, not an array.
  35   Ineq_constrained_qp const *opt;
  36
  37 public:
  38
  39   /** This counts the number of errors the algorithms makes.  The
  40       optimum search should be abandoned if it becomes too high.  */
  41   int degenerate_count_i_;
  42   String status() const;
  43
  44   Vector vec (int k) const { return opt->cons_[k]; }
  45   Real rhs (int k) const { return opt->consrhs_[k]; }
  46
  47
  48   /** drop constraint. drop constraint k from the active set. k is the index of the
  49     constraint in #active#
  50
  51     */
  52   void drop_constraint (int k);
  53
  54
  55   /** add constraint j.
  56     add constraint j to the active set j is the index of the
  57     constraint in #inactive#
  58     */
  59   void add_constraint (int j);
  60
  61   /// exchange in and out.
  62   void exchange (int in, int out) { add_constraint (in); drop_constraint (out); }
  63
  64
  65   Vector find_active_optimum (Vector g);
  66
  67   /// get lagrange multipliers.
  68   Vector get_lagrange (Vector v);
  69
  70   Active_constraints (Ineq_constrained_qp const *op);
  71   /** construct: no constraints active, n vars. Put the equalities
  72     into the constraints.  */
  73
  74   /// check invariants
  75   void OK();
  76 };
  77
  78
  79 /**
  80     loop through the inactive constraints.
  81   */
  82 class Inactive_iter {
  83   int j;
  84   Active_constraints const* ac;
  85 public:
  86   Inactive_iter (Active_constraints const &c) { ac=&c; j=0; }
  87   int idx() const { return j; }
  88   void operator ++(int) { j++; }
  89   int constraint_id() const { return ac->inactive[j]; }
  90   Vector vec() const { return ac->vec (constraint_id ()); }
  91   Real rhs() const { return ac->rhs (constraint_id ()); }
  92   bool ok() const { return j < ac->inactive.size (); }
  93 };
  94
  95 #endif // QLPSOLVE_HH