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