64
63
#define spx_update_dvec glp_spx_update_dvec
65
64
#define spx_err_in_dvec glp_spx_err_in_dvec
66
#define spx_warm_up glp_spx_warm_up
67
#define spx_prim_opt glp_spx_prim_opt
68
#define spx_prim_feas glp_spx_prim_feas
69
#define spx_dual_opt glp_spx_dual_opt
70
#define spx_simplex glp_spx_simplex
67
72
typedef struct SPX SPX;
70
{ /* common block used by the simplex method routines */
72
/* LP problem object */
75
{ /* data block used by simplex method routines */
76
/*--------------------------------------------------------------*/
79
/* number of rows (auxiliary variables) */
81
/* number of columns (structural variables) */
82
int *typx; /* int typx[1+m+n]; */
83
/* typx[0] is not used;
84
typx[k], 1 <= k <= m+n, is the type of the variable x[k]: */
85
#define LPX_FR 110 /* free variable: -inf < x[k] < +inf */
86
#define LPX_LO 111 /* lower bound: l[k] <= x[k] < +inf */
87
#define LPX_UP 112 /* upper bound: -inf < x[k] <= u[k] */
88
#define LPX_DB 113 /* gnm_float bound: l[k] <= x[k] <= u[k] */
89
#define LPX_FX 114 /* fixed variable: l[k] = x[k] = u[k] */
90
gnm_float *lb; /* gnm_float lb[1+m+n]; */
92
lb[k], 1 <= k <= m+n, is an lower bound of the variable x[k];
93
if x[k] has no lower bound, lb[k] is zero */
94
gnm_float *ub; /* gnm_float ub[1+m+n]; */
96
ub[k], 1 <= k <= m+n, is an upper bound of the variable x[k];
97
if x[k] has no upper bound, ub[k] is zero; if x[k] is of fixed
98
type, ub[k] is equal to lb[k] */
100
/* optimization direction (sense of the objective function): */
101
#define LPX_MIN 120 /* minimization */
102
#define LPX_MAX 121 /* maximization */
103
gnm_float *coef; /* gnm_float coef[1+m+n]; */
104
/* coef[0] is a constant term of the objective function;
105
coef[k], 1 <= k <= m+n, is a coefficient of the objective
106
function at the variable x[k] (note that auxiliary variables
107
also may have non-zero objective coefficients) */
108
/*--------------------------------------------------------------*/
109
/* constraint matrix (has m rows and n columns) */
110
int *A_ptr; /* int A_ptr[1+m+1]; */
111
int *A_ind; /* int A_ind[A_ptr[m+1]]; */
112
gnm_float *A_val; /* gnm_float A_val[A_ptr[m+1]]; */
113
/* constraint matrix in storage-by-rows format */
114
int *AT_ptr; /* int AT_ptr[1+n+1]; */
115
int *AT_ind; /* int AT_ind[AT_ptr[n+1]]; */
116
gnm_float *AT_val; /* gnm_float AT_val[AT_ptr[n+1]]; */
117
/* constraint matrix in storage-by-columns format */
118
/*--------------------------------------------------------------*/
121
/* status of the current basis: */
122
#define LPX_B_UNDEF 130 /* current basis is undefined */
123
#define LPX_B_VALID 131 /* current basis is valid */
125
/* status of the primal solution: */
126
#define LPX_P_UNDEF 132 /* primal status is undefined */
127
#define LPX_P_FEAS 133 /* solution is primal feasible */
128
#define LPX_P_INFEAS 134 /* solution is primal infeasible */
129
#define LPX_P_NOFEAS 135 /* no primal feasible solution exists */
131
/* status of the dual solution: */
132
#define LPX_D_UNDEF 136 /* dual status is undefined */
133
#define LPX_D_FEAS 137 /* solution is dual feasible */
134
#define LPX_D_INFEAS 138 /* solution is dual infeasible */
135
#define LPX_D_NOFEAS 139 /* no dual feasible solution exists */
136
int *tagx; /* int tagx[1+m+n]; */
137
/* tagx[0] is not used;
138
tagx[k], 1 <= k <= m+n, is the status of the variable x[k]
139
(contents of this array is always defined independently on the
140
status of the current basis): */
141
#define LPX_BS 140 /* basic variable */
142
#define LPX_NL 141 /* non-basic variable on lower bound */
143
#define LPX_NU 142 /* non-basic variable on upper bound */
144
#define LPX_NF 143 /* non-basic free variable */
145
#define LPX_NS 144 /* non-basic fixed variable */
146
int *posx; /* int posx[1+m+n]; */
147
/* posx[0] is not used;
148
posx[k], 1 <= k <= m+n, is the position of the variable x[k]
149
in the vector of basic variables xB or non-basic variables xN:
150
posx[k] = i means that x[k] = xB[i], 1 <= i <= m
151
posx[k] = m+j means that x[k] = xN[j], 1 <= j <= n
152
(if the current basis is undefined, contents of this array is
154
int *indx; /* int indx[1+m+n]; */
155
/* indx[0] is not used;
156
indx[i], 1 <= i <= m, is the original number of the basic
157
variable xB[i], i.e. indx[i] = k means that posx[k] = i
158
indx[m+j], 1 <= j <= n, is the original number of the non-basic
159
variable xN[j], i.e. indx[m+j] = k means that posx[k] = m+j
160
(if the current basis is undefined, contents of this array is
162
INV *inv; /* INV inv[1:m,1:m]; */
163
/* an invertable (factorized) form of the current basis matrix */
164
gnm_float *bbar; /* gnm_float bbar[1+m]; */
165
/* bbar[0] is not used;
166
bbar[i], 1 <= i <= m, is a value of basic variable xB[i] */
167
gnm_float *pi; /* gnm_float pi[1+m]; */
168
/* pi[0] is not used;
169
pi[i], 1 <= i <= m, is a simplex (Lagrange) multiplier, which
170
corresponds to the i-th row (equality constraint) */
171
gnm_float *cbar; /* gnm_float cbar[1+n]; */
172
/* cbar[0] is not used;
173
cbar[j], 1 <= j <= n, is a reduced cost of non-basic variable
176
/* ordinal number of some auxiliary or structural variable which
177
has certain property, 1 <= some <= m+n */
178
/*--------------------------------------------------------------*/
179
/* control parameters and statistics */
181
/* level of messages output by the solver:
183
1 - error messages only
185
3 - full output (includes informational messages) */
187
/* dual simplex option:
188
0 - do not use the dual simplex
189
1 - if the initial basic solution being primal infeasible is
190
dual feasible, use the dual simplex */
192
/* pricing option (for both primal and dual simplex):
194
1 - steepest edge pricing */
196
/* relaxation parameter used in the ratio test; if it is zero,
197
the textbook ratio test is used; if it is non-zero (should be
198
positive), Harris' two-pass ratio test is used; in the latter
199
case on the first pass basic variables (in the case of primal
200
simplex) or reduced costs of non-basic variables (in the case
201
of dual simplex) are allowed to slightly violate their bounds,
202
but not more than (relax * tol_bnd) or (relax * tol_dj) (thus,
203
relax is a percentage of tol_bnd or tol_dj) */
205
/* relative tolerance used to check if the current basic solution
206
is primal feasible */
208
/* absolute tolerance used to check if the current basic solution
211
/* relative tolerance used to choose eligible pivotal elements of
212
the simplex table in the ratio test */
214
/* lower limit of the objective function; if on the phase II the
215
objective function reaches this limit and continues decreasing,
216
the solver stops the search */
218
/* upper limit of the objective function; if on the phase II the
219
objective function reaches this limit and continues increasing,
220
the solver stops the search */
222
/* simplex iterations limit; if this value is positive, it is
223
decreased by one each time when one simplex iteration has been
224
performed, and reaching zero value signals the solver to stop
225
the search; negative value means no iterations limit */
227
/* simplex iterations count; this count is increased by one each
228
time when one simplex iteration has been performed */
230
/* searching time limit, in seconds; if this value is positive,
231
it is decreased each time when one simplex iteration has been
232
performed by the amount of time spent for the iteration, and
233
reaching zero value signals the solver to stop the search;
234
negative value means no time limit */
236
/* output frequency, in iterations; this parameter specifies how
237
frequently the solver sends information about the solution to
238
the standard output */
240
/* output delay, in seconds; this parameter specifies how long
241
the solver should delay sending information about the solution
242
to the standard output; zero value means no delay */
243
/*--------------------------------------------------------------*/
244
/* working segment */
74
/* what method is used:
246
/* which method is used:
75
247
'P' - primal simplex
76
248
'D' - dual simplex */
135
307
/* is used to save the original objective coefficients */
138
/* basis maintenance routines ----------------------------------------*/
310
/* simplex method generic routines -----------------------------------*/
140
int spx_invert(LPX *lp);
312
int spx_invert(SPX *spx);
141
313
/* reinvert the basis matrix */
143
void spx_ftran(LPX *lp, gnm_float x[], int save);
315
void spx_ftran(SPX *spx, gnm_float x[], int save);
144
316
/* perform forward transformation (FTRAN) */
146
void spx_btran(LPX *lp, gnm_float x[]);
318
void spx_btran(SPX *spx, gnm_float x[]);
147
319
/* perform backward transformation (BTRAN) */
149
int spx_update(LPX *lp, int j);
321
int spx_update(SPX *spx, int j);
150
322
/* update factorization for adjacent basis matrix */
152
/* generic simplex method routines -----------------------------------*/
154
gnm_float spx_eval_xn_j(LPX *lp, int j);
324
gnm_float spx_eval_xn_j(SPX *spx, int j);
155
325
/* determine value of non-basic variable */
157
void spx_eval_bbar(LPX *lp);
327
void spx_eval_bbar(SPX *spx);
158
328
/* compute values of basic variables */
160
void spx_eval_pi(LPX *lp);
330
void spx_eval_pi(SPX *spx);
161
331
/* compute simplex multipliers */
163
void spx_eval_cbar(LPX *lp);
333
void spx_eval_cbar(SPX *spx);
164
334
/* compute reduced costs of non-basic variables */
166
gnm_float spx_eval_obj(LPX *lp);
336
gnm_float spx_eval_obj(SPX *spx);
167
337
/* compute value of the objective function */
169
void spx_eval_col(LPX *lp, int j, gnm_float col[], int save);
339
void spx_eval_col(SPX *spx, int j, gnm_float col[], int save);
170
340
/* compute column of the simplex table */
172
void spx_eval_rho(LPX *lp, int i, gnm_float rho[]);
342
void spx_eval_rho(SPX *spx, int i, gnm_float rho[]);
173
343
/* compute row of the inverse */
175
void spx_eval_row(LPX *lp, gnm_float rho[], gnm_float row[]);
345
void spx_eval_row(SPX *spx, gnm_float rho[], gnm_float row[]);
176
346
/* compute row of the simplex table */
178
gnm_float spx_check_bbar(LPX *lp, gnm_float tol);
348
gnm_float spx_check_bbar(SPX *spx, gnm_float tol);
179
349
/* check primal feasibility */
181
gnm_float spx_check_cbar(LPX *lp, gnm_float tol);
351
gnm_float spx_check_cbar(SPX *spx, gnm_float tol);
182
352
/* check dual feasibility */
184
354
int spx_prim_chuzc(SPX *spx, gnm_float tol);
added
removed
src/tools/solver/glpk/include/glpspx.h
