hartmut_documentation

利用c语言编写

/*************************************************************************/
/**                                                                     **/
/**    Documentation for lp_solve                                       **/
/**                                                                     **/
/**    (C) Hartmut Schwab       [e-mail]    **/
/**                                                                     **/
/**                                                                     **/
/*************************************************************************/




This documentation is Copyright 1996 by Hartmut Schwab. It may be freely
redistributed in its entirety provided that this copyright notice and the
disclaimer is not removed. It may not be sold for profit or incorporated in
commercial documents without the written permission of the copyright holder.
Permission is expressly granted for this document to be made available for
file transfer from installations offering unrestricted anonymous file
transfer on the Internet. Its intent is to promote widespread usage.

     Notice  must  be  given  of  the  location  of  the
     availability of the  unmodified  current  source  code
     of lp_solve
     e.g.,
             ftp://ftp.es.ele.tue.nl/pub/lp_solve



While all information in this documentation is believed to be correct at the
time of writing, it is provided "as is" with no warranty implied.



In compiling this information, I have drawn on my own knowledge of the
field. This file has been read by Michel Berkelaar, the author of lp_solve but
nevertheless the errors in this document came into it by me. I give my
thanks to all those who have offered advice and support. 

Suggestions, corrections, topics you'd like to see covered, and additional
material, are all solicited. Send email to 

            [e-mail]



The newest version of this document is available at the same location than
lp_solve.  



Version: @(#) lp_solve.doc 1.18@(#), Creation date: 97/02/11.







/***************************************************************/
/**                                                           **/
/**                                                           **/
/**             Preface                                       **/
/**                                                           **/
/**                                                           **/
/***************************************************************/

This documentation would not exist, if Michel Berkelaar had not written the
program lp_solve. Thanks to him, we have a version of the simplex algorithm,
where the source code is available, which uses sparse matrix computations
and which everybody can include into his or her own applications. More and
more users in the Operations Research community are using lp_solve.

His program is finding more and more users in the OR community. The growing
interest is easily proven by the still growing number of questions regarding
lp_solve in the News. Questions where to find a source code for the simplex
algorithm are usually answered with a hint to lp_solve.

It is also important to mention Jeroen Dirks who added a subroutine library
to lp_solve. His work makes it easier to include lp_solve in own
applications.

Until now, no documentation about the construction of the program had been
available. This file wants to close this gap. It wants to provide the reader
with some information about the internal structure of the program and add
some documentation to lp_solve.


How is this document organised?

You will find a table of contents in the next section. Section
"Introduction" describes the intention of this document. You also will find
some information, what has been included into this document and what has
been excluded from it. The later one is the more important one. This document
does not contain every information and it doesn't want to contain every
information.

A very important section is "Datastructures used internally by lp_solve".
You can guess, what you will find there. If you want to do some extensions,
if you detect some errors you probably have to look there to understand the
way lp_solve organises all the information internally.

The following sections contain a short description of the functions, but
only the MAIN IDEAS are written down. These sections are organised in the
same way as the source files. Each source file has its own section.

For easier understanding the structure of the program, I also included the
"Function calling tree". It gives an idea how the different functions work
together.

If you want to get more information, which is not covered in this document,
probably the hints you find in the References will be a good starting point.




This file has been prepared carefully. Nevertheless it probably will contain
errors. The author is in no way responsible for any damage caused by using
this file.



This document describes version 2.0 of lp_solve. However now major changes
are expected to occur in the next time. Therefore this document should be
valid also for newer versions of lp_solve.
 



/***************************************************************/
/**                                                           **/
/**                                                           **/
/**             Contents                                      **/
/**                                                           **/
/**                                                           **/
/***************************************************************/


Contents:
=========

- Copyright and distribution

- Preface

- Contents

- Introduction

- Datastructures used internally by lp_solve

- Short description of the functions, the MAIN IDEAS are written down.

- Function calling tree

- References




/***************************************************************/
/**                                                           **/
/**                                                           **/
/**             Introduction                                  **/
/**                                                           **/
/**                                                           **/
/***************************************************************/


Purpose:
========

   This documentation should help the readers to get a better 
   understanding of the source code of lp_solve and its main ideas,
   to be able to make changes in the code and to locate errors in the code,
   if there appear any.
   It should also give the chance to make improvements to the code
   i.e. other product form or different Branch and Bound strategy.



This documentation does NOT describe the simplex algorithm. You can find a
description of the simplex algorithm in every book about linear programming.
If you are interested to find a description which is more adapted to the
sparse form of the simplex, check the literature given in the references.

Some keywords, which describe the implementation of lp_solve:

- selecting pivot variable with largest reduced costs.
  No devex or steepest edge.

- inverting the basis matrix is done in pure product form. No LU
  decomposition.

- Branch and Bound implemented as recursive function, this means pure 
  Depth First. There are two strategies for selecting a branching variable.
  Branching on the first non integer variable, branching on a random
  selected variable.


The result is a relatively small and easy to grasp code.
On the other side it can run into numerical problems. More expenditure
has to be done to make the code numerical stable and fast on large
problems. Perhaps somebody wants to add some parts to improve the program.
However this always should be done in a modular way.














/***************************************************************/
/**                                                           **/
/**                                                           **/
/**             DATASTRUCTURES                                **/
/**                                                           **/
/**                                                           **/
/***************************************************************/


This section describes the most important data structures of 
the program. For arrays I tried to give the size of the array
and give an idea of the contents of miscellaneous fields, if there 
are different parts in the array.
The first part of this section should give the main idea, how a
linear programming problem is transferred into the internal data
structures.
Then a more detailed description of the separate arrays follows.



How is the following linear program transferred to the internal data?

max   c'x
s.t.  A x <= b
      lower <= x <= upper




All data is placed into arrays which can be accessed via pointers in the
structure lprec. There you can find information to the matrix, information,
how to interpret the data and the inverted matrix (Eta file).


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

Something about numbering rows and columns:

The program is written in C, however indices for the data normally start
with 1!

Columns are numbered from 1 to columns.
Rows are numbered from 1 to rows.
row[0] is objective row.


Maximisation or minimisation is only a change of sign in objective row.
This change is marked in ch_sign[0] and in lp->maximise.


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


Internally to lp_solve there exist only EQUALITIES or LESSEQUAL rows.
GREATEREQUAL rows are multiplied with -1 and the information, that 
this is done is written in the array ch_sign.


How to access the right hand side?
Read lp->orig_rhs.


How to access the bounds?
Read lp->orig_lowbo and lp->orig_upbo


How to know the sense of a constraint?
It can be accessed via the information on the bounds of a row.  Internally
there exist only Less-equal and Equal rows.  Upper bound == 0 means row is
equal row. Everything else means:  It is a Less-Equal row. To distinguish
between Less-Equal rows and Greater-Equal rows of the original problem you
have to check ch_sign.





How to access information of the original problem, which is not 
mentioned above?
A good source to find this information is the routine "write_LP" which writes
out the whole original problem. It therefore has to access all the original
data. You can check this routine to get the requested information?



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

typedef struct _lprec
{
  nstring   lp_name;		/* the name of the lp */

  short     active;		/*TRUE if the globals point to this structure*/
  short     verbose;            /* ## Verbose flag */
  short     print_duals;        /* ## PrintDuals flag for PrintSolution */
  short     print_sol;          /* ## used in lp_solve */
  short     debug;              /* ## Print B&B information */
  short     print_at_invert;    /* ## Print information at every reinversion */
  short     trace;              /* ## Print information on pivot selection */
  short     anti_degen;		/* ## Do perturbations */

  int	    rows;               /* Nr of constraint rows in the problem */
  int       rows_alloc;      	/* The allocated memory for Rows sized data */
  int       columns;            /* The number of columns (= variables) */
  int       columns_alloc;  
  int       sum;                /* The size of the variables + the slacks */
  int       sum_alloc;

  short     names_used;         /* Flag to indicate if names for rows and
				   columns are used */







  nstring   *row_name;		/* rows_alloc+1 */

 +-------------------+-------------------+-------------------+
 |  Objective_name(?)|  Row_name[1]      |  UNUSED           |
 +-------------------+-------------------+-------------------+
 \________  ________/          ^                              ^
          \/                   |                              |
     25 Bytes                 rows                     rows_alloc+1


  Each field has a length of NAMELEN = 25 Byte; in total it has rows_alloc+1
  entries. The first entry seems to be unused.



  nstring   *col_name;		/* columns_alloc+1 */


 +-------------------+-------------------+-------------------+
 |  ***************  |  Col_name[1]      |  UNUSED           |
 +-------------------+-------------------+-------------------+
 \________  ________/          ^                              ^
          \/                   |                              |
     25 Bytes               columns                 columns_alloc+1

  Similar to row_name:
  Each field has a length of NAMELEN = 25 Byte; in total it has columns_alloc+1
  entries. The first entry seems to be unused.


 /* Row[0] of the sparse matrix is the objective function */

  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 */
  REAL      *orig_rh;           /* rows_alloc+1 :The RHS after scaling & sign 
				  changing, but before `Bound transformation' */
  REAL      *rh;		/* rows_alloc+1 :As orig_rh, but after Bound 
				   transformation */
  REAL      *rhs;		/* rows_alloc+1 :The RHS of the current simplex 	
				   tableau */
  short     *must_be_int;       /* sum_alloc+1 :TRUE if variable must be 
				   Integer */
  REAL      *orig_upbo;         /* sum_alloc+1 :Bound before transformations */
  REAL      *orig_lowbo;	/*  "       "                   */
  REAL      *upbo;              /*  "       "  :Upper bound after transformation 
				   & B&B work*/
  REAL      *lowbo;             /*  "       "  :Lower bound after transformation
				   & B&B work */

  short     basis_valid;        /* TRUE if the basis is still valid */
  int       *bas;               /* rows_alloc+1 :The basis column list */
  short     *basis;             /* sum_alloc+1 : basis[i] is TRUE if the column
				   is in the basis */
  short     *lower;             /*  "       "  :TRUE if the variable is at its 
				   lower bound (or in the basis), it is FALSE
				   if the variable is at its upper bound */


 The following 

      max c'x


      s.t.  A*x <= b
            l <= x <= u

symbolically:

    +-----------------------------+
    |             c               |
    +-----------------------------+

    +-----------------------------+    +-+
    |                             |    | |
    |             A               | <= |b|
    |                             |    | |
    |                             |    | |
    +-----------------------------+    +-+


     +-----------------------------+
     |          upper Bound        |
     +-----------------------------+

     +-----------------------------+
     |          lower Bound        |
     +-----------------------------+



is transformed to



     +-----------------------------+    +-+      +-+      +-+  \
     |             c               |    | |      | |      | |   |    := row[0]
     +-----------------------------+    +-+      +-+      +-+   |
     |                             |    | |      | |      | |   \  rows_alloc+1
     |             A               | <= | |      | |      | |   /
     |                             |    | |      | |      | |   |