3
/*----------------------------------------------------------------------
8
----------------------------------------------------------------------*/
13
#include "gnumeric-config.h"
19
#define ies_create_tree glp_ies_create_tree
20
#define ies_add_master_row glp_ies_add_master_row
21
#define ies_add_master_col glp_ies_add_master_col
22
#define ies_next_master_row glp_ies_next_master_row
23
#define ies_next_master_col glp_ies_next_master_col
24
#define ies_what_item glp_ies_what_item
25
#define ies_set_item_link glp_ies_set_item_link
26
#define ies_get_item_link glp_ies_get_item_link
27
#define ies_clean_master_set glp_ies_clean_master_set
28
#define ies_del_master_row glp_ies_del_master_row
29
#define ies_del_master_col glp_ies_del_master_col
30
#define ies_set_item_filt glp_ies_set_item_filt
31
#define ies_set_item_hook glp_ies_set_item_hook
32
#define ies_delete_tree glp_ies_delete_tree
34
#define ies_default_tagx glp_ies_default_tagx
35
#define ies_create_node glp_ies_create_node
36
#define ies_revive_node glp_ies_revive_node
37
#define ies_add_rows glp_ies_add_rows
38
#define ies_add_cols glp_ies_add_cols
39
#define ies_del_items glp_ies_del_items
40
#define ies_delete_node glp_ies_delete_node
41
#define ies_prune_branch glp_ies_prune_branch
42
#define ies_set_node_hook glp_ies_set_node_hook
44
#define ies_get_node_level glp_ies_get_node_level
45
#define ies_get_node_count glp_ies_get_node_count
46
#define ies_get_next_node glp_ies_get_next_node
47
#define ies_get_prev_node glp_ies_get_prev_node
48
#define ies_get_this_node glp_ies_get_this_node
49
#define ies_set_node_link glp_ies_set_node_link
50
#define ies_get_node_link glp_ies_get_node_link
51
#define ies_get_num_rows glp_ies_get_num_rows
52
#define ies_get_num_cols glp_ies_get_num_cols
53
#define ies_get_ith_row glp_ies_get_ith_row
54
#define ies_get_jth_col glp_ies_get_jth_col
55
#define ies_get_row_bind glp_ies_get_row_bind
56
#define ies_get_col_bind glp_ies_get_col_bind
57
#define ies_get_row_bnds glp_ies_get_row_bnds
58
#define ies_get_col_bnds glp_ies_get_col_bnds
59
#define ies_get_row_info glp_ies_get_row_info
60
#define ies_get_col_info glp_ies_get_col_info
61
#define ies_eval_red_cost glp_ies_eval_red_cost
62
#define ies_set_row_bnds glp_ies_set_row_bnds
63
#define ies_set_col_bnds glp_ies_set_col_bnds
64
#define ies_set_obj_c0 glp_ies_set_obj_c0
65
#define ies_set_row_stat glp_ies_set_row_stat
66
#define ies_set_col_stat glp_ies_set_col_stat
67
#define ies_get_lp_object glp_ies_get_lp_object
68
#define ies_solve_node glp_ies_solve_node
70
/*----------------------------------------------------------------------
74
typedef struct IESTREE IESTREE;
75
typedef struct IESITEM IESITEM;
76
typedef struct IESELEM IESELEM;
77
typedef struct IESNODE IESNODE;
78
typedef struct IESDIFF IESDIFF;
79
typedef struct IESBNDS IESBNDS;
80
typedef struct IESCOEF IESCOEF;
81
typedef struct IESSTAT IESSTAT;
84
{ /* implicit enumeration tree */
85
/*--------------------------------------------------------------*/
88
/* memory pool for IESITEM objects */
90
/* memory pool for segmented character strings */
92
/* memory pool for IESELEM objects */
94
/* number of master rows (except deleted ones) */
96
/* number of deleted master rows, which are still in the set */
98
/* pointer to the (chronologically) first master row */
100
/* pointer to the (chronologically) last master row */
102
/* number of master columns (except deleted ones) */
104
/* number of deleted master columns, which are still in the set */
106
/* pointer to the (chronologically) first master column */
108
/* pointer to the (chronologically) last master column */
110
/* transit pointer passed to the item filter routine */
111
int (*item_filt)(void *info, IESITEM *item);
112
/* this item filter routine is called when the reference count of
113
some master row/column, pointer to which is passed to this
114
routine, reaches zero; if this routine returns zero, the item
115
is deleted from the master set; otherwise, the item is kept in
116
the master set; if this entry point is NULL, it is equivalent
117
to a filter routine, which always returns zero */
119
/* transit pointer passed to the item hook routine */
120
void (*item_hook)(void *info, IESITEM *item);
121
/* this item hook routine is called when some master row/column,
122
pointer to which is passed to this routine, is being deleted
123
from the master set */
124
/*--------------------------------------------------------------*/
125
/* implicit enumeration tree */
127
/* memory pool for IESNODE objects */
129
/* memory pool for IESDIFF objects */
131
/* memory pool for IESBNDS objects */
133
/* memory pool for IESCOEF objects */
135
/* memory pool for IESSTAT objects */
137
/* size of the tree (i.e. number of nodes in the tree) */
139
/* pointer to the root node; the root node is created before any
140
other nodes, so it is also the (chronologically) first in the
143
/* pointer to a node, which is the (chronologically) last in the
146
/* pointer to the current node (which may be active as well as
147
inactive); NULL means the current node doesn't exist */
149
/* transit pointer passed to the node hook routine */
150
void (*node_hook)(void *info, IESNODE *node);
151
/* this node hook routine is called when some node problem,
152
pointer to which is passed to this routine, is being deleted
153
from the enumeration tree */
154
/*--------------------------------------------------------------*/
155
/* LP problem instance */
156
/* if the field this_node is not NULL, the instance corresponds
157
to the current node problem; when the current problem becomes
158
undefined and the field this_node is set to NULL, the instance
159
is kept unchanged (this allows efficiently reviving another
160
node problem in the case it differs from the instance only in
161
a few rows and columns, i.e. not from scratch) */
163
/* maximal number of rows */
165
/* maximal number of columns */
167
/* number of rows in the problem instance */
169
/* number of columns in the problem instance */
170
IESITEM **item; /* IESITEM *item[1+m_max+n_max]; */
171
/* item[0] is not used;
172
item[i], 1 <= i <= m, is a pointer to the master row, which
173
corresponds to the i-th row of the instance;
174
item[m+j], 1 <= j <= n, is a pointer to the master column,
175
which corresponds to the j-th column of the instance;
176
item[k] = NULL means that the corresponding master row/column
177
was deleted (this may happen only if the current node problem
179
int *typx; /* int typx[1+m_max+n_max]; */
180
/* typx[0] is not used;
181
typx[k], 1 <= k <= m+n, is the type of the variable x[k]:
182
LPX_FR - free variable (-inf < x[k] < +inf)
183
LPX_LO - lower bound (l[k] <= x[k] < +inf)
184
LPX_UP - upper bound (-inf < x[k] <= u[k])
185
LPX_DB - gnm_float bound (l[k] <= x[k] <= u[k])
186
LPX_FX - fixed variable (l[k] = x[k] = u[k]) */
187
gnm_float *lb; /* gnm_float lb[1+m_max+n_max]; */
188
/* lb[0] is not used;
189
lb[k], 1 <= k <= m+n, is an lower bound of the variable x[k];
190
if x[k] has no lower bound, lb[k] is zero */
191
gnm_float *ub; /* gnm_float ub[1+m_max+n_max]; */
192
/* ub[0] is not used;
193
ub[k], 1 <= k <= m+n, is an upper bound of the variable x[k];
194
if x[k] has no upper bound, ub[k] is zero; if x[k] is of fixed
195
type, ub[k] is equal to lb[k] */
196
gnm_float *coef; /* gnm_float coef[1+m_max+n_max]; */
197
/* coef[0] is a constant term of the objective function;
198
coef[k], 1 <= k <= m+n, is a coefficient of the objective
199
function at the variable x[k] (note that auxiliary variables
200
also may have non-zero objective coefficients) */
201
int *tagx; /* int tagx[1+m_max+n_max]; */
202
/* tagx[0] is not used;
203
tagx[k], 1 <= k <= m+n, is the status of the variable x[k]:
204
LPX_BS - basic variable
205
LPX_NL - non-basic variable on lower bound
206
LPX_NU - non-basic variable on upper bound
207
LPX_NF - non-basic free variable
208
LPX_NS - non-basic fixed variable */
210
/* the problem instance in a solver specific format */
214
{ /* master row/column */
216
/* this field determines what this item is:
218
'C' - master column */
220
/* row/column name (1 to 255 chars) or NULL, if row/column has no
223
/* default row/column type */
225
/* default lower bound */
227
/* default upper bound */
229
/* default coefficient in the objective function */
231
/* pointer to the list of non-zero constraint coefficients, which
232
belong to this row/column */
234
/* count of references to this row/column from the add_them patch
235
lists (see below); row/column can be deleted only if its count
236
is zero and it is not used in the current problem; negative
237
count means that this row/column is deleted (physical deletion
238
is performed automatically at appropriate moments) */
240
/* in the case of row bind = i (1 <= i <= tree->m) means this
241
item is referenced as the i-th row of the problem instance and
242
therefore tree->item[i] is a pointer to this item;
243
in the case of column bind = j (1 <= j <= tree->n) means this
244
item is referenced as the j-th column of the problem instance
245
and therefore tree->item[tree->m+j] is a pointer to this item;
246
bind = 0 means that this master row/column is not used in the
249
/* reserved for row/column specific information */
251
/* pointer to the (chronologically) previous master row/column */
253
/* pointer to the (chronologically) next master row/column */
257
{ /* constraint coefficient */
259
/* pointer to the master row, which this element belongs to */
261
/* pointer to the master column, which this element belongs to */
263
/* numerical (non-zero) value of this element */
265
/* pointer to the next element in the same master row */
267
/* pointer to the next element in the same master column */
273
/* pointer to the parent node; NULL means that this node is the
276
/* this node level (the root node has the level 0) */
278
/* if count < 0, this node is active, and therefore has no child
279
nodes; if count >= 0, this node is inactive, and in this case
280
count is number of its child nodes */
282
/* number of rows in this node problem */
284
/* number of columns in this node problem */
286
/* reserved for node specific information */
288
/* pointer to the (chronologically) previous node */
290
/* pointer to the (chronologically) next node */
292
/* auxiliary pointer */
293
/*--------------------------------------------------------------*/
294
/* patch lists; these lists contain information, which should be
295
applied to the parent node problem (or to an empty problem if
296
this node is the root of the tree) in order to construct this
297
node problem; since active nodes are modfiable, if the current
298
node is active, all its patch lists are temporarily empty */
300
/* pointer to the list of master rows/columns, which are presented
301
in the parent node problem and missing in this node problem, so
302
on reviving this node problem they should be removed */
304
/* pointer to the list of master rows/columns, which are missing
305
in the parent node problem and presented in this node problem,
306
so on reviving this node problem they should be added */
308
/* pointer to the list of master rows/columns, which are presented
309
in this node problem and whose bounds should be changed */
311
/* pointer to the list of master rows/columns, which are presented
312
in this node problem and whose objective coefficients should be
315
/* pointer to the list of master rows/columns, which are presented
316
in this node problem and whose status should be changed */
320
{ /* addition/deletion patch entry */
322
/* pointer to master row/column */
324
/* pointer to the next patch entry */
328
{ /* type/bounds patch entry */
330
/* pointer to master row/column */
332
/* new row/column type */
334
/* new lower bound */
336
/* new upper bound */
338
/* pointer to the next patch entry */
342
{ /* objective coefficient patch entry */
344
/* pointer to master row/column; NULL means this entry changes
345
the constant term of the objective function */
347
/* new objective coefficient or the constant term */
349
/* pointer to the next patch entry */
353
{ /* status patch entry */
355
/* pointer to master row/column */
357
/* new row/column status */
359
/* pointer to the next patch entry */
362
/* routines in glpies1.c ---------------------------------------------*/
364
IESTREE *ies_create_tree(void);
365
/* create implicit enumeration tree */
367
IESITEM *ies_add_master_row(IESTREE *tree, char *name, int typx,
368
gnm_float lb, gnm_float ub, gnm_float coef, int len, IESITEM *col[],
370
/* add master row to the master set */
372
IESITEM *ies_add_master_col(IESTREE *tree, char *name, int typx,
373
gnm_float lb, gnm_float ub, gnm_float coef, int len, IESITEM *row[],
375
/* add master column to the master set */
377
IESITEM *ies_next_master_row(IESTREE *tree, IESITEM *row);
378
/* get pointer to the next master row */
380
IESITEM *ies_next_master_col(IESTREE *tree, IESITEM *col);
381
/* get pointer to the next master column */
383
int ies_what_item(IESTREE *tree, IESITEM *item);
384
/* determine of what sort master item is */
386
void ies_set_item_link(IESTREE *tree, IESITEM *item, void *link);
387
/* store master item specific information */
389
void *ies_get_item_link(IESTREE *tree, IESITEM *item);
390
/* retrieve master item specific information */
392
void ies_clean_master_set(IESTREE *tree);
393
/* clean the master set */
395
void ies_del_master_row(IESTREE *tree, IESITEM *row);
396
/* delete master row from the master set */
398
void ies_del_master_col(IESTREE *tree, IESITEM *col);
399
/* delete master column from the master set */
401
void ies_set_item_filt(IESTREE *tree,
402
void *info, int (*filt)(void *info, IESITEM *item));
403
/* install item filter routine */
405
void ies_set_item_hook(IESTREE *tree,
406
void *info, void (*hook)(void *info, IESITEM *item));
407
/* install item hook routine */
409
void ies_delete_tree(IESTREE *tree);
410
/* delete implicit enumeration tree */
412
/* routines in glpies2.c ---------------------------------------------*/
414
int ies_default_tagx(IESITEM *item);
415
/* determine default status of master row/column */
417
IESNODE *ies_create_node(IESTREE *tree, IESNODE *parent);
418
/* create new node problem */
420
void ies_revive_node(IESTREE *tree, IESNODE *node);
421
/* make specified node problem current */
423
void ies_add_rows(IESTREE *tree, int nrs, IESITEM *row[]);
424
/* add master rows to the current node problem */
426
void ies_add_cols(IESTREE *tree, int ncs, IESITEM *col[]);
427
/* add master columns to the current node problem */
429
void ies_del_items(IESTREE *tree);
430
/* delete rows/columns from the current node problem */
432
void ies_delete_node(IESTREE *tree, IESNODE *node);
433
/* delete specified node problem */
435
void ies_prune_branch(IESTREE *tree, IESNODE *node);
436
/* prune branch of the tree */
438
void ies_set_node_hook(IESTREE *tree,
439
void *info, void (*hook)(void *info, IESNODE *node));
440
/* install node hook routine */
442
/* routines in glpies3.c ---------------------------------------------*/
444
int ies_get_node_level(IESTREE *tree, IESNODE *node);
445
/* get node depth level */
447
int ies_get_node_count(IESTREE *tree, IESNODE *node);
448
/* get node reference count */
450
IESNODE *ies_get_next_node(IESTREE *tree, IESNODE *node);
451
/* get pointer to next node */
453
IESNODE *ies_get_prev_node(IESTREE *tree, IESNODE *node);
454
/* get pointer to previous node */
456
IESNODE *ies_get_this_node(IESTREE *tree);
457
/* get pointer to current node */
459
void ies_set_node_link(IESTREE *tree, IESNODE *node, void *link);
460
/* store node problem specific information */
462
void *ies_get_node_link(IESTREE *tree, IESNODE *node);
463
/* retrieve node problem specific information */
465
int ies_get_num_rows(IESTREE *tree);
466
/* determine number of rows */
468
int ies_get_num_cols(IESTREE *tree);
469
/* determine number of columns */
471
IESITEM *ies_get_ith_row(IESTREE *tree, int i);
472
/* determine pointer to i-th row */
474
IESITEM *ies_get_jth_col(IESTREE *tree, int j);
475
/* determine pointer to j-th column */
477
int ies_get_row_bind(IESTREE *tree, IESITEM *row);
478
/* get ordinal number of master row in LP object */
480
int ies_get_col_bind(IESTREE *tree, IESITEM *col);
481
/* get ordinal number of master column in LP object */
483
void ies_get_row_bnds(IESTREE *tree, IESITEM *row, int *typx,
484
gnm_float *lb, gnm_float *ub);
485
/* obtain row bounds */
487
void ies_get_col_bnds(IESTREE *tree, IESITEM *col, int *typx,
488
gnm_float *lb, gnm_float *ub);
489
/* obtain column bounds */
491
void ies_get_row_info(IESTREE *tree, IESITEM *row, int *tagx,
492
gnm_float *vx, gnm_float *dx);
493
/* obtain row solution information */
495
void ies_get_col_info(IESTREE *tree, IESITEM *col, int *tagx,
496
gnm_float *vx, gnm_float *dx);
497
/* obtain column solution information */
499
gnm_float ies_eval_red_cost(IESTREE *tree, IESITEM *col);
500
/* compute reduced cost of master column */
502
void ies_set_row_bnds(IESTREE *tree, IESITEM *row, int typx, gnm_float lb,
504
/* set (change) row bounds */
506
void ies_set_col_bnds(IESTREE *tree, IESITEM *col, int typx, gnm_float lb,
508
/* set (change) column bounds */
510
void ies_set_obj_c0(IESTREE *tree, gnm_float c0);
511
/* set (change) constant term of the objective function */
513
void ies_set_row_stat(IESTREE *tree, IESITEM *row, int stat);
514
/* set (change) row status */
516
void ies_set_col_stat(IESTREE *tree, IESITEM *col, int stat);
517
/* set (change) column status */
519
LPX *ies_get_lp_object(IESTREE *tree);
520
/* get pointer to internal LP object */
522
int ies_solve_node(IESTREE *tree);
523
/* solve the current node problem */