[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Help-glpk] MIP: lpx_integer and ios_driver

From: Richard Prescott
Subject: [Help-glpk] MIP: lpx_integer and ios_driver
Date: Fri, 23 Jul 2004 14:46:04 -0400 (EDT)


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?

        case IOS_V_INIT:

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



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

        actual = create_empty_soln();
        best   =  NULL:

                var   = rip_pop_var();
                        if(actual < best)
                                best = actual;

                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) !=

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.


Richard Prescott

reply via email to

[Prev in Thread] Current Thread [Next in Thread]