1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/glpnpp.h Mon Dec 06 13:09:21 2010 +0100
1.3 @@ -0,0 +1,520 @@
1.4 +/* glpnpp.h (LP/MIP preprocessor) */
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 GLPNPP_H
1.29 +#define GLPNPP_H
1.30 +
1.31 +#include "glpapi.h"
1.32 +
1.33 +typedef struct NPP NPP;
1.34 +typedef struct NPPROW NPPROW;
1.35 +typedef struct NPPCOL NPPCOL;
1.36 +typedef struct NPPAIJ NPPAIJ;
1.37 +typedef struct NPPTSE NPPTSE;
1.38 +typedef struct NPPLFE NPPLFE;
1.39 +
1.40 +struct NPP
1.41 +{ /* LP/MIP preprocessor workspace */
1.42 + /*--------------------------------------------------------------*/
1.43 + /* original problem segment */
1.44 + int orig_dir;
1.45 + /* optimization direction flag:
1.46 + GLP_MIN - minimization
1.47 + GLP_MAX - maximization */
1.48 + int orig_m;
1.49 + /* number of rows */
1.50 + int orig_n;
1.51 + /* number of columns */
1.52 + int orig_nnz;
1.53 + /* number of non-zero constraint coefficients */
1.54 + /*--------------------------------------------------------------*/
1.55 + /* transformed problem segment (always minimization) */
1.56 + DMP *pool;
1.57 + /* memory pool to store problem components */
1.58 + char *name;
1.59 + /* problem name (1 to 255 chars); NULL means no name is assigned
1.60 + to the problem */
1.61 + char *obj;
1.62 + /* objective function name (1 to 255 chars); NULL means no name
1.63 + is assigned to the objective function */
1.64 + double c0;
1.65 + /* constant term of the objective function */
1.66 + int nrows;
1.67 + /* number of rows introduced into the problem; this count
1.68 + increases by one every time a new row is added and never
1.69 + decreases; thus, actual number of rows may be less than nrows
1.70 + due to row deletions */
1.71 + int ncols;
1.72 + /* number of columns introduced into the problem; this count
1.73 + increases by one every time a new column is added and never
1.74 + decreases; thus, actual number of column may be less than
1.75 + ncols due to column deletions */
1.76 + NPPROW *r_head;
1.77 + /* pointer to the beginning of the row list */
1.78 + NPPROW *r_tail;
1.79 + /* pointer to the end of the row list */
1.80 + NPPCOL *c_head;
1.81 + /* pointer to the beginning of the column list */
1.82 + NPPCOL *c_tail;
1.83 + /* pointer to the end of the column list */
1.84 + /*--------------------------------------------------------------*/
1.85 + /* transformation history */
1.86 + DMP *stack;
1.87 + /* memory pool to store transformation entries */
1.88 + NPPTSE *top;
1.89 + /* pointer to most recent transformation entry */
1.90 +#if 0 /* 16/XII-2009 */
1.91 + int count[1+25];
1.92 + /* transformation statistics */
1.93 +#endif
1.94 + /*--------------------------------------------------------------*/
1.95 + /* resultant (preprocessed) problem segment */
1.96 + int m;
1.97 + /* number of rows */
1.98 + int n;
1.99 + /* number of columns */
1.100 + int nnz;
1.101 + /* number of non-zero constraint coefficients */
1.102 + int *row_ref; /* int row_ref[1+m]; */
1.103 + /* row_ref[i], 1 <= i <= m, is the reference number assigned to
1.104 + a row, which is i-th row of the resultant problem */
1.105 + int *col_ref; /* int col_ref[1+n]; */
1.106 + /* col_ref[j], 1 <= j <= n, is the reference number assigned to
1.107 + a column, which is j-th column of the resultant problem */
1.108 + /*--------------------------------------------------------------*/
1.109 + /* recovered solution segment */
1.110 + int sol;
1.111 + /* solution indicator:
1.112 + GLP_SOL - basic solution
1.113 + GLP_IPT - interior-point solution
1.114 + GLP_MIP - mixed integer solution */
1.115 + int scaling;
1.116 + /* scaling option:
1.117 + GLP_OFF - scaling is disabled
1.118 + GLP_ON - scaling is enabled */
1.119 + int p_stat;
1.120 + /* status of primal basic solution:
1.121 + GLP_UNDEF - primal solution is undefined
1.122 + GLP_FEAS - primal solution is feasible
1.123 + GLP_INFEAS - primal solution is infeasible
1.124 + GLP_NOFEAS - no primal feasible solution exists */
1.125 + int d_stat;
1.126 + /* status of dual basic solution:
1.127 + GLP_UNDEF - dual solution is undefined
1.128 + GLP_FEAS - dual solution is feasible
1.129 + GLP_INFEAS - dual solution is infeasible
1.130 + GLP_NOFEAS - no dual feasible solution exists */
1.131 + int t_stat;
1.132 + /* status of interior-point solution:
1.133 + GLP_UNDEF - interior solution is undefined
1.134 + GLP_OPT - interior solution is optimal */
1.135 + int i_stat;
1.136 + /* status of mixed integer solution:
1.137 + GLP_UNDEF - integer solution is undefined
1.138 + GLP_OPT - integer solution is optimal
1.139 + GLP_FEAS - integer solution is feasible
1.140 + GLP_NOFEAS - no integer solution exists */
1.141 + char *r_stat; /* char r_stat[1+nrows]; */
1.142 + /* r_stat[i], 1 <= i <= nrows, is status of i-th row:
1.143 + GLP_BS - inactive constraint
1.144 + GLP_NL - active constraint on lower bound
1.145 + GLP_NU - active constraint on upper bound
1.146 + GLP_NF - active free row
1.147 + GLP_NS - active equality constraint */
1.148 + char *c_stat; /* char c_stat[1+nrows]; */
1.149 + /* c_stat[j], 1 <= j <= nrows, is status of j-th column:
1.150 + GLP_BS - basic variable
1.151 + GLP_NL - non-basic variable on lower bound
1.152 + GLP_NU - non-basic variable on upper bound
1.153 + GLP_NF - non-basic free variable
1.154 + GLP_NS - non-basic fixed variable */
1.155 + double *r_pi; /* double r_pi[1+nrows]; */
1.156 + /* r_pi[i], 1 <= i <= nrows, is Lagrange multiplier (dual value)
1.157 + for i-th row (constraint) */
1.158 + double *c_value; /* double c_value[1+ncols]; */
1.159 + /* c_value[j], 1 <= j <= ncols, is primal value of j-th column
1.160 + (structural variable) */
1.161 +};
1.162 +
1.163 +struct NPPROW
1.164 +{ /* row (constraint) */
1.165 + int i;
1.166 + /* reference number assigned to the row, 1 <= i <= nrows */
1.167 + char *name;
1.168 + /* row name (1 to 255 chars); NULL means no name is assigned to
1.169 + the row */
1.170 + double lb;
1.171 + /* lower bound; -DBL_MAX means the row has no lower bound */
1.172 + double ub;
1.173 + /* upper bound; +DBL_MAX means the row has no upper bound */
1.174 + NPPAIJ *ptr;
1.175 + /* pointer to the linked list of constraint coefficients */
1.176 + int temp;
1.177 + /* working field used by preprocessor routines */
1.178 + NPPROW *prev;
1.179 + /* pointer to previous row in the row list */
1.180 + NPPROW *next;
1.181 + /* pointer to next row in the row list */
1.182 +};
1.183 +
1.184 +struct NPPCOL
1.185 +{ /* column (variable) */
1.186 + int j;
1.187 + /* reference number assigned to the column, 1 <= j <= ncols */
1.188 + char *name;
1.189 + /* column name (1 to 255 chars); NULL means no name is assigned
1.190 + to the column */
1.191 + char is_int;
1.192 + /* 0 means continuous variable; 1 means integer variable */
1.193 + double lb;
1.194 + /* lower bound; -DBL_MAX means the column has no lower bound */
1.195 + double ub;
1.196 + /* upper bound; +DBL_MAX means the column has no upper bound */
1.197 + double coef;
1.198 + /* objective coefficient */
1.199 + NPPAIJ *ptr;
1.200 + /* pointer to the linked list of constraint coefficients */
1.201 + int temp;
1.202 + /* working field used by preprocessor routines */
1.203 +#if 1 /* 28/XII-2009 */
1.204 + union
1.205 + { double ll;
1.206 + /* implied column lower bound */
1.207 + int pos;
1.208 + /* vertex ordinal number corresponding to this binary column
1.209 + in the conflict graph (0, if the vertex does not exist) */
1.210 + } ll;
1.211 + union
1.212 + { double uu;
1.213 + /* implied column upper bound */
1.214 + int neg;
1.215 + /* vertex ordinal number corresponding to complement of this
1.216 + binary column in the conflict graph (0, if the vertex does
1.217 + not exist) */
1.218 + } uu;
1.219 +#endif
1.220 + NPPCOL *prev;
1.221 + /* pointer to previous column in the column list */
1.222 + NPPCOL *next;
1.223 + /* pointer to next column in the column list */
1.224 +};
1.225 +
1.226 +struct NPPAIJ
1.227 +{ /* constraint coefficient */
1.228 + NPPROW *row;
1.229 + /* pointer to corresponding row */
1.230 + NPPCOL *col;
1.231 + /* pointer to corresponding column */
1.232 + double val;
1.233 + /* (non-zero) coefficient value */
1.234 + NPPAIJ *r_prev;
1.235 + /* pointer to previous coefficient in the same row */
1.236 + NPPAIJ *r_next;
1.237 + /* pointer to next coefficient in the same row */
1.238 + NPPAIJ *c_prev;
1.239 + /* pointer to previous coefficient in the same column */
1.240 + NPPAIJ *c_next;
1.241 + /* pointer to next coefficient in the same column */
1.242 +};
1.243 +
1.244 +struct NPPTSE
1.245 +{ /* transformation stack entry */
1.246 + int (*func)(NPP *npp, void *info);
1.247 + /* pointer to routine performing back transformation */
1.248 + void *info;
1.249 + /* pointer to specific info (depends on the transformation) */
1.250 + NPPTSE *link;
1.251 + /* pointer to another entry created *before* this entry */
1.252 +};
1.253 +
1.254 +struct NPPLFE
1.255 +{ /* linear form element */
1.256 + int ref;
1.257 + /* row/column reference number */
1.258 + double val;
1.259 + /* (non-zero) coefficient value */
1.260 + NPPLFE *next;
1.261 + /* pointer to another element */
1.262 +};
1.263 +
1.264 +#define npp_create_wksp _glp_npp_create_wksp
1.265 +NPP *npp_create_wksp(void);
1.266 +/* create LP/MIP preprocessor workspace */
1.267 +
1.268 +#define npp_insert_row _glp_npp_insert_row
1.269 +void npp_insert_row(NPP *npp, NPPROW *row, int where);
1.270 +/* insert row to the row list */
1.271 +
1.272 +#define npp_remove_row _glp_npp_remove_row
1.273 +void npp_remove_row(NPP *npp, NPPROW *row);
1.274 +/* remove row from the row list */
1.275 +
1.276 +#define npp_activate_row _glp_npp_activate_row
1.277 +void npp_activate_row(NPP *npp, NPPROW *row);
1.278 +/* make row active */
1.279 +
1.280 +#define npp_deactivate_row _glp_npp_deactivate_row
1.281 +void npp_deactivate_row(NPP *npp, NPPROW *row);
1.282 +/* make row inactive */
1.283 +
1.284 +#define npp_insert_col _glp_npp_insert_col
1.285 +void npp_insert_col(NPP *npp, NPPCOL *col, int where);
1.286 +/* insert column to the column list */
1.287 +
1.288 +#define npp_remove_col _glp_npp_remove_col
1.289 +void npp_remove_col(NPP *npp, NPPCOL *col);
1.290 +/* remove column from the column list */
1.291 +
1.292 +#define npp_activate_col _glp_npp_activate_col
1.293 +void npp_activate_col(NPP *npp, NPPCOL *col);
1.294 +/* make column active */
1.295 +
1.296 +#define npp_deactivate_col _glp_npp_deactivate_col
1.297 +void npp_deactivate_col(NPP *npp, NPPCOL *col);
1.298 +/* make column inactive */
1.299 +
1.300 +#define npp_add_row _glp_npp_add_row
1.301 +NPPROW *npp_add_row(NPP *npp);
1.302 +/* add new row to the current problem */
1.303 +
1.304 +#define npp_add_col _glp_npp_add_col
1.305 +NPPCOL *npp_add_col(NPP *npp);
1.306 +/* add new column to the current problem */
1.307 +
1.308 +#define npp_add_aij _glp_npp_add_aij
1.309 +NPPAIJ *npp_add_aij(NPP *npp, NPPROW *row, NPPCOL *col, double val);
1.310 +/* add new element to the constraint matrix */
1.311 +
1.312 +#define npp_row_nnz _glp_npp_row_nnz
1.313 +int npp_row_nnz(NPP *npp, NPPROW *row);
1.314 +/* count number of non-zero coefficients in row */
1.315 +
1.316 +#define npp_col_nnz _glp_npp_col_nnz
1.317 +int npp_col_nnz(NPP *npp, NPPCOL *col);
1.318 +/* count number of non-zero coefficients in column */
1.319 +
1.320 +#define npp_push_tse _glp_npp_push_tse
1.321 +void *npp_push_tse(NPP *npp, int (*func)(NPP *npp, void *info),
1.322 + int size);
1.323 +/* push new entry to the transformation stack */
1.324 +
1.325 +#define npp_erase_row _glp_npp_erase_row
1.326 +void npp_erase_row(NPP *npp, NPPROW *row);
1.327 +/* erase row content to make it empty */
1.328 +
1.329 +#define npp_del_row _glp_npp_del_row
1.330 +void npp_del_row(NPP *npp, NPPROW *row);
1.331 +/* remove row from the current problem */
1.332 +
1.333 +#define npp_del_col _glp_npp_del_col
1.334 +void npp_del_col(NPP *npp, NPPCOL *col);
1.335 +/* remove column from the current problem */
1.336 +
1.337 +#define npp_del_aij _glp_npp_del_aij
1.338 +void npp_del_aij(NPP *npp, NPPAIJ *aij);
1.339 +/* remove element from the constraint matrix */
1.340 +
1.341 +#define npp_load_prob _glp_npp_load_prob
1.342 +void npp_load_prob(NPP *npp, glp_prob *orig, int names, int sol,
1.343 + int scaling);
1.344 +/* load original problem into the preprocessor workspace */
1.345 +
1.346 +#define npp_build_prob _glp_npp_build_prob
1.347 +void npp_build_prob(NPP *npp, glp_prob *prob);
1.348 +/* build resultant (preprocessed) problem */
1.349 +
1.350 +#define npp_postprocess _glp_npp_postprocess
1.351 +void npp_postprocess(NPP *npp, glp_prob *prob);
1.352 +/* postprocess solution from the resultant problem */
1.353 +
1.354 +#define npp_unload_sol _glp_npp_unload_sol
1.355 +void npp_unload_sol(NPP *npp, glp_prob *orig);
1.356 +/* store solution to the original problem */
1.357 +
1.358 +#define npp_delete_wksp _glp_npp_delete_wksp
1.359 +void npp_delete_wksp(NPP *npp);
1.360 +/* delete LP/MIP preprocessor workspace */
1.361 +
1.362 +#define npp_error()
1.363 +
1.364 +#define npp_free_row _glp_npp_free_row
1.365 +void npp_free_row(NPP *npp, NPPROW *p);
1.366 +/* process free (unbounded) row */
1.367 +
1.368 +#define npp_geq_row _glp_npp_geq_row
1.369 +void npp_geq_row(NPP *npp, NPPROW *p);
1.370 +/* process row of 'not less than' type */
1.371 +
1.372 +#define npp_leq_row _glp_npp_leq_row
1.373 +void npp_leq_row(NPP *npp, NPPROW *p);
1.374 +/* process row of 'not greater than' type */
1.375 +
1.376 +#define npp_free_col _glp_npp_free_col
1.377 +void npp_free_col(NPP *npp, NPPCOL *q);
1.378 +/* process free (unbounded) column */
1.379 +
1.380 +#define npp_lbnd_col _glp_npp_lbnd_col
1.381 +void npp_lbnd_col(NPP *npp, NPPCOL *q);
1.382 +/* process column with (non-zero) lower bound */
1.383 +
1.384 +#define npp_ubnd_col _glp_npp_ubnd_col
1.385 +void npp_ubnd_col(NPP *npp, NPPCOL *q);
1.386 +/* process column with upper bound */
1.387 +
1.388 +#define npp_dbnd_col _glp_npp_dbnd_col
1.389 +void npp_dbnd_col(NPP *npp, NPPCOL *q);
1.390 +/* process non-negative column with upper bound */
1.391 +
1.392 +#define npp_fixed_col _glp_npp_fixed_col
1.393 +void npp_fixed_col(NPP *npp, NPPCOL *q);
1.394 +/* process fixed column */
1.395 +
1.396 +#define npp_make_equality _glp_npp_make_equality
1.397 +int npp_make_equality(NPP *npp, NPPROW *p);
1.398 +/* process row with almost identical bounds */
1.399 +
1.400 +#define npp_make_fixed _glp_npp_make_fixed
1.401 +int npp_make_fixed(NPP *npp, NPPCOL *q);
1.402 +/* process column with almost identical bounds */
1.403 +
1.404 +#define npp_empty_row _glp_npp_empty_row
1.405 +int npp_empty_row(NPP *npp, NPPROW *p);
1.406 +/* process empty row */
1.407 +
1.408 +#define npp_empty_col _glp_npp_empty_col
1.409 +int npp_empty_col(NPP *npp, NPPCOL *q);
1.410 +/* process empty column */
1.411 +
1.412 +#define npp_implied_value _glp_npp_implied_value
1.413 +int npp_implied_value(NPP *npp, NPPCOL *q, double s);
1.414 +/* process implied column value */
1.415 +
1.416 +#define npp_eq_singlet _glp_npp_eq_singlet
1.417 +int npp_eq_singlet(NPP *npp, NPPROW *p);
1.418 +/* process row singleton (equality constraint) */
1.419 +
1.420 +#define npp_implied_lower _glp_npp_implied_lower
1.421 +int npp_implied_lower(NPP *npp, NPPCOL *q, double l);
1.422 +/* process implied column lower bound */
1.423 +
1.424 +#define npp_implied_upper _glp_npp_implied_upper
1.425 +int npp_implied_upper(NPP *npp, NPPCOL *q, double u);
1.426 +/* process implied upper bound of column */
1.427 +
1.428 +#define npp_ineq_singlet _glp_npp_ineq_singlet
1.429 +int npp_ineq_singlet(NPP *npp, NPPROW *p);
1.430 +/* process row singleton (inequality constraint) */
1.431 +
1.432 +#define npp_implied_slack _glp_npp_implied_slack
1.433 +void npp_implied_slack(NPP *npp, NPPCOL *q);
1.434 +/* process column singleton (implied slack variable) */
1.435 +
1.436 +#define npp_implied_free _glp_npp_implied_free
1.437 +int npp_implied_free(NPP *npp, NPPCOL *q);
1.438 +/* process column singleton (implied free variable) */
1.439 +
1.440 +#define npp_eq_doublet _glp_npp_eq_doublet
1.441 +NPPCOL *npp_eq_doublet(NPP *npp, NPPROW *p);
1.442 +/* process row doubleton (equality constraint) */
1.443 +
1.444 +#define npp_forcing_row _glp_npp_forcing_row
1.445 +int npp_forcing_row(NPP *npp, NPPROW *p, int at);
1.446 +/* process forcing row */
1.447 +
1.448 +#define npp_analyze_row _glp_npp_analyze_row
1.449 +int npp_analyze_row(NPP *npp, NPPROW *p);
1.450 +/* perform general row analysis */
1.451 +
1.452 +#define npp_inactive_bound _glp_npp_inactive_bound
1.453 +void npp_inactive_bound(NPP *npp, NPPROW *p, int which);
1.454 +/* remove row lower/upper inactive bound */
1.455 +
1.456 +#define npp_implied_bounds _glp_npp_implied_bounds
1.457 +void npp_implied_bounds(NPP *npp, NPPROW *p);
1.458 +/* determine implied column bounds */
1.459 +
1.460 +#define npp_binarize_prob _glp_npp_binarize_prob
1.461 +int npp_binarize_prob(NPP *npp);
1.462 +/* binarize MIP problem */
1.463 +
1.464 +#define npp_is_packing _glp_npp_is_packing
1.465 +int npp_is_packing(NPP *npp, NPPROW *row);
1.466 +/* test if constraint is packing inequality */
1.467 +
1.468 +#define npp_hidden_packing _glp_npp_hidden_packing
1.469 +int npp_hidden_packing(NPP *npp, NPPROW *row);
1.470 +/* identify hidden packing inequality */
1.471 +
1.472 +#define npp_implied_packing _glp_npp_implied_packing
1.473 +int npp_implied_packing(NPP *npp, NPPROW *row, int which,
1.474 + NPPCOL *var[], char set[]);
1.475 +/* identify implied packing inequality */
1.476 +
1.477 +#define npp_is_covering _glp_npp_is_covering
1.478 +int npp_is_covering(NPP *npp, NPPROW *row);
1.479 +/* test if constraint is covering inequality */
1.480 +
1.481 +#define npp_hidden_covering _glp_npp_hidden_covering
1.482 +int npp_hidden_covering(NPP *npp, NPPROW *row);
1.483 +/* identify hidden covering inequality */
1.484 +
1.485 +#define npp_is_partitioning _glp_npp_is_partitioning
1.486 +int npp_is_partitioning(NPP *npp, NPPROW *row);
1.487 +/* test if constraint is partitioning equality */
1.488 +
1.489 +#define npp_reduce_ineq_coef _glp_npp_reduce_ineq_coef
1.490 +int npp_reduce_ineq_coef(NPP *npp, NPPROW *row);
1.491 +/* reduce inequality constraint coefficients */
1.492 +
1.493 +#define npp_clean_prob _glp_npp_clean_prob
1.494 +void npp_clean_prob(NPP *npp);
1.495 +/* perform initial LP/MIP processing */
1.496 +
1.497 +#define npp_process_row _glp_npp_process_row
1.498 +int npp_process_row(NPP *npp, NPPROW *row, int hard);
1.499 +/* perform basic row processing */
1.500 +
1.501 +#define npp_improve_bounds _glp_npp_improve_bounds
1.502 +int npp_improve_bounds(NPP *npp, NPPROW *row, int flag);
1.503 +/* improve current column bounds */
1.504 +
1.505 +#define npp_process_col _glp_npp_process_col
1.506 +int npp_process_col(NPP *npp, NPPCOL *col);
1.507 +/* perform basic column processing */
1.508 +
1.509 +#define npp_process_prob _glp_npp_process_prob
1.510 +int npp_process_prob(NPP *npp, int hard);
1.511 +/* perform basic LP/MIP processing */
1.512 +
1.513 +#define npp_simplex _glp_npp_simplex
1.514 +int npp_simplex(NPP *npp, const glp_smcp *parm);
1.515 +/* process LP prior to applying primal/dual simplex method */
1.516 +
1.517 +#define npp_integer _glp_npp_integer
1.518 +int npp_integer(NPP *npp, const glp_iocp *parm);
1.519 +/* process MIP prior to applying branch-and-bound method */
1.520 +
1.521 +#endif
1.522 +
1.523 +/* eof */