Re: Branch & Price

Andrew Eremin wrote:

>"Jesper Hansen Ph.D.Student (jc 1/2002)" wrote:
>
>>Hi
>>
>>I'm doing a Branch & Price algorithm. Instead of solving the primal
>>master problem, I'm solving the dual master problem, adding rows instead
>>of columns. In this way, I can simply post the generated columns as rows
>>and resolve instead of setting up the entire problem at every resolve.
>>
>>Now, to do branching, I need to access the primal variables or when
>>solving the dual problem the values of the dual variables, in order to
>>check if the solution is integral and if not find constraints to branch
>>on.
>>
>
>What sort of branching scheme are you using?
>
My master primal problem is the following:

min cx
s.t.
Ax = b
x >= 0

I was planning to follow the generel branching scheme in Vanderbeck and 
Wolsey.

>
>
>Do you mean that you are finding a fractional primal variable and
>branching on its implicit bound constraints by altering the objective
>coefficients of the corresponding dual variables? If this is the case I
>would point out that branching on master problem variables will in
>general be rather inefficient and will also require adding constraints
>to the subproblems that destroy any special structural properties.
>
>Or do you mean that you have integer coefficients and convert all primal
>constraints to ranged constriants, then by examining the values of the
>primal variables you find primal constraints with fractional
>slack/excess that can be branched on by altering the objective
>coefficient of the corresponding dual variable? If this is the case you
>can more easily determine potential branching constraints by examining
>the reduced costs of the dual variables which correspond to the
>slack/excess of the primal constraints.
>
Well, I'm not sure I understand everything you write, but let me 
elaborate a bit on my part.
Basically I want to find a sum of primal variables which is fractional, 
where the sum is over variables with column coefficients  a>= q*. The 
problem is off-course to find q*, which there is no directions on in 
Vanderbeck and Wolsey. In each of the two branches will be added an 
upper respectively a lower bound constraint on the number of columns 
with a>=q*. Now, when solving the dual problem of the primal master 
problem, these constraints will be columns instead, which requires 
setting up the problem again in each B&B node, but this is acceptable. 
For each branch an additional dual variable is added to the pricing 
problem making it more difficult to solve, but the pricing problem I'm 
solving is anyway a difficult problem. 

>
>
>Of course neither of these observations helps the fact that you will
>still need to obtain the optimal primal solution.
>
Right.

>
>
>>I notice that fewer dual values are returned by eplex than added
>>rows. This is unfortunate since I don't know which, and what the values
>>are of the remaining. A way around this is to setup and solve the primal
>>master problem in each master iteration, but again I cannot be sure to
>>get all the dual variables to send to the pricing problem. I hope the
>>conclusion is NOT that I'll have to solve both the primal and the dual
>>problem in each iteration, which seems a bit inefficient and cumbersome.
>>Alternatively, if I could be sure that all posted rows were actually
>>sent to the solver without any reductions from ECLiPSe, then I would
>>receive all dual variables of the dual master problem (the primal
>>variables of the primal master problem). Is that possible or do you have
>>any other suggestions?
>>
>
>Eplex performs propagation before passing constraints to the external
>solver. The only constraints that eplex doesn't pass to the external
>solver are those that are ground or involve a single variable bound
>update after propagation. I suppose this could happen e.g. if you
>generate a primal variable with 0 objective coefficient for a
>minimization primal master problem so the dual constraint is sum uA =<
>0. The constraint simplification can be avoided by adding an
>unrestricted dummy variable to all dual constraints before posting them
>to eplex, and then simply setting it to 0 before solving the lp.
>
I always have a strictly positive c in uA =< c, but if only one variable 
is involved in the constraint it is removed. Your dummy variable trick 
should avoid this, thanks. With this in mind, I should be able to 
retreive all primal variables.

>
>The external solver may also remove some constraints during presolve.
>You can tell which constraints are present using
>
>	lp_get(+Handle, constraints, -Constraints)
>or
>	EplexInstance:eplex_get(constraints, -Constraints)
>
>and the order they are returned in should correspond to the order of the
>dual values. The simplification of constraints by the external solver
>can be avoided by either calling
>
>	lp_set(presolve, 0)
>
>before setting up the solver or by specifying presolve(no) in the
>ListOfOptions argument of
>
>	EplexInstance:eplex_solver_setup(+Objective, ?Cost, ++ListOfOptions,
>++Priority,
>					 +TriggerModes)
>
I had already presolve switched off. I can't see how 
EplexInstance:eplex_get(constraints, -Constraints) is any useful other 
than for debugging purposes?

>
>Finally, I've been working on a column generation library which allows
>adding new columns to existing constraints. When this is included in the
>eclipse distribution the necessity to work with the dual to avoid
>repeated lp setups will be removed.
>
That would be great. What about branching schemes and sending dual 
information to the pricing problem?


'Jesper

-- 
_______________________________________
Jesper Hansen         
Ph.D. student         
Telephone: (+45) 45 25 33 88 
Telefax.:  (+45) 45 25 26 73
E-mail: mailto:jha@imm.dtu.dk 
Homepage: http://www.imm.dtu.dk/~jha/
Department of Mathematical Modelling 
Building 305                      
Technical University of Denmark
DK-2800 Lyngby