[Help-glpk] [Fwd: Re: Problem with GLPK when trying to find value functions]

[Andrew Makhorin]

-------- Forwarded Message --------
From: Sergey Kuznetsov <address@hidden>
To: Andrew Makhorin <address@hidden>
Subject: Re: [Fwd: Problem with GLPK when trying to find value
functions]
Date: Thu, 26 Jul 2012 15:46:55 +0000

Thanks for your reply. Here is additional information about the machine:
proc: Intel(R) Core(TM)2 CPU T7400  @ 2.16GHz;
cpu MHz : 2167.000
cache size : 4096 KB
Here is the code:
double SolveLP (int **A, int *c, int *rhs, int numcols, int numrows)
{
  double z; // value function
  int ne = numcols*numrows;; // total # of nonzero elements
  int k = 1;
  int *ia = new int[ne];
  int *ja = new int[ne];
  double *ar = new double[ne];


  glp_prob *LP;
  LP = glp_create_prob();


  // Read parametrs
 
 glp_set_obj_dir(LP, GLP_MAX);
 
  // setting righthand side (beta)
  glp_add_rows(LP, numrows);
  for (int i=1; i<=numrows; ++i)
    glp_set_row_bnds(LP, i, GLP_UP, 0.0, rhs[i-1]);
  
  // setting x-vector bounds and obj. function coefficients
  glp_add_cols(LP, numcols);
  for (int j=1; j<=numcols; ++j){
    glp_set_col_bnds(LP, j, GLP_LO, 0.0, 0.0);
    glp_set_obj_coef(LP, j, c[j-1]);
  }


  // read constraint matrix


  for (int i=1; i<=numrows; ++i)
    for (int j=1; j<=numcols; ++j){
      ia[k] = i;
      ja[k] = j;
      ar[k] = double(A[i-1][j-1]);
      ++k;
    }
  
  glp_load_matrix(LP, ne, ia, ja, ar);
 
  // Run simplex
  glp_simplex(LP, NULL);


  // Get obj. value
  z = glp_get_obj_val(LP);
   
  glp_erase_prob(LP); // work with erase problem
  //glp_delete_prob(LP); // doesn't work in loop
  
  return z;
  }


As a matter of fact the code works correctly as far as solving LP
concerned (I've tested the result of the algorithm that uses value
functions and it works correctly). So the problem is memory issue. I'm
thinking that by calling glp_erase_prob() I'm not completely freeing
memory but it doesn't explain
why the code works for [0;3]^3 lattice (4^3 total LP's) and I have
memory problems with [0;4]^2 lattice (25 total LP's). 
in particular, I have the following:
GLPK Simplex Optimizer, v4.45
2 rows, 3 columns, 5 non-zeros
test: malloc.c:4631: _int_malloc: Assertion `(unsigned long)(size) >=
(unsigned long)(nb)' failed.


I'd love to use MathProg and glpsol but it'd be tedious. Solving LP's is
only first step of the bigger algorithm and I need it to be completely
automated
as in the future I'll need to run the code (solve LP) for the big number
of instances randomly generated. So to write all of them in MathProg is
a nightmare. 
Again, thanks for you reply


Sergey

On Thu, Jul 26, 2012 at 2:04 PM, Andrew Makhorin <address@hidden> wrote:
        > I'm using GLPK to find value functions, it's a family of
        linear programs
        > with right-hand side as parameter.
        > For instance, I'm constructing 3D integer lattice and at each
        site
        > (point) I need to find optimal solution using site coordinates
        as
        > right-hand side (in this case it's 3D vector).
        > I wrote a function that solves the linear program using GLPK.
        At first
        > it crashed on the second call. I replaced glp_delete_prob() on
        > gpl_erase_prob() and
        > it worked well for [0;3]^3 lattice (and [0;3]^2 lattice). The
        problems
        > began [0;4]^2 (2D) lattice. I have segmentation fault and it's
        unusual
        > because in [0;3]^3 I'm solving more programs.
        > OS : Linux Debian, i686;  Compiler: GCC  4.7.1
        > Test instances: 3D: 4 columns, 3 rows; 2D: 3 columns, 2 rows;
         all the
        > entries (matrix, objective function coeff, right-hand side)
        are
        > integers.
        > Clearly, the problems begin when I'm setting span of the
        lattice to 4
        > (5, 6, etc.).
        > If anybody has any idea how to fix this, please help me.
        
        
        Not seeing your code it is difficult to say something. Make sure
        that
        all parameters (especially arrays) passed to glpk api routines
        have
        correct types and contents. Before passing the glp_prob object
        to
        glp_simplex write its contents to a text file with glp_write_lp
        and
        inspect that file with a text editor to make sure that the
        instance is
        correctly built. Try to use glpsol, the glpk stand-alone solver,
        to
        solve the instance written in the text file. Check your code
        carefully--most probably it has a bug.
        
        BTW, if you only need to obtain solutions, you might write your
        lp in
        the MathProg modeling language and then use glpsol to solve it.