[Help-glpk] MIP: lpx_integer and ios_driver

[Richard Prescott]

Hello!

First excuse my ignorance on LP/MIP/*P and general optimisation culture. 
Although I have great fun using GLPK and thanks for the great job up to 
now. (excuse also my bad english)

Second, as I seen on the mailing-list archive MIP solver seem to not work 
too well on medium scale problem (mine have 2k rows and 1k cols after 
presolving) and that is what I am confronting.

I wrote an exclusively integer problem and I didn't know about this issue, 
my actual situation is either I find a way to speed up the process of 
solving MIP problem or I rewrote the whole thing in something else 
(intuitively, it shouldn't take more than 10s to solve my problem using an 
other approach, also the number of constraint and variables shouldn't be 
that high -- linearity come at a price)

I want to give GLPK a chance.  (I have too much fun.)  I wrote my problem 
using MathProg.  My users will provide the .dat file.  So I would like to 
stay with this.  lpx_integer and IOS framework seem to both implement a 
branch & bound method.  Is there any plus value using IOS in these case ? 
(Implementing an appl_proc that feedforward LPX into IOS in a 
straightforward way.)

Insight on GLPK specific implementation will be appreciate.  Like: what 
are the requirements for GENCOL, GENROW, BRANCH, SELECT, DELCOL, DELROW. 
tspsol.c provides a select and a branch that seem to be quite generic. 
Is it sufficient?

A
        case IOS_V_INIT:
                ios_put_lp_soln(ios,(LPX*)info);
                break;

doesn't seem to be the way to go.  INIT should always start with an empty 
tree ?  If I put ios->col_gen = ios->row_gen = 0; Does it make sense ?

What else could / should be done in order to obtain more efficiency ?

Here is a my natural approach of the problem (that might be feasible with 
IOS though or maybe it is what lpx_integer already doing, I don't know):

        call lpx_simplex() or lpx_interior();

        rip_create();
        rip_put_lp_soln();

        rip_build_rows_domains();
        rip_build_cols_domains();

        // how close lpx_simplex result into an integer
        rip_sort_asc_rows_by( { v - floor(v) } );

        actual = create_empty_soln();
        best   =  NULL:

        recursively(actual)
        {
                var   = rip_pop_var();
                if(!var)
                {
                        if(actual < best)
                        {
                                best = actual;
                        }
                        return;
                }

                partial = rip_clone_soln(actual);
                domain = rip_get_domain();

                rip_sort_domain_by( { abs(val - var) } );

                // first guests closest to lpx_simplex gives
                foreach(val in sorted_domain)
                {
                        rip_assign_var(partial, var, val);

                        // look-ahead if I understand it right
                        if(rip_reduce_domains_of_soln(partial) !=
                                ONE_OR_MORE_ARE_EMPTY)
                        {
                                recurse(partial);
                        }
                }
        }

Because of my inexperience in both glpk and LP/MIP I don't know if this 
make sense or if glpk already do a better job.  But it looks like a depth 
search of the tree with node choosed from lpx_simplex results and 
with some kind of look-ahead.

Thanks for your time and this good piece of code which is GLPK.

Regards

Richard Prescott