lemon-project-template-glpk

comparison deps/glpk/src/glpapi.h @ 9:33de93886c88

Import GLPK 4.47
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 20:59:10 +0100
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:08383d50fc76
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, 2011 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 unsigned 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 */