Re: [Help-glpk] MIP: lpx_integer and ios_driver

[Tor Myklebust]

Let me begin by warning you (and anyone else who might happen to read this
message) that I am no authority on anything written here.  What follows is
essentially a distillation of some of my experiences messing with GLPK.
If someone finds anything horribly wrong with what I've written below,
please let me know.

On Fri, 23 Jul 2004, Richard Prescott wrote:

[snip]

> 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.)

I believe that IOS was designed to be a system for people who want to hack
together branch-and-cut algorithms using GLPK.

> 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?

The handler for a SELECT event must call ios_select_node(ios, p), where p
is some active node.  IOS provides ios_select_fifo and ios_select_lifo (or
something similar; look in glpios.h) for finding such a p.  tspsol's
handler is generic, and could be written to use ios_select_lifo rather
than ios_get_prev_node.  Note that ios_select_node() terminates the
handling of the SELECT event (i.e. no code after your ios_select_node()
will get executed.)

The handler for a BRANCH event must call ios_branch_on(ios, var, updown),
where var is the index of a variable which is fractional in the current
node, and updown is either -1 or +1.  If updown is -1, the "down" branch
will get executed first; if it is +1, the "up" branch will get executed
first.  Similar to ios_select_node(), an ios_branch_on() call will
terminate your handler.  tspsol's BRANCH event handler is generic, too.

I suppose I should mention that IOS doesn't take kindly to people changing
the current active problem (say, with ios_freeze_node/ios_revive_node)
during a BRANCH event.

The handlers for GENROW and GENCUT events are supposed to generate
inequalities and add them to the problem (using ios_add_rows and friends.)
I believe the sequence goes something like this:

do {
  bored = 1;
  Solve LP relaxation to optimality
  Produce GENROW event
  if rows were generated {
    bored = 0;
    continue;
  }
  Produce GENCUT event
  if cuts were generated
    bored = 0;
} while (!bored);

(The "if rows/cuts were generated" tests work by comparing the number of
rows before and after the event was dispatched.)

In the TSP solver example, GENROW events are used to generate subtour
elimination constraints, and GENCUT events could be used for any number of
weird heuristics.  (I'm not entirely clear as to what the difference is
between the two events.)

The DELCOL and DELROW events are there to let you clean up before a
row/column gets deleted  (say, by freeing associated memory.)

> 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 ?

The INIT event is the first event that happens after you start IOS.  The
tree has one node (the root), and the corresponding LP relaxation is
empty.  Put something there during the INIT event.  You should also set up
the IOS structure during the INIT event.

If you set col_gen to zero, you won't be given GENCOL events. If you set
row_gen to zero, you won't be given GENROW events.  If you set cut_gen to
zero, you won't be given GENCUT events.  (I believe all three are zero by
default.)  I'm not sure there's much point in using IOS if you're not
going to use column/row/cut generation, however.

If you want to get integer feasible solutions, hook the BINGO event.  It
happens whenever IOS finds a new integer optimal solution which is better
than the current best known solution.

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

If your objective function is integral, set the int_obj field of your IOS
structure.  IOS will be able to kill nodes sooner (if the floor of the LP
relaxation's value is no better than the current primal bound, it can
prune.)

> 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.

I believe lpx_integer just does a search of your tree, optionally using
more intelligent heuristics than a simple depth-first search.  I think the
following summary of lpx_integer is accurate, if somewhat simplistic:

lpx_integer(lp) {
  Solve lp to optimality (lp is a plain linear program.)
  If lp is infeasible, return something to that effect
  If the optimal solution to lp is worse than or equivalent to the best
      known solution, return something to that effect
  If the optimal solution to lp is integral, update the best known
      solution and return "Integer optimal solution found"
  Pick a variable v which is fractional in the optimal solution to lp
  Let z(v) be the value of v in the optimal solution to lp.
  Create problems lp1 and lp2, each identical to lp
  In lp1, constrain v <= floor(z(v)).
  In lp2, constrain v >= ceil(z(v)).
  Add lp1 and lp2 to the problem list
  Pick a problem lp3 from the problem list.
  Call lpx_integer(lp3).
}

Of course, if your problem has any sort of structure, there probably
exists a better algorithm for solving it.

[snip]

Someone really should document IOS someday.  Maybe if enough people post
guilt-trips like this on the mailing list (instead of writing
documentation), it will eventually happen.

-Tor