lemon-project-template-glpk

annotate deps/glpk/src/glpnpp05.c @ 9:33de93886c88

find changesets by author, revision, files, or words in the commit message
Import GLPK 4.47
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 20:59:10 +0100
parents
children
rev   line source
alpar@9 1 /* glpnpp05.c */
alpar@9 2
alpar@9 3 /***********************************************************************
alpar@9 4 * This code is part of GLPK (GNU Linear Programming Kit).
alpar@9 5 *
alpar@9 6 * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
alpar@9 7 * 2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics,
alpar@9 8 * Moscow Aviation Institute, Moscow, Russia. All rights reserved.
alpar@9 9 * E-mail: <mao@gnu.org>.
alpar@9 10 *
alpar@9 11 * GLPK is free software: you can redistribute it and/or modify it
alpar@9 12 * under the terms of the GNU General Public License as published by
alpar@9 13 * the Free Software Foundation, either version 3 of the License, or
alpar@9 14 * (at your option) any later version.
alpar@9 15 *
alpar@9 16 * GLPK is distributed in the hope that it will be useful, but WITHOUT
alpar@9 17 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
alpar@9 18 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
alpar@9 19 * License for more details.
alpar@9 20 *
alpar@9 21 * You should have received a copy of the GNU General Public License
alpar@9 22 * along with GLPK. If not, see <http://www.gnu.org/licenses/>.
alpar@9 23 ***********************************************************************/
alpar@9 24
alpar@9 25 #include "glpnpp.h"
alpar@9 26
alpar@9 27 /***********************************************************************
alpar@9 28 * NAME
alpar@9 29 *
alpar@9 30 * npp_clean_prob - perform initial LP/MIP processing
alpar@9 31 *
alpar@9 32 * SYNOPSIS
alpar@9 33 *
alpar@9 34 * #include "glpnpp.h"
alpar@9 35 * void npp_clean_prob(NPP *npp);
alpar@9 36 *
alpar@9 37 * DESCRIPTION
alpar@9 38 *
alpar@9 39 * The routine npp_clean_prob performs initial LP/MIP processing that
alpar@9 40 * currently includes:
alpar@9 41 *
alpar@9 42 * 1) removing free rows;
alpar@9 43 *
alpar@9 44 * 2) replacing double-sided constraint rows with almost identical
alpar@9 45 * bounds, by equality constraint rows;
alpar@9 46 *
alpar@9 47 * 3) removing fixed columns;
alpar@9 48 *
alpar@9 49 * 4) replacing double-bounded columns with almost identical bounds by
alpar@9 50 * fixed columns and removing those columns;
alpar@9 51 *
alpar@9 52 * 5) initial processing constraint coefficients (not implemented);
alpar@9 53 *
alpar@9 54 * 6) initial processing objective coefficients (not implemented). */
alpar@9 55
alpar@9 56 void npp_clean_prob(NPP *npp)
alpar@9 57 { /* perform initial LP/MIP processing */
alpar@9 58 NPPROW *row, *next_row;
alpar@9 59 NPPCOL *col, *next_col;
alpar@9 60 int ret;
alpar@9 61 xassert(npp == npp);
alpar@9 62 /* process rows which originally are free */
alpar@9 63 for (row = npp->r_head; row != NULL; row = next_row)
alpar@9 64 { next_row = row->next;
alpar@9 65 if (row->lb == -DBL_MAX && row->ub == +DBL_MAX)
alpar@9 66 { /* process free row */
alpar@9 67 #ifdef GLP_DEBUG
alpar@9 68 xprintf("1");
alpar@9 69 #endif
alpar@9 70 npp_free_row(npp, row);
alpar@9 71 /* row was deleted */
alpar@9 72 }
alpar@9 73 }
alpar@9 74 /* process rows which originally are double-sided inequalities */
alpar@9 75 for (row = npp->r_head; row != NULL; row = next_row)
alpar@9 76 { next_row = row->next;
alpar@9 77 if (row->lb != -DBL_MAX && row->ub != +DBL_MAX &&
alpar@9 78 row->lb < row->ub)
alpar@9 79 { ret = npp_make_equality(npp, row);
alpar@9 80 if (ret == 0)
alpar@9 81 ;
alpar@9 82 else if (ret == 1)
alpar@9 83 { /* row was replaced by equality constraint */
alpar@9 84 #ifdef GLP_DEBUG
alpar@9 85 xprintf("2");
alpar@9 86 #endif
alpar@9 87 }
alpar@9 88 else
alpar@9 89 xassert(ret != ret);
alpar@9 90 }
alpar@9 91 }
alpar@9 92 /* process columns which are originally fixed */
alpar@9 93 for (col = npp->c_head; col != NULL; col = next_col)
alpar@9 94 { next_col = col->next;
alpar@9 95 if (col->lb == col->ub)
alpar@9 96 { /* process fixed column */
alpar@9 97 #ifdef GLP_DEBUG
alpar@9 98 xprintf("3");
alpar@9 99 #endif
alpar@9 100 npp_fixed_col(npp, col);
alpar@9 101 /* column was deleted */
alpar@9 102 }
alpar@9 103 }
alpar@9 104 /* process columns which are originally double-bounded */
alpar@9 105 for (col = npp->c_head; col != NULL; col = next_col)
alpar@9 106 { next_col = col->next;
alpar@9 107 if (col->lb != -DBL_MAX && col->ub != +DBL_MAX &&
alpar@9 108 col->lb < col->ub)
alpar@9 109 { ret = npp_make_fixed(npp, col);
alpar@9 110 if (ret == 0)
alpar@9 111 ;
alpar@9 112 else if (ret == 1)
alpar@9 113 { /* column was replaced by fixed column; process it */
alpar@9 114 #ifdef GLP_DEBUG
alpar@9 115 xprintf("4");
alpar@9 116 #endif
alpar@9 117 npp_fixed_col(npp, col);
alpar@9 118 /* column was deleted */
alpar@9 119 }
alpar@9 120 }
alpar@9 121 }
alpar@9 122 return;
alpar@9 123 }
alpar@9 124
alpar@9 125 /***********************************************************************
alpar@9 126 * NAME
alpar@9 127 *
alpar@9 128 * npp_process_row - perform basic row processing
alpar@9 129 *
alpar@9 130 * SYNOPSIS
alpar@9 131 *
alpar@9 132 * #include "glpnpp.h"
alpar@9 133 * int npp_process_row(NPP *npp, NPPROW *row, int hard);
alpar@9 134 *
alpar@9 135 * DESCRIPTION
alpar@9 136 *
alpar@9 137 * The routine npp_process_row performs basic row processing that
alpar@9 138 * currently includes:
alpar@9 139 *
alpar@9 140 * 1) removing empty row;
alpar@9 141 *
alpar@9 142 * 2) removing equality constraint row singleton and corresponding
alpar@9 143 * column;
alpar@9 144 *
alpar@9 145 * 3) removing inequality constraint row singleton and corresponding
alpar@9 146 * column if it was fixed;
alpar@9 147 *
alpar@9 148 * 4) performing general row analysis;
alpar@9 149 *
alpar@9 150 * 5) removing redundant row bounds;
alpar@9 151 *
alpar@9 152 * 6) removing forcing row and corresponding columns;
alpar@9 153 *
alpar@9 154 * 7) removing row which becomes free due to redundant bounds;
alpar@9 155 *
alpar@9 156 * 8) computing implied bounds for all columns in the row and using
alpar@9 157 * them to strengthen current column bounds (MIP only, optional,
alpar@9 158 * performed if the flag hard is on).
alpar@9 159 *
alpar@9 160 * Additionally the routine may activate affected rows and/or columns
alpar@9 161 * for further processing.
alpar@9 162 *
alpar@9 163 * RETURNS
alpar@9 164 *
alpar@9 165 * 0 success;
alpar@9 166 *
alpar@9 167 * GLP_ENOPFS primal/integer infeasibility detected;
alpar@9 168 *
alpar@9 169 * GLP_ENODFS dual infeasibility detected. */
alpar@9 170
alpar@9 171 int npp_process_row(NPP *npp, NPPROW *row, int hard)
alpar@9 172 { /* perform basic row processing */
alpar@9 173 NPPCOL *col;
alpar@9 174 NPPAIJ *aij, *next_aij, *aaa;
alpar@9 175 int ret;
alpar@9 176 /* row must not be free */
alpar@9 177 xassert(!(row->lb == -DBL_MAX && row->ub == +DBL_MAX));
alpar@9 178 /* start processing row */
alpar@9 179 if (row->ptr == NULL)
alpar@9 180 { /* empty row */
alpar@9 181 ret = npp_empty_row(npp, row);
alpar@9 182 if (ret == 0)
alpar@9 183 { /* row was deleted */
alpar@9 184 #ifdef GLP_DEBUG
alpar@9 185 xprintf("A");
alpar@9 186 #endif
alpar@9 187 return 0;
alpar@9 188 }
alpar@9 189 else if (ret == 1)
alpar@9 190 { /* primal infeasibility */
alpar@9 191 return GLP_ENOPFS;
alpar@9 192 }
alpar@9 193 else
alpar@9 194 xassert(ret != ret);
alpar@9 195 }
alpar@9 196 if (row->ptr->r_next == NULL)
alpar@9 197 { /* row singleton */
alpar@9 198 col = row->ptr->col;
alpar@9 199 if (row->lb == row->ub)
alpar@9 200 { /* equality constraint */
alpar@9 201 ret = npp_eq_singlet(npp, row);
alpar@9 202 if (ret == 0)
alpar@9 203 { /* column was fixed, row was deleted */
alpar@9 204 #ifdef GLP_DEBUG
alpar@9 205 xprintf("B");
alpar@9 206 #endif
alpar@9 207 /* activate rows affected by column */
alpar@9 208 for (aij = col->ptr; aij != NULL; aij = aij->c_next)
alpar@9 209 npp_activate_row(npp, aij->row);
alpar@9 210 /* process fixed column */
alpar@9 211 npp_fixed_col(npp, col);
alpar@9 212 /* column was deleted */
alpar@9 213 return 0;
alpar@9 214 }
alpar@9 215 else if (ret == 1 || ret == 2)
alpar@9 216 { /* primal/integer infeasibility */
alpar@9 217 return GLP_ENOPFS;
alpar@9 218 }
alpar@9 219 else
alpar@9 220 xassert(ret != ret);
alpar@9 221 }
alpar@9 222 else
alpar@9 223 { /* inequality constraint */
alpar@9 224 ret = npp_ineq_singlet(npp, row);
alpar@9 225 if (0 <= ret && ret <= 3)
alpar@9 226 { /* row was deleted */
alpar@9 227 #ifdef GLP_DEBUG
alpar@9 228 xprintf("C");
alpar@9 229 #endif
alpar@9 230 /* activate column, since its length was changed due to
alpar@9 231 row deletion */
alpar@9 232 npp_activate_col(npp, col);
alpar@9 233 if (ret >= 2)
alpar@9 234 { /* column bounds changed significantly or column was
alpar@9 235 fixed */
alpar@9 236 /* activate rows affected by column */
alpar@9 237 for (aij = col->ptr; aij != NULL; aij = aij->c_next)
alpar@9 238 npp_activate_row(npp, aij->row);
alpar@9 239 }
alpar@9 240 if (ret == 3)
alpar@9 241 { /* column was fixed; process it */
alpar@9 242 #ifdef GLP_DEBUG
alpar@9 243 xprintf("D");
alpar@9 244 #endif
alpar@9 245 npp_fixed_col(npp, col);
alpar@9 246 /* column was deleted */
alpar@9 247 }
alpar@9 248 return 0;
alpar@9 249 }
alpar@9 250 else if (ret == 4)
alpar@9 251 { /* primal infeasibility */
alpar@9 252 return GLP_ENOPFS;
alpar@9 253 }
alpar@9 254 else
alpar@9 255 xassert(ret != ret);
alpar@9 256 }
alpar@9 257 }
alpar@9 258 #if 0
alpar@9 259 /* sometimes this causes too large round-off errors; probably
alpar@9 260 pivot coefficient should be chosen more carefully */
alpar@9 261 if (row->ptr->r_next->r_next == NULL)
alpar@9 262 { /* row doubleton */
alpar@9 263 if (row->lb == row->ub)
alpar@9 264 { /* equality constraint */
alpar@9 265 if (!(row->ptr->col->is_int ||
alpar@9 266 row->ptr->r_next->col->is_int))
alpar@9 267 { /* both columns are continuous */
alpar@9 268 NPPCOL *q;
alpar@9 269 q = npp_eq_doublet(npp, row);
alpar@9 270 if (q != NULL)
alpar@9 271 { /* column q was eliminated */
alpar@9 272 #ifdef GLP_DEBUG
alpar@9 273 xprintf("E");
alpar@9 274 #endif
alpar@9 275 /* now column q is singleton of type "implied slack
alpar@9 276 variable"; we process it here to make sure that on
alpar@9 277 recovering basic solution the row is always active
alpar@9 278 equality constraint (as required by the routine
alpar@9 279 rcv_eq_doublet) */
alpar@9 280 xassert(npp_process_col(npp, q) == 0);
alpar@9 281 /* column q was deleted; note that row p also may be
alpar@9 282 deleted */
alpar@9 283 return 0;
alpar@9 284 }
alpar@9 285 }
alpar@9 286 }
alpar@9 287 }
alpar@9 288 #endif
alpar@9 289 /* general row analysis */
alpar@9 290 ret = npp_analyze_row(npp, row);
alpar@9 291 xassert(0x00 <= ret && ret <= 0xFF);
alpar@9 292 if (ret == 0x33)
alpar@9 293 { /* row bounds are inconsistent with column bounds */
alpar@9 294 return GLP_ENOPFS;
alpar@9 295 }
alpar@9 296 if ((ret & 0x0F) == 0x00)
alpar@9 297 { /* row lower bound does not exist or redundant */
alpar@9 298 if (row->lb != -DBL_MAX)
alpar@9 299 { /* remove redundant row lower bound */
alpar@9 300 #ifdef GLP_DEBUG
alpar@9 301 xprintf("F");
alpar@9 302 #endif
alpar@9 303 npp_inactive_bound(npp, row, 0);
alpar@9 304 }
alpar@9 305 }
alpar@9 306 else if ((ret & 0x0F) == 0x01)
alpar@9 307 { /* row lower bound can be active */
alpar@9 308 /* see below */
alpar@9 309 }
alpar@9 310 else if ((ret & 0x0F) == 0x02)
alpar@9 311 { /* row lower bound is a forcing bound */
alpar@9 312 #ifdef GLP_DEBUG
alpar@9 313 xprintf("G");
alpar@9 314 #endif
alpar@9 315 /* process forcing row */
alpar@9 316 if (npp_forcing_row(npp, row, 0) == 0)
alpar@9 317 fixup: { /* columns were fixed, row was made free */
alpar@9 318 for (aij = row->ptr; aij != NULL; aij = next_aij)
alpar@9 319 { /* process column fixed by forcing row */
alpar@9 320 #ifdef GLP_DEBUG
alpar@9 321 xprintf("H");
alpar@9 322 #endif
alpar@9 323 col = aij->col;
alpar@9 324 next_aij = aij->r_next;
alpar@9 325 /* activate rows affected by column */
alpar@9 326 for (aaa = col->ptr; aaa != NULL; aaa = aaa->c_next)
alpar@9 327 npp_activate_row(npp, aaa->row);
alpar@9 328 /* process fixed column */
alpar@9 329 npp_fixed_col(npp, col);
alpar@9 330 /* column was deleted */
alpar@9 331 }
alpar@9 332 /* process free row (which now is empty due to deletion of
alpar@9 333 all its columns) */
alpar@9 334 npp_free_row(npp, row);
alpar@9 335 /* row was deleted */
alpar@9 336 return 0;
alpar@9 337 }
alpar@9 338 }
alpar@9 339 else
alpar@9 340 xassert(ret != ret);
alpar@9 341 if ((ret & 0xF0) == 0x00)
alpar@9 342 { /* row upper bound does not exist or redundant */
alpar@9 343 if (row->ub != +DBL_MAX)
alpar@9 344 { /* remove redundant row upper bound */
alpar@9 345 #ifdef GLP_DEBUG
alpar@9 346 xprintf("I");
alpar@9 347 #endif
alpar@9 348 npp_inactive_bound(npp, row, 1);
alpar@9 349 }
alpar@9 350 }
alpar@9 351 else if ((ret & 0xF0) == 0x10)
alpar@9 352 { /* row upper bound can be active */
alpar@9 353 /* see below */
alpar@9 354 }
alpar@9 355 else if ((ret & 0xF0) == 0x20)
alpar@9 356 { /* row upper bound is a forcing bound */
alpar@9 357 #ifdef GLP_DEBUG
alpar@9 358 xprintf("J");
alpar@9 359 #endif
alpar@9 360 /* process forcing row */
alpar@9 361 if (npp_forcing_row(npp, row, 1) == 0) goto fixup;
alpar@9 362 }
alpar@9 363 else
alpar@9 364 xassert(ret != ret);
alpar@9 365 if (row->lb == -DBL_MAX && row->ub == +DBL_MAX)
alpar@9 366 { /* row became free due to redundant bounds removal */
alpar@9 367 #ifdef GLP_DEBUG
alpar@9 368 xprintf("K");
alpar@9 369 #endif
alpar@9 370 /* activate its columns, since their length will change due
alpar@9 371 to row deletion */
alpar@9 372 for (aij = row->ptr; aij != NULL; aij = aij->r_next)
alpar@9 373 npp_activate_col(npp, aij->col);
alpar@9 374 /* process free row */
alpar@9 375 npp_free_row(npp, row);
alpar@9 376 /* row was deleted */
alpar@9 377 return 0;
alpar@9 378 }
alpar@9 379 #if 1 /* 23/XII-2009 */
alpar@9 380 /* row lower and/or upper bounds can be active */
alpar@9 381 if (npp->sol == GLP_MIP && hard)
alpar@9 382 { /* improve current column bounds (optional) */
alpar@9 383 if (npp_improve_bounds(npp, row, 1) < 0)
alpar@9 384 return GLP_ENOPFS;
alpar@9 385 }
alpar@9 386 #endif
alpar@9 387 return 0;
alpar@9 388 }
alpar@9 389
alpar@9 390 /***********************************************************************
alpar@9 391 * NAME
alpar@9 392 *
alpar@9 393 * npp_improve_bounds - improve current column bounds
alpar@9 394 *
alpar@9 395 * SYNOPSIS
alpar@9 396 *
alpar@9 397 * #include "glpnpp.h"
alpar@9 398 * int npp_improve_bounds(NPP *npp, NPPROW *row, int flag);
alpar@9 399 *
alpar@9 400 * DESCRIPTION
alpar@9 401 *
alpar@9 402 * The routine npp_improve_bounds analyzes specified row (inequality
alpar@9 403 * or equality constraint) to determine implied column bounds and then
alpar@9 404 * uses these bounds to improve (strengthen) current column bounds.
alpar@9 405 *
alpar@9 406 * If the flag is on and current column bounds changed significantly
alpar@9 407 * or the column was fixed, the routine activate rows affected by the
alpar@9 408 * column for further processing. (This feature is intended to be used
alpar@9 409 * in the main loop of the routine npp_process_row.)
alpar@9 410 *
alpar@9 411 * NOTE: This operation can be used for MIP problem only.
alpar@9 412 *
alpar@9 413 * RETURNS
alpar@9 414 *
alpar@9 415 * The routine npp_improve_bounds returns the number of significantly
alpar@9 416 * changed bounds plus the number of column having been fixed due to
alpar@9 417 * bound improvements. However, if the routine detects primal/integer
alpar@9 418 * infeasibility, it returns a negative value. */
alpar@9 419
alpar@9 420 int npp_improve_bounds(NPP *npp, NPPROW *row, int flag)
alpar@9 421 { /* improve current column bounds */
alpar@9 422 NPPCOL *col;
alpar@9 423 NPPAIJ *aij, *next_aij, *aaa;
alpar@9 424 int kase, ret, count = 0;
alpar@9 425 double lb, ub;
alpar@9 426 xassert(npp->sol == GLP_MIP);
alpar@9 427 /* row must not be free */
alpar@9 428 xassert(!(row->lb == -DBL_MAX && row->ub == +DBL_MAX));
alpar@9 429 /* determine implied column bounds */
alpar@9 430 npp_implied_bounds(npp, row);
alpar@9 431 /* and use these bounds to strengthen current column bounds */
alpar@9 432 for (aij = row->ptr; aij != NULL; aij = next_aij)
alpar@9 433 { col = aij->col;
alpar@9 434 next_aij = aij->r_next;
alpar@9 435 for (kase = 0; kase <= 1; kase++)
alpar@9 436 { /* save current column bounds */
alpar@9 437 lb = col->lb, ub = col->ub;
alpar@9 438 if (kase == 0)
alpar@9 439 { /* process implied column lower bound */
alpar@9 440 if (col->ll.ll == -DBL_MAX) continue;
alpar@9 441 ret = npp_implied_lower(npp, col, col->ll.ll);
alpar@9 442 }
alpar@9 443 else
alpar@9 444 { /* process implied column upper bound */
alpar@9 445 if (col->uu.uu == +DBL_MAX) continue;
alpar@9 446 ret = npp_implied_upper(npp, col, col->uu.uu);
alpar@9 447 }
alpar@9 448 if (ret == 0 || ret == 1)
alpar@9 449 { /* current column bounds did not change or changed, but
alpar@9 450 not significantly; restore current column bounds */
alpar@9 451 col->lb = lb, col->ub = ub;
alpar@9 452 }
alpar@9 453 else if (ret == 2 || ret == 3)
alpar@9 454 { /* current column bounds changed significantly or column
alpar@9 455 was fixed */
alpar@9 456 #ifdef GLP_DEBUG
alpar@9 457 xprintf("L");
alpar@9 458 #endif
alpar@9 459 count++;
alpar@9 460 /* activate other rows affected by column, if required */
alpar@9 461 if (flag)
alpar@9 462 { for (aaa = col->ptr; aaa != NULL; aaa = aaa->c_next)
alpar@9 463 { if (aaa->row != row)
alpar@9 464 npp_activate_row(npp, aaa->row);
alpar@9 465 }
alpar@9 466 }
alpar@9 467 if (ret == 3)
alpar@9 468 { /* process fixed column */
alpar@9 469 #ifdef GLP_DEBUG
alpar@9 470 xprintf("M");
alpar@9 471 #endif
alpar@9 472 npp_fixed_col(npp, col);
alpar@9 473 /* column was deleted */
alpar@9 474 break; /* for kase */
alpar@9 475 }
alpar@9 476 }
alpar@9 477 else if (ret == 4)
alpar@9 478 { /* primal/integer infeasibility */
alpar@9 479 return -1;
alpar@9 480 }
alpar@9 481 else
alpar@9 482 xassert(ret != ret);
alpar@9 483 }
alpar@9 484 }
alpar@9 485 return count;
alpar@9 486 }
alpar@9 487
alpar@9 488 /***********************************************************************
alpar@9 489 * NAME
alpar@9 490 *
alpar@9 491 * npp_process_col - perform basic column processing
alpar@9 492 *
alpar@9 493 * SYNOPSIS
alpar@9 494 *
alpar@9 495 * #include "glpnpp.h"
alpar@9 496 * int npp_process_col(NPP *npp, NPPCOL *col);
alpar@9 497 *
alpar@9 498 * DESCRIPTION
alpar@9 499 *
alpar@9 500 * The routine npp_process_col performs basic column processing that
alpar@9 501 * currently includes:
alpar@9 502 *
alpar@9 503 * 1) fixing and removing empty column;
alpar@9 504 *
alpar@9 505 * 2) removing column singleton, which is implied slack variable, and
alpar@9 506 * corresponding row if it becomes free;
alpar@9 507 *
alpar@9 508 * 3) removing bounds of column, which is implied free variable, and
alpar@9 509 * replacing corresponding row by equality constraint.
alpar@9 510 *
alpar@9 511 * Additionally the routine may activate affected rows and/or columns
alpar@9 512 * for further processing.
alpar@9 513 *
alpar@9 514 * RETURNS
alpar@9 515 *
alpar@9 516 * 0 success;
alpar@9 517 *
alpar@9 518 * GLP_ENOPFS primal/integer infeasibility detected;
alpar@9 519 *
alpar@9 520 * GLP_ENODFS dual infeasibility detected. */
alpar@9 521
alpar@9 522 int npp_process_col(NPP *npp, NPPCOL *col)
alpar@9 523 { /* perform basic column processing */
alpar@9 524 NPPROW *row;
alpar@9 525 NPPAIJ *aij;
alpar@9 526 int ret;
alpar@9 527 /* column must not be fixed */
alpar@9 528 xassert(col->lb < col->ub);
alpar@9 529 /* start processing column */
alpar@9 530 if (col->ptr == NULL)
alpar@9 531 { /* empty column */
alpar@9 532 ret = npp_empty_col(npp, col);
alpar@9 533 if (ret == 0)
alpar@9 534 { /* column was fixed and deleted */
alpar@9 535 #ifdef GLP_DEBUG
alpar@9 536 xprintf("N");
alpar@9 537 #endif
alpar@9 538 return 0;
alpar@9 539 }
alpar@9 540 else if (ret == 1)
alpar@9 541 { /* dual infeasibility */
alpar@9 542 return GLP_ENODFS;
alpar@9 543 }
alpar@9 544 else
alpar@9 545 xassert(ret != ret);
alpar@9 546 }
alpar@9 547 if (col->ptr->c_next == NULL)
alpar@9 548 { /* column singleton */
alpar@9 549 row = col->ptr->row;
alpar@9 550 if (row->lb == row->ub)
alpar@9 551 { /* equality constraint */
alpar@9 552 if (!col->is_int)
alpar@9 553 slack: { /* implied slack variable */
alpar@9 554 #ifdef GLP_DEBUG
alpar@9 555 xprintf("O");
alpar@9 556 #endif
alpar@9 557 npp_implied_slack(npp, col);
alpar@9 558 /* column was deleted */
alpar@9 559 if (row->lb == -DBL_MAX && row->ub == +DBL_MAX)
alpar@9 560 { /* row became free due to implied slack variable */
alpar@9 561 #ifdef GLP_DEBUG
alpar@9 562 xprintf("P");
alpar@9 563 #endif
alpar@9 564 /* activate columns affected by row */
alpar@9 565 for (aij = row->ptr; aij != NULL; aij = aij->r_next)
alpar@9 566 npp_activate_col(npp, aij->col);
alpar@9 567 /* process free row */
alpar@9 568 npp_free_row(npp, row);
alpar@9 569 /* row was deleted */
alpar@9 570 }
alpar@9 571 else
alpar@9 572 { /* row became inequality constraint; activate it
alpar@9 573 since its length changed due to column deletion */
alpar@9 574 npp_activate_row(npp, row);
alpar@9 575 }
alpar@9 576 return 0;
alpar@9 577 }
alpar@9 578 }
alpar@9 579 else
alpar@9 580 { /* inequality constraint */
alpar@9 581 if (!col->is_int)
alpar@9 582 { ret = npp_implied_free(npp, col);
alpar@9 583 if (ret == 0)
alpar@9 584 { /* implied free variable */
alpar@9 585 #ifdef GLP_DEBUG
alpar@9 586 xprintf("Q");
alpar@9 587 #endif
alpar@9 588 /* column bounds were removed, row was replaced by
alpar@9 589 equality constraint */
alpar@9 590 goto slack;
alpar@9 591 }
alpar@9 592 else if (ret == 1)
alpar@9 593 { /* column is not implied free variable, because its
alpar@9 594 lower and/or upper bounds can be active */
alpar@9 595 }
alpar@9 596 else if (ret == 2)
alpar@9 597 { /* dual infeasibility */
alpar@9 598 return GLP_ENODFS;
alpar@9 599 }
alpar@9 600 }
alpar@9 601 }
alpar@9 602 }
alpar@9 603 /* column still exists */
alpar@9 604 return 0;
alpar@9 605 }
alpar@9 606
alpar@9 607 /***********************************************************************
alpar@9 608 * NAME
alpar@9 609 *
alpar@9 610 * npp_process_prob - perform basic LP/MIP processing
alpar@9 611 *
alpar@9 612 * SYNOPSIS
alpar@9 613 *
alpar@9 614 * #include "glpnpp.h"
alpar@9 615 * int npp_process_prob(NPP *npp, int hard);
alpar@9 616 *
alpar@9 617 * DESCRIPTION
alpar@9 618 *
alpar@9 619 * The routine npp_process_prob performs basic LP/MIP processing that
alpar@9 620 * currently includes:
alpar@9 621 *
alpar@9 622 * 1) initial LP/MIP processing (see the routine npp_clean_prob),
alpar@9 623 *
alpar@9 624 * 2) basic row processing (see the routine npp_process_row), and
alpar@9 625 *
alpar@9 626 * 3) basic column processing (see the routine npp_process_col).
alpar@9 627 *
alpar@9 628 * If the flag hard is on, the routine attempts to improve current
alpar@9 629 * column bounds multiple times within the main processing loop, in
alpar@9 630 * which case this feature may take a time. Otherwise, if the flag hard
alpar@9 631 * is off, improving column bounds is performed only once at the end of
alpar@9 632 * the main loop. (Note that this feature is used for MIP only.)
alpar@9 633 *
alpar@9 634 * The routine uses two sets: the set of active rows and the set of
alpar@9 635 * active columns. Rows/columns are marked by a flag (the field temp in
alpar@9 636 * NPPROW/NPPCOL). If the flag is non-zero, the row/column is active,
alpar@9 637 * in which case it is placed in the beginning of the row/column list;
alpar@9 638 * otherwise, if the flag is zero, the row/column is inactive, in which
alpar@9 639 * case it is placed in the end of the row/column list. If a row/column
alpar@9 640 * being currently processed may affect other rows/columns, the latters
alpar@9 641 * are activated for further processing.
alpar@9 642 *
alpar@9 643 * RETURNS
alpar@9 644 *
alpar@9 645 * 0 success;
alpar@9 646 *
alpar@9 647 * GLP_ENOPFS primal/integer infeasibility detected;
alpar@9 648 *
alpar@9 649 * GLP_ENODFS dual infeasibility detected. */
alpar@9 650
alpar@9 651 int npp_process_prob(NPP *npp, int hard)
alpar@9 652 { /* perform basic LP/MIP processing */
alpar@9 653 NPPROW *row;
alpar@9 654 NPPCOL *col;
alpar@9 655 int processing, ret;
alpar@9 656 /* perform initial LP/MIP processing */
alpar@9 657 npp_clean_prob(npp);
alpar@9 658 /* activate all remaining rows and columns */
alpar@9 659 for (row = npp->r_head; row != NULL; row = row->next)
alpar@9 660 row->temp = 1;
alpar@9 661 for (col = npp->c_head; col != NULL; col = col->next)
alpar@9 662 col->temp = 1;
alpar@9 663 /* main processing loop */
alpar@9 664 processing = 1;
alpar@9 665 while (processing)
alpar@9 666 { processing = 0;
alpar@9 667 /* process all active rows */
alpar@9 668 for (;;)
alpar@9 669 { row = npp->r_head;
alpar@9 670 if (row == NULL || !row->temp) break;
alpar@9 671 npp_deactivate_row(npp, row);
alpar@9 672 ret = npp_process_row(npp, row, hard);
alpar@9 673 if (ret != 0) goto done;
alpar@9 674 processing = 1;
alpar@9 675 }
alpar@9 676 /* process all active columns */
alpar@9 677 for (;;)
alpar@9 678 { col = npp->c_head;
alpar@9 679 if (col == NULL || !col->temp) break;
alpar@9 680 npp_deactivate_col(npp, col);
alpar@9 681 ret = npp_process_col(npp, col);
alpar@9 682 if (ret != 0) goto done;
alpar@9 683 processing = 1;
alpar@9 684 }
alpar@9 685 }
alpar@9 686 #if 1 /* 23/XII-2009 */
alpar@9 687 if (npp->sol == GLP_MIP && !hard)
alpar@9 688 { /* improve current column bounds (optional) */
alpar@9 689 for (row = npp->r_head; row != NULL; row = row->next)
alpar@9 690 { if (npp_improve_bounds(npp, row, 0) < 0)
alpar@9 691 { ret = GLP_ENOPFS;
alpar@9 692 goto done;
alpar@9 693 }
alpar@9 694 }
alpar@9 695 }
alpar@9 696 #endif
alpar@9 697 /* all seems ok */
alpar@9 698 ret = 0;
alpar@9 699 done: xassert(ret == 0 || ret == GLP_ENOPFS || ret == GLP_ENODFS);
alpar@9 700 #ifdef GLP_DEBUG
alpar@9 701 xprintf("\n");
alpar@9 702 #endif
alpar@9 703 return ret;
alpar@9 704 }
alpar@9 705
alpar@9 706 /**********************************************************************/
alpar@9 707
alpar@9 708 int npp_simplex(NPP *npp, const glp_smcp *parm)
alpar@9 709 { /* process LP prior to applying primal/dual simplex method */
alpar@9 710 int ret;
alpar@9 711 xassert(npp->sol == GLP_SOL);
alpar@9 712 xassert(parm == parm);
alpar@9 713 ret = npp_process_prob(npp, 0);
alpar@9 714 return ret;
alpar@9 715 }
alpar@9 716
alpar@9 717 /**********************************************************************/
alpar@9 718
alpar@9 719 int npp_integer(NPP *npp, const glp_iocp *parm)
alpar@9 720 { /* process MIP prior to applying branch-and-bound method */
alpar@9 721 NPPROW *row, *prev_row;
alpar@9 722 NPPCOL *col;
alpar@9 723 NPPAIJ *aij;
alpar@9 724 int count, ret;
alpar@9 725 xassert(npp->sol == GLP_MIP);
alpar@9 726 xassert(parm == parm);
alpar@9 727 /*==============================================================*/
alpar@9 728 /* perform basic MIP processing */
alpar@9 729 ret = npp_process_prob(npp, 1);
alpar@9 730 if (ret != 0) goto done;
alpar@9 731 /*==============================================================*/
alpar@9 732 /* binarize problem, if required */
alpar@9 733 if (parm->binarize)
alpar@9 734 npp_binarize_prob(npp);
alpar@9 735 /*==============================================================*/
alpar@9 736 /* identify hidden packing inequalities */
alpar@9 737 count = 0;
alpar@9 738 /* new rows will be added to the end of the row list, so we go
alpar@9 739 from the end to beginning of the row list */
alpar@9 740 for (row = npp->r_tail; row != NULL; row = prev_row)
alpar@9 741 { prev_row = row->prev;
alpar@9 742 /* skip free row */
alpar@9 743 if (row->lb == -DBL_MAX && row->ub == +DBL_MAX) continue;
alpar@9 744 /* skip equality constraint */
alpar@9 745 if (row->lb == row->ub) continue;
alpar@9 746 /* skip row having less than two variables */
alpar@9 747 if (row->ptr == NULL || row->ptr->r_next == NULL) continue;
alpar@9 748 /* skip row having non-binary variables */
alpar@9 749 for (aij = row->ptr; aij != NULL; aij = aij->r_next)
alpar@9 750 { col = aij->col;
alpar@9 751 if (!(col->is_int && col->lb == 0.0 && col->ub == 1.0))
alpar@9 752 break;
alpar@9 753 }
alpar@9 754 if (aij != NULL) continue;
alpar@9 755 count += npp_hidden_packing(npp, row);
alpar@9 756 }
alpar@9 757 if (count > 0)
alpar@9 758 xprintf("%d hidden packing inequaliti(es) were detected\n",
alpar@9 759 count);
alpar@9 760 /*==============================================================*/
alpar@9 761 /* identify hidden covering inequalities */
alpar@9 762 count = 0;
alpar@9 763 /* new rows will be added to the end of the row list, so we go
alpar@9 764 from the end to beginning of the row list */
alpar@9 765 for (row = npp->r_tail; row != NULL; row = prev_row)
alpar@9 766 { prev_row = row->prev;
alpar@9 767 /* skip free row */
alpar@9 768 if (row->lb == -DBL_MAX && row->ub == +DBL_MAX) continue;
alpar@9 769 /* skip equality constraint */
alpar@9 770 if (row->lb == row->ub) continue;
alpar@9 771 /* skip row having less than three variables */
alpar@9 772 if (row->ptr == NULL || row->ptr->r_next == NULL ||
alpar@9 773 row->ptr->r_next->r_next == NULL) continue;
alpar@9 774 /* skip row having non-binary variables */
alpar@9 775 for (aij = row->ptr; aij != NULL; aij = aij->r_next)
alpar@9 776 { col = aij->col;
alpar@9 777 if (!(col->is_int && col->lb == 0.0 && col->ub == 1.0))
alpar@9 778 break;
alpar@9 779 }
alpar@9 780 if (aij != NULL) continue;
alpar@9 781 count += npp_hidden_covering(npp, row);
alpar@9 782 }
alpar@9 783 if (count > 0)
alpar@9 784 xprintf("%d hidden covering inequaliti(es) were detected\n",
alpar@9 785 count);
alpar@9 786 /*==============================================================*/
alpar@9 787 /* reduce inequality constraint coefficients */
alpar@9 788 count = 0;
alpar@9 789 /* new rows will be added to the end of the row list, so we go
alpar@9 790 from the end to beginning of the row list */
alpar@9 791 for (row = npp->r_tail; row != NULL; row = prev_row)
alpar@9 792 { prev_row = row->prev;
alpar@9 793 /* skip equality constraint */
alpar@9 794 if (row->lb == row->ub) continue;
alpar@9 795 count += npp_reduce_ineq_coef(npp, row);
alpar@9 796 }
alpar@9 797 if (count > 0)
alpar@9 798 xprintf("%d constraint coefficient(s) were reduced\n", count);
alpar@9 799 /*==============================================================*/
alpar@9 800 #ifdef GLP_DEBUG
alpar@9 801 routine(npp);
alpar@9 802 #endif
alpar@9 803 /*==============================================================*/
alpar@9 804 /* all seems ok */
alpar@9 805 ret = 0;
alpar@9 806 done: return ret;
alpar@9 807 }
alpar@9 808
alpar@9 809 /* eof */