PresolvePresolve is a preprocess of the lp-model. It looks for ways to simplify it.
For example it can delete unused variables and restrictions. Substitute fixed variable values by a
constant and so on. The result is a new model that is less complex than the original model and likely solves faster.
Presolve is not active by default. It must specifically being enabled via the API call set_presolve. A simple example: max: x1 + x2 + x3; r1: x2 = 2; r2: x1 + x2 <= 6; r3: x1 - 2 x3 >= 2; r4: x2 + 3 x3 <= 5; Row r1 is a constraint on one variable. Presolve can detect this and convert it to a bound on that variable. For this, presolve of rows must be activated: lp_solve model.lp -wlp con -S1 -wafter -presolverow /* Objective function */ max: +x1 +x2 +x3; /* Constraints */ r2: +x1 +x2 <= 6; r3: +x1 -2 x3 >= 2; r4: +x2 +3 x3 <= 5; /* Variable bounds */ x2 = 2;
And even this model can be presolved further. lp_solve model.lp -wlp con -S1 -wafter -presolverow -presolvecol /* Objective function */ max: +x1 +x3 +2; /* Constraints */ r3: +x1 -2 x3 >= 2; /* Variable bounds */ x1 <= 4; x3 <= 1; Note the -wafter option. If this option is not specified, the original model is printed. The reason for this is the moment that write_lp is called. The effect of presolve happens when a solve is done. If write_lp is called before solve then the original model is given. If called after solve then the presolved model is.
As previously stated, presolve can result in removal of variables and/or constraints.
For some models, presolve can even find the solution of the model. Example in C: #include <stdio.h> #include "lp_lib.h" int main(void) { # if defined ERROR # undef ERROR # endif # define ERROR() { fprintf(stderr, "Error\n"); exit(1); } lprec *lp; if ((lp=make_lp(0, 3)) == NULL) ERROR(); set_col_name(lp, 1, "x1"); set_col_name(lp, 2, "x2"); set_col_name(lp, 3, "x3"); set_maxim(lp); if (!str_add_constraint(lp, "0 1 0", EQ, 2)) ERROR(); set_row_name(lp, 1, "R1"); if (!str_add_constraint(lp, "1 1 0", LE, 6)) ERROR(); set_row_name(lp, 2, "R2"); if (!str_add_constraint(lp, "1 0 -2", GE, 2)) ERROR(); set_row_name(lp, 3, "R3"); if (!str_add_constraint(lp, "0 1 3", LE, 5)) ERROR(); set_row_name(lp, 4, "R4"); if (!str_set_obj_fn(lp, "1 1 1")) ERROR(); write_LP(lp, stdout); set_presolve(lp, PRESOLVE_ROWS + PRESOLVE_COLS, 0); solve(lp); print_objective(lp); print_solution(lp, 1); print_constraints(lp, 1); print_duals(lp); write_LP(lp, stdout); delete_lp(lp); } This gives: /* Objective function */ max: +x1 +x2 +x3; /* Constraints */ R1: +x2 = 2; R2: +x1 +x2 <= 6; R3: +x1 -2 x3 >= 2; R4: +x2 +3 x3 <= 5; Model name: '' - run #1 Objective: Maximize(R0) SUBMITTED Model size: 4 constraints, 3 variables, 7 non-zeros. Sets: 0 GUB, 0 SOS. Presolve O:1 -> Reduced rows: 3, cols: 1 --- changed bnds: 4, Ab: 0. PRESOLVE Elimination loops performed.......... O3:M3:I5 1 empty or fixed variables............. REMOVED. 3 empty or redundant constraints....... REMOVED. 4 bounds............................... TIGHTENED. [ +2 < Z < +7 ] REDUCED Model size: 1 constraints, 2 variables, 2 non-zeros. Sets: 0 GUB, 0 SOS. Row-types: 0 LE, 1 GE, 0 EQ. Using DUAL simplex for phase 1 and PRIMAL simplex for phase 2. The primal and dual simplex pricing strategy set to 'Devex'. Optimal solution 7 after 0 iter. Excellent numeric accuracy ||*|| = 0 MEMO: lp_solve version 5.5.2.5 for 32 bit OS, with 64 bit REAL variables. In the total iteration count 0, 0 (100.0%) were bound flips. There were 0 refactorizations, 0 triggered by time and 0 by density. ... on average 0.0 major pivots per refactorization. The largest [etaPFI v1.4] fact(B) had 0 NZ entries, 0.0x largest basis. The constraint matrix inf-norm is 2, with a dynamic range of 2. Time to load data was 0.235 seconds, presolve used 0.140 seconds, ... 0.047 seconds in simplex solver, in total 0.422 seconds. Value of objective function: 7 Actual values of the variables: x1 4 x2 2 x3 1 Actual values of the constraints: R3 2 Objective function limits: From Till FromValue x1 0 1e+030 -1e+030 x3 0 1e+030 -1e+030 Dual values with from - till limits: Dual value From Till R3 0 -1e+030 1e+030 x1 1 4 1e+030 x3 1 -1e+030 1 /* Objective function */ max: +x1 +x3 +2; /* Constraints */ R3: +x1 -2 x3 >= 2; /* Variable bounds */ x1 <= 4; x3 <= 1;
The result only shows values of contraint R3, the one that is kept.
The information of the removed constraints is no longer there. Almost all API calls return information of the presolved model. get_Nrows and get_Ncolumns return the number of rows and columns of the presolved model. To know the original values, get_Norig_rows and get_Norig_columns must be used: printf("get_Nrows: %d\n", get_Nrows(lp)); printf("get_Norig_rows: %d\n", get_Norig_rows(lp)); printf("get_Ncolumns: %d\n", get_Ncolumns(lp)); printf("get_Norig_columns: %d\n", get_Norig_columns(lp)); get_Nrows: 1 get_Norig_rows: 4 get_Ncolumns: 2 get_Norig_columns: 3
To retrieve the variable data of all variables, including the presolved variables, API call
get_var_primalresult must be used.
This is the only call available to get all information. int column, Nrows, Ncolumns; Ncolumns = get_Norig_columns(lp); Nrows = get_Norig_rows(lp); for (column = 1; column <= Ncolumns; column++) { printf("x%d: %f\n", column, get_var_primalresult(lp, Nrows + column)); } With result: x1: 4.000000 x2: 2.000000 x3: 1.000000
get_var_primalresult also returns information about rows. int row, Nrows; Nrows = get_Norig_rows(lp); for (row = 1; row <= Nrows; row++) { printf("R%d: %f\n", row, get_var_primalresult(lp, row)); } With result: R1: 0.000000 R2: 0.000000 R3: 2.000000 R4: 0.000000 You could think here that a result for all original rows are returned, but this is not the case. Only the result of constraints that were kept in the model are given. The other rows will return 0!
There is also a possibility to know which rows and columns are removed from the model.
get_orig_index can be used for that. int row, Nrows; int column, Ncolumns; Ncolumns = get_Ncolumns(lp); Nrows = get_Nrows(lp); for (row = 1; row <= Nrows; row++) printf("row %d was row R%d\n", row, get_orig_index(lp, row)); for (column = 1; column <= Ncolumns; column++) printf("column %d was column x%d\n", column, get_orig_index(lp, Nrows + column)); With result: row 1 was row R3 column 1 was column x1 column 2 was column x3 So from this it can be determined that only row R3 and columns x1 and x3 are kept in the model. The others are removed by presolve. Again note that all other API calls return information about the presolved model. So for example get_ptr_primal_solution must be used like this: int row, Nrows; int column, Ncolumns; double *pv; get_ptr_primal_solution(lp, &pv); Ncolumns = get_Ncolumns(lp); Nrows = get_Nrows(lp); for (row = 1; row <= Nrows; row++) printf("row %d: %f\n", row, pv[row]); for (column = 1; column <= Ncolumns; column++) printf("column %d: %f\n", column, pv[Nrows + column]); With result: row 1: 2.000000 column 1: 4.000000 column 2: 1.000000 Row and column names of the original model can be obtained via get_origrow_name and get_origcol_name: int row, Nrows; int column, Ncolumns; Ncolumns = get_Norig_columns(lp); Nrows = get_Norig_rows(lp); for (row = 1; row <= Nrows; row++) printf("row %d: %s\n", row, get_origrow_name(lp, row)); for (column = 1; column <= Ncolumns; column++) printf("column %d: %s\n", column, get_origcol_name(lp, column)); With result: row 1: R1 row 2: R2 row 3: R3 row 4: R4 column 1: x1 column 2: x2 column 3: x3 Row and column names of the presolved model can be obtained via get_row_name and get_col_name: int row, Nrows; int column, Ncolumns; Ncolumns = get_Ncolumns(lp); Nrows = get_Nrows(lp); for (row = 1; row <= Nrows; row++) printf("row %d: %s\n", row, get_row_name(lp, row)); for (column = 1; column <= Ncolumns; column++) printf("column %d: %s\n", column, get_col_name(lp, column)); With result: row 1: R3 column 1: x1 column 2: x3 |