1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/deps/glpk/src/glpapi.h	Sun Nov 06 20:59:10 2011 +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, 2011 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 +      unsigned 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 */