1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/glpapi.h Mon Dec 06 13:09:21 2010 +0100
1.3 @@ -0,0 +1,314 @@
1.4 +/* glpapi.h (application program interface) */
1.5 +
1.6 +/***********************************************************************
1.7 +* This code is part of GLPK (GNU Linear Programming Kit).
1.8 +*
1.9 +* Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
1.10 +* 2009, 2010 Andrew Makhorin, Department for Applied Informatics,
1.11 +* Moscow Aviation Institute, Moscow, Russia. All rights reserved.
1.12 +* E-mail: <mao@gnu.org>.
1.13 +*
1.14 +* GLPK is free software: you can redistribute it and/or modify it
1.15 +* under the terms of the GNU General Public License as published by
1.16 +* the Free Software Foundation, either version 3 of the License, or
1.17 +* (at your option) any later version.
1.18 +*
1.19 +* GLPK is distributed in the hope that it will be useful, but WITHOUT
1.20 +* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
1.21 +* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
1.22 +* License for more details.
1.23 +*
1.24 +* You should have received a copy of the GNU General Public License
1.25 +* along with GLPK. If not, see <http://www.gnu.org/licenses/>.
1.26 +***********************************************************************/
1.27 +
1.28 +#ifndef GLPAPI_H
1.29 +#define GLPAPI_H
1.30 +
1.31 +#define GLP_PROB_DEFINED
1.32 +typedef struct glp_prob glp_prob;
1.33 +
1.34 +#include "glpk.h"
1.35 +#include "glpavl.h"
1.36 +#include "glpbfd.h"
1.37 +
1.38 +typedef struct GLPROW GLPROW;
1.39 +typedef struct GLPCOL GLPCOL;
1.40 +typedef struct GLPAIJ GLPAIJ;
1.41 +
1.42 +#define GLP_PROB_MAGIC 0xD7D9D6C2
1.43 +
1.44 +struct glp_prob
1.45 +{ /* LP/MIP problem object */
1.46 + int magic;
1.47 + /* magic value used for debugging */
1.48 + DMP *pool;
1.49 + /* memory pool to store problem object components */
1.50 + glp_tree *tree;
1.51 + /* pointer to the search tree; set by the MIP solver when this
1.52 + object is used in the tree as a core MIP object */
1.53 + void *parms;
1.54 + /* reserved for backward compatibility */
1.55 + /*--------------------------------------------------------------*/
1.56 + /* LP/MIP data */
1.57 + char *name;
1.58 + /* problem name (1 to 255 chars); NULL means no name is assigned
1.59 + to the problem */
1.60 + char *obj;
1.61 + /* objective function name (1 to 255 chars); NULL means no name
1.62 + is assigned to the objective function */
1.63 + int dir;
1.64 + /* optimization direction flag (objective "sense"):
1.65 + GLP_MIN - minimization
1.66 + GLP_MAX - maximization */
1.67 + double c0;
1.68 + /* constant term of the objective function ("shift") */
1.69 + int m_max;
1.70 + /* length of the array of rows (enlarged automatically) */
1.71 + int n_max;
1.72 + /* length of the array of columns (enlarged automatically) */
1.73 + int m;
1.74 + /* number of rows, 0 <= m <= m_max */
1.75 + int n;
1.76 + /* number of columns, 0 <= n <= n_max */
1.77 + int nnz;
1.78 + /* number of non-zero constraint coefficients, nnz >= 0 */
1.79 + GLPROW **row; /* GLPROW *row[1+m_max]; */
1.80 + /* row[i], 1 <= i <= m, is a pointer to i-th row */
1.81 + GLPCOL **col; /* GLPCOL *col[1+n_max]; */
1.82 + /* col[j], 1 <= j <= n, is a pointer to j-th column */
1.83 + AVL *r_tree;
1.84 + /* row index to find rows by their names; NULL means this index
1.85 + does not exist */
1.86 + AVL *c_tree;
1.87 + /* column index to find columns by their names; NULL means this
1.88 + index does not exist */
1.89 + /*--------------------------------------------------------------*/
1.90 + /* basis factorization (LP) */
1.91 + int valid;
1.92 + /* the factorization is valid only if this flag is set */
1.93 + int *head; /* int head[1+m_max]; */
1.94 + /* basis header (valid only if the factorization is valid);
1.95 + head[i] = k is the ordinal number of auxiliary (1 <= k <= m)
1.96 + or structural (m+1 <= k <= m+n) variable which corresponds to
1.97 + i-th basic variable xB[i], 1 <= i <= m */
1.98 + glp_bfcp *bfcp;
1.99 + /* basis factorization control parameters; may be NULL */
1.100 + BFD *bfd; /* BFD bfd[1:m,1:m]; */
1.101 + /* basis factorization driver; may be NULL */
1.102 + /*--------------------------------------------------------------*/
1.103 + /* basic solution (LP) */
1.104 + int pbs_stat;
1.105 + /* primal basic solution status:
1.106 + GLP_UNDEF - primal solution is undefined
1.107 + GLP_FEAS - primal solution is feasible
1.108 + GLP_INFEAS - primal solution is infeasible
1.109 + GLP_NOFEAS - no primal feasible solution exists */
1.110 + int dbs_stat;
1.111 + /* dual basic solution status:
1.112 + GLP_UNDEF - dual solution is undefined
1.113 + GLP_FEAS - dual solution is feasible
1.114 + GLP_INFEAS - dual solution is infeasible
1.115 + GLP_NOFEAS - no dual feasible solution exists */
1.116 + double obj_val;
1.117 + /* objective function value */
1.118 + int it_cnt;
1.119 + /* simplex method iteration count; increased by one on performing
1.120 + one simplex iteration */
1.121 + int some;
1.122 + /* ordinal number of some auxiliary or structural variable having
1.123 + certain property, 0 <= some <= m+n */
1.124 + /*--------------------------------------------------------------*/
1.125 + /* interior-point solution (LP) */
1.126 + int ipt_stat;
1.127 + /* interior-point solution status:
1.128 + GLP_UNDEF - interior solution is undefined
1.129 + GLP_OPT - interior solution is optimal
1.130 + GLP_INFEAS - interior solution is infeasible
1.131 + GLP_NOFEAS - no feasible solution exists */
1.132 + double ipt_obj;
1.133 + /* objective function value */
1.134 + /*--------------------------------------------------------------*/
1.135 + /* integer solution (MIP) */
1.136 + int mip_stat;
1.137 + /* integer solution status:
1.138 + GLP_UNDEF - integer solution is undefined
1.139 + GLP_OPT - integer solution is optimal
1.140 + GLP_FEAS - integer solution is feasible
1.141 + GLP_NOFEAS - no integer solution exists */
1.142 + double mip_obj;
1.143 + /* objective function value */
1.144 +};
1.145 +
1.146 +struct GLPROW
1.147 +{ /* LP/MIP row (auxiliary variable) */
1.148 + int i;
1.149 + /* ordinal number (1 to m) assigned to this row */
1.150 + char *name;
1.151 + /* row name (1 to 255 chars); NULL means no name is assigned to
1.152 + this row */
1.153 + AVLNODE *node;
1.154 + /* pointer to corresponding node in the row index; NULL means
1.155 + that either the row index does not exist or this row has no
1.156 + name assigned */
1.157 +#if 1 /* 20/IX-2008 */
1.158 + int level;
1.159 + unsigned char origin;
1.160 + unsigned char klass;
1.161 +#endif
1.162 + int type;
1.163 + /* type of the auxiliary variable:
1.164 + GLP_FR - free variable
1.165 + GLP_LO - variable with lower bound
1.166 + GLP_UP - variable with upper bound
1.167 + GLP_DB - double-bounded variable
1.168 + GLP_FX - fixed variable */
1.169 + double lb; /* non-scaled */
1.170 + /* lower bound; if the row has no lower bound, lb is zero */
1.171 + double ub; /* non-scaled */
1.172 + /* upper bound; if the row has no upper bound, ub is zero */
1.173 + /* if the row type is GLP_FX, ub is equal to lb */
1.174 + GLPAIJ *ptr; /* non-scaled */
1.175 + /* pointer to doubly linked list of constraint coefficients which
1.176 + are placed in this row */
1.177 + double rii;
1.178 + /* diagonal element r[i,i] of scaling matrix R for this row;
1.179 + if the scaling is not used, r[i,i] is 1 */
1.180 + int stat;
1.181 + /* status of the auxiliary variable:
1.182 + GLP_BS - basic variable
1.183 + GLP_NL - non-basic variable on lower bound
1.184 + GLP_NU - non-basic variable on upper bound
1.185 + GLP_NF - non-basic free variable
1.186 + GLP_NS - non-basic fixed variable */
1.187 + int bind;
1.188 + /* if the auxiliary variable is basic, head[bind] refers to this
1.189 + row, otherwise, bind is 0; this attribute is valid only if the
1.190 + basis factorization is valid */
1.191 + double prim; /* non-scaled */
1.192 + /* primal value of the auxiliary variable in basic solution */
1.193 + double dual; /* non-scaled */
1.194 + /* dual value of the auxiliary variable in basic solution */
1.195 + double pval; /* non-scaled */
1.196 + /* primal value of the auxiliary variable in interior solution */
1.197 + double dval; /* non-scaled */
1.198 + /* dual value of the auxiliary variable in interior solution */
1.199 + double mipx; /* non-scaled */
1.200 + /* primal value of the auxiliary variable in integer solution */
1.201 +};
1.202 +
1.203 +struct GLPCOL
1.204 +{ /* LP/MIP column (structural variable) */
1.205 + int j;
1.206 + /* ordinal number (1 to n) assigned to this column */
1.207 + char *name;
1.208 + /* column name (1 to 255 chars); NULL means no name is assigned
1.209 + to this column */
1.210 + AVLNODE *node;
1.211 + /* pointer to corresponding node in the column index; NULL means
1.212 + that either the column index does not exist or the column has
1.213 + no name assigned */
1.214 + int kind;
1.215 + /* kind of the structural variable:
1.216 + GLP_CV - continuous variable
1.217 + GLP_IV - integer or binary variable */
1.218 + int type;
1.219 + /* type of the structural variable:
1.220 + GLP_FR - free variable
1.221 + GLP_LO - variable with lower bound
1.222 + GLP_UP - variable with upper bound
1.223 + GLP_DB - double-bounded variable
1.224 + GLP_FX - fixed variable */
1.225 + double lb; /* non-scaled */
1.226 + /* lower bound; if the column has no lower bound, lb is zero */
1.227 + double ub; /* non-scaled */
1.228 + /* upper bound; if the column has no upper bound, ub is zero */
1.229 + /* if the column type is GLP_FX, ub is equal to lb */
1.230 + double coef; /* non-scaled */
1.231 + /* objective coefficient at the structural variable */
1.232 + GLPAIJ *ptr; /* non-scaled */
1.233 + /* pointer to doubly linked list of constraint coefficients which
1.234 + are placed in this column */
1.235 + double sjj;
1.236 + /* diagonal element s[j,j] of scaling matrix S for this column;
1.237 + if the scaling is not used, s[j,j] is 1 */
1.238 + int stat;
1.239 + /* status of the structural variable:
1.240 + GLP_BS - basic variable
1.241 + GLP_NL - non-basic variable on lower bound
1.242 + GLP_NU - non-basic variable on upper bound
1.243 + GLP_NF - non-basic free variable
1.244 + GLP_NS - non-basic fixed variable */
1.245 + int bind;
1.246 + /* if the structural variable is basic, head[bind] refers to
1.247 + this column; otherwise, bind is 0; this attribute is valid only
1.248 + if the basis factorization is valid */
1.249 + double prim; /* non-scaled */
1.250 + /* primal value of the structural variable in basic solution */
1.251 + double dual; /* non-scaled */
1.252 + /* dual value of the structural variable in basic solution */
1.253 + double pval; /* non-scaled */
1.254 + /* primal value of the structural variable in interior solution */
1.255 + double dval; /* non-scaled */
1.256 + /* dual value of the structural variable in interior solution */
1.257 + double mipx; /* non-scaled */
1.258 + /* primal value of the structural variable in integer solution */
1.259 +};
1.260 +
1.261 +struct GLPAIJ
1.262 +{ /* constraint coefficient a[i,j] */
1.263 + GLPROW *row;
1.264 + /* pointer to row, where this coefficient is placed */
1.265 + GLPCOL *col;
1.266 + /* pointer to column, where this coefficient is placed */
1.267 + double val;
1.268 + /* numeric (non-zero) value of this coefficient */
1.269 + GLPAIJ *r_prev;
1.270 + /* pointer to previous coefficient in the same row */
1.271 + GLPAIJ *r_next;
1.272 + /* pointer to next coefficient in the same row */
1.273 + GLPAIJ *c_prev;
1.274 + /* pointer to previous coefficient in the same column */
1.275 + GLPAIJ *c_next;
1.276 + /* pointer to next coefficient in the same column */
1.277 +};
1.278 +
1.279 +void _glp_check_kkt(glp_prob *P, int sol, int cond, double *ae_max,
1.280 + int *ae_ind, double *re_max, int *re_ind);
1.281 +/* check feasibility and optimality conditions */
1.282 +
1.283 +#define lpx_put_solution _glp_put_solution
1.284 +void lpx_put_solution(glp_prob *lp, int inval, const int *p_stat,
1.285 + const int *d_stat, const double *obj_val, const int r_stat[],
1.286 + const double r_prim[], const double r_dual[], const int c_stat[],
1.287 + const double c_prim[], const double c_dual[]);
1.288 +/* store basic solution components */
1.289 +
1.290 +#define lpx_put_mip_soln _glp_put_mip_soln
1.291 +void lpx_put_mip_soln(LPX *lp, int i_stat, double row_mipx[],
1.292 + double col_mipx[]);
1.293 +/* store mixed integer solution components */
1.294 +
1.295 +#if 1 /* 28/XI-2009 */
1.296 +int _glp_analyze_row(glp_prob *P, int len, const int ind[],
1.297 + const double val[], int type, double rhs, double eps, int *_piv,
1.298 + double *_x, double *_dx, double *_y, double *_dy, double *_dz);
1.299 +/* simulate one iteration of dual simplex method */
1.300 +#endif
1.301 +
1.302 +#if 1 /* 08/XII-2009 */
1.303 +void _glp_mpl_init_rand(glp_tran *tran, int seed);
1.304 +#endif
1.305 +
1.306 +#define glp_skpgen _glp_skpgen
1.307 +void glp_skpgen(int n, int r, int type, int v, int s, int a[],
1.308 + int *b, int c[]);
1.309 +/* Pisinger's 0-1 single knapsack problem generator */
1.310 +
1.311 +#if 1 /* 28/V-2010 */
1.312 +int _glp_intopt1(glp_prob *P, const glp_iocp *parm);
1.313 +#endif
1.314 +
1.315 +#endif
1.316 +
1.317 +/* eof */