hartmut_documentation

linux下的源码分类器SVM

   +--------+         +--------+      
   | ------------->   | -------------> 
   +--------+         +--------+      


typedef struct _constraint_name
{
  char                    name[NAMELEN];
  int                     row;
  struct _constraint_name *next;
} constraint_name;





 
typedef struct _tmp_store_struct
{
  nstring name;
  int     row;
  REAL    value;
  REAL    rhs_value;
  short   relat;
} tmp_store_struct;
 







/***************************************************************/
/**                                                           **/
/**                                                           **/
/**             Routines in file "solve.c"                    **/
/**                                                           **/
/**                                                           **/
/***************************************************************/





This file contains the routines which are important to use the 
SIMPLEX algorithm. For example you find routines to do basis
exchange, to select new pivot element etc. in this file.


set_globals()	Copy/initialize the global variables for a special LP.

ftran (int start,
       int end,
       REAL *pcol)         /* The column which will be used in ftran */
        /* multiply the column with all matrices in etafile */

	for every matrix between start and end
		calculate End of the matrix
		r = number of column in Eta matrix
		theta = pcol[r]
		for one matrix
			multiply pcol with the matrix (?)
		update pcol[r]
	round values in pcol

btran (REAL *row)
	For all Eta matrices, Starting with the highest number
		k = number of column in Eta-matrix
		for one matrix
			do multiplication
		round result
		set row[Eta_row_nr[k]] = result


Isvalid (lprec *lp)
		Calculate the structures row_end[] and 
		col_no[].
		internally two arrays are used:
		row_nr[], which contains the number of coefficients
		in row[i] and num[], which is a working array and
		contains the already used part of col_no in row[i].
		The array col_no is written at several positions
		at the same time. So it could look like

		+------------------------------------+
		|**         ****         *     **    |
		+------------------------------------+

		The second part of the routine uses two arrays
		rownum[] and colnum[]. It tests, if there are some
		empty columns in the matrix and prints a
		Warning message in this case.

		In detail:
		if (!lp->row_end_valid)
		   malloc space for arrays num and rownum.
		   initialise with zero
		   count in rownum[i] how many coefficients are in row i
		   set row_end (ATTENTION: documentation of row_end
                                seems to be wrong. row_end points to LAST
		      coefficient in row. But this is never used??)
		      col_no[0] is not used!!!
		   loop through all the columns,
		      forget row[0] = objective row
		      write column index in array col_no.
		   free num, rownum
		   row_end_valid = TRUE
		if (!lp->valid)    
		   Calloc rownum, colnum.
		   for all columns
		      colnum[i]++, for every coefficient in column.

		   if colnum[i] = 0, print warning.


resize_eta()		simple REALLOC




condensecol(int row_nr, REAL *pcol)
	if necessary:
		resize_eta()
	For all rows
		if i <> row_nr && pcol[i] <> 0
			Eta_row_nr = i
			Eta_value  = pcol[i]
			elnr++

	/* Last Action: write element for diagonal */
	Eta_row_nr = row_nr
	Eta_value = pcol[row_nr]

	update Eta_col_end


addetacol()
	Determine Begin and End of last Eta matrix.
	calculate theta = 1/ Eta_value[Diagonal element]
	multiply all coefficients in last matrix with -theta
	JustInverted = FALSE




setpivcol(short lower, int varin, REAL *pcol)
/* Main idea: take one column from original matrix and call ftran */

	/* init */
		...
		pcol[i] = 0  for all i

	If variable   /* This means not surplus/slack variable */
		copy column coefficients into pcol[]
		Actualise pcol[0] -= Extrad*f
	else          /* surplus/slack variable */
		/* This column is column from identity matrix */
		pcol[varin] = 1 or -1

	ftran(1, Etasize, pcol)



minoriteration(colnr, row_nr)
	set varin
	elnr = wk = Eta_col_end[Eta_size]  /* next free element */
	Eta_size++
	/* Eta_size = number of matrices in Eta file */
	/* Eta_col_end = End of one matrix           */

	Do something if Extrad <> 0          /* I do not know what to do 
	                                        and what is Extrad  */
	For all coefficients in column
		set row_nr
		If Objective_row and Extrad
			Eta_value[Eta_col_end[Eta_size -1]] += Mat[j].value
		else if k <> row_nr
			Eta_row_nr[elnr] = k
			Eta_value[elnr] = Mat[j].value
			elnr++
		else
			piv = Mat[j].value

	/* Last action: Write element on diagonal */
	insert row_nr and 1/piv
	
	theta = rhs[row_nr] / piv
	Rhs[row_nr] = theta

	For all coefficients of last eta matrix without diagonal element
		Rhs[Eta_row_nr[i]] -= theta*Eta_value[i]

	/* set administration data for Basis */
	varout =
	Bas[row_nr] = varin
	Basis[varout] = FALSE
	Basis[varin] = TRUE

	For all coefficients of last eta matrix without diagonal element
		Eta_value[i] /= -piv

	/* update Eta_col_end */
	Eta_col_end[Eta_size] = elnr



rhsmincol(REAL theta, int row_nr, int varin)
	Error test
	Find for last matrix in etafile the begin and end
	for all coefficients in last eta matrix without diagonal coefficient
		calculate rhs[eta_row_nr] -= theta * etavalue[i]
	rhs[row_nr] = theta

	varout = bas[row_nr]
	Bas[row_nr] = varin
	Basis[varout] = FALSE
	Basis[varin]  = TRUE



invert()
	allocate

	+---+---+---+---+---+---+
	| 0 |   |   |   |   |   | rownum
	+---+---+---+---+---+---+
	                         ^
	                         |
	                       Rows+1

	+---+---+---+---+---+---+
	|   |   |   |   |   |   | col
	+---+---+---+---+---+---+

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

	+---+---+---+---+---+---+
	|   |   |   |   |   |   | pcol               REAL pivot column??
	+---+---+---+---+---+---+

	+---+---+---+---+---+---+
	|TRU|   |   |   |   |   | frow               short
	+---+---+---+---+---+---+

	+---+---+---+---+---+---+---+---+
	|FAL|   |   |   |   |   |   |   | fcol       short
	+---+---+---+---+---+---+---+---+
	                                 ^
	                                 |
	                              columns+1

	+---+---+---+---+---+---+---+---+
	| 0 |   |   |   |   |   |   |   | colnum   /* count number of 
	+---+---+---+---+---+---+---+---+             Coefficients which 
	                                              appear in basis matrix */

	change frow and fcol depending on Bas[i]
		frow = FALSE if Bas[i] <= Rows
		fcol = TRUE  if Bas[i] >  Rows


	set
		Bas[i] = i   for all i
		Basis[i] = TRUE   for all slack variables
		           FALSE  for all other variables
		Rhs[i] = Rh[i]   for all i    /* initialise original Rhs */
 
	Correct Rhs for all Variables on upper bound
	Correct Rhs for all slack variables on upper bound (if necessary)

	Etasize =0
	v = 0
	row_nr = 0
	Num_inv = 0
	numit = 0

	Look for rows with only one Coefficient  (while)
		if found
		look for column of coefficient
		set     fcol[colnr - 1] = FALSE  /* This col is no longer
                                                    in Basis */
			colnum[colnr] = 0
		correct rownum counter
		set frow[row_num] = FALSE    /* This row is no longer
                                                in Basis */
		minoriteration(colnr, row_nr)

	Look for columns with only one Coefficient  (while)
		if found

		set frow[row_num] = FALSE    /* This row is no longer
                                                in Basis */
		rownum[] = 0
		update column[]
		numit++                /* counter how many iterations to do */
                                       /* at end                            */
		col[numit] = colnr     /* replaces minoriteration. But this */
                                       /* is done later and we need arrays  */
		row[numit] = row_nr    /* col and row therefore             */

	/* real invertation */
	for all columns   (From beginning to end )
		if fcol
			set fcol[] = FALSE
			setpivcol ( Lower[Rows + j] , Rows + j, pcol)
			Loop through all the rows to find coefficient with
				frow[row_nr] && pcol[row_nr]
			/* Interpretation:
			   Look for first coefficient in (partly inverted)
                           Basis matrix which is nonzero and use it for pivot.*/

			/* comparison for pcol is dangerous, but ok after
                           rounding */

			Error conditions

			/* Now we know pivot element */

			frow[row_nr] = FALSE
			condensecol (row_nr, pcol)
			rhsmincol (theta, row_nr, Rows + j)
			addetacol()

	For all stored actions   /* compare numit */
		set colnr / varin
		    row_nr
		init pcol with 0
		set pcol[]
		actualize pcol[0]
		condensecol(row_nr, pcol)
		rhsmincol(theta, row_nr, varin)
		addetacol()

	Round Rhs
	print info
	Justinverted = TRUE
	Doinvert = FALSE

	free()



colprim(int *colnr,
          short minit,
          REAL* drow)
	/* Each, colprimal - rowprimal and rowdual - coldual form a couple */
	btran( 1,0,0,0,0,0,...)
	update result depending on variables at upper bound

        look for variable with negative reduced costs

	========================
	More detailed:

	init *colnr = 0
	     dpiv = set to a small negative number.
	if  NOT minit
		drow = 1,0,0,0,0......
		btran(drow)
		For variables at upper bound we have to calculate the
		reduced cost differently:
		multiply each coefficient in column with reduced cost of row=  
		slackvariable and sum. This is new reduced cost.
		round reduced costs "drow"
	Look for variable which has upper bound Greater than Zero, which
	is nonbasic.
		Perhaps correct sign of reduced costs of variables
		at upper bound.
		take variable with most negative reduced costs.
		save reduced costs in dpiv and
		col_nr in *col_nr
	print trace info
	if *col_nr == 0
		set some variables, that indicate that we are optimal.
	return True, if *col_nr > 0



rowprim(int colnr,
	int * row_nr,
	REAL * theta,
	REAL * pcol)            /* contains current column from var conr */

	/* search for good candidate in a column for pivot */
	First look for big entries
	Second ( this means first failed ) look also for smaller entries
	Warning numerical instability

	Determine UNBOUNDED
	Perhaps shift variable to its upper bound

	Aim: determin valid pivot element

	print some info

	Return true, if we had been successful finding a pivot element.

	========================
	More detailed:

	init *row_nr = 0
	     *theta = infinity
	loop through all the rows
		qout = maximal steplength = *thetha
		*row_nr = number of that row.
		/* At first look only for Steps which are not calculated with
		   very small divisors. If no such steps found, take also
		   small divisors in consideration */
	Perhaps we found numerical problems. Print warning in this case

	If we did not find a limiting row, we are perhaps unbounded.
	(upperbound on that variable = infinity)
	The case that we have an upper bound is treated separately

	print some trace info

	return (*row_nr > 0)



rowdual(int *row_nr) 
	look for infeasibilities

	init *row_nr = 0
             minrhs = a little bit negative

	loop through all the rows
		if we find a variable which is not zero, but has to be
		then we break this loop. *row_nr = i

		calculate distance between rhs[i] and upperbound[i]
		take smaller one

		|-------|----------------|
                0      rhs[i]          upperbound[i]
                       =g


		minrhs is smallest g
                *row_nr is corresponding rownumber.

	print some trace info
	return (*row_nr > 0)