lemon-project-template-glpk
diff deps/glpk/src/glpnpp.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 |
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/deps/glpk/src/glpnpp.h Sun Nov 06 20:59:10 2011 +0100 1.3 @@ -0,0 +1,638 @@ 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, 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 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 +/**********************************************************************/ 1.522 + 1.523 +#define npp_sat_free_row _glp_npp_sat_free_row 1.524 +void npp_sat_free_row(NPP *npp, NPPROW *p); 1.525 +/* process free (unbounded) row */ 1.526 + 1.527 +#define npp_sat_fixed_col _glp_npp_sat_fixed_col 1.528 +int npp_sat_fixed_col(NPP *npp, NPPCOL *q); 1.529 +/* process fixed column */ 1.530 + 1.531 +#define npp_sat_is_bin_comb _glp_npp_sat_is_bin_comb 1.532 +int npp_sat_is_bin_comb(NPP *npp, NPPROW *row); 1.533 +/* test if row is binary combination */ 1.534 + 1.535 +#define npp_sat_num_pos_coef _glp_npp_sat_num_pos_coef 1.536 +int npp_sat_num_pos_coef(NPP *npp, NPPROW *row); 1.537 +/* determine number of positive coefficients */ 1.538 + 1.539 +#define npp_sat_num_neg_coef _glp_npp_sat_num_neg_coef 1.540 +int npp_sat_num_neg_coef(NPP *npp, NPPROW *row); 1.541 +/* determine number of negative coefficients */ 1.542 + 1.543 +#define npp_sat_is_cover_ineq _glp_npp_sat_is_cover_ineq 1.544 +int npp_sat_is_cover_ineq(NPP *npp, NPPROW *row); 1.545 +/* test if row is covering inequality */ 1.546 + 1.547 +#define npp_sat_is_pack_ineq _glp_npp_sat_is_pack_ineq 1.548 +int npp_sat_is_pack_ineq(NPP *npp, NPPROW *row); 1.549 +/* test if row is packing inequality */ 1.550 + 1.551 +#define npp_sat_is_partn_eq _glp_npp_sat_is_partn_eq 1.552 +int npp_sat_is_partn_eq(NPP *npp, NPPROW *row); 1.553 +/* test if row is partitioning equality */ 1.554 + 1.555 +#define npp_sat_reverse_row _glp_npp_sat_reverse_row 1.556 +int npp_sat_reverse_row(NPP *npp, NPPROW *row); 1.557 +/* multiply both sides of row by -1 */ 1.558 + 1.559 +#define npp_sat_split_pack _glp_npp_sat_split_pack 1.560 +NPPROW *npp_sat_split_pack(NPP *npp, NPPROW *row, int nnn); 1.561 +/* split packing inequality */ 1.562 + 1.563 +#define npp_sat_encode_pack _glp_npp_sat_encode_pack 1.564 +void npp_sat_encode_pack(NPP *npp, NPPROW *row); 1.565 +/* encode packing inequality */ 1.566 + 1.567 +typedef struct NPPLIT NPPLIT; 1.568 +typedef struct NPPLSE NPPLSE; 1.569 +typedef struct NPPSED NPPSED; 1.570 + 1.571 +struct NPPLIT 1.572 +{ /* literal (binary variable or its negation) */ 1.573 + NPPCOL *col; 1.574 + /* pointer to binary variable; NULL means constant false */ 1.575 + int neg; 1.576 + /* negation flag: 1.577 + 0 - literal is variable (or constant false) 1.578 + 1 - literal is negation of variable (or constant true) */ 1.579 +}; 1.580 + 1.581 +struct NPPLSE 1.582 +{ /* literal set element */ 1.583 + NPPLIT lit; 1.584 + /* literal */ 1.585 + NPPLSE *next; 1.586 + /* pointer to another element */ 1.587 +}; 1.588 + 1.589 +struct NPPSED 1.590 +{ /* summation encoding descriptor */ 1.591 + /* this struct describes the equality 1.592 + x + y + z = s + 2 * c, 1.593 + which was encoded as CNF and included into the transformed 1.594 + problem; here x and y are literals, z is either a literal or 1.595 + constant zero, s and c are binary variables modeling, resp., 1.596 + the low and high (carry) sum bits */ 1.597 + NPPLIT x, y, z; 1.598 + /* literals; if z.col = NULL, z is constant zero */ 1.599 + NPPCOL *s, *c; 1.600 + /* binary variables modeling the sum bits */ 1.601 +}; 1.602 + 1.603 +#define npp_sat_encode_sum2 _glp_npp_sat_encode_sum2 1.604 +void npp_sat_encode_sum2(NPP *npp, NPPLSE *set, NPPSED *sed); 1.605 +/* encode 2-bit summation */ 1.606 + 1.607 +#define npp_sat_encode_sum3 _glp_npp_sat_encode_sum3 1.608 +void npp_sat_encode_sum3(NPP *npp, NPPLSE *set, NPPSED *sed); 1.609 +/* encode 3-bit summation */ 1.610 + 1.611 +#define npp_sat_encode_sum_ax _glp_npp_sat_encode_sum_ax 1.612 +int npp_sat_encode_sum_ax(NPP *npp, NPPROW *row, NPPLIT y[]); 1.613 +/* encode linear combination of 0-1 variables */ 1.614 + 1.615 +#define npp_sat_normalize_clause _glp_npp_sat_normalize_clause 1.616 +int npp_sat_normalize_clause(NPP *npp, int size, NPPLIT lit[]); 1.617 +/* normalize clause */ 1.618 + 1.619 +#define npp_sat_encode_clause _glp_npp_sat_encode_clause 1.620 +NPPROW *npp_sat_encode_clause(NPP *npp, int size, NPPLIT lit[]); 1.621 +/* translate clause to cover inequality */ 1.622 + 1.623 +#define npp_sat_encode_geq _glp_npp_sat_encode_geq 1.624 +int npp_sat_encode_geq(NPP *npp, int n, NPPLIT y[], int rhs); 1.625 +/* encode "not less than" constraint */ 1.626 + 1.627 +#define npp_sat_encode_leq _glp_npp_sat_encode_leq 1.628 +int npp_sat_encode_leq(NPP *npp, int n, NPPLIT y[], int rhs); 1.629 +/* encode "not greater than" constraint */ 1.630 + 1.631 +#define npp_sat_encode_row _glp_npp_sat_encode_row 1.632 +int npp_sat_encode_row(NPP *npp, NPPROW *row); 1.633 +/* encode constraint (row) of general type */ 1.634 + 1.635 +#define npp_sat_encode_prob _glp_npp_sat_encode_prob 1.636 +int npp_sat_encode_prob(NPP *npp); 1.637 +/* encode 0-1 feasibility problem */ 1.638 + 1.639 +#endif 1.640 + 1.641 +/* eof */