[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 

> 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

reply via email to

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