> My apologies. It is not add_rows, but del_cols that is an issue. I > wrote the previous email from memory, which was incorrect. > > I am attaching a test case. If we remove the first column of p0033, > then re-solving fails. However, if you remove the second column, it > succeeds. You can check this by changing the index to be removed. > > Presumably the first column is basic in the original solution and the > second column is non-basic.
Yes, it is expected behavior. > > My question is this: > - If a basic column is removed, what behavior do you expect from GLPK? > Should it adjust the basis and resolve? Resolve starting from the > beginning (a new basis)? Fail? In principle, it would be possible to implement a "smart" mode, i.e. if before modifying the problem instance its basis is valid, do something in order to keep it valid after modifications have done. However, such a mode would be: (a) very time-consuming, and (b) useless if the model is not intended to be reoptimized later. So, I decided to keep only statuses of rows and columns stored in LPX object. The statuses are initially assigned on creating rows and columns (by default the row is basic and the column is non-basic), and then they are not changed until either the solver routine change them or the application program explicitly does that through the routines lpx_set_row_stat/lpx_set_col_stat. No checks are made until the basis factorization actually needs to be computed, i.e. the statuses can be changed arbitrarily at any time. If, on creating the lp instance, the application did not change the statuses, then the basis is valid, because all rows (i.e. slacks, or more precisely, artificial variables) are basic and all columns (structural variables) are non-basic. The routines lpx_adv_basis and lpx_cpx_basis produce advanced basis changing the statuses and guarantee that the new basis is valid. If lpx_simplex terminates successfully, it is also guarantees that the final basis is valid independently on the primal/dual solution status. Thus the basis can become invalid only in the two cases: a) basic row/column is made non-basic or vice versa by excplicitly changing its status; and b) non-basic rows (active constraint) and/or basic columns have been removed from the instance. Note that the case (b) should happen in re-optimization. Indeed, if you are using cutting planes or "lazy" constraints, you either add new rows which becoming basic retain the basis valid, or remove non-active constraints, i.e. basic rows, in which case the basis also remains valid. If you are using column generation, you either add new and therefore non-basic columns or remove non-basic columns to temporarily or permanently fix them at zero, and again the basis remains valid. I think an intelligent way to remove a basic column is to fix it at zero instead to remove it immediately and keep it so until it has became non-basic, in which case it can be safely removed. The same way can be used to remove a non-basic row: we make it free and wait until it has entered the basis. Another (less intelligent) way is to compute the row of the simplex tableau corresponding to the basic column to be removed (lpx_eval_tab_row), find an appropriate non-basic row or column having non-zero influence coefficient, and change to the adjacent basis, where the basic column becomes non-basic while the non-basic row/column becomes basic. Note, however, that on api level currently there is no routine to perform this pivot operation efficiently, so using lpx_set_row_stat and lpx_set_col_stat to change the basis will destroy lu-factorization for the current basis (which is also kept in LPX object from the last call to lpx_warm_up or lpx_simplex). Andrew Makhorin _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
