Re: AVL tree silently accept duplicate keys

2020-08-10 Thread Erwin Kalvelagen 
Sorry, I was not paying attention and replied to the wrong email.

Erwin Kalvelagen
Amsterdam Optimization Modeling Group
er...@amsterdamoptimization.com
https://www.amsterdamoptimization.com 



On Mon, Aug 10, 2020 at 10:25 AM Erwin Kalvelagen <
er...@amsterdamoptimization.com> wrote:

> Operator error!!
> 
> Erwin Kalvelagen
> Amsterdam Optimization Modeling Group
> er...@amsterdamoptimization.com
> https://www.amsterdamoptimization.com 
> 
>
>
> On Mon, Aug 10, 2020 at 9:41 AM Andrew Makhorin  wrote:
>
>> On Mon, 2020-08-10 at 14:28 +0200, Domingo Alvarez Duarte wrote:
>> > Hello !
>> >
>> > Replacing usages of AVL tree by SplayTree I found that AVL tree
>> > silently
>> > accepts duplicate keys on "avl_insert_node" see example bellow, there
>> > is
>> > only one way to find by key "avl_find_node" which make it prone to
>> > write
>> > incorrect code:
>> >
>>
>> AVL routines are not intended to be used on API level. Formally, these
>> routines are not available to the user.
>>
>> Both AVL and splay trees take logarithmic time, so there is not much
>> sense to use the latter. To really reduce the search time it would be
>> better to use hashing.
>>
>>
>> PS: Please post messages not related to bug reports to help-glpk rather
>> than to bug-glpk. Thanks.
>>
>>
>> > 
>> >
>> > #include 
>> > #include 
>> > #include "avl.h"
>> >
>> > int main(int argc, char *argv[])
>> > {
>> >  AVL *tree = avl_create_tree(avl_strcmp, NULL);
>> >  AVLNODE *node1 = avl_insert_node(tree, "one");
>> >  printf("node1 = %p\n", node1);
>> >  AVLNODE *node2 = avl_insert_node(tree, "one");
>> >  printf("node2 = %p\n", node2);
>> >  AVLNODE *node3 = avl_insert_node(tree, "one");
>> >  printf("node3 = %p\n", node3);
>> >  AVLNODE *node = avl_find_node(tree, "one");
>> >  printf("node = %p\n", node);
>> >  avl_delete_node(tree, node1);
>> >  node = avl_find_node(tree, "one");
>> >  printf("node = %p\n", node);
>> >  avl_delete_node(tree, node2);
>> >  node = avl_find_node(tree, "one");
>> >  printf("node = %p\n", node);
>> >  avl_delete_tree(tree);
>> >  return 0;
>> > }
>> >
>> > 
>> >
>> > Build:
>> >
>> > 
>> >
>> > gcc -g -o test-avl test-avl.c -I../src/misc -I../src
>> > ../src/.libs/libglpk.a
>> >
>> > 
>> >
>> > Output:
>> >
>> > =
>> >
>> > ./test-avl
>> > node1 = 0x55f599e6d908
>> > node2 = 0x55f599e6d940
>> > node3 = 0x55f599e6d978
>> > node = 0x55f599e6d940
>> > node = 0x55f599e6d940
>> > node = 0x55f599e6d978
>> >
>> > =
>> >
>> > Cheers !
>> >
>> >
>> >
>>
>>

Re: AVL tree silently accept duplicate keys

2020-08-10 Thread Erwin Kalvelagen 
Operator error!!

Erwin Kalvelagen
Amsterdam Optimization Modeling Group
er...@amsterdamoptimization.com
https://www.amsterdamoptimization.com 



On Mon, Aug 10, 2020 at 9:41 AM Andrew Makhorin  wrote:

> On Mon, 2020-08-10 at 14:28 +0200, Domingo Alvarez Duarte wrote:
> > Hello !
> >
> > Replacing usages of AVL tree by SplayTree I found that AVL tree
> > silently
> > accepts duplicate keys on "avl_insert_node" see example bellow, there
> > is
> > only one way to find by key "avl_find_node" which make it prone to
> > write
> > incorrect code:
> >
>
> AVL routines are not intended to be used on API level. Formally, these
> routines are not available to the user.
>
> Both AVL and splay trees take logarithmic time, so there is not much
> sense to use the latter. To really reduce the search time it would be
> better to use hashing.
>
>
> PS: Please post messages not related to bug reports to help-glpk rather
> than to bug-glpk. Thanks.
>
>
> > 
> >
> > #include 
> > #include 
> > #include "avl.h"
> >
> > int main(int argc, char *argv[])
> > {
> >  AVL *tree = avl_create_tree(avl_strcmp, NULL);
> >  AVLNODE *node1 = avl_insert_node(tree, "one");
> >  printf("node1 = %p\n", node1);
> >  AVLNODE *node2 = avl_insert_node(tree, "one");
> >  printf("node2 = %p\n", node2);
> >  AVLNODE *node3 = avl_insert_node(tree, "one");
> >  printf("node3 = %p\n", node3);
> >  AVLNODE *node = avl_find_node(tree, "one");
> >  printf("node = %p\n", node);
> >  avl_delete_node(tree, node1);
> >  node = avl_find_node(tree, "one");
> >  printf("node = %p\n", node);
> >  avl_delete_node(tree, node2);
> >  node = avl_find_node(tree, "one");
> >  printf("node = %p\n", node);
> >  avl_delete_tree(tree);
> >  return 0;
> > }
> >
> > 
> >
> > Build:
> >
> > 
> >
> > gcc -g -o test-avl test-avl.c -I../src/misc -I../src
> > ../src/.libs/libglpk.a
> >
> > 
> >
> > Output:
> >
> > =
> >
> > ./test-avl
> > node1 = 0x55f599e6d908
> > node2 = 0x55f599e6d940
> > node3 = 0x55f599e6d978
> > node = 0x55f599e6d940
> > node = 0x55f599e6d940
> > node = 0x55f599e6d978
> >
> > =
> >
> > Cheers !
> >
> >
> >
>
>

Re: AVL tree silently accept duplicate keys

2020-08-10 Thread Andrew Makhorin 
On Mon, 2020-08-10 at 14:28 +0200, Domingo Alvarez Duarte wrote:
> Hello !
> 
> Replacing usages of AVL tree by SplayTree I found that AVL tree
> silently 
> accepts duplicate keys on "avl_insert_node" see example bellow, there
> is 
> only one way to find by key "avl_find_node" which make it prone to
> write 
> incorrect code:
> 

AVL routines are not intended to be used on API level. Formally, these
routines are not available to the user.

Both AVL and splay trees take logarithmic time, so there is not much
sense to use the latter. To really reduce the search time it would be
better to use hashing.


PS: Please post messages not related to bug reports to help-glpk rather
than to bug-glpk. Thanks.


> 
> 
> #include 
> #include 
> #include "avl.h"
> 
> int main(int argc, char *argv[])
> {
>  AVL *tree = avl_create_tree(avl_strcmp, NULL);
>  AVLNODE *node1 = avl_insert_node(tree, "one");
>  printf("node1 = %p\n", node1);
>  AVLNODE *node2 = avl_insert_node(tree, "one");
>  printf("node2 = %p\n", node2);
>  AVLNODE *node3 = avl_insert_node(tree, "one");
>  printf("node3 = %p\n", node3);
>  AVLNODE *node = avl_find_node(tree, "one");
>  printf("node = %p\n", node);
>  avl_delete_node(tree, node1);
>  node = avl_find_node(tree, "one");
>  printf("node = %p\n", node);
>  avl_delete_node(tree, node2);
>  node = avl_find_node(tree, "one");
>  printf("node = %p\n", node);
>  avl_delete_tree(tree);
>  return 0;
> }
> 
> 
> 
> Build:
> 
> 
> 
> gcc -g -o test-avl test-avl.c -I../src/misc -I../src
> ../src/.libs/libglpk.a
> 
> 
> 
> Output:
> 
> =
> 
> ./test-avl
> node1 = 0x55f599e6d908
> node2 = 0x55f599e6d940
> node3 = 0x55f599e6d978
> node = 0x55f599e6d940
> node = 0x55f599e6d940
> node = 0x55f599e6d978
> 
> =
> 
> Cheers !
> 
> 
>

Re: How to retrieve intermediate solutions of MIP problems without interrupting the solver?

2020-08-10 Thread Domingo Alvarez Duarte 

Hello Heinrich !

Thank you for reply !

My bad, I did followed the code instead of reading the manual !

There is a old saying:

When everything else fails, read the  manual !

Cheers !

On 10/8/20 11:56, Heinrich Schuchardt wrote:

On 10.08.20 11:47, Domingo Alvarez Duarte wrote:

Hello Yuri !

Following the code again I found this lines in examples/glpsol.c:



#ifdef GLP_CB_FUNC /* 05/IV-2016 */
  {  extern void GLP_CB_FUNC(glp_tree *, void *);
     csa->iocp.cb_func = GLP_CB_FUNC;
     csa->iocp.cb_info = NULL;
  }
#endif



It seems that the user callback can be set that way but could not found
any other reference so far.


The callback is described in chapter 5.1.1 "Using the callback routine"
of doc/glpk.pdf. There is a reason code

GLP_IBINGO — better integer solution found.

Best regards

Heinrich



Cheers !

On 9/8/20 20:04, Yuri wrote:

For my problem Glpk quickly finds some solution and then goes on to
find better solutions and this takes a lot of time.


I'm interested in all solutions, beginning from the first integer
solution in finds.

I couldn't find a callback that is called when a better solution
becomes known.


For example, in this run it called glp_intopt which progressively
found 3 solutions, each better than the previous one:

Long-step dual simplex will be used
+   633: mip = not found yet >=  -inf (1; 0)
+  1006: >   1.098691667e+01 >= 5.512339583e+00  49.8% (18; 0)
+  4134: >   1.098525000e+01 >= 6.681520833e+00  39.2% (31; 22)
+  7210: >   1.098458333e+01 >= 1.043275926e+01   5.0% (24; 87)
+  7654: mip =   1.098458333e+01 >= tree is empty   0.0% (0; 195)
INTEGER OPTIMAL SOLUTION FOUND

I am looking for access to all of  them as they become available.


Yuri

Re: How to retrieve intermediate solutions of MIP problems without interrupting the solver?

2020-08-10 Thread Heinrich Schuchardt 
On 10.08.20 11:47, Domingo Alvarez Duarte wrote:
> Hello Yuri !
>
> Following the code again I found this lines in examples/glpsol.c:
>
> 
>
> #ifdef GLP_CB_FUNC /* 05/IV-2016 */
>  {  extern void GLP_CB_FUNC(glp_tree *, void *);
>     csa->iocp.cb_func = GLP_CB_FUNC;
>     csa->iocp.cb_info = NULL;
>  }
> #endif
>
> 
>
> It seems that the user callback can be set that way but could not found
> any other reference so far.


The callback is described in chapter 5.1.1 "Using the callback routine"
of doc/glpk.pdf. There is a reason code

GLP_IBINGO — better integer solution found.

Best regards

Heinrich


>
> Cheers !
>
> On 9/8/20 20:04, Yuri wrote:
>> For my problem Glpk quickly finds some solution and then goes on to
>> find better solutions and this takes a lot of time.
>>
>>
>> I'm interested in all solutions, beginning from the first integer
>> solution in finds.
>>
>> I couldn't find a callback that is called when a better solution
>> becomes known.
>>
>>
>> For example, in this run it called glp_intopt which progressively
>> found 3 solutions, each better than the previous one:
>>
>> Long-step dual simplex will be used
>> +   633: mip = not found yet >=  -inf (1; 0)
>> +  1006: >   1.098691667e+01 >= 5.512339583e+00  49.8% (18; 0)
>> +  4134: >   1.098525000e+01 >= 6.681520833e+00  39.2% (31; 22)
>> +  7210: >   1.098458333e+01 >= 1.043275926e+01   5.0% (24; 87)
>> +  7654: mip =   1.098458333e+01 >= tree is empty   0.0% (0; 195)
>> INTEGER OPTIMAL SOLUTION FOUND
>>
>> I am looking for access to all of  them as they become available.
>>
>>
>> Yuri
>>
>>
>>
>

Re: How to retrieve intermediate solutions of MIP problems without interrupting the solver?

2020-08-10 Thread Domingo Alvarez Duarte 

Hello Yuri !

Following the code again I found this lines in examples/glpsol.c:



#ifdef GLP_CB_FUNC /* 05/IV-2016 */
 {  extern void GLP_CB_FUNC(glp_tree *, void *);
    csa->iocp.cb_func = GLP_CB_FUNC;
    csa->iocp.cb_info = NULL;
 }
#endif



It seems that the user callback can be set that way but could not found 
any other reference so far.


Cheers !

On 9/8/20 20:04, Yuri wrote:
For my problem Glpk quickly finds some solution and then goes on to 
find better solutions and this takes a lot of time.



I'm interested in all solutions, beginning from the first integer 
solution in finds.


I couldn't find a callback that is called when a better solution 
becomes known.



For example, in this run it called glp_intopt which progressively 
found 3 solutions, each better than the previous one:


Long-step dual simplex will be used
+   633: mip = not found yet >=  -inf (1; 0)
+  1006: >   1.098691667e+01 >= 5.512339583e+00  49.8% (18; 0)
+  4134: >   1.098525000e+01 >= 6.681520833e+00  39.2% (31; 22)
+  7210: >   1.098458333e+01 >= 1.043275926e+01   5.0% (24; 87)
+  7654: mip =   1.098458333e+01 >= tree is empty   0.0% (0; 195)
INTEGER OPTIMAL SOLUTION FOUND

I am looking for access to all of  them as they become available.


Yuri

Re: How to retrieve intermediate solutions of MIP problems without interrupting the solver?

2020-08-10 Thread Domingo Alvarez Duarte 

Hello Yuri !

After my last reply I followed the code again and found that it seems to 
already have a way to do it using src/proxy/proxy.h but I couldn't find 
a way to set our own proxy function/wrapper for it.


Cheers !

On 9/8/20 20:04, Yuri wrote:
For my problem Glpk quickly finds some solution and then goes on to 
find better solutions and this takes a lot of time.



I'm interested in all solutions, beginning from the first integer 
solution in finds.


I couldn't find a callback that is called when a better solution 
becomes known.



For example, in this run it called glp_intopt which progressively 
found 3 solutions, each better than the previous one:


Long-step dual simplex will be used
+   633: mip = not found yet >=  -inf (1; 0)
+  1006: >   1.098691667e+01 >= 5.512339583e+00  49.8% (18; 0)
+  4134: >   1.098525000e+01 >= 6.681520833e+00  39.2% (31; 22)
+  7210: >   1.098458333e+01 >= 1.043275926e+01   5.0% (24; 87)
+  7654: mip =   1.098458333e+01 >= tree is empty   0.0% (0; 195)
INTEGER OPTIMAL SOLUTION FOUND

I am looking for access to all of  them as they become available.


Yuri

Re: How to retrieve intermediate solutions of MIP problems without interrupting the solver?

2020-08-10 Thread Domingo Alvarez Duarte 

Hello Yuri !

Looking through the code I can see that the function 
src/draft/glpios03.c::record_solution would be a good candidate to hook 
a callback to do what you'll want, probably we'll also want a way to 
signal to stop searching for more solutions based on the return value of 
the callback.


Cheers !

On 9/8/20 20:04, Yuri wrote:
For my problem Glpk quickly finds some solution and then goes on to 
find better solutions and this takes a lot of time.



I'm interested in all solutions, beginning from the first integer 
solution in finds.


I couldn't find a callback that is called when a better solution 
becomes known.



For example, in this run it called glp_intopt which progressively 
found 3 solutions, each better than the previous one:


Long-step dual simplex will be used
+   633: mip = not found yet >=  -inf (1; 0)
+  1006: >   1.098691667e+01 >= 5.512339583e+00  49.8% (18; 0)
+  4134: >   1.098525000e+01 >= 6.681520833e+00  39.2% (31; 22)
+  7210: >   1.098458333e+01 >= 1.043275926e+01   5.0% (24; 87)
+  7654: mip =   1.098458333e+01 >= tree is empty   0.0% (0; 195)
INTEGER OPTIMAL SOLUTION FOUND

I am looking for access to all of  them as they become available.


Yuri