Re: [Help-glpk] Thread safety of GLPK

[Andrew Makhorin]

> Pthread_getspecific and pthread_setspecific are part of the pthread
> library. On Linux you probably need to specify -lpthread along with
> other options passed to gcc and libtool.

> So, um, where/how do I put that in?

make LIBS=-lpthread




___
Help-glpk mailing list
Help-glpk@gnu.org
http://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] Thread safety of GLPK

[Andrew Makhorin]

> Let me put it more directly:

> I replaced glpenv02.c with the version someone posted as being
> thread-safe.  ./configure worked fine, but make yielded:

> /bin/bash ../libtool --tag=CC   --mode=link gcc  -g -O2   -o glpsol
> glpsol.o ../src/libglpk.la -lm -L/usr/include/

> libtool: link: gcc -g -O2 -o .libs/glpsol glpsol.o
>  ../src/.libs/libglpk.so -L/usr/include/ -lm

> ../src/.libs/libglpk.so: undefined reference to `pthread_getspecific #39;

> ../src/.libs/libglpk.so: undefined reference to `pthread_setspecific #39;

Pthread_getspecific and pthread_setspecific are part of the pthread
library. On Linux you probably need to specify -lpthread along with
other options passed to gcc and libtool.





___
Help-glpk mailing list
Help-glpk@gnu.org
http://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] Thread safety of GLPK

[Louis Wasserman]

Let me put it more directly:


I replaced glpenv02.c with the version someone posted as being thread-safe.  
./configure worked fine, but make yielded:




/bin/bash ../libtool --tag=CC   --mode=link gcc  -g -O2   -o glpsol glpsol.o 
../src/libglpk.la -lm -L/usr/include/

libtool: link: gcc -g -O2 -o .libs/glpsol glpsol.o  ../src/.libs/libglpk.so 
-L/usr/include/ -lm

../src/.libs/libglpk.so: undefined reference to `pthread_getspecific #39;

../src/.libs/libglpk.so: undefined reference to `pthread_setspecific #39;







Louis Wasserman
wasserman.lo...@gmail.com
http://profiles.google.com/wasserman.louis


On Wed, Apr 21, 2010 at 7:43 PM, Louis Wasserman  
wrote:
Do I need to mess with the configure options to build with this modified 
glpenv02.c?


Louis Wasserman
wasserman.lo...@gmail.com
http://profiles.google.com/wasserman.louis









 Let me put it more directly:I replaced glpenv02.c with the version someone posted as being thread-safe.  ./configure worked fine, but make yielded:/bin/bash ../libtool --tag=CC   --mode=link gcc  -g -O2   -o glpsol glpsol.o ../src/libglpk.la -lm -L/usr/include/

libtool: link: gcc -g -O2 -o .libs/glpsol glpsol.o  ../src/.libs/libglpk.so -L/usr/include/ -lm../src/.libs/libglpk.so: undefined reference to `pthread_getspecific'../src/.libs/libglpk.so: undefined reference to `pthread_setspecific'

Louis Wassermanwasserman.lo...@gmail.comhttp://profiles.google.com/wasserman.louis


On Wed, Apr 21, 2010 at 7:43 PM, Louis Wasserman  wrote:

Do I need to mess with the configure options to build with this modified glpenv02.c?Louis Wassermanwasserman.lo...@gmail.comhttp://profiles.google.com/wasserman.louis





___
Help-glpk mailing list
Help-glpk@gnu.org
http://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] Solving shortest path problem and getting wrong answer

[Andrew Makhorin]

> I'm trying to solve shortest path problem using glpsol and mps format. I
> have it working correct with one example but I'm getting wrong results
> with another one and I can't understand if there's something wrong with
> my input or if it's glpsol that gives wrong output.

> My directed graph is the following, first number being edge tail id, the
> second one head id and last one respective weight.
> ...

> I haven't verified all of these but X1 being 9 cannot be correct looking
> at graph data. There's no way to get from 5 to 1 with total weight of 9.
> I can't see anything wrong with my input though.
> All help and pointers appreciated.

Glpsol solves your instance correctly, so you need to check your mps
file.

Writing models in mps format by hand is cumbersome. You may look at
the example model spp.mod, which solves the shortest path problem and
is written in MathProg modeling language (see subdirectory 'examples').



___
Help-glpk mailing list
Help-glpk@gnu.org
http://lists.gnu.org/mailman/listinfo/help-glpk

[Help-glpk] Solving shortest path problem and getting wrong answer

[Merike]

  Hi,

I'm trying to solve shortest path problem using glpsol and mps format. I 
have it working correct with one example but I'm getting wrong results 
with another one and I can't understand if there's something wrong with 
my input or if it's glpsol that gives wrong output.

My directed graph is the following, first number being edge tail id, the 
second one head id and last one respective weight.
3 5 19
5 1 26
1 4 28
4 9 11
9 7 29
7 8 21
8 6 18
6 2 30
2 1 23
10 3 27
9 5 20
1 7 26
6 4 21
9 8 11
9 8 29
9 3 13
10 1 19
2 4 29
5 2 18
2 5 28
8 7 14
5 7 29
2 6 20
8 4 18
8 2 14
1 7 17
2 4 19
4 5 29
10 6 26
10 7 17

Based on that I generate the following mps file to find shortest path 
from 5 to 3:
NAME shortest-path
ROWS
  N PATH
  L EQ14
  L EQ17
  L EQ21
  L EQ24
  L EQ25
  L EQ26
  L EQ35
  L EQ45
  L EQ49
  L EQ51
  L EQ52
  L EQ57
  L EQ62
  L EQ64
  L EQ78
  L EQ82
  L EQ84
  L EQ86
  L EQ87
  L EQ93
  L EQ95
  L EQ97
  L EQ98
  L EQ101
  L EQ103
  L EQ106
  L EQ107
  E START
COLUMNS
  X1 EQ14 -1
  X1 EQ17 -1
  X1 EQ21  1
  X1 EQ51  1
  X1 EQ101  1
  X2 EQ21 -1
  X2 EQ24 -1
  X2 EQ25 -1
  X2 EQ26 -1
  X2 EQ52  1
  X2 EQ62  1
  X2 EQ82  1
  X3 EQ35 -1
  X3 EQ93  1
  X3 EQ103  1
  X3 PATH -1
  X4 EQ45 -1
  X4 EQ49 -1
  X4 EQ14  1
  X4 EQ24  1
  X4 EQ64  1
  X4 EQ84  1
  X5 EQ51 -1
  X5 EQ52 -1
  X5 EQ57 -1
  X5 EQ25  1
  X5 EQ35  1
  X5 EQ45  1
  X5 EQ95  1
  X5 START 1
  X6 EQ62 -1
  X6 EQ64 -1
  X6 EQ26  1
  X6 EQ86  1
  X6 EQ106  1
  X7 EQ78 -1
  X7 EQ17  1
  X7 EQ57  1
  X7 EQ87  1
  X7 EQ97  1
  X7 EQ107  1
  X8 EQ82 -1
  X8 EQ84 -1
  X8 EQ86 -1
  X8 EQ87 -1
  X8 EQ78  1
  X8 EQ98  1
  X9 EQ93 -1
  X9 EQ95 -1
  X9 EQ97 -1
  X9 EQ98 -1
  X9 EQ49  1
  X10 EQ101 -1
  X10 EQ103 -1
  X10 EQ106 -1
  X10 EQ107 -1
RHS
  RHS1 START 0
  RHS1 EQ14 28
  RHS1 EQ17 17
  RHS1 EQ21 23
  RHS1 EQ24 19
  RHS1 EQ25 28
  RHS1 EQ26 20
  RHS1 EQ35 19
  RHS1 EQ45 29
  RHS1 EQ49 11
  RHS1 EQ51 26
  RHS1 EQ52 18
  RHS1 EQ57 29
  RHS1 EQ62 30
  RHS1 EQ64 21
  RHS1 EQ78 21
  RHS1 EQ82 14
  RHS1 EQ84 18
  RHS1 EQ86 18
  RHS1 EQ87 14
  RHS1 EQ93 13
  RHS1 EQ95 20
  RHS1 EQ97 29
  RHS1 EQ98 11
  RHS1 EQ101 19
  RHS1 EQ103 27
  RHS1 EQ106 26
  RHS1 EQ107 17
ENDATA

Which gives me:
X1 9
X2   18
X3   61
X4   37
X5 0
X6   16
X7 0
X8   19
X9   48
X10 34

I haven't verified all of these but X1 being 9 cannot be correct looking 
at graph data. There's no way to get from 5 to 1 with total weight of 9. 
I can't see anything wrong with my input though.
All help and pointers appreciated.

Merike





___
Help-glpk mailing list
Help-glpk@gnu.org
http://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] glp_get_col_prim() problem

[Andrew Makhorin]

> OTOH, please excuse my ignorance, but assuming all
> my variables are marked as binary in CPLEX LP file, do I really need to
> call glp_intopt() after glp_simplex() even if glp_get_status(lp) ==
> GLP_OPT assertion holds?

Yes. Glp_simplex solves lp relaxation, i.e. it considers all integer
variables as continuous (e.g. binary variable x is considered as
continuous variable 0 <= x <= 1), and glp_get_status reports the status
of optimal solution to lp relaxation, not to mip. To determine the
status of integer solution you need to call glp_mip_status. You can find
details in the reference manual.



___
Help-glpk mailing list
Help-glpk@gnu.org
http://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] glp_get_col_prim() problem

[Volkan YAZICI]

Hi,

On Thu, 22 Apr 2010, Andrew Makhorin  writes:
> Most likely your instance has multiple optima, so your program finds
> one optimal solution while glpsol finds another. As you can see the
> optimal objective value is the same in both cases.
>
> Note that to solve mip you need to call glp_simplex (to find optimal
> solution to lp relaxation) and *then* call glp_intopt (to find integer
> optimal solution), in which case the column values should be obtained
> with glp_mip_col_val, not with glp_get_col_prim. It happened that for
> your particular instance optimal solution to lp relaxation is integer
> feasible and therefore integer optimal; however, in a general case
> glp_intopt should be used. For details please see the glpk reference
> manual.

I incorporated glp_mip_col_val() and glp_intopt() into the code, and it
works like a charm. OTOH, please excuse my ignorance, but assuming all
my variables are marked as binary in CPLEX LP file, do I really need to
call glp_intopt() after glp_simplex() even if glp_get_status(lp) ==
GLP_OPT assertion holds?


Regards.


___
Help-glpk mailing list
Help-glpk@gnu.org
http://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] glp_get_col_prim() problem

[Andrew Makhorin]

>> I'm having troubles while trying to get the solution variables via C
>> API. Below is the code I use in my program:
> 
>>   return (int) glp_get_col_prim(lp, i);
> 
> Please note that glp_get_col_prim returns a floating-point value, so
> it would be better to write:
> 
>return (int) (glp_get_col_prim(lp, i) + .5);

Yes, this may cause incorrect results. Imagine that x = 0.99 due
to round-off errors in the simplex solver. Then

   (int)x -> 0 (incorrect)

while

   (int)(x + .5) -> 1 (correct)



___
Help-glpk mailing list
Help-glpk@gnu.org
http://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] glp_get_col_prim() problem

[Andrew Makhorin]

> is there
> any parallel implementation of GLPK? My other 23 cores are sitting
> idle.]

Currently not.

> I'm having troubles while trying to get the solution variables via C
> API. Below is the code I use in my program:

>   return (int) glp_get_col_prim(lp, i);

Please note that glp_get_col_prim returns a floating-point value, so
it would be better to write:

   return (int) (glp_get_col_prim(lp, i) + .5);

> The problem is, while above program outputs:
>   *13: obj =   2.0e+00  infeas =  0.000e+00 (0)
>   OPTIMAL SOLUTION FOUND
>   xs[12]:  0  0  0  0  0  0  0  0  0  0  0  0
>   ys[3]:  0  0  0

> glpsol gives a different result.
>   + 2: mip =   2.0e+00 <= tree is empty   0.0% (0; 1)
>   INTEGER OPTIMAL SOLUTION FOUND

> And the results returned by glpsol are the right ones. What might I be
> missing in the C code? (To be honest, I'm in a quite hurry and any
> replies will be really really appreciated.)

Most likely your instance has multiple optima, so your program finds
one optimal solution while glpsol finds another. As you can see the
optimal objective value is the same in both cases.

Note that to solve mip you need to call glp_simplex (to find optimal
solution to lp relaxation) and *then* call glp_intopt (to find integer
optimal solution), in which case the column values should be obtained
with glp_mip_col_val, not with glp_get_col_prim. It happened that for
your particular instance optimal solution to lp relaxation is integer
feasible and therefore integer optimal; however, in a general case
glp_intopt should be used. For details please see the glpk reference
manual.



___
Help-glpk mailing list
Help-glpk@gnu.org
http://lists.gnu.org/mailman/listinfo/help-glpk

[Help-glpk] glp_get_col_prim() problem

[Volkan YAZICI]

Hi,

[First, thanks Mr. Andrew Makhorin for such a fantastic tool. BTW, if
you would need any relatively huge (~200MB) sample CPLEX LP problems to
benchmark GLPK, I'd be happy to share our archives. Moreover, is there
any parallel implementation of GLPK? My other 23 cores are sitting
idle.]

I'm having troubles while trying to get the solution variables via C
API. Below is the code I use in my program:


  /* Maximum # of characters will be used by a variable symbol. */
  #define MAX_VAR_LEN 32


  static int
  glp_get_col_val(glp_prob *lp, const char name, int index)
  {
  char var[MAX_VAR_LEN];
  int  i;
  
  snprintf(var, (MAX_VAR_LEN * sizeof(char)), "%c%d", name, index);
  assert(lp);
  i = glp_find_col(lp, var);
  assert(i > 0);
  return (int) glp_get_col_prim(lp, i);
  }
  
  
  int *
  solve_ilp(...)
  {
  glp_prob *lp;
  
  ...
  
  /* Load the problem instance. */
  lp = glp_create_prob();
  assert(!glp_read_lp(lp, NULL, pathname));
  glp_create_index(lp);
  
  /* Solve the problem instance. */
  assert(!glp_simplex(lp, NULL) && glp_get_status(lp) == GLP_OPT);
  
  #ifdef DEBUG_ILP
  {
  int  i;
  int *xs;
  int *ys;
  
  xs = gc_nonref_malloc(g->n * sizeof(int));
  for (i = 0; i < g->n; i++) xs[i] = glp_get_col_val(lp, 'x', i);
  PRINT_VECTOR(xs, g->n, "xs");
  
  ys = gc_nonref_malloc(g->c * sizeof(int));
  for (i = 0; i < g->c; i++) ys[i] = glp_get_col_val(lp, 'y', i);
  PRINT_VECTOR(ys, g->c, "ys");
  }
  #endif
  
  ...
  }


The problem is, while above program outputs:


  Reading problem data from `repl-ilp-Pycj92'...
  13 rows, 15 columns, 27 non-zeros
  15 integer variables, all of which are binary
  33 lines were read
  GLPK Simplex Optimizer, v4.43
  13 rows, 15 columns, 27 non-zeros
  * 0: obj =   0.0e+00  infeas =  0.000e+00 (0)
  *13: obj =   2.0e+00  infeas =  0.000e+00 (0)
  OPTIMAL SOLUTION FOUND
  xs[12]:  0  0  0  0  0  0  0  0  0  0  0  0
  ys[3]:  0  0  0


glpsol gives a different result.


  $ glpsol --cpxlp /tmp/repl-ilp-Pycj92 -o /tmp/repl-ilp-Pycj92.out
  glp_read_lp: reading problem data from `/tmp/repl-ilp-Pycj92'...
  glp_read_lp: 13 rows, 15 columns, 27 non-zeros
  glp_read_lp: 15 integer columns, all of which are binary
  glp_read_lp: 33 lines were read
  glp_simplex: original LP has 13 rows, 15 columns, 27 non-zeros
  glp_simplex: presolved LP has 13 rows, 15 columns, 27 non-zeros
  lpx_adv_basis: size of triangular part = 13
  * 0:   objval =   0.0e+00   infeas =   0.0e+00 (0)
  * 1:   objval =   2.0e+00   infeas =   0.0e+00 (0)
  OPTIMAL SOLUTION FOUND
  Integer optimization begins...
  + 1: mip = not found yet <=  +inf(1; 0)
  + 2: >   2.0e+00 <=   2.0e+00   0.0% (1; 0)
  + 2: mip =   2.0e+00 <= tree is empty   0.0% (0; 1)
  INTEGER OPTIMAL SOLUTION FOUND
  Time used:   0.0 secs
  Memory used: 0.0 Mb (45904 bytes)
  lpx_print_mip: writing MIP problem solution to `/tmp/repl-ilp-Pycj92.out'...

  $ cat /tmp/repl-ilp-Pycj92.out
  Problem:
  Rows:   13
  Columns:15 (15 integer, 15 binary)
  Non-zeros:  27
  Status: INTEGER OPTIMAL
  Objective:  obj = 2 (MAXimum)
  
 No.   Row nameActivity Lower bound   Upper bound
  -- - - -
   1 r.4 0   0
   2 r.5 0   0
   3 r.6 0   0
   4 r.7 0   0
   5 r.8 0   0
   6 r.9 0   0
   7 r.100   0
   8 r.110   0
   9 r.120   0
  10 r.130   0
  11 r.140   0
  12 r.150   0
  13 r.161   1
  
 No. Column name   Activity Lower bound   Upper bound
  -- - - -
   1 x0   *  0 0 1
   2 x1   *  0 0 1
   3 x2   *  0 0 1
   4 x3   *  0 0 1
   5 x4   *  0 0 1
   6 x5   *  0 0 1
   7 x6   *  0 0 1
   8 x7   *