lemon-project-template-glpk

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

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