1 | /* glpapi.h (application program interface) */ |
---|
2 | |
---|
3 | /*********************************************************************** |
---|
4 | * This code is part of GLPK (GNU Linear Programming Kit). |
---|
5 | * |
---|
6 | * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, |
---|
7 | * 2009, 2010 Andrew Makhorin, Department for Applied Informatics, |
---|
8 | * Moscow Aviation Institute, Moscow, Russia. All rights reserved. |
---|
9 | * E-mail: <mao@gnu.org>. |
---|
10 | * |
---|
11 | * GLPK is free software: you can redistribute it and/or modify it |
---|
12 | * under the terms of the GNU General Public License as published by |
---|
13 | * the Free Software Foundation, either version 3 of the License, or |
---|
14 | * (at your option) any later version. |
---|
15 | * |
---|
16 | * GLPK is distributed in the hope that it will be useful, but WITHOUT |
---|
17 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY |
---|
18 | * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public |
---|
19 | * License for more details. |
---|
20 | * |
---|
21 | * You should have received a copy of the GNU General Public License |
---|
22 | * along with GLPK. If not, see <http://www.gnu.org/licenses/>. |
---|
23 | ***********************************************************************/ |
---|
24 | |
---|
25 | #ifndef GLPAPI_H |
---|
26 | #define GLPAPI_H |
---|
27 | |
---|
28 | #define GLP_PROB_DEFINED |
---|
29 | typedef struct glp_prob glp_prob; |
---|
30 | |
---|
31 | #include "glpk.h" |
---|
32 | #include "glpavl.h" |
---|
33 | #include "glpbfd.h" |
---|
34 | |
---|
35 | typedef struct GLPROW GLPROW; |
---|
36 | typedef struct GLPCOL GLPCOL; |
---|
37 | typedef struct GLPAIJ GLPAIJ; |
---|
38 | |
---|
39 | #define GLP_PROB_MAGIC 0xD7D9D6C2 |
---|
40 | |
---|
41 | struct glp_prob |
---|
42 | { /* LP/MIP problem object */ |
---|
43 | int magic; |
---|
44 | /* magic value used for debugging */ |
---|
45 | DMP *pool; |
---|
46 | /* memory pool to store problem object components */ |
---|
47 | glp_tree *tree; |
---|
48 | /* pointer to the search tree; set by the MIP solver when this |
---|
49 | object is used in the tree as a core MIP object */ |
---|
50 | void *parms; |
---|
51 | /* reserved for backward compatibility */ |
---|
52 | /*--------------------------------------------------------------*/ |
---|
53 | /* LP/MIP data */ |
---|
54 | char *name; |
---|
55 | /* problem name (1 to 255 chars); NULL means no name is assigned |
---|
56 | to the problem */ |
---|
57 | char *obj; |
---|
58 | /* objective function name (1 to 255 chars); NULL means no name |
---|
59 | is assigned to the objective function */ |
---|
60 | int dir; |
---|
61 | /* optimization direction flag (objective "sense"): |
---|
62 | GLP_MIN - minimization |
---|
63 | GLP_MAX - maximization */ |
---|
64 | double c0; |
---|
65 | /* constant term of the objective function ("shift") */ |
---|
66 | int m_max; |
---|
67 | /* length of the array of rows (enlarged automatically) */ |
---|
68 | int n_max; |
---|
69 | /* length of the array of columns (enlarged automatically) */ |
---|
70 | int m; |
---|
71 | /* number of rows, 0 <= m <= m_max */ |
---|
72 | int n; |
---|
73 | /* number of columns, 0 <= n <= n_max */ |
---|
74 | int nnz; |
---|
75 | /* number of non-zero constraint coefficients, nnz >= 0 */ |
---|
76 | GLPROW **row; /* GLPROW *row[1+m_max]; */ |
---|
77 | /* row[i], 1 <= i <= m, is a pointer to i-th row */ |
---|
78 | GLPCOL **col; /* GLPCOL *col[1+n_max]; */ |
---|
79 | /* col[j], 1 <= j <= n, is a pointer to j-th column */ |
---|
80 | AVL *r_tree; |
---|
81 | /* row index to find rows by their names; NULL means this index |
---|
82 | does not exist */ |
---|
83 | AVL *c_tree; |
---|
84 | /* column index to find columns by their names; NULL means this |
---|
85 | index does not exist */ |
---|
86 | /*--------------------------------------------------------------*/ |
---|
87 | /* basis factorization (LP) */ |
---|
88 | int valid; |
---|
89 | /* the factorization is valid only if this flag is set */ |
---|
90 | int *head; /* int head[1+m_max]; */ |
---|
91 | /* basis header (valid only if the factorization is valid); |
---|
92 | head[i] = k is the ordinal number of auxiliary (1 <= k <= m) |
---|
93 | or structural (m+1 <= k <= m+n) variable which corresponds to |
---|
94 | i-th basic variable xB[i], 1 <= i <= m */ |
---|
95 | glp_bfcp *bfcp; |
---|
96 | /* basis factorization control parameters; may be NULL */ |
---|
97 | BFD *bfd; /* BFD bfd[1:m,1:m]; */ |
---|
98 | /* basis factorization driver; may be NULL */ |
---|
99 | /*--------------------------------------------------------------*/ |
---|
100 | /* basic solution (LP) */ |
---|
101 | int pbs_stat; |
---|
102 | /* primal basic solution status: |
---|
103 | GLP_UNDEF - primal solution is undefined |
---|
104 | GLP_FEAS - primal solution is feasible |
---|
105 | GLP_INFEAS - primal solution is infeasible |
---|
106 | GLP_NOFEAS - no primal feasible solution exists */ |
---|
107 | int dbs_stat; |
---|
108 | /* dual basic solution status: |
---|
109 | GLP_UNDEF - dual solution is undefined |
---|
110 | GLP_FEAS - dual solution is feasible |
---|
111 | GLP_INFEAS - dual solution is infeasible |
---|
112 | GLP_NOFEAS - no dual feasible solution exists */ |
---|
113 | double obj_val; |
---|
114 | /* objective function value */ |
---|
115 | int it_cnt; |
---|
116 | /* simplex method iteration count; increased by one on performing |
---|
117 | one simplex iteration */ |
---|
118 | int some; |
---|
119 | /* ordinal number of some auxiliary or structural variable having |
---|
120 | certain property, 0 <= some <= m+n */ |
---|
121 | /*--------------------------------------------------------------*/ |
---|
122 | /* interior-point solution (LP) */ |
---|
123 | int ipt_stat; |
---|
124 | /* interior-point solution status: |
---|
125 | GLP_UNDEF - interior solution is undefined |
---|
126 | GLP_OPT - interior solution is optimal |
---|
127 | GLP_INFEAS - interior solution is infeasible |
---|
128 | GLP_NOFEAS - no feasible solution exists */ |
---|
129 | double ipt_obj; |
---|
130 | /* objective function value */ |
---|
131 | /*--------------------------------------------------------------*/ |
---|
132 | /* integer solution (MIP) */ |
---|
133 | int mip_stat; |
---|
134 | /* integer solution status: |
---|
135 | GLP_UNDEF - integer solution is undefined |
---|
136 | GLP_OPT - integer solution is optimal |
---|
137 | GLP_FEAS - integer solution is feasible |
---|
138 | GLP_NOFEAS - no integer solution exists */ |
---|
139 | double mip_obj; |
---|
140 | /* objective function value */ |
---|
141 | }; |
---|
142 | |
---|
143 | struct GLPROW |
---|
144 | { /* LP/MIP row (auxiliary variable) */ |
---|
145 | int i; |
---|
146 | /* ordinal number (1 to m) assigned to this row */ |
---|
147 | char *name; |
---|
148 | /* row name (1 to 255 chars); NULL means no name is assigned to |
---|
149 | this row */ |
---|
150 | AVLNODE *node; |
---|
151 | /* pointer to corresponding node in the row index; NULL means |
---|
152 | that either the row index does not exist or this row has no |
---|
153 | name assigned */ |
---|
154 | #if 1 /* 20/IX-2008 */ |
---|
155 | int level; |
---|
156 | unsigned char origin; |
---|
157 | unsigned char klass; |
---|
158 | #endif |
---|
159 | int type; |
---|
160 | /* type of the auxiliary variable: |
---|
161 | GLP_FR - free variable |
---|
162 | GLP_LO - variable with lower bound |
---|
163 | GLP_UP - variable with upper bound |
---|
164 | GLP_DB - double-bounded variable |
---|
165 | GLP_FX - fixed variable */ |
---|
166 | double lb; /* non-scaled */ |
---|
167 | /* lower bound; if the row has no lower bound, lb is zero */ |
---|
168 | double ub; /* non-scaled */ |
---|
169 | /* upper bound; if the row has no upper bound, ub is zero */ |
---|
170 | /* if the row type is GLP_FX, ub is equal to lb */ |
---|
171 | GLPAIJ *ptr; /* non-scaled */ |
---|
172 | /* pointer to doubly linked list of constraint coefficients which |
---|
173 | are placed in this row */ |
---|
174 | double rii; |
---|
175 | /* diagonal element r[i,i] of scaling matrix R for this row; |
---|
176 | if the scaling is not used, r[i,i] is 1 */ |
---|
177 | int stat; |
---|
178 | /* status of the auxiliary variable: |
---|
179 | GLP_BS - basic variable |
---|
180 | GLP_NL - non-basic variable on lower bound |
---|
181 | GLP_NU - non-basic variable on upper bound |
---|
182 | GLP_NF - non-basic free variable |
---|
183 | GLP_NS - non-basic fixed variable */ |
---|
184 | int bind; |
---|
185 | /* if the auxiliary variable is basic, head[bind] refers to this |
---|
186 | row, otherwise, bind is 0; this attribute is valid only if the |
---|
187 | basis factorization is valid */ |
---|
188 | double prim; /* non-scaled */ |
---|
189 | /* primal value of the auxiliary variable in basic solution */ |
---|
190 | double dual; /* non-scaled */ |
---|
191 | /* dual value of the auxiliary variable in basic solution */ |
---|
192 | double pval; /* non-scaled */ |
---|
193 | /* primal value of the auxiliary variable in interior solution */ |
---|
194 | double dval; /* non-scaled */ |
---|
195 | /* dual value of the auxiliary variable in interior solution */ |
---|
196 | double mipx; /* non-scaled */ |
---|
197 | /* primal value of the auxiliary variable in integer solution */ |
---|
198 | }; |
---|
199 | |
---|
200 | struct GLPCOL |
---|
201 | { /* LP/MIP column (structural variable) */ |
---|
202 | int j; |
---|
203 | /* ordinal number (1 to n) assigned to this column */ |
---|
204 | char *name; |
---|
205 | /* column name (1 to 255 chars); NULL means no name is assigned |
---|
206 | to this column */ |
---|
207 | AVLNODE *node; |
---|
208 | /* pointer to corresponding node in the column index; NULL means |
---|
209 | that either the column index does not exist or the column has |
---|
210 | no name assigned */ |
---|
211 | int kind; |
---|
212 | /* kind of the structural variable: |
---|
213 | GLP_CV - continuous variable |
---|
214 | GLP_IV - integer or binary variable */ |
---|
215 | int type; |
---|
216 | /* type of the structural variable: |
---|
217 | GLP_FR - free variable |
---|
218 | GLP_LO - variable with lower bound |
---|
219 | GLP_UP - variable with upper bound |
---|
220 | GLP_DB - double-bounded variable |
---|
221 | GLP_FX - fixed variable */ |
---|
222 | double lb; /* non-scaled */ |
---|
223 | /* lower bound; if the column has no lower bound, lb is zero */ |
---|
224 | double ub; /* non-scaled */ |
---|
225 | /* upper bound; if the column has no upper bound, ub is zero */ |
---|
226 | /* if the column type is GLP_FX, ub is equal to lb */ |
---|
227 | double coef; /* non-scaled */ |
---|
228 | /* objective coefficient at the structural variable */ |
---|
229 | GLPAIJ *ptr; /* non-scaled */ |
---|
230 | /* pointer to doubly linked list of constraint coefficients which |
---|
231 | are placed in this column */ |
---|
232 | double sjj; |
---|
233 | /* diagonal element s[j,j] of scaling matrix S for this column; |
---|
234 | if the scaling is not used, s[j,j] is 1 */ |
---|
235 | int stat; |
---|
236 | /* status of the structural variable: |
---|
237 | GLP_BS - basic variable |
---|
238 | GLP_NL - non-basic variable on lower bound |
---|
239 | GLP_NU - non-basic variable on upper bound |
---|
240 | GLP_NF - non-basic free variable |
---|
241 | GLP_NS - non-basic fixed variable */ |
---|
242 | int bind; |
---|
243 | /* if the structural variable is basic, head[bind] refers to |
---|
244 | this column; otherwise, bind is 0; this attribute is valid only |
---|
245 | if the basis factorization is valid */ |
---|
246 | double prim; /* non-scaled */ |
---|
247 | /* primal value of the structural variable in basic solution */ |
---|
248 | double dual; /* non-scaled */ |
---|
249 | /* dual value of the structural variable in basic solution */ |
---|
250 | double pval; /* non-scaled */ |
---|
251 | /* primal value of the structural variable in interior solution */ |
---|
252 | double dval; /* non-scaled */ |
---|
253 | /* dual value of the structural variable in interior solution */ |
---|
254 | double mipx; /* non-scaled */ |
---|
255 | /* primal value of the structural variable in integer solution */ |
---|
256 | }; |
---|
257 | |
---|
258 | struct GLPAIJ |
---|
259 | { /* constraint coefficient a[i,j] */ |
---|
260 | GLPROW *row; |
---|
261 | /* pointer to row, where this coefficient is placed */ |
---|
262 | GLPCOL *col; |
---|
263 | /* pointer to column, where this coefficient is placed */ |
---|
264 | double val; |
---|
265 | /* numeric (non-zero) value of this coefficient */ |
---|
266 | GLPAIJ *r_prev; |
---|
267 | /* pointer to previous coefficient in the same row */ |
---|
268 | GLPAIJ *r_next; |
---|
269 | /* pointer to next coefficient in the same row */ |
---|
270 | GLPAIJ *c_prev; |
---|
271 | /* pointer to previous coefficient in the same column */ |
---|
272 | GLPAIJ *c_next; |
---|
273 | /* pointer to next coefficient in the same column */ |
---|
274 | }; |
---|
275 | |
---|
276 | void _glp_check_kkt(glp_prob *P, int sol, int cond, double *ae_max, |
---|
277 | int *ae_ind, double *re_max, int *re_ind); |
---|
278 | /* check feasibility and optimality conditions */ |
---|
279 | |
---|
280 | #define lpx_put_solution _glp_put_solution |
---|
281 | void lpx_put_solution(glp_prob *lp, int inval, const int *p_stat, |
---|
282 | const int *d_stat, const double *obj_val, const int r_stat[], |
---|
283 | const double r_prim[], const double r_dual[], const int c_stat[], |
---|
284 | const double c_prim[], const double c_dual[]); |
---|
285 | /* store basic solution components */ |
---|
286 | |
---|
287 | #define lpx_put_mip_soln _glp_put_mip_soln |
---|
288 | void lpx_put_mip_soln(LPX *lp, int i_stat, double row_mipx[], |
---|
289 | double col_mipx[]); |
---|
290 | /* store mixed integer solution components */ |
---|
291 | |
---|
292 | #if 1 /* 28/XI-2009 */ |
---|
293 | int _glp_analyze_row(glp_prob *P, int len, const int ind[], |
---|
294 | const double val[], int type, double rhs, double eps, int *_piv, |
---|
295 | double *_x, double *_dx, double *_y, double *_dy, double *_dz); |
---|
296 | /* simulate one iteration of dual simplex method */ |
---|
297 | #endif |
---|
298 | |
---|
299 | #if 1 /* 08/XII-2009 */ |
---|
300 | void _glp_mpl_init_rand(glp_tran *tran, int seed); |
---|
301 | #endif |
---|
302 | |
---|
303 | #define glp_skpgen _glp_skpgen |
---|
304 | void glp_skpgen(int n, int r, int type, int v, int s, int a[], |
---|
305 | int *b, int c[]); |
---|
306 | /* Pisinger's 0-1 single knapsack problem generator */ |
---|
307 | |
---|
308 | #if 1 /* 28/V-2010 */ |
---|
309 | int _glp_intopt1(glp_prob *P, const glp_iocp *parm); |
---|
310 | #endif |
---|
311 | |
---|
312 | #endif |
---|
313 | |
---|
314 | /* eof */ |
---|