lemon-project-template-glpk
comparison deps/glpk/src/glpnpp05.c @ 11:4fc6ad2fb8a6
Test GLPK in src/main.cc
author | Alpar Juttner <alpar@cs.elte.hu> |
---|---|
date | Sun, 06 Nov 2011 21:43:29 +0100 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:60de17774b30 |
---|---|
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, 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 #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 */ |