📄 hartmut_documentation
字号:
/*************************************************************************/
/** **/
/** Documentation for lp_solve **/
/** **/
/** (C) Hartmut Schwab Hartmut.Schwab@IWR.Uni-Heidelberg.De **/
/** **/
/** **/
/*************************************************************************/
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
Hartmut.Schwab@IWR.Uni-Heidelberg.De
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 |
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -