Re: [Help-glpk] A question on row generation

[Andrew Makhorin]

> See if I understood it correctly:

> If at the parent node (say it is at level k), you have two
> branches, branch A and B (at level k+1), for example, then A and B
> will inherit their parent's subproblem (the parent may have already
> added some rows via the row generation callback BEFORE branching, but
> AFTER the optimal LP solution found -- Is that timing correct?),

Yes, it is correct.

>  but
> each with a different 'branching constraint' (that is, the constraint
> added to define the branches, for example, if in the parent node, the
> optimal solution of an integer variable x* = 2.5 is chosen to branch
> on, you add x<=2 and x>=3 to define branch A and B respectively).

Branching on variable needs adding no rows; this just changes current
bounds of the branching variable. It is possible to branch on constraint
(for example, on disjunctive or GUB constraint), however, currently this
feature is not used in glpk.

> Also, what rows added by child A to its subproblem is invisible to
> child B, and vice versa, so that their actions do not interfere each
> other

You may think that after branching child subproblems A and B co-exist
independently on each other, i.e. if you add new rows to A or change its
other components, this does not affect B, and vice versa.

>  (is it true that each child has an independent copy of the GLP
> problem structure?).

No. On freezing the current subproblem glp_intopt saves only those
things, in which the current subproblem differs from its parent.

>> Note, however, that the callback routine being called at level k (i.e.
>> if the current subproblem has level k) can change or remove only rows,
>> which were added on the same level; it must neither remove nor change
> 
> Is this a moral rule (that you can break) or an enforcement (that you
> can not break)?

This is implementation restriction. I don't think this is cumbersome,
because it is allowed to change row/column bounds at any levels, so if
you need to remove a row added on some previous level, you may make it
free (unbounded) instead. However, only locally redundant rows can be
made free, because the feasible region of a subproblem must be a proper
subset of the parent's feasible region.