[9] | 1 | /* glpnpp.h (LP/MIP preprocessor) */ |
---|
| 2 | |
---|
| 3 | /*********************************************************************** |
---|
| 4 | * This code is part of GLPK (GNU Linear Programming Kit). |
---|
| 5 | * |
---|
| 6 | * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, |
---|
| 7 | * 2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics, |
---|
| 8 | * Moscow Aviation Institute, Moscow, Russia. All rights reserved. |
---|
| 9 | * E-mail: <mao@gnu.org>. |
---|
| 10 | * |
---|
| 11 | * GLPK is free software: you can redistribute it and/or modify it |
---|
| 12 | * under the terms of the GNU General Public License as published by |
---|
| 13 | * the Free Software Foundation, either version 3 of the License, or |
---|
| 14 | * (at your option) any later version. |
---|
| 15 | * |
---|
| 16 | * GLPK is distributed in the hope that it will be useful, but WITHOUT |
---|
| 17 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY |
---|
| 18 | * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public |
---|
| 19 | * License for more details. |
---|
| 20 | * |
---|
| 21 | * You should have received a copy of the GNU General Public License |
---|
| 22 | * along with GLPK. If not, see <http://www.gnu.org/licenses/>. |
---|
| 23 | ***********************************************************************/ |
---|
| 24 | |
---|
| 25 | #ifndef GLPNPP_H |
---|
| 26 | #define GLPNPP_H |
---|
| 27 | |
---|
| 28 | #include "glpapi.h" |
---|
| 29 | |
---|
| 30 | typedef struct NPP NPP; |
---|
| 31 | typedef struct NPPROW NPPROW; |
---|
| 32 | typedef struct NPPCOL NPPCOL; |
---|
| 33 | typedef struct NPPAIJ NPPAIJ; |
---|
| 34 | typedef struct NPPTSE NPPTSE; |
---|
| 35 | typedef struct NPPLFE NPPLFE; |
---|
| 36 | |
---|
| 37 | struct NPP |
---|
| 38 | { /* LP/MIP preprocessor workspace */ |
---|
| 39 | /*--------------------------------------------------------------*/ |
---|
| 40 | /* original problem segment */ |
---|
| 41 | int orig_dir; |
---|
| 42 | /* optimization direction flag: |
---|
| 43 | GLP_MIN - minimization |
---|
| 44 | GLP_MAX - maximization */ |
---|
| 45 | int orig_m; |
---|
| 46 | /* number of rows */ |
---|
| 47 | int orig_n; |
---|
| 48 | /* number of columns */ |
---|
| 49 | int orig_nnz; |
---|
| 50 | /* number of non-zero constraint coefficients */ |
---|
| 51 | /*--------------------------------------------------------------*/ |
---|
| 52 | /* transformed problem segment (always minimization) */ |
---|
| 53 | DMP *pool; |
---|
| 54 | /* memory pool to store problem components */ |
---|
| 55 | char *name; |
---|
| 56 | /* problem name (1 to 255 chars); NULL means no name is assigned |
---|
| 57 | to the problem */ |
---|
| 58 | char *obj; |
---|
| 59 | /* objective function name (1 to 255 chars); NULL means no name |
---|
| 60 | is assigned to the objective function */ |
---|
| 61 | double c0; |
---|
| 62 | /* constant term of the objective function */ |
---|
| 63 | int nrows; |
---|
| 64 | /* number of rows introduced into the problem; this count |
---|
| 65 | increases by one every time a new row is added and never |
---|
| 66 | decreases; thus, actual number of rows may be less than nrows |
---|
| 67 | due to row deletions */ |
---|
| 68 | int ncols; |
---|
| 69 | /* number of columns introduced into the problem; this count |
---|
| 70 | increases by one every time a new column is added and never |
---|
| 71 | decreases; thus, actual number of column may be less than |
---|
| 72 | ncols due to column deletions */ |
---|
| 73 | NPPROW *r_head; |
---|
| 74 | /* pointer to the beginning of the row list */ |
---|
| 75 | NPPROW *r_tail; |
---|
| 76 | /* pointer to the end of the row list */ |
---|
| 77 | NPPCOL *c_head; |
---|
| 78 | /* pointer to the beginning of the column list */ |
---|
| 79 | NPPCOL *c_tail; |
---|
| 80 | /* pointer to the end of the column list */ |
---|
| 81 | /*--------------------------------------------------------------*/ |
---|
| 82 | /* transformation history */ |
---|
| 83 | DMP *stack; |
---|
| 84 | /* memory pool to store transformation entries */ |
---|
| 85 | NPPTSE *top; |
---|
| 86 | /* pointer to most recent transformation entry */ |
---|
| 87 | #if 0 /* 16/XII-2009 */ |
---|
| 88 | int count[1+25]; |
---|
| 89 | /* transformation statistics */ |
---|
| 90 | #endif |
---|
| 91 | /*--------------------------------------------------------------*/ |
---|
| 92 | /* resultant (preprocessed) problem segment */ |
---|
| 93 | int m; |
---|
| 94 | /* number of rows */ |
---|
| 95 | int n; |
---|
| 96 | /* number of columns */ |
---|
| 97 | int nnz; |
---|
| 98 | /* number of non-zero constraint coefficients */ |
---|
| 99 | int *row_ref; /* int row_ref[1+m]; */ |
---|
| 100 | /* row_ref[i], 1 <= i <= m, is the reference number assigned to |
---|
| 101 | a row, which is i-th row of the resultant problem */ |
---|
| 102 | int *col_ref; /* int col_ref[1+n]; */ |
---|
| 103 | /* col_ref[j], 1 <= j <= n, is the reference number assigned to |
---|
| 104 | a column, which is j-th column of the resultant problem */ |
---|
| 105 | /*--------------------------------------------------------------*/ |
---|
| 106 | /* recovered solution segment */ |
---|
| 107 | int sol; |
---|
| 108 | /* solution indicator: |
---|
| 109 | GLP_SOL - basic solution |
---|
| 110 | GLP_IPT - interior-point solution |
---|
| 111 | GLP_MIP - mixed integer solution */ |
---|
| 112 | int scaling; |
---|
| 113 | /* scaling option: |
---|
| 114 | GLP_OFF - scaling is disabled |
---|
| 115 | GLP_ON - scaling is enabled */ |
---|
| 116 | int p_stat; |
---|
| 117 | /* status of primal basic solution: |
---|
| 118 | GLP_UNDEF - primal solution is undefined |
---|
| 119 | GLP_FEAS - primal solution is feasible |
---|
| 120 | GLP_INFEAS - primal solution is infeasible |
---|
| 121 | GLP_NOFEAS - no primal feasible solution exists */ |
---|
| 122 | int d_stat; |
---|
| 123 | /* status of dual basic solution: |
---|
| 124 | GLP_UNDEF - dual solution is undefined |
---|
| 125 | GLP_FEAS - dual solution is feasible |
---|
| 126 | GLP_INFEAS - dual solution is infeasible |
---|
| 127 | GLP_NOFEAS - no dual feasible solution exists */ |
---|
| 128 | int t_stat; |
---|
| 129 | /* status of interior-point solution: |
---|
| 130 | GLP_UNDEF - interior solution is undefined |
---|
| 131 | GLP_OPT - interior solution is optimal */ |
---|
| 132 | int i_stat; |
---|
| 133 | /* status of mixed integer solution: |
---|
| 134 | GLP_UNDEF - integer solution is undefined |
---|
| 135 | GLP_OPT - integer solution is optimal |
---|
| 136 | GLP_FEAS - integer solution is feasible |
---|
| 137 | GLP_NOFEAS - no integer solution exists */ |
---|
| 138 | char *r_stat; /* char r_stat[1+nrows]; */ |
---|
| 139 | /* r_stat[i], 1 <= i <= nrows, is status of i-th row: |
---|
| 140 | GLP_BS - inactive constraint |
---|
| 141 | GLP_NL - active constraint on lower bound |
---|
| 142 | GLP_NU - active constraint on upper bound |
---|
| 143 | GLP_NF - active free row |
---|
| 144 | GLP_NS - active equality constraint */ |
---|
| 145 | char *c_stat; /* char c_stat[1+nrows]; */ |
---|
| 146 | /* c_stat[j], 1 <= j <= nrows, is status of j-th column: |
---|
| 147 | GLP_BS - basic variable |
---|
| 148 | GLP_NL - non-basic variable on lower bound |
---|
| 149 | GLP_NU - non-basic variable on upper bound |
---|
| 150 | GLP_NF - non-basic free variable |
---|
| 151 | GLP_NS - non-basic fixed variable */ |
---|
| 152 | double *r_pi; /* double r_pi[1+nrows]; */ |
---|
| 153 | /* r_pi[i], 1 <= i <= nrows, is Lagrange multiplier (dual value) |
---|
| 154 | for i-th row (constraint) */ |
---|
| 155 | double *c_value; /* double c_value[1+ncols]; */ |
---|
| 156 | /* c_value[j], 1 <= j <= ncols, is primal value of j-th column |
---|
| 157 | (structural variable) */ |
---|
| 158 | }; |
---|
| 159 | |
---|
| 160 | struct NPPROW |
---|
| 161 | { /* row (constraint) */ |
---|
| 162 | int i; |
---|
| 163 | /* reference number assigned to the row, 1 <= i <= nrows */ |
---|
| 164 | char *name; |
---|
| 165 | /* row name (1 to 255 chars); NULL means no name is assigned to |
---|
| 166 | the row */ |
---|
| 167 | double lb; |
---|
| 168 | /* lower bound; -DBL_MAX means the row has no lower bound */ |
---|
| 169 | double ub; |
---|
| 170 | /* upper bound; +DBL_MAX means the row has no upper bound */ |
---|
| 171 | NPPAIJ *ptr; |
---|
| 172 | /* pointer to the linked list of constraint coefficients */ |
---|
| 173 | int temp; |
---|
| 174 | /* working field used by preprocessor routines */ |
---|
| 175 | NPPROW *prev; |
---|
| 176 | /* pointer to previous row in the row list */ |
---|
| 177 | NPPROW *next; |
---|
| 178 | /* pointer to next row in the row list */ |
---|
| 179 | }; |
---|
| 180 | |
---|
| 181 | struct NPPCOL |
---|
| 182 | { /* column (variable) */ |
---|
| 183 | int j; |
---|
| 184 | /* reference number assigned to the column, 1 <= j <= ncols */ |
---|
| 185 | char *name; |
---|
| 186 | /* column name (1 to 255 chars); NULL means no name is assigned |
---|
| 187 | to the column */ |
---|
| 188 | char is_int; |
---|
| 189 | /* 0 means continuous variable; 1 means integer variable */ |
---|
| 190 | double lb; |
---|
| 191 | /* lower bound; -DBL_MAX means the column has no lower bound */ |
---|
| 192 | double ub; |
---|
| 193 | /* upper bound; +DBL_MAX means the column has no upper bound */ |
---|
| 194 | double coef; |
---|
| 195 | /* objective coefficient */ |
---|
| 196 | NPPAIJ *ptr; |
---|
| 197 | /* pointer to the linked list of constraint coefficients */ |
---|
| 198 | int temp; |
---|
| 199 | /* working field used by preprocessor routines */ |
---|
| 200 | #if 1 /* 28/XII-2009 */ |
---|
| 201 | union |
---|
| 202 | { double ll; |
---|
| 203 | /* implied column lower bound */ |
---|
| 204 | int pos; |
---|
| 205 | /* vertex ordinal number corresponding to this binary column |
---|
| 206 | in the conflict graph (0, if the vertex does not exist) */ |
---|
| 207 | } ll; |
---|
| 208 | union |
---|
| 209 | { double uu; |
---|
| 210 | /* implied column upper bound */ |
---|
| 211 | int neg; |
---|
| 212 | /* vertex ordinal number corresponding to complement of this |
---|
| 213 | binary column in the conflict graph (0, if the vertex does |
---|
| 214 | not exist) */ |
---|
| 215 | } uu; |
---|
| 216 | #endif |
---|
| 217 | NPPCOL *prev; |
---|
| 218 | /* pointer to previous column in the column list */ |
---|
| 219 | NPPCOL *next; |
---|
| 220 | /* pointer to next column in the column list */ |
---|
| 221 | }; |
---|
| 222 | |
---|
| 223 | struct NPPAIJ |
---|
| 224 | { /* constraint coefficient */ |
---|
| 225 | NPPROW *row; |
---|
| 226 | /* pointer to corresponding row */ |
---|
| 227 | NPPCOL *col; |
---|
| 228 | /* pointer to corresponding column */ |
---|
| 229 | double val; |
---|
| 230 | /* (non-zero) coefficient value */ |
---|
| 231 | NPPAIJ *r_prev; |
---|
| 232 | /* pointer to previous coefficient in the same row */ |
---|
| 233 | NPPAIJ *r_next; |
---|
| 234 | /* pointer to next coefficient in the same row */ |
---|
| 235 | NPPAIJ *c_prev; |
---|
| 236 | /* pointer to previous coefficient in the same column */ |
---|
| 237 | NPPAIJ *c_next; |
---|
| 238 | /* pointer to next coefficient in the same column */ |
---|
| 239 | }; |
---|
| 240 | |
---|
| 241 | struct NPPTSE |
---|
| 242 | { /* transformation stack entry */ |
---|
| 243 | int (*func)(NPP *npp, void *info); |
---|
| 244 | /* pointer to routine performing back transformation */ |
---|
| 245 | void *info; |
---|
| 246 | /* pointer to specific info (depends on the transformation) */ |
---|
| 247 | NPPTSE *link; |
---|
| 248 | /* pointer to another entry created *before* this entry */ |
---|
| 249 | }; |
---|
| 250 | |
---|
| 251 | struct NPPLFE |
---|
| 252 | { /* linear form element */ |
---|
| 253 | int ref; |
---|
| 254 | /* row/column reference number */ |
---|
| 255 | double val; |
---|
| 256 | /* (non-zero) coefficient value */ |
---|
| 257 | NPPLFE *next; |
---|
| 258 | /* pointer to another element */ |
---|
| 259 | }; |
---|
| 260 | |
---|
| 261 | #define npp_create_wksp _glp_npp_create_wksp |
---|
| 262 | NPP *npp_create_wksp(void); |
---|
| 263 | /* create LP/MIP preprocessor workspace */ |
---|
| 264 | |
---|
| 265 | #define npp_insert_row _glp_npp_insert_row |
---|
| 266 | void npp_insert_row(NPP *npp, NPPROW *row, int where); |
---|
| 267 | /* insert row to the row list */ |
---|
| 268 | |
---|
| 269 | #define npp_remove_row _glp_npp_remove_row |
---|
| 270 | void npp_remove_row(NPP *npp, NPPROW *row); |
---|
| 271 | /* remove row from the row list */ |
---|
| 272 | |
---|
| 273 | #define npp_activate_row _glp_npp_activate_row |
---|
| 274 | void npp_activate_row(NPP *npp, NPPROW *row); |
---|
| 275 | /* make row active */ |
---|
| 276 | |
---|
| 277 | #define npp_deactivate_row _glp_npp_deactivate_row |
---|
| 278 | void npp_deactivate_row(NPP *npp, NPPROW *row); |
---|
| 279 | /* make row inactive */ |
---|
| 280 | |
---|
| 281 | #define npp_insert_col _glp_npp_insert_col |
---|
| 282 | void npp_insert_col(NPP *npp, NPPCOL *col, int where); |
---|
| 283 | /* insert column to the column list */ |
---|
| 284 | |
---|
| 285 | #define npp_remove_col _glp_npp_remove_col |
---|
| 286 | void npp_remove_col(NPP *npp, NPPCOL *col); |
---|
| 287 | /* remove column from the column list */ |
---|
| 288 | |
---|
| 289 | #define npp_activate_col _glp_npp_activate_col |
---|
| 290 | void npp_activate_col(NPP *npp, NPPCOL *col); |
---|
| 291 | /* make column active */ |
---|
| 292 | |
---|
| 293 | #define npp_deactivate_col _glp_npp_deactivate_col |
---|
| 294 | void npp_deactivate_col(NPP *npp, NPPCOL *col); |
---|
| 295 | /* make column inactive */ |
---|
| 296 | |
---|
| 297 | #define npp_add_row _glp_npp_add_row |
---|
| 298 | NPPROW *npp_add_row(NPP *npp); |
---|
| 299 | /* add new row to the current problem */ |
---|
| 300 | |
---|
| 301 | #define npp_add_col _glp_npp_add_col |
---|
| 302 | NPPCOL *npp_add_col(NPP *npp); |
---|
| 303 | /* add new column to the current problem */ |
---|
| 304 | |
---|
| 305 | #define npp_add_aij _glp_npp_add_aij |
---|
| 306 | NPPAIJ *npp_add_aij(NPP *npp, NPPROW *row, NPPCOL *col, double val); |
---|
| 307 | /* add new element to the constraint matrix */ |
---|
| 308 | |
---|
| 309 | #define npp_row_nnz _glp_npp_row_nnz |
---|
| 310 | int npp_row_nnz(NPP *npp, NPPROW *row); |
---|
| 311 | /* count number of non-zero coefficients in row */ |
---|
| 312 | |
---|
| 313 | #define npp_col_nnz _glp_npp_col_nnz |
---|
| 314 | int npp_col_nnz(NPP *npp, NPPCOL *col); |
---|
| 315 | /* count number of non-zero coefficients in column */ |
---|
| 316 | |
---|
| 317 | #define npp_push_tse _glp_npp_push_tse |
---|
| 318 | void *npp_push_tse(NPP *npp, int (*func)(NPP *npp, void *info), |
---|
| 319 | int size); |
---|
| 320 | /* push new entry to the transformation stack */ |
---|
| 321 | |
---|
| 322 | #define npp_erase_row _glp_npp_erase_row |
---|
| 323 | void npp_erase_row(NPP *npp, NPPROW *row); |
---|
| 324 | /* erase row content to make it empty */ |
---|
| 325 | |
---|
| 326 | #define npp_del_row _glp_npp_del_row |
---|
| 327 | void npp_del_row(NPP *npp, NPPROW *row); |
---|
| 328 | /* remove row from the current problem */ |
---|
| 329 | |
---|
| 330 | #define npp_del_col _glp_npp_del_col |
---|
| 331 | void npp_del_col(NPP *npp, NPPCOL *col); |
---|
| 332 | /* remove column from the current problem */ |
---|
| 333 | |
---|
| 334 | #define npp_del_aij _glp_npp_del_aij |
---|
| 335 | void npp_del_aij(NPP *npp, NPPAIJ *aij); |
---|
| 336 | /* remove element from the constraint matrix */ |
---|
| 337 | |
---|
| 338 | #define npp_load_prob _glp_npp_load_prob |
---|
| 339 | void npp_load_prob(NPP *npp, glp_prob *orig, int names, int sol, |
---|
| 340 | int scaling); |
---|
| 341 | /* load original problem into the preprocessor workspace */ |
---|
| 342 | |
---|
| 343 | #define npp_build_prob _glp_npp_build_prob |
---|
| 344 | void npp_build_prob(NPP *npp, glp_prob *prob); |
---|
| 345 | /* build resultant (preprocessed) problem */ |
---|
| 346 | |
---|
| 347 | #define npp_postprocess _glp_npp_postprocess |
---|
| 348 | void npp_postprocess(NPP *npp, glp_prob *prob); |
---|
| 349 | /* postprocess solution from the resultant problem */ |
---|
| 350 | |
---|
| 351 | #define npp_unload_sol _glp_npp_unload_sol |
---|
| 352 | void npp_unload_sol(NPP *npp, glp_prob *orig); |
---|
| 353 | /* store solution to the original problem */ |
---|
| 354 | |
---|
| 355 | #define npp_delete_wksp _glp_npp_delete_wksp |
---|
| 356 | void npp_delete_wksp(NPP *npp); |
---|
| 357 | /* delete LP/MIP preprocessor workspace */ |
---|
| 358 | |
---|
| 359 | #define npp_error() |
---|
| 360 | |
---|
| 361 | #define npp_free_row _glp_npp_free_row |
---|
| 362 | void npp_free_row(NPP *npp, NPPROW *p); |
---|
| 363 | /* process free (unbounded) row */ |
---|
| 364 | |
---|
| 365 | #define npp_geq_row _glp_npp_geq_row |
---|
| 366 | void npp_geq_row(NPP *npp, NPPROW *p); |
---|
| 367 | /* process row of 'not less than' type */ |
---|
| 368 | |
---|
| 369 | #define npp_leq_row _glp_npp_leq_row |
---|
| 370 | void npp_leq_row(NPP *npp, NPPROW *p); |
---|
| 371 | /* process row of 'not greater than' type */ |
---|
| 372 | |
---|
| 373 | #define npp_free_col _glp_npp_free_col |
---|
| 374 | void npp_free_col(NPP *npp, NPPCOL *q); |
---|
| 375 | /* process free (unbounded) column */ |
---|
| 376 | |
---|
| 377 | #define npp_lbnd_col _glp_npp_lbnd_col |
---|
| 378 | void npp_lbnd_col(NPP *npp, NPPCOL *q); |
---|
| 379 | /* process column with (non-zero) lower bound */ |
---|
| 380 | |
---|
| 381 | #define npp_ubnd_col _glp_npp_ubnd_col |
---|
| 382 | void npp_ubnd_col(NPP *npp, NPPCOL *q); |
---|
| 383 | /* process column with upper bound */ |
---|
| 384 | |
---|
| 385 | #define npp_dbnd_col _glp_npp_dbnd_col |
---|
| 386 | void npp_dbnd_col(NPP *npp, NPPCOL *q); |
---|
| 387 | /* process non-negative column with upper bound */ |
---|
| 388 | |
---|
| 389 | #define npp_fixed_col _glp_npp_fixed_col |
---|
| 390 | void npp_fixed_col(NPP *npp, NPPCOL *q); |
---|
| 391 | /* process fixed column */ |
---|
| 392 | |
---|
| 393 | #define npp_make_equality _glp_npp_make_equality |
---|
| 394 | int npp_make_equality(NPP *npp, NPPROW *p); |
---|
| 395 | /* process row with almost identical bounds */ |
---|
| 396 | |
---|
| 397 | #define npp_make_fixed _glp_npp_make_fixed |
---|
| 398 | int npp_make_fixed(NPP *npp, NPPCOL *q); |
---|
| 399 | /* process column with almost identical bounds */ |
---|
| 400 | |
---|
| 401 | #define npp_empty_row _glp_npp_empty_row |
---|
| 402 | int npp_empty_row(NPP *npp, NPPROW *p); |
---|
| 403 | /* process empty row */ |
---|
| 404 | |
---|
| 405 | #define npp_empty_col _glp_npp_empty_col |
---|
| 406 | int npp_empty_col(NPP *npp, NPPCOL *q); |
---|
| 407 | /* process empty column */ |
---|
| 408 | |
---|
| 409 | #define npp_implied_value _glp_npp_implied_value |
---|
| 410 | int npp_implied_value(NPP *npp, NPPCOL *q, double s); |
---|
| 411 | /* process implied column value */ |
---|
| 412 | |
---|
| 413 | #define npp_eq_singlet _glp_npp_eq_singlet |
---|
| 414 | int npp_eq_singlet(NPP *npp, NPPROW *p); |
---|
| 415 | /* process row singleton (equality constraint) */ |
---|
| 416 | |
---|
| 417 | #define npp_implied_lower _glp_npp_implied_lower |
---|
| 418 | int npp_implied_lower(NPP *npp, NPPCOL *q, double l); |
---|
| 419 | /* process implied column lower bound */ |
---|
| 420 | |
---|
| 421 | #define npp_implied_upper _glp_npp_implied_upper |
---|
| 422 | int npp_implied_upper(NPP *npp, NPPCOL *q, double u); |
---|
| 423 | /* process implied upper bound of column */ |
---|
| 424 | |
---|
| 425 | #define npp_ineq_singlet _glp_npp_ineq_singlet |
---|
| 426 | int npp_ineq_singlet(NPP *npp, NPPROW *p); |
---|
| 427 | /* process row singleton (inequality constraint) */ |
---|
| 428 | |
---|
| 429 | #define npp_implied_slack _glp_npp_implied_slack |
---|
| 430 | void npp_implied_slack(NPP *npp, NPPCOL *q); |
---|
| 431 | /* process column singleton (implied slack variable) */ |
---|
| 432 | |
---|
| 433 | #define npp_implied_free _glp_npp_implied_free |
---|
| 434 | int npp_implied_free(NPP *npp, NPPCOL *q); |
---|
| 435 | /* process column singleton (implied free variable) */ |
---|
| 436 | |
---|
| 437 | #define npp_eq_doublet _glp_npp_eq_doublet |
---|
| 438 | NPPCOL *npp_eq_doublet(NPP *npp, NPPROW *p); |
---|
| 439 | /* process row doubleton (equality constraint) */ |
---|
| 440 | |
---|
| 441 | #define npp_forcing_row _glp_npp_forcing_row |
---|
| 442 | int npp_forcing_row(NPP *npp, NPPROW *p, int at); |
---|
| 443 | /* process forcing row */ |
---|
| 444 | |
---|
| 445 | #define npp_analyze_row _glp_npp_analyze_row |
---|
| 446 | int npp_analyze_row(NPP *npp, NPPROW *p); |
---|
| 447 | /* perform general row analysis */ |
---|
| 448 | |
---|
| 449 | #define npp_inactive_bound _glp_npp_inactive_bound |
---|
| 450 | void npp_inactive_bound(NPP *npp, NPPROW *p, int which); |
---|
| 451 | /* remove row lower/upper inactive bound */ |
---|
| 452 | |
---|
| 453 | #define npp_implied_bounds _glp_npp_implied_bounds |
---|
| 454 | void npp_implied_bounds(NPP *npp, NPPROW *p); |
---|
| 455 | /* determine implied column bounds */ |
---|
| 456 | |
---|
| 457 | #define npp_binarize_prob _glp_npp_binarize_prob |
---|
| 458 | int npp_binarize_prob(NPP *npp); |
---|
| 459 | /* binarize MIP problem */ |
---|
| 460 | |
---|
| 461 | #define npp_is_packing _glp_npp_is_packing |
---|
| 462 | int npp_is_packing(NPP *npp, NPPROW *row); |
---|
| 463 | /* test if constraint is packing inequality */ |
---|
| 464 | |
---|
| 465 | #define npp_hidden_packing _glp_npp_hidden_packing |
---|
| 466 | int npp_hidden_packing(NPP *npp, NPPROW *row); |
---|
| 467 | /* identify hidden packing inequality */ |
---|
| 468 | |
---|
| 469 | #define npp_implied_packing _glp_npp_implied_packing |
---|
| 470 | int npp_implied_packing(NPP *npp, NPPROW *row, int which, |
---|
| 471 | NPPCOL *var[], char set[]); |
---|
| 472 | /* identify implied packing inequality */ |
---|
| 473 | |
---|
| 474 | #define npp_is_covering _glp_npp_is_covering |
---|
| 475 | int npp_is_covering(NPP *npp, NPPROW *row); |
---|
| 476 | /* test if constraint is covering inequality */ |
---|
| 477 | |
---|
| 478 | #define npp_hidden_covering _glp_npp_hidden_covering |
---|
| 479 | int npp_hidden_covering(NPP *npp, NPPROW *row); |
---|
| 480 | /* identify hidden covering inequality */ |
---|
| 481 | |
---|
| 482 | #define npp_is_partitioning _glp_npp_is_partitioning |
---|
| 483 | int npp_is_partitioning(NPP *npp, NPPROW *row); |
---|
| 484 | /* test if constraint is partitioning equality */ |
---|
| 485 | |
---|
| 486 | #define npp_reduce_ineq_coef _glp_npp_reduce_ineq_coef |
---|
| 487 | int npp_reduce_ineq_coef(NPP *npp, NPPROW *row); |
---|
| 488 | /* reduce inequality constraint coefficients */ |
---|
| 489 | |
---|
| 490 | #define npp_clean_prob _glp_npp_clean_prob |
---|
| 491 | void npp_clean_prob(NPP *npp); |
---|
| 492 | /* perform initial LP/MIP processing */ |
---|
| 493 | |
---|
| 494 | #define npp_process_row _glp_npp_process_row |
---|
| 495 | int npp_process_row(NPP *npp, NPPROW *row, int hard); |
---|
| 496 | /* perform basic row processing */ |
---|
| 497 | |
---|
| 498 | #define npp_improve_bounds _glp_npp_improve_bounds |
---|
| 499 | int npp_improve_bounds(NPP *npp, NPPROW *row, int flag); |
---|
| 500 | /* improve current column bounds */ |
---|
| 501 | |
---|
| 502 | #define npp_process_col _glp_npp_process_col |
---|
| 503 | int npp_process_col(NPP *npp, NPPCOL *col); |
---|
| 504 | /* perform basic column processing */ |
---|
| 505 | |
---|
| 506 | #define npp_process_prob _glp_npp_process_prob |
---|
| 507 | int npp_process_prob(NPP *npp, int hard); |
---|
| 508 | /* perform basic LP/MIP processing */ |
---|
| 509 | |
---|
| 510 | #define npp_simplex _glp_npp_simplex |
---|
| 511 | int npp_simplex(NPP *npp, const glp_smcp *parm); |
---|
| 512 | /* process LP prior to applying primal/dual simplex method */ |
---|
| 513 | |
---|
| 514 | #define npp_integer _glp_npp_integer |
---|
| 515 | int npp_integer(NPP *npp, const glp_iocp *parm); |
---|
| 516 | /* process MIP prior to applying branch-and-bound method */ |
---|
| 517 | |
---|
| 518 | /**********************************************************************/ |
---|
| 519 | |
---|
| 520 | #define npp_sat_free_row _glp_npp_sat_free_row |
---|
| 521 | void npp_sat_free_row(NPP *npp, NPPROW *p); |
---|
| 522 | /* process free (unbounded) row */ |
---|
| 523 | |
---|
| 524 | #define npp_sat_fixed_col _glp_npp_sat_fixed_col |
---|
| 525 | int npp_sat_fixed_col(NPP *npp, NPPCOL *q); |
---|
| 526 | /* process fixed column */ |
---|
| 527 | |
---|
| 528 | #define npp_sat_is_bin_comb _glp_npp_sat_is_bin_comb |
---|
| 529 | int npp_sat_is_bin_comb(NPP *npp, NPPROW *row); |
---|
| 530 | /* test if row is binary combination */ |
---|
| 531 | |
---|
| 532 | #define npp_sat_num_pos_coef _glp_npp_sat_num_pos_coef |
---|
| 533 | int npp_sat_num_pos_coef(NPP *npp, NPPROW *row); |
---|
| 534 | /* determine number of positive coefficients */ |
---|
| 535 | |
---|
| 536 | #define npp_sat_num_neg_coef _glp_npp_sat_num_neg_coef |
---|
| 537 | int npp_sat_num_neg_coef(NPP *npp, NPPROW *row); |
---|
| 538 | /* determine number of negative coefficients */ |
---|
| 539 | |
---|
| 540 | #define npp_sat_is_cover_ineq _glp_npp_sat_is_cover_ineq |
---|
| 541 | int npp_sat_is_cover_ineq(NPP *npp, NPPROW *row); |
---|
| 542 | /* test if row is covering inequality */ |
---|
| 543 | |
---|
| 544 | #define npp_sat_is_pack_ineq _glp_npp_sat_is_pack_ineq |
---|
| 545 | int npp_sat_is_pack_ineq(NPP *npp, NPPROW *row); |
---|
| 546 | /* test if row is packing inequality */ |
---|
| 547 | |
---|
| 548 | #define npp_sat_is_partn_eq _glp_npp_sat_is_partn_eq |
---|
| 549 | int npp_sat_is_partn_eq(NPP *npp, NPPROW *row); |
---|
| 550 | /* test if row is partitioning equality */ |
---|
| 551 | |
---|
| 552 | #define npp_sat_reverse_row _glp_npp_sat_reverse_row |
---|
| 553 | int npp_sat_reverse_row(NPP *npp, NPPROW *row); |
---|
| 554 | /* multiply both sides of row by -1 */ |
---|
| 555 | |
---|
| 556 | #define npp_sat_split_pack _glp_npp_sat_split_pack |
---|
| 557 | NPPROW *npp_sat_split_pack(NPP *npp, NPPROW *row, int nnn); |
---|
| 558 | /* split packing inequality */ |
---|
| 559 | |
---|
| 560 | #define npp_sat_encode_pack _glp_npp_sat_encode_pack |
---|
| 561 | void npp_sat_encode_pack(NPP *npp, NPPROW *row); |
---|
| 562 | /* encode packing inequality */ |
---|
| 563 | |
---|
| 564 | typedef struct NPPLIT NPPLIT; |
---|
| 565 | typedef struct NPPLSE NPPLSE; |
---|
| 566 | typedef struct NPPSED NPPSED; |
---|
| 567 | |
---|
| 568 | struct NPPLIT |
---|
| 569 | { /* literal (binary variable or its negation) */ |
---|
| 570 | NPPCOL *col; |
---|
| 571 | /* pointer to binary variable; NULL means constant false */ |
---|
| 572 | int neg; |
---|
| 573 | /* negation flag: |
---|
| 574 | 0 - literal is variable (or constant false) |
---|
| 575 | 1 - literal is negation of variable (or constant true) */ |
---|
| 576 | }; |
---|
| 577 | |
---|
| 578 | struct NPPLSE |
---|
| 579 | { /* literal set element */ |
---|
| 580 | NPPLIT lit; |
---|
| 581 | /* literal */ |
---|
| 582 | NPPLSE *next; |
---|
| 583 | /* pointer to another element */ |
---|
| 584 | }; |
---|
| 585 | |
---|
| 586 | struct NPPSED |
---|
| 587 | { /* summation encoding descriptor */ |
---|
| 588 | /* this struct describes the equality |
---|
| 589 | x + y + z = s + 2 * c, |
---|
| 590 | which was encoded as CNF and included into the transformed |
---|
| 591 | problem; here x and y are literals, z is either a literal or |
---|
| 592 | constant zero, s and c are binary variables modeling, resp., |
---|
| 593 | the low and high (carry) sum bits */ |
---|
| 594 | NPPLIT x, y, z; |
---|
| 595 | /* literals; if z.col = NULL, z is constant zero */ |
---|
| 596 | NPPCOL *s, *c; |
---|
| 597 | /* binary variables modeling the sum bits */ |
---|
| 598 | }; |
---|
| 599 | |
---|
| 600 | #define npp_sat_encode_sum2 _glp_npp_sat_encode_sum2 |
---|
| 601 | void npp_sat_encode_sum2(NPP *npp, NPPLSE *set, NPPSED *sed); |
---|
| 602 | /* encode 2-bit summation */ |
---|
| 603 | |
---|
| 604 | #define npp_sat_encode_sum3 _glp_npp_sat_encode_sum3 |
---|
| 605 | void npp_sat_encode_sum3(NPP *npp, NPPLSE *set, NPPSED *sed); |
---|
| 606 | /* encode 3-bit summation */ |
---|
| 607 | |
---|
| 608 | #define npp_sat_encode_sum_ax _glp_npp_sat_encode_sum_ax |
---|
| 609 | int npp_sat_encode_sum_ax(NPP *npp, NPPROW *row, NPPLIT y[]); |
---|
| 610 | /* encode linear combination of 0-1 variables */ |
---|
| 611 | |
---|
| 612 | #define npp_sat_normalize_clause _glp_npp_sat_normalize_clause |
---|
| 613 | int npp_sat_normalize_clause(NPP *npp, int size, NPPLIT lit[]); |
---|
| 614 | /* normalize clause */ |
---|
| 615 | |
---|
| 616 | #define npp_sat_encode_clause _glp_npp_sat_encode_clause |
---|
| 617 | NPPROW *npp_sat_encode_clause(NPP *npp, int size, NPPLIT lit[]); |
---|
| 618 | /* translate clause to cover inequality */ |
---|
| 619 | |
---|
| 620 | #define npp_sat_encode_geq _glp_npp_sat_encode_geq |
---|
| 621 | int npp_sat_encode_geq(NPP *npp, int n, NPPLIT y[], int rhs); |
---|
| 622 | /* encode "not less than" constraint */ |
---|
| 623 | |
---|
| 624 | #define npp_sat_encode_leq _glp_npp_sat_encode_leq |
---|
| 625 | int npp_sat_encode_leq(NPP *npp, int n, NPPLIT y[], int rhs); |
---|
| 626 | /* encode "not greater than" constraint */ |
---|
| 627 | |
---|
| 628 | #define npp_sat_encode_row _glp_npp_sat_encode_row |
---|
| 629 | int npp_sat_encode_row(NPP *npp, NPPROW *row); |
---|
| 630 | /* encode constraint (row) of general type */ |
---|
| 631 | |
---|
| 632 | #define npp_sat_encode_prob _glp_npp_sat_encode_prob |
---|
| 633 | int npp_sat_encode_prob(NPP *npp); |
---|
| 634 | /* encode 0-1 feasibility problem */ |
---|
| 635 | |
---|
| 636 | #endif |
---|
| 637 | |
---|
| 638 | /* eof */ |
---|