Re : [Help-glpk] Different objective values

[Andrew Makhorin]

> Please find in attachment an LP file ("colgen.lp") corresponding to
> one of the iterations of STEP1.

> I found out that the objectives at the end of STEP1 were different
> because the dual values computed during the iterations are not the
> same with glpk 4.27 and 4.29 and the sub problem rely on the dual
> values to generate the new columns.

> When I solve "colgen.lp" with glpsol version 4.27 and 4.29 (both
> compiled with mingw 4.2.2), I obtain the same dual values for each
> constraint.
> The command used is: "../glpsol.exe --cpxlp ~/colgen.lp -o
> output_exe_4XX.txt".

> When I use the API with the small program below, the dual values
> are the same for both versions but are different from those computed
> with GLPSOL
>  (why?).

> For an obscure reason, when I look at the dual values obtained
> during the column generation, they are different.
> To illustrate this, here are the dual values of the 9 first constraints:

> ROW   GLPSOL       API          COLGEN_427     COLGEN_429
> 1     152732       152732       152732         152732
> 2     99415.8      99415.8      99415,8        99415,8
> 3     15872        15872        15872          15872
> 4    
>  12130.5      25768.6      25768,6        1834
> 5     151631       137993       151631         151631
> 6     -289600      -289600      -358909        -358909
> 7     151631       151631       151631         151631
> 8     -1654.49     -1654.49     -15292,6       8642,01
> 9     151631       151631       151631        
>  151631


> I don't understand why we don't have exactly the same dual values in all 
> cases... ?
> Thanks for your help,

> Joel.


> ---

> /*
> g++ compare.cpp -o compare.exe -I ../glpk-4.29/include/ -L 
> ../glpk-4.29/src/.libs/ -lglpk
./compare.exe >> output_api_429.txt
> g++ compare.cpp -o compare.exe -I ../glpk-4.27/include/ -L 
> ../glpk-4.27/src/.libs/ -lglpk
./compare.exe >> output_api_427.txt
> */

> #include "glpk.h"
> #include <iostream>

> using namespace std ;

> int main()
> {
>     glp_prob * lp = lpx_read_cpxlp("colgen.lp");
>     lpx_set_int_parm(lp, LPX_K_DUAL, 1);
>     lpx_simplex(lp);
>     cout << "GLPK version: " << glp_version() << endl ;
>     for(int i=1; i<=86; i++)
>         cout << i << "\t" << glp_get_row_dual(lp, i)
>  << endl ;
> }

There is nothing unusual. Your lp instance is degenerate in the dual
space that means that reduced costs (i.e. dual values) of *some*
non-basic variables are zero; therefore, multiple *optimal* basic
solutions exist, and in one case the solver finds one solution while
in other case it finds another. Since the flow of your algorithm
depends on the set of non-basic variables and their reduced costs,
different optima may lead to generating different columns.