|
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 */ |