[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] A question on row generation
From: |
Yingjie Lan |
Subject: |
Re: [Help-glpk] A question on row generation |
Date: |
Wed, 27 Jan 2010 16:56:18 -0800 (PST) |
> Yes, it is true. Every child subproblem is exact copy of its parent
> having some additional constraints (depending on the branching type).
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?), 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). 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 (is it true that each
child has an independent copy of the GLP problem structure?).
> 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)?
> rows added on previous levels as well as original rows,
> which already
> exist on entry to glp_intopt. New rows generated by the
> callback are
> added to the end of the row list, so on entry to the
> callback routine
> the current subproblem has the following structure:
>
> original row
> <--- first row
> original row
> ...
> original row
> row added on level 0
> ...
> row added on level 0
> row added on level 1
> ...
> row added on level 1
> ...
> ...
> row added on level k-1
> row added on level k
> ...
> row added on level
> k <--- last row
>
>