Return to dictionaries.ads CVS log

Up to [local] / OpenXM_contrib / PHC / Ada / Math_Lib / Supports

Annotation of OpenXM_contrib/PHC/Ada/Math_Lib/Supports/dictionaries.ads, Revision 1.1.1.1

1.1       maekawa     1: with Standard_Floating_Numbers;          use Standard_Floating_Numbers;
                      2: with Standard_Floating_Vectors;          use Standard_Floating_Vectors;
                      3: with Standard_Floating_Matrices;         use Standard_Floating_Matrices;
                      4: with Standard_Integer_Vectors;
                      5:
                      6: package Dictionaries is
                      7:
                      8: -- DESCRIPTION :
                      9: --   This package manages dictionaries, used to solve
                     10: --   the linear programming problem, in standard primal form
                     11: --
                     12: --      max <c,x>
                     13: --          <a,x> <= 0,   m linear inequalities
                     14: --
                     15: --   where x = (1,x1,x2,..,xn);
                     16: --
                     17: --   and for the dual formulation of the problem
                     18: --
                     19: --      min <c,x>
                     20: --          <a,x> >= 0,   m linear inequalities
                     21: --
                     22: --   where x = (1,x1,x2,..,xn).
                     23:
                     24: --   A dictionary is the linear system that corresponds to a feasible solution.
                     25: --   The right-hand side vector yields the primal solution, whereas the
                     26: --   vector of the objective function determines the dual solution.
                     27: --   A dictionary is reprented by a matrix of dimension (0..m,0..n) and
                     28: --   by two vectors which indicate the unknowns that are in/out the basis,
                     29: --   of respective dimensions (1..m) and (1..n).
                     30:
                     31: -- USAGE : be consequent when using primal and dual models.
                     32:
                     33: -- IMPORTANT ASSUMPTIONS :
                     34: --   The initializers do not check on the validity on the input tableau.
                     35: --   In particular:
                     36: --    * primal : all right-hand sides to be positive;
                     37: --    * dual   : all coefficients of the objective function must be positive.
                     38: --   Otherwise, the claims on unboundedness and infeasibility may be false.
                     39:
                     40: -- INITIALIZERS :
                     41:
                     42:   procedure Init_Basis
                     43:                 ( in_bas,out_bas : in out Standard_Integer_Vectors.Vector );
                     44:
                     45:   -- DESCRIPTION : Initializes the basis.
                     46:
                     47:   -- ON ENTRY :
                     48:   --   in_bas     unknowns in the basis, vector with range 1..m,
                     49:   --   out_bas    unknowns out the basis, vector with range 1..n.
                     50:
                     51:   function Init_Primal_Dictionary
                     52:                 ( c : Standard_Floating_Vectors.Vector; a : Matrix )
                     53:                 return Matrix;
                     54:
                     55:   function Init_Dual_Dictionary
                     56:                 ( c : Standard_Floating_Vectors.Vector; a : Matrix )
                     57:                 return Matrix;
                     58:
                     59:   -- DESCRIPTION : Initializes the matrix for the dictionary.
                     60:
                     61:   -- MATRIX DIMENSIONS : c(0..m), a(1..m,0..n).
                     62:
                     63:   -- ON ENTRY :
                     64:   --   c          coefficients of the target function;
                     65:   --   a          coefficients of the constraints, stored row-wise,
                     66:   --              with right-hand side at column zero.
                     67:
                     68:   -- ON RETURN :
                     69:   --   Matrix of dimension (0..m,0..n), with first row contains -c, the
                     70:   --   rest is filled with a, or with -a in the dual case.
                     71:
                     72:   procedure Primal_Init
                     73:                 ( c : in Standard_Floating_Vectors.Vector;
                     74:                   a : in Matrix; dic : out Matrix;
                     75:                   in_bas,out_bas : in out Standard_Integer_Vectors.Vector );
                     76:
                     77:   procedure Dual_Init
                     78:                 ( c : in Standard_Floating_Vectors.Vector;
                     79:                   a : in Matrix; dic : out Matrix;
                     80:                   in_bas,out_bas : in out Standard_Integer_Vectors.Vector );
                     81:
                     82:   -- DESCRIPTION :
                     83:   --   This procedure initializes the dictionary by consecutive application
                     84:   --   of the producedure Init_Basis and Init_Primal/Dual_Dictionary.
                     85:
                     86:   -- ON ENTRY :
                     87:   --   c          the coefficients of the target function: c(0..n);
                     88:   --   a          the coefficients of the constraints: a(1..m,0..n).
                     89:
                     90:   -- ON RETURN :
                     91:   --   dic        dictionary a matrix of ranges 0..m,0..n;
                     92:   --   in_bas     unknowns in the basis, vector with range 1..m;
                     93:   --   out_bas    unknowns out the basis, vector with range 1..n.
                     94:
                     95: -- MODIFIERS :
                     96:
                     97:   procedure Primal_Update
                     98:                 ( dic : in out Matrix;
                     99:                   in_bas,out_bas : in out Standard_Integer_Vectors.Vector;
                    100:                   eps : in double_float; unbounded : out boolean );
                    101:
                    102:   procedure Dual_Update
                    103:                 ( dic : in out Matrix;
                    104:                   in_bas,out_bas : in out Standard_Integer_Vectors.Vector;
                    105:                   eps : in double_float; feasible: out boolean );
                    106:
                    107:   -- DESCRIPTION :
                    108:   --   This procedure performs one step of the simplex algorithm.
                    109:
                    110:   -- ON ENTRY :
                    111:   --   dic        current matrix for the dictionary;
                    112:   --   in_bas     unknowns in the basis;
                    113:   --   out_bas    unknowns not in the basis;
                    114:   --   eps        used to determine wether a number is zero.
                    115:
                    116:   -- ON RETURN :
                    117:   --   dic        modified matrix for the dictionary;
                    118:   --   in_bas     updated list of basis unknowns;
                    119:   --   out_bas    updated list of non-basis unknowns;
                    120:   --   unbounded  true when the solution is unbounded, false otherwise;
                    121:   --   feasible   false when infeasibility is detected, true otherwise.
                    122:
                    123: -- SELECTORS :
                    124:
                    125:   function Primal_Optimal ( dic : Matrix; eps : double_float ) return boolean;
                    126:   function Dual_Optimal   ( dic : Matrix; eps : double_float ) return boolean;
                    127:
                    128:   -- DESCRIPTION :
                    129:   --   Returns true if the dictionary offers an optimal solution.
                    130:   --   The parameter eps is used determine whether a number equals zero or not.
                    131:
                    132:   function Optimum ( dic : Matrix ) return double_float;
                    133:
                    134:   -- DESCRIPTION :
                    135:   --   Returns the current value of the objective function.
                    136:
                    137:   function Primal_Solution
                    138:                   ( dic : Matrix;
                    139:                     in_bas,out_bas : Standard_Integer_Vectors.Vector )
                    140:                   return Standard_Floating_Vectors.Vector;
                    141:
                    142:   function Dual_Solution
                    143:                   ( dic : Matrix;
                    144:                     in_bas,out_bas : Standard_Integer_Vectors.Vector )
                    145:                   return Standard_Floating_Vectors.Vector;
                    146:
                    147:   -- DESCRIPTION :
                    148:   --   Returns the current values of the n unknowns in the primal or the
                    149:   --   dual formulation of the linear program.  If the program is dual,
                    150:   --   then the signs of the dual solution should be reversed.
                    151:
                    152: end Dictionaries;