1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/glpnpp05.c Mon Dec 06 13:09:21 2010 +0100
1.3 @@ -0,0 +1,809 @@
1.4 +/* glpnpp05.c */
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 +#include "glpnpp.h"
1.29 +
1.30 +/***********************************************************************
1.31 +* NAME
1.32 +*
1.33 +* npp_clean_prob - perform initial LP/MIP processing
1.34 +*
1.35 +* SYNOPSIS
1.36 +*
1.37 +* #include "glpnpp.h"
1.38 +* void npp_clean_prob(NPP *npp);
1.39 +*
1.40 +* DESCRIPTION
1.41 +*
1.42 +* The routine npp_clean_prob performs initial LP/MIP processing that
1.43 +* currently includes:
1.44 +*
1.45 +* 1) removing free rows;
1.46 +*
1.47 +* 2) replacing double-sided constraint rows with almost identical
1.48 +* bounds, by equality constraint rows;
1.49 +*
1.50 +* 3) removing fixed columns;
1.51 +*
1.52 +* 4) replacing double-bounded columns with almost identical bounds by
1.53 +* fixed columns and removing those columns;
1.54 +*
1.55 +* 5) initial processing constraint coefficients (not implemented);
1.56 +*
1.57 +* 6) initial processing objective coefficients (not implemented). */
1.58 +
1.59 +void npp_clean_prob(NPP *npp)
1.60 +{ /* perform initial LP/MIP processing */
1.61 + NPPROW *row, *next_row;
1.62 + NPPCOL *col, *next_col;
1.63 + int ret;
1.64 + xassert(npp == npp);
1.65 + /* process rows which originally are free */
1.66 + for (row = npp->r_head; row != NULL; row = next_row)
1.67 + { next_row = row->next;
1.68 + if (row->lb == -DBL_MAX && row->ub == +DBL_MAX)
1.69 + { /* process free row */
1.70 +#ifdef GLP_DEBUG
1.71 + xprintf("1");
1.72 +#endif
1.73 + npp_free_row(npp, row);
1.74 + /* row was deleted */
1.75 + }
1.76 + }
1.77 + /* process rows which originally are double-sided inequalities */
1.78 + for (row = npp->r_head; row != NULL; row = next_row)
1.79 + { next_row = row->next;
1.80 + if (row->lb != -DBL_MAX && row->ub != +DBL_MAX &&
1.81 + row->lb < row->ub)
1.82 + { ret = npp_make_equality(npp, row);
1.83 + if (ret == 0)
1.84 + ;
1.85 + else if (ret == 1)
1.86 + { /* row was replaced by equality constraint */
1.87 +#ifdef GLP_DEBUG
1.88 + xprintf("2");
1.89 +#endif
1.90 + }
1.91 + else
1.92 + xassert(ret != ret);
1.93 + }
1.94 + }
1.95 + /* process columns which are originally fixed */
1.96 + for (col = npp->c_head; col != NULL; col = next_col)
1.97 + { next_col = col->next;
1.98 + if (col->lb == col->ub)
1.99 + { /* process fixed column */
1.100 +#ifdef GLP_DEBUG
1.101 + xprintf("3");
1.102 +#endif
1.103 + npp_fixed_col(npp, col);
1.104 + /* column was deleted */
1.105 + }
1.106 + }
1.107 + /* process columns which are originally double-bounded */
1.108 + for (col = npp->c_head; col != NULL; col = next_col)
1.109 + { next_col = col->next;
1.110 + if (col->lb != -DBL_MAX && col->ub != +DBL_MAX &&
1.111 + col->lb < col->ub)
1.112 + { ret = npp_make_fixed(npp, col);
1.113 + if (ret == 0)
1.114 + ;
1.115 + else if (ret == 1)
1.116 + { /* column was replaced by fixed column; process it */
1.117 +#ifdef GLP_DEBUG
1.118 + xprintf("4");
1.119 +#endif
1.120 + npp_fixed_col(npp, col);
1.121 + /* column was deleted */
1.122 + }
1.123 + }
1.124 + }
1.125 + return;
1.126 +}
1.127 +
1.128 +/***********************************************************************
1.129 +* NAME
1.130 +*
1.131 +* npp_process_row - perform basic row processing
1.132 +*
1.133 +* SYNOPSIS
1.134 +*
1.135 +* #include "glpnpp.h"
1.136 +* int npp_process_row(NPP *npp, NPPROW *row, int hard);
1.137 +*
1.138 +* DESCRIPTION
1.139 +*
1.140 +* The routine npp_process_row performs basic row processing that
1.141 +* currently includes:
1.142 +*
1.143 +* 1) removing empty row;
1.144 +*
1.145 +* 2) removing equality constraint row singleton and corresponding
1.146 +* column;
1.147 +*
1.148 +* 3) removing inequality constraint row singleton and corresponding
1.149 +* column if it was fixed;
1.150 +*
1.151 +* 4) performing general row analysis;
1.152 +*
1.153 +* 5) removing redundant row bounds;
1.154 +*
1.155 +* 6) removing forcing row and corresponding columns;
1.156 +*
1.157 +* 7) removing row which becomes free due to redundant bounds;
1.158 +*
1.159 +* 8) computing implied bounds for all columns in the row and using
1.160 +* them to strengthen current column bounds (MIP only, optional,
1.161 +* performed if the flag hard is on).
1.162 +*
1.163 +* Additionally the routine may activate affected rows and/or columns
1.164 +* for further processing.
1.165 +*
1.166 +* RETURNS
1.167 +*
1.168 +* 0 success;
1.169 +*
1.170 +* GLP_ENOPFS primal/integer infeasibility detected;
1.171 +*
1.172 +* GLP_ENODFS dual infeasibility detected. */
1.173 +
1.174 +int npp_process_row(NPP *npp, NPPROW *row, int hard)
1.175 +{ /* perform basic row processing */
1.176 + NPPCOL *col;
1.177 + NPPAIJ *aij, *next_aij, *aaa;
1.178 + int ret;
1.179 + /* row must not be free */
1.180 + xassert(!(row->lb == -DBL_MAX && row->ub == +DBL_MAX));
1.181 + /* start processing row */
1.182 + if (row->ptr == NULL)
1.183 + { /* empty row */
1.184 + ret = npp_empty_row(npp, row);
1.185 + if (ret == 0)
1.186 + { /* row was deleted */
1.187 +#ifdef GLP_DEBUG
1.188 + xprintf("A");
1.189 +#endif
1.190 + return 0;
1.191 + }
1.192 + else if (ret == 1)
1.193 + { /* primal infeasibility */
1.194 + return GLP_ENOPFS;
1.195 + }
1.196 + else
1.197 + xassert(ret != ret);
1.198 + }
1.199 + if (row->ptr->r_next == NULL)
1.200 + { /* row singleton */
1.201 + col = row->ptr->col;
1.202 + if (row->lb == row->ub)
1.203 + { /* equality constraint */
1.204 + ret = npp_eq_singlet(npp, row);
1.205 + if (ret == 0)
1.206 + { /* column was fixed, row was deleted */
1.207 +#ifdef GLP_DEBUG
1.208 + xprintf("B");
1.209 +#endif
1.210 + /* activate rows affected by column */
1.211 + for (aij = col->ptr; aij != NULL; aij = aij->c_next)
1.212 + npp_activate_row(npp, aij->row);
1.213 + /* process fixed column */
1.214 + npp_fixed_col(npp, col);
1.215 + /* column was deleted */
1.216 + return 0;
1.217 + }
1.218 + else if (ret == 1 || ret == 2)
1.219 + { /* primal/integer infeasibility */
1.220 + return GLP_ENOPFS;
1.221 + }
1.222 + else
1.223 + xassert(ret != ret);
1.224 + }
1.225 + else
1.226 + { /* inequality constraint */
1.227 + ret = npp_ineq_singlet(npp, row);
1.228 + if (0 <= ret && ret <= 3)
1.229 + { /* row was deleted */
1.230 +#ifdef GLP_DEBUG
1.231 + xprintf("C");
1.232 +#endif
1.233 + /* activate column, since its length was changed due to
1.234 + row deletion */
1.235 + npp_activate_col(npp, col);
1.236 + if (ret >= 2)
1.237 + { /* column bounds changed significantly or column was
1.238 + fixed */
1.239 + /* activate rows affected by column */
1.240 + for (aij = col->ptr; aij != NULL; aij = aij->c_next)
1.241 + npp_activate_row(npp, aij->row);
1.242 + }
1.243 + if (ret == 3)
1.244 + { /* column was fixed; process it */
1.245 +#ifdef GLP_DEBUG
1.246 + xprintf("D");
1.247 +#endif
1.248 + npp_fixed_col(npp, col);
1.249 + /* column was deleted */
1.250 + }
1.251 + return 0;
1.252 + }
1.253 + else if (ret == 4)
1.254 + { /* primal infeasibility */
1.255 + return GLP_ENOPFS;
1.256 + }
1.257 + else
1.258 + xassert(ret != ret);
1.259 + }
1.260 + }
1.261 +#if 0
1.262 + /* sometimes this causes too large round-off errors; probably
1.263 + pivot coefficient should be chosen more carefully */
1.264 + if (row->ptr->r_next->r_next == NULL)
1.265 + { /* row doubleton */
1.266 + if (row->lb == row->ub)
1.267 + { /* equality constraint */
1.268 + if (!(row->ptr->col->is_int ||
1.269 + row->ptr->r_next->col->is_int))
1.270 + { /* both columns are continuous */
1.271 + NPPCOL *q;
1.272 + q = npp_eq_doublet(npp, row);
1.273 + if (q != NULL)
1.274 + { /* column q was eliminated */
1.275 +#ifdef GLP_DEBUG
1.276 + xprintf("E");
1.277 +#endif
1.278 + /* now column q is singleton of type "implied slack
1.279 + variable"; we process it here to make sure that on
1.280 + recovering basic solution the row is always active
1.281 + equality constraint (as required by the routine
1.282 + rcv_eq_doublet) */
1.283 + xassert(npp_process_col(npp, q) == 0);
1.284 + /* column q was deleted; note that row p also may be
1.285 + deleted */
1.286 + return 0;
1.287 + }
1.288 + }
1.289 + }
1.290 + }
1.291 +#endif
1.292 + /* general row analysis */
1.293 + ret = npp_analyze_row(npp, row);
1.294 + xassert(0x00 <= ret && ret <= 0xFF);
1.295 + if (ret == 0x33)
1.296 + { /* row bounds are inconsistent with column bounds */
1.297 + return GLP_ENOPFS;
1.298 + }
1.299 + if ((ret & 0x0F) == 0x00)
1.300 + { /* row lower bound does not exist or redundant */
1.301 + if (row->lb != -DBL_MAX)
1.302 + { /* remove redundant row lower bound */
1.303 +#ifdef GLP_DEBUG
1.304 + xprintf("F");
1.305 +#endif
1.306 + npp_inactive_bound(npp, row, 0);
1.307 + }
1.308 + }
1.309 + else if ((ret & 0x0F) == 0x01)
1.310 + { /* row lower bound can be active */
1.311 + /* see below */
1.312 + }
1.313 + else if ((ret & 0x0F) == 0x02)
1.314 + { /* row lower bound is a forcing bound */
1.315 +#ifdef GLP_DEBUG
1.316 + xprintf("G");
1.317 +#endif
1.318 + /* process forcing row */
1.319 + if (npp_forcing_row(npp, row, 0) == 0)
1.320 +fixup: { /* columns were fixed, row was made free */
1.321 + for (aij = row->ptr; aij != NULL; aij = next_aij)
1.322 + { /* process column fixed by forcing row */
1.323 +#ifdef GLP_DEBUG
1.324 + xprintf("H");
1.325 +#endif
1.326 + col = aij->col;
1.327 + next_aij = aij->r_next;
1.328 + /* activate rows affected by column */
1.329 + for (aaa = col->ptr; aaa != NULL; aaa = aaa->c_next)
1.330 + npp_activate_row(npp, aaa->row);
1.331 + /* process fixed column */
1.332 + npp_fixed_col(npp, col);
1.333 + /* column was deleted */
1.334 + }
1.335 + /* process free row (which now is empty due to deletion of
1.336 + all its columns) */
1.337 + npp_free_row(npp, row);
1.338 + /* row was deleted */
1.339 + return 0;
1.340 + }
1.341 + }
1.342 + else
1.343 + xassert(ret != ret);
1.344 + if ((ret & 0xF0) == 0x00)
1.345 + { /* row upper bound does not exist or redundant */
1.346 + if (row->ub != +DBL_MAX)
1.347 + { /* remove redundant row upper bound */
1.348 +#ifdef GLP_DEBUG
1.349 + xprintf("I");
1.350 +#endif
1.351 + npp_inactive_bound(npp, row, 1);
1.352 + }
1.353 + }
1.354 + else if ((ret & 0xF0) == 0x10)
1.355 + { /* row upper bound can be active */
1.356 + /* see below */
1.357 + }
1.358 + else if ((ret & 0xF0) == 0x20)
1.359 + { /* row upper bound is a forcing bound */
1.360 +#ifdef GLP_DEBUG
1.361 + xprintf("J");
1.362 +#endif
1.363 + /* process forcing row */
1.364 + if (npp_forcing_row(npp, row, 1) == 0) goto fixup;
1.365 + }
1.366 + else
1.367 + xassert(ret != ret);
1.368 + if (row->lb == -DBL_MAX && row->ub == +DBL_MAX)
1.369 + { /* row became free due to redundant bounds removal */
1.370 +#ifdef GLP_DEBUG
1.371 + xprintf("K");
1.372 +#endif
1.373 + /* activate its columns, since their length will change due
1.374 + to row deletion */
1.375 + for (aij = row->ptr; aij != NULL; aij = aij->r_next)
1.376 + npp_activate_col(npp, aij->col);
1.377 + /* process free row */
1.378 + npp_free_row(npp, row);
1.379 + /* row was deleted */
1.380 + return 0;
1.381 + }
1.382 +#if 1 /* 23/XII-2009 */
1.383 + /* row lower and/or upper bounds can be active */
1.384 + if (npp->sol == GLP_MIP && hard)
1.385 + { /* improve current column bounds (optional) */
1.386 + if (npp_improve_bounds(npp, row, 1) < 0)
1.387 + return GLP_ENOPFS;
1.388 + }
1.389 +#endif
1.390 + return 0;
1.391 +}
1.392 +
1.393 +/***********************************************************************
1.394 +* NAME
1.395 +*
1.396 +* npp_improve_bounds - improve current column bounds
1.397 +*
1.398 +* SYNOPSIS
1.399 +*
1.400 +* #include "glpnpp.h"
1.401 +* int npp_improve_bounds(NPP *npp, NPPROW *row, int flag);
1.402 +*
1.403 +* DESCRIPTION
1.404 +*
1.405 +* The routine npp_improve_bounds analyzes specified row (inequality
1.406 +* or equality constraint) to determine implied column bounds and then
1.407 +* uses these bounds to improve (strengthen) current column bounds.
1.408 +*
1.409 +* If the flag is on and current column bounds changed significantly
1.410 +* or the column was fixed, the routine activate rows affected by the
1.411 +* column for further processing. (This feature is intended to be used
1.412 +* in the main loop of the routine npp_process_row.)
1.413 +*
1.414 +* NOTE: This operation can be used for MIP problem only.
1.415 +*
1.416 +* RETURNS
1.417 +*
1.418 +* The routine npp_improve_bounds returns the number of significantly
1.419 +* changed bounds plus the number of column having been fixed due to
1.420 +* bound improvements. However, if the routine detects primal/integer
1.421 +* infeasibility, it returns a negative value. */
1.422 +
1.423 +int npp_improve_bounds(NPP *npp, NPPROW *row, int flag)
1.424 +{ /* improve current column bounds */
1.425 + NPPCOL *col;
1.426 + NPPAIJ *aij, *next_aij, *aaa;
1.427 + int kase, ret, count = 0;
1.428 + double lb, ub;
1.429 + xassert(npp->sol == GLP_MIP);
1.430 + /* row must not be free */
1.431 + xassert(!(row->lb == -DBL_MAX && row->ub == +DBL_MAX));
1.432 + /* determine implied column bounds */
1.433 + npp_implied_bounds(npp, row);
1.434 + /* and use these bounds to strengthen current column bounds */
1.435 + for (aij = row->ptr; aij != NULL; aij = next_aij)
1.436 + { col = aij->col;
1.437 + next_aij = aij->r_next;
1.438 + for (kase = 0; kase <= 1; kase++)
1.439 + { /* save current column bounds */
1.440 + lb = col->lb, ub = col->ub;
1.441 + if (kase == 0)
1.442 + { /* process implied column lower bound */
1.443 + if (col->ll.ll == -DBL_MAX) continue;
1.444 + ret = npp_implied_lower(npp, col, col->ll.ll);
1.445 + }
1.446 + else
1.447 + { /* process implied column upper bound */
1.448 + if (col->uu.uu == +DBL_MAX) continue;
1.449 + ret = npp_implied_upper(npp, col, col->uu.uu);
1.450 + }
1.451 + if (ret == 0 || ret == 1)
1.452 + { /* current column bounds did not change or changed, but
1.453 + not significantly; restore current column bounds */
1.454 + col->lb = lb, col->ub = ub;
1.455 + }
1.456 + else if (ret == 2 || ret == 3)
1.457 + { /* current column bounds changed significantly or column
1.458 + was fixed */
1.459 +#ifdef GLP_DEBUG
1.460 + xprintf("L");
1.461 +#endif
1.462 + count++;
1.463 + /* activate other rows affected by column, if required */
1.464 + if (flag)
1.465 + { for (aaa = col->ptr; aaa != NULL; aaa = aaa->c_next)
1.466 + { if (aaa->row != row)
1.467 + npp_activate_row(npp, aaa->row);
1.468 + }
1.469 + }
1.470 + if (ret == 3)
1.471 + { /* process fixed column */
1.472 +#ifdef GLP_DEBUG
1.473 + xprintf("M");
1.474 +#endif
1.475 + npp_fixed_col(npp, col);
1.476 + /* column was deleted */
1.477 + break; /* for kase */
1.478 + }
1.479 + }
1.480 + else if (ret == 4)
1.481 + { /* primal/integer infeasibility */
1.482 + return -1;
1.483 + }
1.484 + else
1.485 + xassert(ret != ret);
1.486 + }
1.487 + }
1.488 + return count;
1.489 +}
1.490 +
1.491 +/***********************************************************************
1.492 +* NAME
1.493 +*
1.494 +* npp_process_col - perform basic column processing
1.495 +*
1.496 +* SYNOPSIS
1.497 +*
1.498 +* #include "glpnpp.h"
1.499 +* int npp_process_col(NPP *npp, NPPCOL *col);
1.500 +*
1.501 +* DESCRIPTION
1.502 +*
1.503 +* The routine npp_process_col performs basic column processing that
1.504 +* currently includes:
1.505 +*
1.506 +* 1) fixing and removing empty column;
1.507 +*
1.508 +* 2) removing column singleton, which is implied slack variable, and
1.509 +* corresponding row if it becomes free;
1.510 +*
1.511 +* 3) removing bounds of column, which is implied free variable, and
1.512 +* replacing corresponding row by equality constraint.
1.513 +*
1.514 +* Additionally the routine may activate affected rows and/or columns
1.515 +* for further processing.
1.516 +*
1.517 +* RETURNS
1.518 +*
1.519 +* 0 success;
1.520 +*
1.521 +* GLP_ENOPFS primal/integer infeasibility detected;
1.522 +*
1.523 +* GLP_ENODFS dual infeasibility detected. */
1.524 +
1.525 +int npp_process_col(NPP *npp, NPPCOL *col)
1.526 +{ /* perform basic column processing */
1.527 + NPPROW *row;
1.528 + NPPAIJ *aij;
1.529 + int ret;
1.530 + /* column must not be fixed */
1.531 + xassert(col->lb < col->ub);
1.532 + /* start processing column */
1.533 + if (col->ptr == NULL)
1.534 + { /* empty column */
1.535 + ret = npp_empty_col(npp, col);
1.536 + if (ret == 0)
1.537 + { /* column was fixed and deleted */
1.538 +#ifdef GLP_DEBUG
1.539 + xprintf("N");
1.540 +#endif
1.541 + return 0;
1.542 + }
1.543 + else if (ret == 1)
1.544 + { /* dual infeasibility */
1.545 + return GLP_ENODFS;
1.546 + }
1.547 + else
1.548 + xassert(ret != ret);
1.549 + }
1.550 + if (col->ptr->c_next == NULL)
1.551 + { /* column singleton */
1.552 + row = col->ptr->row;
1.553 + if (row->lb == row->ub)
1.554 + { /* equality constraint */
1.555 + if (!col->is_int)
1.556 +slack: { /* implied slack variable */
1.557 +#ifdef GLP_DEBUG
1.558 + xprintf("O");
1.559 +#endif
1.560 + npp_implied_slack(npp, col);
1.561 + /* column was deleted */
1.562 + if (row->lb == -DBL_MAX && row->ub == +DBL_MAX)
1.563 + { /* row became free due to implied slack variable */
1.564 +#ifdef GLP_DEBUG
1.565 + xprintf("P");
1.566 +#endif
1.567 + /* activate columns affected by row */
1.568 + for (aij = row->ptr; aij != NULL; aij = aij->r_next)
1.569 + npp_activate_col(npp, aij->col);
1.570 + /* process free row */
1.571 + npp_free_row(npp, row);
1.572 + /* row was deleted */
1.573 + }
1.574 + else
1.575 + { /* row became inequality constraint; activate it
1.576 + since its length changed due to column deletion */
1.577 + npp_activate_row(npp, row);
1.578 + }
1.579 + return 0;
1.580 + }
1.581 + }
1.582 + else
1.583 + { /* inequality constraint */
1.584 + if (!col->is_int)
1.585 + { ret = npp_implied_free(npp, col);
1.586 + if (ret == 0)
1.587 + { /* implied free variable */
1.588 +#ifdef GLP_DEBUG
1.589 + xprintf("Q");
1.590 +#endif
1.591 + /* column bounds were removed, row was replaced by
1.592 + equality constraint */
1.593 + goto slack;
1.594 + }
1.595 + else if (ret == 1)
1.596 + { /* column is not implied free variable, because its
1.597 + lower and/or upper bounds can be active */
1.598 + }
1.599 + else if (ret == 2)
1.600 + { /* dual infeasibility */
1.601 + return GLP_ENODFS;
1.602 + }
1.603 + }
1.604 + }
1.605 + }
1.606 + /* column still exists */
1.607 + return 0;
1.608 +}
1.609 +
1.610 +/***********************************************************************
1.611 +* NAME
1.612 +*
1.613 +* npp_process_prob - perform basic LP/MIP processing
1.614 +*
1.615 +* SYNOPSIS
1.616 +*
1.617 +* #include "glpnpp.h"
1.618 +* int npp_process_prob(NPP *npp, int hard);
1.619 +*
1.620 +* DESCRIPTION
1.621 +*
1.622 +* The routine npp_process_prob performs basic LP/MIP processing that
1.623 +* currently includes:
1.624 +*
1.625 +* 1) initial LP/MIP processing (see the routine npp_clean_prob),
1.626 +*
1.627 +* 2) basic row processing (see the routine npp_process_row), and
1.628 +*
1.629 +* 3) basic column processing (see the routine npp_process_col).
1.630 +*
1.631 +* If the flag hard is on, the routine attempts to improve current
1.632 +* column bounds multiple times within the main processing loop, in
1.633 +* which case this feature may take a time. Otherwise, if the flag hard
1.634 +* is off, improving column bounds is performed only once at the end of
1.635 +* the main loop. (Note that this feature is used for MIP only.)
1.636 +*
1.637 +* The routine uses two sets: the set of active rows and the set of
1.638 +* active columns. Rows/columns are marked by a flag (the field temp in
1.639 +* NPPROW/NPPCOL). If the flag is non-zero, the row/column is active,
1.640 +* in which case it is placed in the beginning of the row/column list;
1.641 +* otherwise, if the flag is zero, the row/column is inactive, in which
1.642 +* case it is placed in the end of the row/column list. If a row/column
1.643 +* being currently processed may affect other rows/columns, the latters
1.644 +* are activated for further processing.
1.645 +*
1.646 +* RETURNS
1.647 +*
1.648 +* 0 success;
1.649 +*
1.650 +* GLP_ENOPFS primal/integer infeasibility detected;
1.651 +*
1.652 +* GLP_ENODFS dual infeasibility detected. */
1.653 +
1.654 +int npp_process_prob(NPP *npp, int hard)
1.655 +{ /* perform basic LP/MIP processing */
1.656 + NPPROW *row;
1.657 + NPPCOL *col;
1.658 + int processing, ret;
1.659 + /* perform initial LP/MIP processing */
1.660 + npp_clean_prob(npp);
1.661 + /* activate all remaining rows and columns */
1.662 + for (row = npp->r_head; row != NULL; row = row->next)
1.663 + row->temp = 1;
1.664 + for (col = npp->c_head; col != NULL; col = col->next)
1.665 + col->temp = 1;
1.666 + /* main processing loop */
1.667 + processing = 1;
1.668 + while (processing)
1.669 + { processing = 0;
1.670 + /* process all active rows */
1.671 + for (;;)
1.672 + { row = npp->r_head;
1.673 + if (row == NULL || !row->temp) break;
1.674 + npp_deactivate_row(npp, row);
1.675 + ret = npp_process_row(npp, row, hard);
1.676 + if (ret != 0) goto done;
1.677 + processing = 1;
1.678 + }
1.679 + /* process all active columns */
1.680 + for (;;)
1.681 + { col = npp->c_head;
1.682 + if (col == NULL || !col->temp) break;
1.683 + npp_deactivate_col(npp, col);
1.684 + ret = npp_process_col(npp, col);
1.685 + if (ret != 0) goto done;
1.686 + processing = 1;
1.687 + }
1.688 + }
1.689 +#if 1 /* 23/XII-2009 */
1.690 + if (npp->sol == GLP_MIP && !hard)
1.691 + { /* improve current column bounds (optional) */
1.692 + for (row = npp->r_head; row != NULL; row = row->next)
1.693 + { if (npp_improve_bounds(npp, row, 0) < 0)
1.694 + { ret = GLP_ENOPFS;
1.695 + goto done;
1.696 + }
1.697 + }
1.698 + }
1.699 +#endif
1.700 + /* all seems ok */
1.701 + ret = 0;
1.702 +done: xassert(ret == 0 || ret == GLP_ENOPFS || ret == GLP_ENODFS);
1.703 +#ifdef GLP_DEBUG
1.704 + xprintf("\n");
1.705 +#endif
1.706 + return ret;
1.707 +}
1.708 +
1.709 +/**********************************************************************/
1.710 +
1.711 +int npp_simplex(NPP *npp, const glp_smcp *parm)
1.712 +{ /* process LP prior to applying primal/dual simplex method */
1.713 + int ret;
1.714 + xassert(npp->sol == GLP_SOL);
1.715 + xassert(parm == parm);
1.716 + ret = npp_process_prob(npp, 0);
1.717 + return ret;
1.718 +}
1.719 +
1.720 +/**********************************************************************/
1.721 +
1.722 +int npp_integer(NPP *npp, const glp_iocp *parm)
1.723 +{ /* process MIP prior to applying branch-and-bound method */
1.724 + NPPROW *row, *prev_row;
1.725 + NPPCOL *col;
1.726 + NPPAIJ *aij;
1.727 + int count, ret;
1.728 + xassert(npp->sol == GLP_MIP);
1.729 + xassert(parm == parm);
1.730 + /*==============================================================*/
1.731 + /* perform basic MIP processing */
1.732 + ret = npp_process_prob(npp, 1);
1.733 + if (ret != 0) goto done;
1.734 + /*==============================================================*/
1.735 + /* binarize problem, if required */
1.736 + if (parm->binarize)
1.737 + npp_binarize_prob(npp);
1.738 + /*==============================================================*/
1.739 + /* identify hidden packing inequalities */
1.740 + count = 0;
1.741 + /* new rows will be added to the end of the row list, so we go
1.742 + from the end to beginning of the row list */
1.743 + for (row = npp->r_tail; row != NULL; row = prev_row)
1.744 + { prev_row = row->prev;
1.745 + /* skip free row */
1.746 + if (row->lb == -DBL_MAX && row->ub == +DBL_MAX) continue;
1.747 + /* skip equality constraint */
1.748 + if (row->lb == row->ub) continue;
1.749 + /* skip row having less than two variables */
1.750 + if (row->ptr == NULL || row->ptr->r_next == NULL) continue;
1.751 + /* skip row having non-binary variables */
1.752 + for (aij = row->ptr; aij != NULL; aij = aij->r_next)
1.753 + { col = aij->col;
1.754 + if (!(col->is_int && col->lb == 0.0 && col->ub == 1.0))
1.755 + break;
1.756 + }
1.757 + if (aij != NULL) continue;
1.758 + count += npp_hidden_packing(npp, row);
1.759 + }
1.760 + if (count > 0)
1.761 + xprintf("%d hidden packing inequaliti(es) were detected\n",
1.762 + count);
1.763 + /*==============================================================*/
1.764 + /* identify hidden covering inequalities */
1.765 + count = 0;
1.766 + /* new rows will be added to the end of the row list, so we go
1.767 + from the end to beginning of the row list */
1.768 + for (row = npp->r_tail; row != NULL; row = prev_row)
1.769 + { prev_row = row->prev;
1.770 + /* skip free row */
1.771 + if (row->lb == -DBL_MAX && row->ub == +DBL_MAX) continue;
1.772 + /* skip equality constraint */
1.773 + if (row->lb == row->ub) continue;
1.774 + /* skip row having less than three variables */
1.775 + if (row->ptr == NULL || row->ptr->r_next == NULL ||
1.776 + row->ptr->r_next->r_next == NULL) continue;
1.777 + /* skip row having non-binary variables */
1.778 + for (aij = row->ptr; aij != NULL; aij = aij->r_next)
1.779 + { col = aij->col;
1.780 + if (!(col->is_int && col->lb == 0.0 && col->ub == 1.0))
1.781 + break;
1.782 + }
1.783 + if (aij != NULL) continue;
1.784 + count += npp_hidden_covering(npp, row);
1.785 + }
1.786 + if (count > 0)
1.787 + xprintf("%d hidden covering inequaliti(es) were detected\n",
1.788 + count);
1.789 + /*==============================================================*/
1.790 + /* reduce inequality constraint coefficients */
1.791 + count = 0;
1.792 + /* new rows will be added to the end of the row list, so we go
1.793 + from the end to beginning of the row list */
1.794 + for (row = npp->r_tail; row != NULL; row = prev_row)
1.795 + { prev_row = row->prev;
1.796 + /* skip equality constraint */
1.797 + if (row->lb == row->ub) continue;
1.798 + count += npp_reduce_ineq_coef(npp, row);
1.799 + }
1.800 + if (count > 0)
1.801 + xprintf("%d constraint coefficient(s) were reduced\n", count);
1.802 + /*==============================================================*/
1.803 +#ifdef GLP_DEBUG
1.804 + routine(npp);
1.805 +#endif
1.806 + /*==============================================================*/
1.807 + /* all seems ok */
1.808 + ret = 0;
1.809 +done: return ret;
1.810 +}
1.811 +
1.812 +/* eof */