📄 hartmut_documentation
字号:
+-----------------------------+
is transformed to
+-----------------------------+ +-+ +-+ +-+ \
| c | | | | | | | | := row[0]
+-----------------------------+ +-+ +-+ +-+ |
| | | | | | | | \ rows_alloc+1
| A | <= | | | | | | /
| | | | | | | | |
| | | | | | | | |
+-----------------------------+ +-+ +-+ +-+ /
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;
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -