hartmut_documentation

linux下的源码分类器SVM

     |                             |    | |      | |      | |   |
     +-----------------------------+    +-+      +-+      +-+  /
                                       orig_rh    rh      rhs
                                     scaled +    =orig_rh current rhs
                                     signchange  + Bound  dh. Basis values(?)
                                                 transform


sum_alloc = rows_alloc + columns_alloc;
Be careful: There is a difference between "rows" and "rows_alloc". We
allocate "rows_alloc" elements, but use only "rows" elements. This means,
the space between "rows" and "rows_alloc" is empty/not used.

The same is true for "columns" and "columns_alloc".
The pair for matrix is called "non_zeros" and "mat_alloc".



 rows
    |
  rows_alloc+1                 sum_alloc+1. Index [0] seems to be unused.
    | |                             | 
slack v                             v
+----+-----------------------------+
|    |          must_be_int        |
+----+-----------------------------+

slack
+----+-----------------------------+
|    |          orig_upbo          | before Bound transform
+----+-----------------------------+

slack
+----+-----------------------------+
|    |          orig_lowbo         | before Bound transform
+----+-----------------------------+

slack
+----+-----------------------------+
|    |               upbo          | after Bound transform and in B+B
+----+-----------------------------+

slack
+----+-----------------------------+
|    |              lowbo          | after Bound transform and in B+B
+----+-----------------------------+


slack
+----+-----------------------------+
|    |          Basis              |  TRUE, if column is in Basis.
+----+-----------------------------+  FALSE otherwise.

slack
+----+-----------------------------+
|    |          lower              |  TRUE, if column is in Basis or
+----+-----------------------------+  nonbasic and at lower bound.
 ^                                    FALSE otherwise.
 |
 0


     +-+
     | |
     +-+
     | |
     | |   indices of columns which are in Basis.
     | |
     | |
     +-+
     bas


The matrix is stored in sparse form in the usual way.


  int       non_zeros;          /* The number of elements in the sparse matrix*/
  int       mat_alloc;		/* The allocated size for matrix sized 
				   structures */
  matrec    *mat;               /* mat_alloc :The sparse matrix */
  int       *col_end;           /* columns_alloc+1 :Cend[i] is the index of the
		 		   first element after column i.
				   column[i] is stored in elements 
				   col_end[i-1] to col_end[i]-1 */
  int       *col_no;            /* mat_alloc :From Row 1 on, col_no contains the
				   column nr. of the
                                   nonzero elements, row by row */
  short     row_end_valid;	/* true if row_end & col_no are valid */
  int       *row_end;           /* rows_alloc+1 :row_end[i] is the index of the 
				   first element in Colno after row i */

  +-----+-----+-----+-----+-----+-----+-----+
  |  1  |  3  |  7  |  1  | *** | *** | *** |        (row_nr)
  +-----+-----+-----+-----+-----+-----+-----+   mat
  | 2.5 | 4.7 | 1.0 | 2.0 | *** | *** | *** |        (value)
  +-----+-----+-----+-----+-----+-----+-----+
                             ^               ^
                             |               |
                          non_zeros         mat_alloc

Entry Zero is valid.




  +-----+-----+-----+-----+
  | *** |  3  |  4  |     |    col_end  (in fact beginning of next column)
  +-----+-----+-----+-----+
                 ^         ^
                 |         |
             columns   columns_alloc+1

Entry Zero is NOT valid.(?)



  +-----+-----+-----+-----+-----+-----+-----+
  |  1  |  2  |  5  |  1  | *** | *** | *** |  col_no: Which columns appear in
  +-----+-----+-----+-----+-----+-----+-----+          row[i]. Row[i] starts at
                             ^               ^         row_end[i-1] and ends at
                             |               |         row_end[i] - 1.
                          non_zeros         mat_alloc

ATTENTION: Documentation in header file seems to be wrong!!!
col_no[0] is not used! row[i] starts in row_end[i-1]+1 and ends in row_end[i].
In array there are used (non_zero - number of coefficients in objective row +1)
elements used.

Col_no is used in invert. (And nowhere else, but set in Isvalid)

     +-+
     | |
     +-+
     | |
     | |  How many coefficients are in rows 1 to i. Equivalent:
     | |  row_end[i] is the index of the first element in col_no after row i.
     | |
     +-+
     row_end



How is sense of the constraints/rows coded?

Look at slack variable of the row. If the orig_upbo[i] < infinite (this
should be: orig_upbo[i] == 0) then we have an equality row.  This comparison
can be found in write_MPS(), where all Rows with upper bound == infinity are
"L" or "G" rows. All other rows are "E" rows. See also write_LP().

In the other cases, that means orig_upbo[[i] == infinite, we have to look
at ch_sign[i]. If ch_sign[i] == TRUE, we have a greater equal row, if
ch_sign == FALSE, we have a less equal row.

=================================


  short     eta_valid;          /* TRUE if current Eta structures are valid */
  int       eta_alloc;          /* The allocated memory for Eta */
  int       eta_size;           /* The number of Eta columns */
  int       num_inv;            /* The number of real pivots */
  int       max_num_inv;        /* ## The number of real pivots between 
				   reinvertions */ 
  REAL      *eta_value;         /* eta_alloc :The Structure containing the
				   values of Eta */
  int       *eta_row_nr;         /*  "     "  :The Structure containing the Row
				   indexes of Eta */
  int       *eta_col_end;       /* rows_alloc + MaxNumInv : eta_col_end[i] is
				   the start index of the next Eta column */

     +-------+----------------------------+
     |       |    eta_col_end             |   Startindex of next Eta column
     +-------+----------------------------+
     rows_alloc     max_num_inv       ^
  this is needed    we can have      eta_size
  for first         maximal so many
  invert            inverts, i.e. etamatrices.
                    until next inversion.


     +---+---+---+---+---+---+---+---+---+---+---+---+---+
     |   |   |   |   |   |   |   |   |   |   |   |   |   | eta_value
     +---+---+---+---+---+---+---+---+---+---+---+---+---+

     +---+---+---+---+---+---+---+---+---+---+---+---+---+
     |   |   |   |   |   |   |   |   |   |   |   |   |   | eta_row_nr
     +---+---+---+---+---+---+---+---+---+---+---+---+---+
                                                          ^
                                                          |
                                                      eta_alloc


Normal way of sparse matrix representation. But how to built one Eta
Matrix? I do not know, in which column to put eta-column.

Guess:
This is one eta_matrix. Last entry contains index of the column and value
on the diagonal.
     +---+---+---+---+---+
     |1.3|.5 |.8 |.7 |2.5|   eta_value
     +---+---+---+---+---+

     +---+---+---+---+---+
     | 1 | 3 | 7 | 8 | 6 |   eta_row_nr
     +---+---+---+---+---+


The matrix in dense form would be:

    +---+---+---+---+---+---+---+---+
    | 1 |   |   |   |   |1.3|   |   |
    +---+---+---+---+---+---+---+---+
    |   | 1 |   |   |   |   |   |   |
    +---+---+---+---+---+---+---+---+
    |   |   | 1 |   |   |.5 |   |   |
    +---+---+---+---+---+---+---+---+
    |   |   |   | 1 |   |   |   |   |
    +---+---+---+---+---+---+---+---+
    |   |   |   |   | 1 |   |   |   |
    +---+---+---+---+---+---+---+---+
    |   |   |   |   |   |2.5|   |   |
    +---+---+---+---+---+---+---+---+
    |   |   |   |   |   |.8 | 1 |   |
    +---+---+---+---+---+---+---+---+
    |   |   |   |   |   |.7 |   | 1 |
    +---+---+---+---+---+---+---+---+
                          ^
                          |
                     column 6






  short	    bb_rule;		/* what rule for selecting B&B variables */

  short     break_at_int;       /* TRUE if stop at first integer better than
                                   break_value */
  REAL      break_value;        

  REAL      obj_bound;          /* ## Objective function bound for speedup of 
				   B&B */
  int       iter;               /* The number of iterations in the simplex
				   solver (LP) */
  int       total_iter;         /* The total number of iterations (B&B) (ILP)*/ 
  int       max_level;          /* The Deepest B&B level of the last solution */
  int	    total_nodes;	/* total number of nodes processed in b&b */








  REAL      *solution;          /* sum_alloc+1 :The Solution of the last LP, 
				   0 = The Optimal Value, 
                                   1..rows The Slacks, 
				   rows+1..sum The Variables */
  REAL      *best_solution;     /*  "       "  :The Best 'Integer' Solution */
  REAL      *duals;             /* rows_alloc+1 :The dual variables of the
				   last LP */


                              sum_alloc+1. Index [0] is optimal solution value. 
                                    | 
slack                               v
+----+-----------------------------+
|    |          solution           |
+----+-----------------------------+
 ^  ^                             ^
 |  |                             |
 |  rows                         sum=rows+columns
Optimal
value
= Index 0


slack 
+----+-----------------------------+
|    |          best_solution      | Best integer solution so far.
+----+-----------------------------+

     +-+
     | |
     +-+
     | |
     | |  dual variables
     | |
     | |
     +-+
     duals






  
  short     maximise;           /* TRUE if the goal is to maximise the 
				   objective function */
  short     floor_first;        /* TRUE if B&B does floor bound first */
  short     *ch_sign;           /* rows_alloc+1 :TRUE if the Row in the matrix
				   has changed sign 
                                   (a`x > b, x>=0) is translated to 
				   s + -a`x = -b with x>=0, s>=0) */ 




     +-+
     | |
     +-+
     | |
     | | TRUE or FALSE
     | |
     | |
     +-+
     ch_sign    (compare sense of a row described above)

  short     scaling_used;	/* TRUE if scaling is used */
  short     columns_scaled;     /* TRUE is the columns are scaled too, Only use
		 		   if all variables are non-integer */
  REAL      *scale;             /* sum_alloc+1 :0..Rows the scaling of the Rows,
				   Rows+1..Sum the scaling of the columns */



                                sum_alloc+1
                                    |
rows            columns             v
+----+-----------------------------+
|    |                             | scale: Scaling factors for rows and columns
+----+-----------------------------+
 ^  ^                             ^
 |  |                             |
 0 rows                         sum=rows+columns





  int	    nr_lagrange;	/* Nr. of Langrangian relaxation constraints */
  REAL	    **lag_row;		/* NumLagrange, columns+1:Pointer to pointer of 
				   rows */
  REAL      *lag_rhs;		/* NumLagrange :Pointer to pointer of Rhs */
  REAL      *lambda;		/* NumLagrange :Lambda Values */
  short     *lag_con_type;      /* NumLagrange :TRUE if constraint type EQ */
  REAL      lag_bound;		/* the lagrangian lower bound */

  short     valid;		/* Has this lp passed the 'test' */
  REAL      infinite;           /* ## numerical stuff */
  REAL      epsilon;            /* ## */
  REAL      epsb;               /* ## */
  REAL      epsd;               /* ## */
  REAL      epsel;              /* ## */
} lprec;









The HASH structure:
===================

 Hash_tab
   +---+
   |   |       hashelem
   +---+      +---------+
   | -------->| colname |
   +---+      +---------+
   |   |      | -------------------------------------------> next
   +---+      +---------+                          column
   |   |      | -------------------------------> +---------+
   +---+      +---------+      bound             |  row    |
   |   |      | ------------>+------------+      +---------+
   +---+      +---------+    |  upbound   |      |  value  |
   |   |      |must_be_i|    +------------+      +---------+
   +---+      +---------+    |  lobound   |      |  -------------> next
   |   |                     +------------+      +---------+
   +---+
   |   |
   +---+





typedef struct _hashelem
{
  nstring          colname;
  struct _hashelem *next;
  struct _column   *col;
  struct _bound    *bnd;
  int              must_be_int;
} hashelem;


typedef struct _column
{
  int            row;
  float          value;
  struct _column *next ;
} column;

typedef struct _bound
{
  REAL          upbo;
  REAL          lowbo;
} bound;
 




   First_rside

   +--------+         +--------+      
   | value  |         | value  |      
   +--------+         +--------+      
   | ------------->   | -------------> 
   +--------+         +--------+      
   | relat  |         | relat  |      
   +--------+         +--------+      

typedef struct _rside /* contains relational operator and rhs value */
{
  REAL          value;
  struct _rside *next;
  short         relat;
} rside;



 

   First_constraint_name

   +--------+         +--------+      
   | name   |         | name   |      
   +--------+         +--------+      
   | row    |         | row    |