Re: [Help-glpk] Example for column generation

[Mark Gritter]

There is no need to do anything special, just add a column (and its
coefficients in the constraint matrix) like you would when setting up
the initial problem, then call lpx_simplex again.

I included a code fragment below from a project I did using column
generation.  (Sorry, this code was written for an earlier version of
GLPK and doesn't use glp_ functions where is should.)  My problem is
dense so the vector I create internally (by calling createLpVector) is
continguous and converted to a sparse representation before adding it
to the LP.

Mark

void
addVectorToProblem( LPX *lp, int c, double *coeff ) {
   // GLPK uses 1-based indices.
   int height0 = getColumnHeight();
   int height1 = height0 + 1;
   int nnz = 0;
   int sparseIndex[ height1 ];
   double sparseCoeff[ height1 ];
   for ( int i = 0; i < height0; ++i ) {
       if ( coeff[ i ] != 0.0 ) {
           sparseIndex[ nnz + 1 ] = i + 1;
           sparseCoeff[ nnz + 1 ] = coeff[ i ];
           ++nnz;
       }
   }

   lpx_set_mat_col( lp, c, nnz, sparseIndex, sparseCoeff );
}

void
addStrategyToProblem( LPX *lp, int hA, int sA ) {
   double *newCol = newColumn();
   createLpVector( hA, sA, newCol );

   lpx_add_cols( lp, 1 );
   int c = lpx_get_num_cols( lp );
   lpx_set_col_name( lp, c, (char *)p_var( hA, sA ).c_str() );
   lpx_set_col_bnds( lp, c, LPX_LO, 0.0, 0.0 );
   addVectorToProblem( lp, c, newCol );

   free( newCol );
}


On 6/26/07, Marc Goetschalckx <address@hidden> wrote:
> I solving a problem with column generation.  I have solved the root
> problem and now need to add columns to this existing problem and using
> the current basis.  Is there an example that illustrates the mechanics
> of column generation?  Thanks
> Marc Goetschalckx
>
>
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> http://lists.gnu.org/mailman/listinfo/help-glpk