[Help-glpk] Re: Intermediate solutions

[Carlos Javier Sosa Gonzalez]

Hi, me again.

I have done your recomendations, but I have several intermediate solutions
that the problem said LPX_I_FEAS, and it violates several constrains.
On the other hand the final solution report gives a feasible solution
that satifies all constrains.

The code added is:

int inter_sol = 0;

void write_intermediate_solution(MIPTREE *tree)
{
  LPX   *lp;
  FILE  *file;
  int    col;
  int    ncols;

  lp = (LPX *)tree->info;

  if((lp->i_stat == LPX_I_FEAS)&&(tree->found)) {
    file = fopen("intermediate.out", "a");
    
    fprintf(file,"\nStart Solution %d %d\n", inter_sol,
                 lpx_get_mip_obj(lp));
    ncols = lpx_get_num_cols(lp);
    for(col = 1; col <= ncols; col++){
      fprintf(file, "%s %d\n",
              lpx_get_col_name(lp, col),
              (int)lpx_get_mip_col(lp, col));
    }
    fprintf(file,"END\n");
    
    fclose(file);
    inter_sol++;
  }
}

...

         case MIP_V_BINGO:
            /* better integer feasible solution has been found */
            /* copy components of this solution to the original problem
               object */
            {  int k;
               mip->i_stat = LPX_I_FEAS;
               for (k = 1; k <= tree->orig_m + tree->orig_n; k++)
                  mip->mipx[k] = tree->best[k];
            }
            write_intermediate_solution(tree);
            break;


Thanks in advance,
Javier Sosa


On Tue, 24 Jun 2003, [windows-1251] "Andrew Makhorin[windows-1251] "  wrote:

> >* Are these non-optimal solutions of the problem? or can they violate any
> >problem constrain or bound? are they feasible solutions?
> 
> Each line printed after the message "Integer optimization begins..."
> correspond to best integer feasible solution known at the current point.
> "Integer feasible" means the solution satisfies to all constraints and
> all integer variables have integral values.
> 
> >* If they are solutions of the problem, how can I access to these
> >MIP non-optimal solutions?
> 
> You cannot do that on api level. However you can add your code directly
> in the b&b driver as explained below.
> 
> Get into the module glplpx6c.c which is a b&b driver (lpx_integer) and
> find the following fragment (lines 466-475 in glpk 4.0):
> 
>          case MIP_V_BINGO:
>             /* better integer feasible solution has been found */
>             /* copy components of this solution to the original problem
>                object */
>             {  int k;
>                mip->i_stat = LPX_I_FEAS;
>                for (k = 1; k <= tree->orig_m + tree->orig_n; k++)
>                   mip->mipx[k] = tree->best[k];
>             }
>             break;
> 
> This fragment is executed whenever the b&b solver discovers a new integer
> feasible solution which is better than the currently known one.
> 
> You should add your code immediately before the break statement. At that
> point 'mip' is a pointer to your problem object passed to the routine
> lpx_integer. Using that pointer you can access components of the current
> mip solution (which is integer feasible) with the following routines:
> 
> lpx_get_num_rows - obtain number of auxiliary variables (rows);
> 
> lpx_get_num_cols - obtain number of structural variables (columns);
> 
> lpx_get_mip_obj - obtain value of the objective function;
> 
> lpx_get_mip_row - obtain value of i-th auxiliary variable (row);
> 
> lpx_get_mip_col - obtain value of j-th structural variable (column).
> 
> Note that you must not change the problem object within the b&b driver.
> 

--
 Carlos Javier Sosa González  E.T.S.I. de Telecomunicación
  address@hidden         Campus Universitario de Tafira, Pab. A, Desp. 301 
  Tel.: +34 928 457 324       Univ. de Las Palmas de Gran Canaria
  Fax : +34 928 451 243       35017 Las Palmas de Gran Canaria
  ICQ : 1756350985            Canary Islands. SPAIN