Re: [Help-glpk] glp_get_col_prim() problem
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
Re: [Help-glpk] glp_get_col_prim() problem
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
Hi, On Thu, 22 Apr 2010, Andrew Makhorin m...@gnu.org 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
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
[Help-glpk] Solving shortest path problem and getting wrong answer
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] Solving shortest path problem and getting wrong answer
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
Re: [Help-glpk] Thread safety of GLPK
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
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
