hartmut_documentation

linux下的源码分类器SVM

coldual(int row_nr,
	int *colnr,
	short minit,
	REAL *prow,
	REAL *drow)
	looks also for a candidate for pivot.




iteration (int row_nr,
           int varin,
           REAL *theta,
           REAL up,
           short *minit,
           short *low,
           short primal,
           REAL *pcol)

		execute one iteration




solvelp()
                First check if right hand side is positive everywhere
                and smaller than possible upper bound of this row.
                In this case we start with a feasible basis.



		ATTENTION:
		If we want to use solvelp() directly, skipping
		solve() and milpsolve() we have to be very careful.
		e.g. solve() sets the global variables!!!

is_int(REAL value)
		simple routine, checks, if a REAL value is integer.

construct_solution(REAL *sol)
                The routine does exactly, what its name says.
                There are two parts, with and without scaling.


                First set all variables to their lower bounds.
                Then set all basis variables to their true values, i.e.
                the right hand side is added to the lower bound.
                (The reason is that all variables have been transformed
                to have lower bound zero) ## Autor fragen!!
                Finally set the non basic variables, which are not at 
                their lower bound to their upper bound.
                Calculate values of the slack variables of a row.



calculate_duals()
                In fact calculate the reduced costs of the slack variables
                and correct values.



milpsolve(REAL   *upbo,
          REAL   *lowbo,
          short  *sbasis,
          short  *slower,
          int    *sbas)
			First of all: copy the arrays upbo and lowbo
			to the pointers of Upbo and Lowbo. (Memory
			is allocated for these arrays. Pointers point
			to lp->upbo and lp->lowbo)
			(size of memory is updated, if new columns are 
			added.)
			These arrays came from solve() as ORIGINAL
			bounds. Therefore no shifting of transformed bounds 
			necessary in lpkit.c if solve() is called.

			if (LP->anti_degen)
			   disturb lower and upper bound a little bit.
			if (!LP->eta_valid)
			   shift lower bounds to zero. This means:
			   Orig_lowbo   ... unchanged
			   Orig_upbo    ... unchanged
			   lowbo        ... unchanged (implicit in code = 0)
			   upbo         ... mainly upbo_old - lowbo.

			solvelp()

			if (LP->anti_degen)
			   restore upbo, lowbo, Orig_rh and solve again.

			if (OPTIMAL solution of LP)
			   check, if we can cutoff branch with LP value.
			   look for noninteger variable (look for first 
			   or look random)
			   if (noninteger variables)
			      setup two new problems.
			      Malloc new memory
			      memcpy the data
			      solve problems recursively (Floor_first/ceiling_irst)
			      set return values
			   else
			      /* all required values are int */
			      check, if better solution found.
			      /* Yes */
			      memcpy data
			      perhaps break B+B


			Recursive Function. Pure depth first search. 
                        No easily accessible nodelist, because of depth
                        first search. (Also less active nodes)
			Branching on first noninteger variablen or
                        on a randomly selected variable.
			Avoid inverting if possible.



solve(lprec *lp)
			init BEST-Solution, init perhaps basis, call milpsolve



lag_solve(lprec *lp, REAL start_bound, int num_iter, short verbose)
		Lagrangean solver.






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


static void print_indent(void)
void debug_print_solution()
void debug_print_bounds(REAL *upbo, REAL *lowbo)
void debug_print(char *format, ...)


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

static void print_indent(void)
   Used for printing the branch and bound tree. For every node the depth
   in the tree is shown with some ASCII graphic.

void debug_print_solution()
   For all columns
      print_indent()
      print the variable name (true or artificial) and its value.

void debug_print_bounds(REAL *upbo, REAL *lowbo)
   For all columns
      Print the lower bounds if they are different from zero with true or
      artificial name.
      Print the upper bounds if they are different from infinity with true or
      artificial name.

void debug_print(char *format, ...)




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


void print_help(char *argv[])
   Print usage message. If the program is called with option "-h" the usage
   message is printed. The usage message gives the options which can be
   given when calling the program.

int main(int argc, char *argv[])
   Initialise some data. Read all the options and make use of them.
   (Options have to be given separately, non existing options are just ignored.)

   Read MPS file or lp_file from stdin.

   Perhaps print out some information about LP and do some manipulations on
   LP (i.e. scaling).

   call solve(lp)

   Check return status:
   If (OPTIMAL)
      Print out solution and some statistics.
   else print solution status.




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

The main purpose of this file is to give several "manipulation" routines to
the user. The user should be able to read information from the current
problem. But he/she should also be able to change information in the
problem. So for example, it is possible to add new constraints to the
problem, to change the bounds of the variables etc.



void error(char *format, ...)
lprec *make_lp(int rows, int columns)
void delete_lp(lprec *lp)
lprec *copy_lp(lprec *lp)
void inc_mat_space(lprec *lp, int maxextra)
void inc_row_space(lprec *lp)
void inc_col_space(lprec *lp)
void set_mat(lprec *lp, int Row, int Column, REAL Value)
void set_obj_fn(lprec *lp, REAL *row)
void str_set_obj_fn(lprec *lp, char *row)
void add_constraint(lprec *lp, REAL *row, short constr_type, REAL rh)
void str_add_constraint(lprec *lp,
                        char *row_string,
                        short constr_type,
                        REAL rh)
void del_constraint(lprec *lp, int del_row)
void add_lag_con(lprec *lp, REAL *row, short con_type, REAL rhs)
void str_add_lag_con(lprec *lp, char *row, short con_type, REAL rhs)
void add_column(lprec *lp, REAL *column)
void str_add_column(lprec *lp, char *col_string)
void del_column(lprec *lp, int column)
void set_upbo(lprec *lp, int column, REAL value)
void set_lowbo(lprec *lp, int column, REAL value)
void set_int(lprec *lp, int column, short must_be_int)
void set_rh(lprec *lp, int row, REAL value)
void set_rh_vec(lprec *lp, REAL *rh)
void str_set_rh_vec(lprec *lp, char *rh_string)
void set_maxim(lprec *lp)
void set_minim(lprec *lp)
void set_constr_type(lprec *lp, int row, short con_type)
REAL mat_elm(lprec *lp, int row, int column)
void get_row(lprec *lp, int row_nr, REAL *row)
void get_column(lprec *lp, int col_nr, REAL *column)
void get_reduced_costs(lprec *lp, REAL *rc)
short is_feasible(lprec *lp, REAL *values)
short column_in_lp(lprec *lp, REAL *testcolumn)
void print_lp(lprec *lp)
void set_row_name(lprec *lp, int row, nstring new_name)
void set_col_name(lprec *lp, int column, nstring new_name)
static REAL minmax_to_scale(REAL min, REAL max)
void unscale_columns(lprec *lp)
void unscale(lprec *lp)
void auto_scale(lprec *lp)
void reset_basis(lprec *lp)
void print_solution(lprec *lp)
void write_LP(lprec *lp, FILE *output)
void write_MPS(lprec *lp, FILE *output)
void print_duals(lprec *lp)
void print_scales(lprec *lp)


What is done in the routines:
=============================

void error(char *format, ...)
lprec *make_lp(int rows, int columns)

   Construct a new LP. Set all variables to some default values.
   The LP has "rows" rows and "columns" columns. The matrix contains
   no values, but space for one value. All arrays which depend on
   "rows" and "columns" are malloced.

   The problem contains only continuous variables.
   Upper bounds are infinity, lower bounds are zero.
   The basis is true, all rows are in basis. All columns are nonbasic.
   The eta-file is valid. Solution, best_solution and duals are Zero.
   And some other default values.



void delete_lp(lprec *lp)

    Delete ALL the malloced arrays. At last free the structure.


lprec *copy_lp(lprec *lp)

   Copy first the structure of the lp, this means especially, that all
   the constant values are copied.
   Copy all the arrays of the lp and set the pointers to the new arrays.
   Mainly use MALLOCCOPY for this, this means: malloc space and copy data.


void inc_mat_space(lprec *lp, int maxextra)

   Test if realloc necessary. If yes, realloc arrays "mat" and "col_no".
   If Lp is active, set some global variables which could be changed by
   realloc.


void inc_row_space(lprec *lp)

   Test, if increment necessary.
   This routine increments the space for rows with 10 additional rows.
   Therefore one condition for correct work of this routine is that 
   it is never necessary to increase the
   number of additionally rows in one step with more than 10!
   Several arrays are realloced. 
   At last, if LP is active, set some global variables new, because they could
   have changed.
   

void inc_col_space(lprec *lp)

   similar to routine increment row space. The problems are also the same.
   Several Arrays are realloced, but no shift of values.




void set_mat(lprec *lp, int Row, int Column, REAL Value)

   set one element in matrix.
   Test, if row and column are in range. Scale value.
   If colnum is in basis and row not objective row set Basis_valid = FALSE
   Always set eta_valid = FALSE (is this necessary?)

   Search in column for entry with correct rownumber.
   If row found scale value again but with other expression than first time.
   Perhaps change sign
   
   If row not found:
    Increment mat_space for one additional element.
    Shift matrix and update col_end.
    Set new element "row" and scale value perhaps (same problem as above)
    Rowend is not valid any longer
    update number of nonzeros and copy this value if lp is active



void set_obj_fn(lprec *lp, REAL *row)

   call in one loop for dense row the function set_mat().
   No test is done, if we want to include Elements with value "0".
   These values are included into the matrix!



void str_set_obj_fn(lprec *lp, char *row)

   reserve space for one row
   try with "strtod()" to change all the strings to real values
   call set_obj_fn()
   free space



void add_constraint(lprec *lp, REAL *row, short constr_type, REAL rh)

   first reserve space for integers for length of one row.
   Mark all the positions, which contain nonzeros and update non_zeros
   malloc space for a complete new matrix
   increment matrix space by null??
   rows++
   sum++
   increment row space
   if scaling
      shift the values 
      and set scaling value for new row to 1
   if names used
      invent new name for row
   if columns are scaled
      scale coefficients
   calculate change_sign
   copy every column from old matrix to new matrix. Perhaps add new entry for
   new row.
   Update col_end
   copy new matrix back to old matrix.
   free the allocated arrays
   
   shift orig_upper_bounds
         orig_lower_bounds
         basis
         lower
         must_be_int

   update Basis info
   set bounds for slack variables

   change_sign for rhs, but comparison is made with sense of constraint. 
   
   rows_end_valid = false
   put slackvariable for this row into basis
   if lp == active, set globals
   eta_file = non_valid.
 


void str_add_constraint(lprec *lp,
                        char *row_string,
                        short constr_type,
                        REAL rh)

   This routine is similar to the routine str_set_obj_fn. The same idea,
   but call add_constraint.




void del_constraint(lprec *lp, int del_row)

   First check, if rownumber exists.
   For all columns
      For every coefficient in column
         if it is not rownumber,
         then shift elements to smaller nonzero index and perhaps correct row index.
         else  delete
         update col_end
   shift values for orig_rhs, ch_sign, bas, row_name down by one.
   Update values in bas
   shift values for lower, basis, orig_upbo, orig_lowbo, must_be_int, scaling down
      by one.
   update rows and sum
   set row_end_valid = FALSE
   if lp = active, set globals.
   eta_valid = FALSE
   basis_valid = FALSE



void add_lag_con(lprec *lp, REAL *row, short con_type, REAL rhs)

   Calloc/Realloc space for lag_row, lag_rhs, lambda, lag_con_type
   Fill arrays.

void str_add_lag_con(lprec *lp, char *row, short con_type, REAL rhs)