help-glpk
[Top][All Lists]

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

 From: Andrew Makhorin Subject: [Help-glpk] [Fwd: Re: Problem with GLPK when trying to find value functions] Date: Thu, 26 Jul 2012 21:57:54 +0400

```-------- Forwarded Message --------
Subject: Re: [Fwd: Problem with GLPK when trying to find value
functions]
Date: Thu, 26 Jul 2012 15:46:55 +0000

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();

glp_set_obj_dir(LP, GLP_MAX);

// setting righthand side (beta)
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
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]);
}

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;
}

// 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.

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.).

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.

```