[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) |
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
- [Help-glpk] MIP: lpx_integer and ios_driver,
Richard Prescott <=